Security: Improper handling of U2F counters.

[StormTide]

The reference applications incorrectly handle a rolled back counter -- needs to disable the login on valid signature with a rolled back counter to prevent security failures. Current model allows for counter iteration, defeating the security of the counter.

[konklone]

Any response at all?

[jas4711]

As far as we could tell from the U2F specs, there is no way to do anything useful with the counter as it is it can wrap and it is underspecified how devices uses the counter. Do you have any suggestions otherwise? Also, as far as we could tell, there is no real security problem caused by this anyway.

[StormTide]

facepalm No real security problem? This allows for counter iteration and dual-use of a cloned token. This is not only a security problem, but a critical one. There are a number of strategies that must be put in place for counter tracking -- the most important of which is tracking for a simple signed rollback @ < countermax. However that's not a real solution either as a token cloner would simply use cloned values of countermax-1, countermax, 1 and then the cloned counter value again to reset state. The counter is a key part of the security model in the U2F spec and is definitely not optional. Devices must be watched for rollover (likely involving a lockout and re-enrollment) and for the more obvious simple rollback.

[jas4711]

Please explain how we could do better. As far as we can tell, there is no way to check the U2F counter in any generically useful way. I believe our library allows your application to retrieve the counter value, so your application can perform counter-related checks. However, as a library, I have not been able to see any useful checks that are possible.

To give you some background, let's cite all text in the specification related to the counter.

Quoting "FIDO U2F Implementation Considerations" section 2.6: "A U2F token must increase a counter each time it performs an authentication operation. This counter may be 'global' (i.e., the same counter is incremented regardless of the application parameter in Authentication Request message), or per-application (i.e., one counter for each value of application parameter in the Authentication Request message). U2F token counters should start at 0, and wrap around to 0 when they have reached their maximum value."

Quoting "FIDO U2F Raw Message Formats" section 5.4: "A counter [4 bytes]. This is the big-endian representation of a counter value that the U2F token increments every time it performs an authentication operation. (See Implementation Considerations [U2FImplCons] for more detail.)"

Quoting "Universal 2nd Factor (U2F) Overview" section 8.1: "The U2F device protocol incorporates a usage counter to allow the origin to detect problems in some circumstances. The U2F device remembers a count of the number of signature operations it has performed -- either per key pair (if it has sufficient memory) or globally (if it has a memory constraint, this leaks some privacy across keys) or even something in between (e.g., buckets of keys sharing a counter, with a bit less privacy leakage). The U2F device sends the actual counter value back to the browser which relays it to the origin after every signing operation. The U2F device also concatenates the counter value on to the hash of the client data before signing so that the origin can strongly verify that the counter value was not tampered with (by the browser). The server can compare the counter value that the U2F device sent it and compare it against the counter value it saw in earlier interactions with the same U2F device. If the counter value has moved backward, it signals that there is more than one U2F device with the same key pair for the origin (i.e., a clone of the U2F device has been created at some point)."

Let's say you have recorded a last known counter value of, say, 42, and receive 43 or 41 as a current counter there is no useful distinction to be made as far as I can tell. If you received 43, things may be fine, but the counter may also have wrapped (due to large number of uses against some other site, assuming a global counter) and there is a cloned device out there. If you receive 41, things look fishy, but the counter may just have wrapped and there is no cloned device. As far as I can tell, the only useful way to check the counter is for the APPLICATION to perform two U2F Authenticate operations after each other, and compare the counter values. This minimize the chances that a counter wrap occured. In theory, the user might perform ~2^32 U2F Authenticate operations against some other site between the two attempts, but if the time passed between the two attempts is small, this is unlikely. I argue this is hard to know inside the library, though, making it hard to do anything useful inside the library.

I would prefer to resolve this issue by changing the specs to say that U2F counter rollover MUST NOT be permitted by devices.

Thoughts?

[konklone]

Yes, the counter could wrap, and that's acknowledged in the spec, but that's not something that should be considered normal expected use of the token. It definitely shouldn't prevent any use of the counter to mitigate device cloning.

If a counter wraps, and starts sending wrong numbers, that token should probably be considered invalidated against all the places it's currently authorized with. That's certainly annoying for a token holder, and there's no guarantee on how many bytes the counter has available to it, but 2^32 U2F authentication operations is over 4 billion operations.

Even 2^16 operations is 65536, which would take 3 login attempts a day, every single day, for 60 years, to wrap.

And that's only for the worst case: a token which uses a single global counter for all logins. The spec notes that using such a global counter will leak privacy across websites (it becomes much easier for multiple service providers to make a good guess at whose token is which in both databases), and that tokens with larger memory requirements may/should use separate counters -- either for individual sites, or buckets of sites.

In fact, a counter wrap is perhaps only viable when an attacker has taken control of someone's token and put it through mechanized counting attempts in an effort to wrap the counter. In which case: please consider my token invalidated! 😃

That's all to say that counter wrapping is a highly exceptional scenario. So when it does happen, if someone's token gets effectively de-authorized from all their existing sites and needs to be re-authorized -- that's probably okay. Every U2F-implementing site is going to have a way of dealing with lost or stolen tokens, and that can apply in situations where a counter has gone awry.

[StormTide]

In your example, you must catch 41, after 42 as a cloned-token. A rollover is, as you point out an exceptional and rare event that should never happen in legitimate usage, and as you point out, really probably shouldn't even be allowed by the spec. Part of the problem with the U2F spec is the use of wrapped-keys and global counters. Really, this should be a per-realm keypair and a per-realm counter in an ideal world.

Regardless, the solution ( within the spec allowance of global counters and wrapped keys ) -- I would add to the lib a data access layer (either as an interface to be implemented or just as user-model object) indicating that there are certain user metadata fields that must be stored and monitored for secure operations. At a minimum those fields should include the counter details, number of authentications, and track key rollovers, authentication events and failures, etc.

It may take some Bayesian math to decide when to throw an audit or lockout event, however, I would suggest if the counter moves more than > 256 or so points between authentication events or exceeds a rate of say 128 auth's per 24 hours, it needs to lock the token out and throw a security exception of some sort. If the counter rolls back outside the rate limit, you know it has been hacked and must lock it out and alert an administrative user.

Ignoring the counters as is currently implemented (and as is being picked up by relying parties) however, leaves a massive everyday security hole, where the utility of the counter is entirely negated, and detection of token cloning just wont happen in practice.

TL;DR: add a Security Exception framework, User Metadata tracking model and some rate limiting algorithms and check counter values for rollback. Update docs to include a checklist that there's a mechanism for notifying an admin if a security exception is thrown.

[jas4711]

The code related to the counter check in the library is here:

https://github.com/Yubico/php-u2flib-server/blob/master/src/u2flib_server/U2F.php#L283

So the counters aren't ignored, as I mistakenly assumed. However, applications using this library needs to pay attention to this issue, which may turn this into a documentation feature request issue. If someone would contribute a security exception framework, that would be awesome, but pending that, simply documenting that if you get a 'counter-too-low' exception, you should invalidated the credential for that user and alert the admin of a cloned device. Anything missing with that approach?

[StormTide]

None of the implementations of this lib pick up that exception as anything but an auth failure. Also, that code was added after this bug was opened. If left as is, I'd wager on this being ignored in the ecosystem and cloned tokens being an effective hack. Better to fix it now than try to redeploy the tech in the face of cloning.

[konklone]

So the counters aren't ignored, as I mistakenly assumed. However, applications using this library needs to pay attention to this issue, which may turn this into a documentation feature request issue. If someone would contribute a security exception framework, that would be awesome, but pending that, simply documenting that if you get a 'counter-too-low' exception, you should invalidated the credential for that user and alert the admin of a cloned device. Anything missing with that approach?

Totally. The library should (as I guess it does?) consider a too-low counter an invalid authentication. Implementors should be aware that that's one of several possible reasons an authentication could fail.

In my own implementation work, I don't know if I'd even try to communicate to the users the threat of cloning -- I might just say: "Unfortunately, your device has gotten out of sync with our application and needs to be reauthorized." and then take them into the lost/stolen token workflow.

[StormTide]

@konklone A simple auth failure is useless here as the attacker will just move the counter up by one until he hits the next valid counter. Then when the real user logs in next time, they'll get one auth failure followed by an auth success --- and unless the implementer is tracking counter-too-low exceptions to the db (which isnt in this pattern), no one will really be the wiser.

[jas4711]

Agreed -- I believe that as soon as you get ERR_COUNTER_TOO_LOW applications must invalidate the credential rather than treating it as an authentication error.

[jas4711]

Also note that typically the device that would trigger this error would be the original device, not the cloned one, as an attacker who is able to clone a U2F device is surely capable of incrementing the counter value by a sufficient amount to make it higher than the counter stored in the database for that user. So when this incident is noticed by the server, an attack has likely already occured earlier on. What to do in a situation like that is not simple, and probably depends on what you are implementing, so it is an application concern.

[StormTide]

Well, yes/no. If the attacker is smart he'll start at the cloned value and iterate up if long-term access is the goal. In such cases, it will be the cloned token generating a number of auth failures until the right counter is hit. Then the real one hits one bad login, tries again (cuz users always do) and it works -- so no alert gets raised. So no, not really in the realm of the app, but rather in the realm of the 2fa scheme.