Clarify the need for truly randomly generated challenges (aka challenge callback issue)

[dolda2000]

Proposed Change

The current standard says, with regards to challenge strings, that their main use is to "avoid replay attacks", which certainly agrees with my layman understanding of cryptography. It goes on, however, to conclude that this means that challenges...

MUST be randomly generated by Relying Parties in an environment they trust [...] and the returned challenge value in the client’s response MUST match what was generated

... which does not agree with my layman understanding of cryptography.

If avoiding replay attacks is the only purpose of the challenge, then, at least according to my layman understanding of cryptography, that would mean that the only requirement would be preventing the same challenge from being used twice, not that it needs to be cryptographically random. The standard goes on to state that...

In order to prevent replay attacks, the challenges MUST contain enough entropy to make guessing them infeasible.

... and unless my layman understanding of cryptography is lacking, this is not correct. Guessing a challenge in advance, or being able to use a challenge that has not strictly been pre-generated by the server should not be a problem in preventing replay attacks.

On the other hand, requiring the challenge to be cryptographically securely generated on the server implies quite a number of restrictions on the implementation, not least the need to statefully maintain a conception of current valid challenges. In fact, I am currently considering a challenge maintenance protocol that would be stateless, in order to avoid the need to create web sessions for clients that merely visit a login page and trigger a conditional mediation flow that they quite likely never utilize, and also to avoid potential DoS attacks from spamming the challenge generator, generating an unbounded number of sessions only limited by the rate at which they can be requested.

For this reason, if there actually does exist a need to generate cryptographically random challenges in a trusted environment, I would appreciate that this need be clarified. Otherwise, I think the specification should be updated to reflect that the requirement is to prevent challenges from being used more than once, rather than being unguessable.

[emlun]

Perhaps "replay attack" is too narrow a term. The purpose of "replay protection" is not only to prevent a challenge from being used more than once - rather, the more accurate underlying motivation is that a challenge-response protocol should ensure that the response was created in response to the challenge. An unpredictable challenge establishes a temporal guarantee that the response was freshly created on request, and thus that the subject is currently in possession of the signing key. If the challenge can be known beforehand, then there is no such guarantee as the response could have been created far in advance.

As a practical example, say you (an attacker) have access to a victim's security key for a short window of time - maybe you broke into their hotel room, or "borrowed" it from their desk while they were on the toilet. If the target RP uses predictable challenges - say, a timestamp or an incrementing counter - you can have the security key pre-generate a large amount of assertion signatures ahead of time and still use them after returning the security key. (The signature counter may defeat this if the RP verifies it, but only after the next time the victim uses the security key - and current RP implementations only rarely ask for the security key.)

So yes, you do need to "maintain a conception of current valid challenges". The easiest and least error-prone way to do so is likely to keep the state in server memory. But it is also possible to do with a stateless server, as long as you can protect the data from tampering. You could for example put the challenge and an expiration time in a JWT or similar signed data structure stored on the client side. But note that this comes with its own set of issues, in particular in managing the signing key(s).

Would an edit like this make this clearer?

From:

As a cryptographic protocol, Web Authentication is dependent upon randomized challenges to avoid replay attacks. Therefore, [...]

To:

As a cryptographic challenge-response protocol, Web Authentication is dependent upon randomized challenges to avoid replay attacks and verify current possession of the credential private key. Therefore, [...]

[serianox]

If avoiding replay attacks is the only purpose of the challenge, then, at least according to my layman understanding of cryptography, that would mean that the only requirement would be preventing the same challenge from being used twice, not that it needs to be cryptographically random. The standard goes on to state that...

@dolda2000 If the challenge can be guessed in any way, then the protocol is also - potentially - vulnerable to pre-play attack, i.e. generating and registering transaction in advance and playing it when needed.

This attack is rarely seen or heard of, but can be worse than replay attack because you can perform it without seeing twice the message which makes detection or auditing it nearly impossible.

[dolda2000]

While I can understand the "temporarily stolen key" scenario, I do wonder how well that is protected against as is.

In particular, the availability of conditional mediation requires the use of challenges that are not only very long-lived, but also that can be generated without any prior authentication. It seems to me that if an attacker can gain temporary access to a key, and wishes to use it on a service with conditional mediation, then he can already make the service generate many valid challenges, that are kept current for a long time, sign them all, and use them at his leisure.

Am I missing something about this? If I'm not, does that mean that services will need to choose between conditional mediation and higher security guarantees? In that case, that should probably also be clarified in the specification.

[sbweeden]

Conditional WebAuthn does not require long lived challenges.

Sent from my iPhone

On 20 Feb 2023, at 10:13 pm, Fredrik Tolf @.***> wrote:

 While I can understand the "temporarily stolen key" scenario, I do wonder how well that is protected against as is. In particular, the availability of conditional mediation requires the use of challenges that are not only very long-lived, but ZjQcmQRYFpfptBannerStart This Message Is From an External Sender This message came from outside your organization.

ZjQcmQRYFpfptBannerEnd

While I can understand the "temporarily stolen key" scenario, I do wonder how well that is protected against as is.

In particular, the availability of conditional mediation requires the use of challenges that are not only very long-lived, but also that can be generated without any prior authentication. It seems to me that if an attacker can gain temporary access to a key, and wishes to use it on a service with conditional mediation, then he can already make the service generate many valid challenges, that are kept current for a long time, and use them at his leisure.

Am I missing something about this? If I'm not, does that mean that services will need to choose between conditional mediation and higher security guarantees?

— Reply to this email directly, view it on GitHubhttps://github.com/w3c/webauthn/issues/1856#issuecomment-1437395961, or unsubscribehttps://github.com/notifications/unsubscribe-auth/ACDAGXJCXLQK26CL52DZJD3WYOX3PANCNFSM6AAAAAAVB7TV5I. You are receiving this because you are subscribed to this thread.Message ID: @.***>

[Firstyear]

Conditional mediation still requires a "per-session" and unique challenge, the same as non-conditional mediation. The challenge isn't unique "per user" it's "per-page-access".

[dolda2000]

@sbweeden I do realize that conditional mediation doesn't strictly require long-lived challenges, but it does seem to be the assumption. For example, from this very GitHub project:

Timeout values should be ignored when using Conditional UI. This is because removing the credentials from the autofill list at an arbitrary time would make for poor UX, and the dialog is triggered directly by the user anyway.

Or from Yubico's documentation:

One of the primary reasons why traditional WebAuthn implementations don’t allow for this non-invasive prompt is due to the timeout of the WebAuthn ceremony. Typically a get() call will remain active for a short duration of time before timing out and requesting the user to trigger a new auth ceremony. Autofill has a longer timeout period, allowing a user to leisurely select their credential if one is available, without the need to reinvoke the authentication ceremony.

Or from one of Apple's videos:

When you make AutoFill-assisted requests, you should make them early in the page lifetime [...]. AutoFill requests are not modal, so they don't require a user gesture and have a much longer timeout.

I'm sure I could cite more that I've come across, but those are just the ones I remembered off the top of my head.

---

@Firstyear I'm sorry if I'm misunderstanding you, but the fact that conditional challenges are per-page-access rather than per-user is exactly the problem I'm trying to point out, because it means that you can request as many as you'd like, just as if you were using just as many tabs (or browser instances, or machines) to make simultaneous page accesses, and the server wouldn't be the wiser. So you could get as many as you need for "pre-play" signatures.

[emlun]

@dolda2000 When you say "very long-lived", what do you mean in concrete terms? Minutes, hours, days, months?

I'm guessing that when most of those resources say "long timeout" they mean something like 15 minutes at most - as opposed to the maybe 1 or 2 minutes one might have in second factor authentication flows. While ~15 minutes is long enough that memory exhaustion attacks could be an issue, it's short enough to prevent most "pre-play" attacks.

[dolda2000]

@emlun In my current implementation, I have in fact made challenges for conditional mediation unbounded in time. I think it would be quite weird if the login-prompt mysteriously stopped working just because the user leaves it alone for 15 minutes, and I would assume that that's what the link I referred to above means when it says "This is because removing the credentials from the autofill list at an arbitrary time would make for poor UX".

With this information in hand, I can see that challenge lifetimes should perhaps not be unbounded, but I'd be hard pressed to see that they should be shorter than a day, and that seems like the least I could imagine. It is hardly strange to imagine a user leaving a log-in prompt dangling for a day, especially if you consider potential "passive" log-in prompts that are simply part of other pages but not necessarily expected to be used.

---

Speaking of the randomness of the challenge, however; you mentioned above the possibility to use something like JWT to store the information on the client-side without requiring server-side state. I had entertained a similar idea as well, only that I had intended to let the crypto-token be the challenge, rather than being stored along-side the challenge. Does there remain some other need to have the challenge be truly and fully random that would preclude such use? If not, would such a token need to include some sort of nonce to increase its entropy?

[emlun]

Does there remain some other need to have the challenge be truly and fully random that would preclude such use? If not, would such a token need to include some sort of nonce to increase its entropy?

Right, the challenge doesn't necessarily need to be fully random, just contain enough entropy to be practically impossible to predict. So yes, I would recommend explicitly mixing in a 16-byte or longer random nonce to make sure of that. Assuming that by "let the crypto-token be the challenge" you meant the whole JWT including the signature, the signature probably would be enough entropy already - BUT! that assumes the signature algorithm uses a random nonce. Not all signature algorithms do - for example, HMAC has no internal nonce at all, and deterministic ECDSA derives the nonce from the input to be signed. So it's safest to mix in some additional entropy to be sure, in case you change the signature algorithm later.

I think it would be quite weird if the login-prompt mysteriously stopped working just because the user leaves it alone for 15 minutes, and I would assume that that's what the link I referred to above means when it says "This is because removing the credentials from the autofill list at an arbitrary time would make for poor UX".

Agreed, but you can work around this by periodically refreshing the challenge and using an abort signal to cancel the timed-out conditional WebAuthn request and restart it with the new challenge. This could make for a poor UX if the user happens to be interacting with the conditional UI right then, but that seems fairly unlikely to me.

[arianvp]

Storing the challenge client-side in a JWT opens you up for replay-attacks in the validity window of the JWT. Challenges should be "use-exactly-once" which JWTs (or encrypted cookie; or signed cookie) will not give you. I'd say storing the challenge server-side is a must for security.

[dolda2000]

@emlun

Agreed, but you can work around this by periodically refreshing the challenge and using an abort signal to cancel the timed-out conditional WebAuthn request and restart it with the new challenge.

Hm. I understand this is an option, but if that is how conditional mediation should/must work, then some clarification really does seem to be in order, since the references I quoted above are from pretty big names in the WebAuthn/Passkey community, and all of them seem to be implying that long-lived challenges are the intended solution (at least that's what I personally gathered from them).

I will add, however, that I also also posted #1854 recently, about the greater-than-perhaps-expected complexity of using modal and conditional mediation on the same page, and having a timed loop restarting a conditional mediation periodically doesn't exactly improve that situation. Don't get me wrong, I'm sure it's implementable and all, it just seems like a fair bit of complexity for what seems to be intended to be a pretty standard thing to do.

I also suggested in passing in #1848 that it would probably be nicer if conditional mediation were a two-stage process where the browser effectively requests the full challenge information from the page if and when the user actually decides to start using WebAuthn. As I mentioned therein, I understand more than well that it might be difficult to change at this point, but especially if it is a security concern to have challenges be as short-lived as possible, I can't help but think that that strengthens the case.

This could make for a poor UX if the user happens to be interacting with the conditional UI right then, but that seems fairly unlikely to me.

If the expected challenge lifetime is on the order of 15 minutes, then assuming an average interaction takes some 5-10 seconds or so, that's about a one-in-a-hundred chance of that happening. Not the end of the world by any means, but still high enough that it starts to border on slightly unelegant. Not to toot my own horn, but the two-stage process mentioned above would fix the issue.

---

@arianvp What I currently plan on doing is to include the value of a monotonically increasing challenge counter in the challenge token, and then keep, per account, a list of the counters of the $SOMENUMBER last challenges, along with a record of the highest counter value expunged from that list, and then reject challenges that are either in the list, or have a counter value <= the highest-expunged value. Unless there's something I'm not thinking through properly, I believe that fixes the "use-exactly-once" problem (with O(1) storage requirements).

[agl]

I think dolda2000 has a reasonable point here. Challenges can be stored client-side, and contain something like HMAC(timestamp), but we want those challenges to be time-bounded otherwise the assertion turns into a password that, if leaked, can be reused. But a page using conditional UI could be open for days in a tab before use so the time bound would have to be equally long. Much better than forever, for sure, but hmm.

Telling every site to abort and restart the request works, but how many will? (dolda2000 is applying supererogatory attention to this issue as it is, compared to an average site!)

Having the site remember and reject used challenges is also good, but the same "how many will?" applies.

it would probably be nicer if conditional mediation were a two-stage process where the browser effectively requests the full challenge information from the page if and when the user actually decides to start using WebAuthn

While the implementation challenge is non-trivial for the browser, a challengeCallback of type () -> Promise<BufferSource> as an alternative to challenge is interesting.

[emlun]

While the implementation challenge is non-trivial for the browser, a challengeCallback of type () -> Promise<BufferSource> as an alternative to challenge is interesting.

I would support this addition to the API.

[sbweeden]

So would I. It might also have value in the modal use case so that the platform dialog could take longer for things like just-in-time UV provisioning (including PIN), guided help, etc.

[MasterKale]

I try to avoid "me too" comments but I really like the idea of a callback for challenge for JIT querying for a challenge. It'd nicely solve the challenges lifetime question in #1848.

[dolda2000]

@agl

While the implementation challenge is non-trivial for the browser, a challengeCallback of type () -> Promise as an alternative to challenge is interesting.

Though I'm speaking from the RP side rather than the browser side, this would be very nice, and would certainly work for me. (Especially if combined with #1854.)

Challenges can be stored client-side, and contain something like HMAC(timestamp), but we want those challenges to be time-bounded otherwise the assertion turns into a password that, if leaked, can be reused.

I am curious, are you saying that it would be acceptable for RPs to ignore actual replays so long as challenges are tightly time-bounded?

---

@sbweeden Truly, I was thinking the same thing. If challenge lifetimes are a security concern, it would be quite nice to be able to make them sub-minute long.

[agl]

I am curious, are you saying that it would be acceptable for RPs to ignore actual replays so long as challenges are tightly time-bounded?

The "can" there was in the spirit of "technically possible, and something that sites might do in practice". Time bounding does not fully prevent replays and is thus weaker. But time bounding also makes it a lot easier to fully prevent replays by limiting the amount of server-side state that needs to be kept.

It might also have value in the modal use case so that the platform dialog could take longer for things like just-in-time UV provisioning (including PIN), guided help, etc.

I'm only proposing it for conditional UI requests:

1. Once the request has gone modal browsers have often passed things off to the operating system. Wiring a loop from there all the way back to the renderer is going to be a lot.
2. Just-in-time UV configuration is slow, but it happens when making a credential, and the challenge has completely different requirements there. (E.g. if you're not checking attestation it can be a fixed value. Even if you are checking, the security properties of freshness are very different.)
3. The time to complete the modal part of a getAssertion should be on the order of a couple of minutes and it should be reasonable for sites to keep server-side state for that amount of time and completely prevent replays.
4. The site can set the timeout on a modal getAssertion to enforce its limit and the user can get a reasonable error message and manually retry in the small fraction of cases that exceed that.

[dolda2000]

I'm only proposing it for conditional UI requests: [...]

All of your concerns are surely reasonable in practice, but if a challenge callback is going to be part of the spec, I think it should be technically possible to use it for both conditional and modal requests, if only for orthogonality reasons. If the browser wishes to request the challenge before displaying the UI, there should be nothing preventing that (outside of the timeout values used by the RP, of course).

[timurnkey]

I'm trying to understand the various attack vectors around challenge generation. The assertion case makes a lot of sense to me, but I'm having trouble understanding why the challenge matters in the attestation case. Specifically, why is step #8 important?

1. (challenge generated in trusted environment) -> I asked "you" to show proof of real-time ownership
2. (challenge generated in untrusted environment) -> Someone asked "you", or someone else, to prove previous ownership

Is this the right way to think about that? Since this uses a trust-on-first-use model... what's the worst case scenario if the attestation challenge isn't generated in a trusted environment?

[dolda2000]

@timurnkey Clearly, I'm not the expert here (so the actual experts can feel very free to correct me), but my understanding is that the main circumstance where challenges for attestation matters is when the attestation itself contains some relevant identity information.

For instance, you could imagine an enterprise/government identity scheme where USB keys have information about the physical person that is supposed to own the key fused into them and being a part of the attestation statement, and registering an account with said key implies associating the account with the same physical person. In this case, you would clearly want to avoid registration reuse.

[ve7jtb]

In the case of enterprise attestation the attestation contains a serial number for an authenticator given to a specific individual. In that case the challenge is important to be unique and not replayed. Some large enterprises may also have custom AAGUID restricting registration to company provided authenticators.

In general without attestation the challenge in the response is mostly to link the request and response. It is not providing security if unsigned or signed by a self signed batch certificate.

[sbweeden]

Following WG call of 2023-06-28, I undertook to determine if its currently possible (at least on Chrome and Safari where conditional UI is supported) to use a setTimeout() method to occassionally fetch a new challenge and abort and then restart the autofill call to navigator.credentials.get().

It seems this does work ok, although in Safari each time that the new autofill call is invoked, the console log shows: User gesture is not detected. To use the WebAuthn API, call 'navigator.credentials.create' or 'navigator.credentials.get' within user activated events. Despite this the autofill call works, and I can complete autofill login. Safari should probably not do this since a user activated event is not needed for the autofill call to work. FYI - @pascoej

As a result, I don't think that servers have to support very long-lived challenges, and a period challenge refresh is practical. I am ok with abandoning this feature.

[dolda2000]

@sbweeden Correct me if I'm wrong, but I don't think it was ever in doubt that periodically aborting and restarting the challenge was technically possible, only that it might be undesirable. This was explicitly discussed in previous comments (https://github.com/w3c/webauthn/issues/1856#issuecomment-1438575614, https://github.com/w3c/webauthn/issues/1856#issuecomment-1439027536 and https://github.com/w3c/webauthn/issues/1856#issuecomment-1443822151).

[sbweeden]

What was in doubt was whether or not this would work in Safari without a user gesture. It does work.

[dolda2000]

What was in doubt was whether or not this would work in Safari without a user gesture. It does work.

For what it's worth, it was mentioned explicitly in the Apple video that I referenced previously, so it wasn't in doubt for me, at least. :)

It is in fact part of what I already quoted in that post, namely the "so they don't require a user gesture" part.

[timcappalli]

2023-08-30 meeting: @akshayku was there anything left in this issue that needs to be addressed?