Engineering · 2026-09-14

A Verifier Can Hang Your Wallet with One Regular Expression

By J. W. Bouckaert

The pattern comes from the verifier

A wallet that holds credentials has to decide which of them satisfy a request. In OpenID4VP that decision is local by design: the verifier describes what it wants, the wallet matches against its own store, and the holder approves what leaves. Keeping the matching on the holder's device is the entire privacy argument for the architecture.

Presentation Exchange 2.0 is the language the request is written in. Each input descriptor carries constraints, each constraint carries fields, and each field may carry a filter expressed in a JSON Schema dialect. Among the keywords that filter can use is pattern, and pattern is a regular expression.

Follow what that means operationally. A string authored by the party asking for your credentials is compiled by your wallet and executed against the contents of those credentials. OpenID4VP delivers the definition inside the authorization request, so the pattern arrives and runs before the holder has consented to disclose anything at all. Being asked is sufficient.

Our own wallet SDK did what the spec implies, and until version 0.5.0 it did so with no bound of any kind: take filter.pattern, hand it to new RegExp, call .test() on the claim value. That code was correct against every definition a cooperative verifier sends, which is why it survived review.

The shape that backtracks

JavaScript's regular expression engine backtracks. When a pattern can match a span in more than one way, the engine tries the possibilities in order and reverses out of the ones that fail. For most patterns the number of possibilities is small. When a quantified group contains another quantifier or an alternation, the number of ways to divide the input among the repetitions grows exponentially with the length of the input.

^(a+)+b$ is the canonical demonstration. Against a run of a characters that ends without a b, the engine must rule out every way of splitting that run between the inner a+ and the outer repetition before it can report a failure. Each additional character roughly doubles the work. OWASP catalogues this as ReDoS, and it is well travelled ground in web servers, where the untrusted string is usually the input and the pattern is yours.

The wallet case inverts that. The value being matched is the holder's own credential claim and is not under the attacker's control. The pattern is. A verifier does not need to guess anything about your stored credentials to write ^(a+)+b$, because the cost is paid whether or not anything matches.

Measured on one machine

Numbers from this repository's container on 2026-09-13, Node 22.22.2, one run each, testing /^(a+)+b$/ against a string of n a characters with the guard removed. One machine and one run, so read the shape of the curve rather than the absolute milliseconds.

Roughly four times the work for every two characters added. Thirty characters is already past any deadline a user interface has, and the string that produces it is eight characters long. There is no volume of requests involved: one authorization request, one field, one pattern.

The guarded path in 0.5.0, against the same pattern and the same inputs, measured through the built bundle:

Flat, because the pattern is refused before it is ever compiled. The work that disappears is work that was never useful.

Three bounds, applied together

The fix is three refusals rather than one, because each covers a gap the others leave.

The first is length. A pattern longer than 512 characters is refused without inspection. This is a blunt instrument and it is meant to be: the patterns a real verifier sends are short, and the ones that are not are worth a second look by a person.

The second is shape. A pattern whose structure admits catastrophic backtracking is refused, which is the bound that actually addresses the attack.

The third is input length. A claim value longer than 4,096 characters is not matched against at all. This exists because the shape check is a heuristic and heuristics are permeable. Even a hostile pattern that slips past the second bound never meets an unbounded string, so the exponent has a ceiling.

All three fail closed. A refused pattern means the field does not match, which means the credential is not selected, which means it is not offered to the verifier. A verifier that sends something exotic gets no credential. It does not get a hung wallet, and it does not get a credential it should not have.

Truncation turns a non-match into a match

The first version of the third bound truncated the value to 4,096 characters and matched against the prefix. That seemed obviously equivalent and it is obviously wrong, which is a combination worth dwelling on.

Consider a claim value of 200,000 characters, did:web: followed by a long run of x, tested against ^did:web:x+$. Truncated to its first 4,096 characters, it matches. In full, whether it matches depends on what is in the remaining 195,904 characters, and if anything there is not an x, it does not.

So truncation converts a non-match into a match. The wallet then offers the verifier a credential that the verifier's own filter was written to exclude. The failure mode of the safety bound is over-disclosure: exactly the harm the architecture exists to prevent, introduced by the code meant to harden it.

The test written alongside the guard is what caught it, before the code was released. That is the argument for writing the adversarial test at the same time as the defence rather than after it, and for making a test assert the direction of a failure and not only its absence. Refusing an oversized value is the version that shipped.

Reading the shape check

The shape check walks the pattern once, tracking group depth on a stack. It skips the character after a backslash, so an escaped parenthesis is treated as the literal it is. It skips the interior of a character class, so a class holding quantifier characters, as in ([*+]a)+, is not mistaken for a nested quantifier: inside a class those characters are ordinary members of a set. When a group closes and is immediately quantified, the check reports a problem if that group also contained a quantifier or an alternation. A quantifier on a group counts as a quantifier inside its parent, so nesting two levels deep is caught as well.

It is deliberately conservative and it rejects patterns that would have run perfectly well. ^(US|CA|GB)$ passes, since the group is not quantified. Something contrived that combines an alternation with an outer repetition is refused even where the alternation branches are disjoint and the engine would have terminated quickly.

That trade is easy in this direction. The cost of a false positive is one credential not offered against one exotic filter, and the holder can be told. The cost of a false negative is a wallet that stops responding while it is being asked for credentials.

The heuristic lives in the module rather than in the package's public surface. Callers get matchCredentials, and the bounds apply underneath it without anything to configure or remember to switch on. A guard that has to be enabled is a guard that is off in the deployment that needed it.

The limits of these bounds

These three refusals remove the practical attack. They do not make matching provably linear, and the module header says so in as many words rather than leaving a future reader to assume a stronger property than the code has.

A proof needs a different engine. RE2 and its relatives compile to automata that have no backtracking to exploit, and they give a real time bound rather than a heuristic one. Adopting one would mean adding a dependency to a package that currently declares none at all, which is a property with its own security value for something that runs inside a wallet. That trade may be worth making later. Recording why it has not been made yet is more useful than implying the question never arose.

An attacker who finds a catastrophic pattern the shape check misses still meets the 4,096-character ceiling on the input, which bounds the exponent. Bounded is a weaker claim than safe, and it is the one the code can actually support.

Failure modes

The uniform column is the point. Every refusal lands on the same outcome, and that outcome is the conservative one.

Scope

This is about the matcher in a wallet, which is one component with one job: decide locally which stored credentials satisfy a request, without leaking the ones that do not. Verification of a presentation, once the holder has approved it, is a separate server-side path with a different threat model.

If you maintain a wallet that consumes presentation definitions, the check worth running today is a search for new RegExp and .test( near your Presentation Exchange handling, and then asking where the string came from. The answer is the verifier. Our own implementation ships in @passkeybridge/vc-wallet-sdk from 0.5.0 onward, and the bounds are on by default with nothing to configure. The VC Wallet SDK quickstart is where to start if you want to read the matcher against your own definitions. Adjacent reading: selective disclosure with SD-JWT and browser-native wallet selection.

Start free · Test the API