Reliable, Secure and Universal Backup for U2F Token

I really love the security level U2F provides, but together with security, we have to think carefully about the backup and recovery plan. It would totally suck to get locked out of my accounts if something happens with my U2F token. At the same time, it doesn't make sense to have a backup which compromises U2F security.

The advice I've seen in many places is that the best practice is having a second U2F token for backup, which should be manually added to every service and which should be kept in some “safe” place. And another common practice is to have some non-U2F method as a backup (OTP, or recovery codes, etc). Well, both of those leave a lot to be desired, honestly.

Let's talk about the first option, the “best” one: having a backup token.

Having a second token means that whenever I register on a new service, I have to add both of my tokens to my account. It poses a few problems:

• The backup token needs to be easily accessible. Even though I'm not going to carry it on my keyring, I should be able to access it quickly, so I can hardly do any better than keeping it somewhere at home.
• When I'm traveling and need to register on a new service, I can't access my backup token immediately. So, I'll have to remember to add it to the new account when I get home, and until that, I have no backup for that service. Worst case, I can even forget.
• Whenever I'm at home, both of my tokens (primary and backup) are basically in the same place. That is a bad, bad way to backup things. If something happens with the apartment, both tokens can be affected by the same event (get destroyed or stolen).
• The idea to keep a backup token at home is pretty obvious, and even though we try to make it hard for other people to break into our homes, it might be doable if one really wants to.
• Non-universal method: if some service doesn't allow adding more than one U2F token to a single account, then we're out of luck. At the time of writing this, an example of such service is Twitter.

Clearly this “best practice” is not so secure and also quite burdensome. So let's look at another common option (spoiler: which sucks even more).

OTP:

• Even though having a backup OTP is better than using it as the primary 2FA (because as long as I keep using the U2F token, I'm not vulnerable to phishing), it still opens one more attack vector;
• Phones can break or get lost or stolen, and in the case of such event, I'd have to revoke backup creds from all services and recreate them;
• Probably the biggest issue for me: I always carry my u2f token and my phone with me, so again, it's a bad way to backup things. It's not too unlikely that I could lose both my phone and u2f token at the same time and thus get myself locked out of my accounts. We could use Authy which synchronizes the database with the server, but the Authy account can be recovered using SMS, which is anything but secure (however the backup is encrypted by a password which only I know, so overall I'm okay about those backups);
• Non-universal method. Even though many services support Google Authenticator (with the alternatives like Authy), some only have an option to use custom app.

Recovery codes:

• It's desirable to keep recovery codes for all services in a single, safe place. Again, this place is likely to be my home with (almost) the same problems as already discussed with the backup U2F token.
• Again, non-universal method: whether the service supports recovery codes depends on a service.

So bottom line, all of the above methods are non-universal, burdensome and not so secure.

Now that I ranted enough on why everything is so bad, let me tell what I want. I do actually want to have two U2F tokens: primary and backup, but they should be set up in a special way:

• When I register the primary token on some service, the backup automatically becomes valid for this service as well;
• Just when I use the backup token on some service for the first time, the primary one is invalidated for that service.

Before we discuss the technical possibility of it, let me elaborate why I actually want that and how I'd use it.

If we refer to my points above on why a distinct U2F backup token is a bad idea, we can see that all shortcomings of such approach are solved:

• The backup token does not need to be easily accessible anymore. Extreme use cases are: I could secretly brick it up into the wall in the villa's basement, or bury somewhere in the forest. I'm not kidding, I would actually go that far. A fair warning is that obviously one has to remember very well where the token is stored. :)
• Whether I'm at home or I'm travelling, and I need to register on some new service, I do the same thing about maintaining the backup token. That is, I do nothing. I just use my primary token as if it was my the only token, and I have the peace in mind knowing that I'm covered by the backup automatically.
• It's not at all obvious for other people where is my backup token. Few people know it exists in the first place (okay let me say it straight up: it does exist), but even though you now know it exists, I bet it's not feasible to even consider looking for it.
• It's safe. Even if something bad happens with my primary token, it's highly unlikely that my backup token could be affected by the same event.
• It's universal. Having the two tokens set up as I described above, I could use the primary one on any number of services supporting U2F, and it would work independently of whether the service supports multiple tokens, or which backup options does it have, etc.

And if I'm unlucky enough to actually lose my primary token somehow, here's what I should do:

• Unbrick / dig out the backup token;
• Log into all accounts with the backup token, thus invalidating the primary one;
• Since the lost primary token is invalidated, I should be mostly safe at this point, but still, the backup should only be used to enroll a new token. So, time to get a new pair of tokens, add them (i.e. the new primary one) to all accounts and revoke the old token.

I consider this strategy overall to be a really good tradeoff for being secure and still have a reliable, burden-free backup. It's both more reliable and more secure than all other backup strategies.

Before we can talk about actually making it a reality, we need to understand briefly how U2F works. So, here's how it's implemented by the majority of manufacturers (there are some details which are not specified in FIDO U2F, and thus are implementation details)

A U2F token device has a device_secret programmed into it, together with a 32-bit counter which starts from 1 and can only be incremented. When we register that device on some new service, here's what happens:

• Browser sends an AppID (basically, a domain you're on) to the U2F device;
• Device generates a random number (nonce), mixes this with the AppID, runs all that through HMAC-SHA256 using device_secret as a key, and the output becomes the private key for that particular service: service_private_key;
• From service_private_key, a public counterpart is generated: service_public_key;
• Device takes AppID again, mixes it with the service_private_key, and again runs through HMAC-SHA256 using device_secret. The resulting data (MAC), together with nonce generated earlier, becomes a key_handle.
• Device sends key_handle and service_public_key to the browser, and browser transfers it to the service which keeps that data for future authentications.

And authentication goes as follows:

• Service generates a challenge (a piece of random data) and sends it to the browser together with key_handle (which consists of nonce and MAC). Browser sends all of that to the device, together with AppID (i.e. the domain);
• Device generates service_private_key the same way it did on registration, but this time it uses the received nonce instead of the randomly generated one;
• Device generates MAC in the same way it did on registration, and by comparing it with the MAC received from browser it verifies that the received nonce is not tampered and thus the generated service_private_key is valid;
• Device increments its internal counter;
• Device signs the challenge, AppID and counter with service_private_key, and sends the resulting signature along with the counter to the browser, which forwards this data further to the service;
• Service verifies the signature using the service_public_key it has from the registration. It also checks that the received counter is larger than it was the last time (if any). That check is designed to prevent device clones. So if signature matches and counter > last_counter, the authentication is successful, and service saves counter as last_counter.

Curious reader can refer to FIDO Alliance Proposed Standard 11 April 2017 and Yubico's developer documentation for more details.

Let me highlight the parts which are very relevant to our today's discussion.

First, the token doesn't store service_private_keys for each service: instead, it derives keys from other data it has using HMAC-SHA256. This is very important for us: obviously if each device was keeping its own set of per-service private keys, it would be technically not possible to use the backup token on a service without actually registering that same physical token on that service.

(By the way, this is not actually a U2F requirement: U2F doesn't specify how to store keys, and at least in the past there were some implementations which were keeping private keys on the device, e.g. see this github issue. And the rationale for not storing private keys was to avoid limiting the maximum number of services registered with a given token: since device doesn't store any per-service data, the number of services is unlimited)

And second, the token has a counter to prevent device clones.

At first sight, it might seem that this counter thing prevents us from implementing the desired strategy (at least it seemed so to me when I was trying to come up with some solution), but in fact, it only helps us! Bear with me.

The idea is as follows: at the time of manufacturing, program two tokens so that they share the same device_secret, but the backup token needs to have a small tweak: instead of returning counter from 1 (as normal tokens do), it should add some large constant to each returned value: I'd say, approx. half of the 32-bit range, e.g. 2 000 000 000, looks reasonable: I'm unlikely to exceed it during the whole life.

That's basically it, simple and effective.

Having two tokens programmed this way, I hide the backup token somewhere far away and never use it, and just keep using the primary one, so the counter will start from 1 and will be incremented by 1 at each authentication. If something terrible happens and the primary token is gone, I go all the way down to get the backup token from where I hidden it, and I can immediately use it on all the services I used the primary one with, because it has the same secret, and its initial counter is set to a very large number, which I'm unlikely to exceed during the lifetime anyway. Some service's admin might get surprised if they happen to look at authentication counter logs when they see a number suddenly jumping from some small value to 2 milliards, but that shouldn't be a concern. :)

Also let me clarify that I'm not suggesting making the tokens cloneable. As you see, they are not entirely clones anyway (because the backup token has different counter); they only share device_secret which needs to be just programmed to them at the same time, and after that it's not possible to read that data from the token or otherwise make a clone.

Attentive reader could notice that there is some security flaw in the idea above: what if attacker gains access to the primary token, and then somehow forces it to count up to 2 000 000 000? Then they'll be able to use the token even after the backup token was activated.

Luckily, this issue has a simple solution. The counter should be implemented as some hardware counter (presumably on some cryptoprocessor), and that hardware counter should have the range less than 32-bit. E.g. on ATECC508A, monotonic counters can count only up to 2097151. So, by setting the boost counter value in the backup token to anything larger than 2097151 ensures that the primary token could never possibly use the counter value which larger than the backup's counter. To clarify: let's refer to the value from ATECC508A's counter as hw_counter. Then:

• In the primary token, we use: hw_counter;
• In the backup token, we use: hw_counter + 2000000000.

Note that we do not modify the actual hw_counter in ATECC508A; it will still count from 0 to 2097151. Instead, every time we need to get a counter value, we read hw_counter from ATECC508A, then add boost constant, and return further (for using in u2f calculations).

This way, the counter range of the primary token is [0, 2097151], while the counter range of the backup is [2000000000, 2002097151]. The fact that those ranges don't intersect ensures that once backup token is used on some service, the primary one is invalidated for good on that service.

We cannot use YubiKeys for that. Even though YubiKeys do support programming of OTP keys easily (and they even have two slots for them), the U2F key material is totally set in stone. They say that the device_secret is generated on-chip at the time of manufacturing. Well, that's cool and secure and all, but as I mentioned in the beginning, along with security we have to think about a good recovery plan, otherwise one has to actually weaken that security with some back-way if they want at least some recovery plan. Okay, so no YubiKeys for me.

Ideally we should be able to program U2F key material and the counter boost value; having that, creating backups as explained would be easy. Also, it's actually a good thing to be able to control our keys: even though Yubico claims that they do not know the U2F keys in the devices they sell, we have no way to prove that. At the moment, there are no U2F manufacturers who would allow us to program U2F keys and counter Actually, there is! See the section on Trezor below.

Luckily, there is an open source implementation of U2F: U2F Zero. Hats off to Conor Patrick for that! I totally appreciate it, thank you Conor.

There are detailed instructions on reprogramming the devices on their wiki: Building a U2F Token, read that page carefully.

I'm not a hardware guy and I'm not excited about soldering parts together, so I just ordered a few pre-made devices, and reprogrammed them. I personally used a programmer by Silicon Labs for that, but there are alternatives, check the link above and the programmer datasheet. GND is pins 2, 3 or 9; C2D is pin 4, C2CK is pin 7.

At the device configuring stage, we need to specify the same keys when programming both primary and backup tokens. At the moment of writing it, the tools in the u2f-zero repo don't support that (they can only generate pseudo-random keys), so I forked it and added a small commit which implements a few flags. I'll make a pull request and hopefully it will be merged in some shape, but for now, use my fork if you need backups as discussed: https://github.com/dimonomid/u2f-zero .

So, to program two tokens, the sequence is very similar to what's described in the wiki page linked above; the only differences are:

• Before doing anything, generate your keys and store them e.g. into environment vars. Due to implementation details of u2f-zero, we need two 32-byte keys: wkey and rkey. On Linux, it could be done as follows:

$ MY_WKEY=$(dd if=/dev/urandom bs=1 count=32 | od -t x1 -An | tr -d '\n ')
$ MY_RKEY=$(dd if=/dev/urandom bs=1 count=32 | od -t x1 -An | tr -d '\n ')

• When invoking ./setup_device.sh, we need to provide those keys as follows:

$ ./setup_device.sh -w ${MY_WKEY} -r ${MY_RKEY} gencert/ca/key.pem gencert/ca/cert.der

• When programming a backup token, we need to additionally modify the source code to return boosted counter: in the file firmware/src/u2f_atecc.c, there is a function:

uint32_t u2f_count()
{
	struct atecc_response res;
	atecc_send_recv(ATECC_CMD_COUNTER,
			ATECC_COUNTER_INC, ATECC_COUNTER0,NULL,0,
			appdata.tmp, sizeof(appdata.tmp), &res);
	return le32toh(*(uint32_t*)res.buf);
}

For backup token, the last line should be modified as follows (obviously the exact boost value is up to you, I used 2000000000 here) :

	return le32toh(*(uint32_t*)res.buf) + 2000000000;

Everything else is the same as explained in the u2f-zero wiki. To outline the overall process real quick:

• Generate random wkey and rkey, store in environment vars MY_WKEY and MY_RKEY
• Insert primary token, erase it and flash SETUP.hex
• From the tools dir, run ./setup_device.sh -w ${MY_WKEY} -r ${MY_RKEY} gencert/ca/key.pem gencert/ca/cert.der
• Rebuild firmware
• Erase the device again and flash the hex you just built: firmware/release/u2f-firmware.hex
• Unplug primary token
• Insert backup token, erase it and flash SETUP.hex
• From the tools dir, run ./setup_device.sh -w ${MY_WKEY} -r ${MY_RKEY} gencert/ca/key.pem gencert/ca/cert.der
• Modify the firmware to return boosted counter
• Rebuild firmware
• Erase the device again and flash the hex you just built: firmware/release/u2f-firmware.hex
• Wipe your MY_WKEY and MY_RKEY environment vars

That's it! Go to https://demo.yubico.com/u2f , register your primary token, then authenticate with it, and click on the “Techical data” button: on the bottom there will be a counter with some small value. Then try to authenticate again but with your backup token, it'll let you in and you'll see the boosted counter.

I verified that if I add the primary token on Google account, then use it for authentication, then use backup token, and after that if I try to use the primary one again, it won't work (because of the counter). So, as desired, the first usage of the backup invalidates the primary token. Github does the same, and supposedly does any other sane service which supports U2F. Awwwwww. <3

This is a new section I added a year after writing the original article.

Luckily, Trezor now supports U2F as well, so one can program their own key using the BIP39 recovery seed, and that key will be used for U2F.

At the time of device reset, one can specify custom counter as well, like this:

$ trezorctl reset-device -t 256 --u2f-counter 2000000

(more details on trezorctl is available in their wiki)

Therefore, one could have two Trezor devices set up with the same recovery seed, but different counters, and achieve the desired backup goal. Or, if having a readily-available backup device isn't a concern, just backing up the recovery seed is enough.

Even though I keep saying that the backup strategy is awesome (isn't it?!), I'm not so sure about the particular implementation of it, i.e. by means of u2f-zero or Trezor. u2f-zero is the only way I could implement it at the time of writing, so that's what I did, but if we imagine that a hacker gets physical access to the u2f-zero device, I'm not sure whether hacking it (i.e. getting secret key from it) would be as hard as hacking a YubiKey. U2f-zero guys claim that “the security level is about the same as a modern car key”, but I'd need to do a more thorough review of the implementation to judge whether it's true.

The same is true for Trezor as well, unfortunately: Kraken Security Labs were able to successfully extract seeds from all Trezor models.

Nevertheless, to tell the truth, I'm not too worried about it. If an attacker just steals the token without an intention to return it back, then it doesn't matter how hard it is to hack the token, because the attacker can then just use it to log into my accounts and then do whatever they want, like add another token, revoke this one, etc. However, for that I have to be already compromised otherwise as well, because the u2f token is only a second factor.

So, the only scenario in which u2f-zero or Trezor can be less secure than e.g. yubikey is when the attacker tries to get access to my u2f device for some short period of time, learn the secret key from it, and then return the device back to me, all without me noticing anything. For that to be done, one would have to read the contents of the MCU flash (or RAM in the right moment), which isn't impossible of course but isn't trivial either, especially in the short period of time they have until I could notice that I got my key stolen or replaced by another one. Just to be safe, I keep verifying almost every day that the key in my pocket is legit.

Considering all that, I still believe that having a backup as described by means of u2f-zero or Trezor is a lot more secure and reliable than having backup by any other means. At least for me.

The discussed backup strategy beats all alternatives on every dimension: it's universal, it's more secure and more reliable than any other backup method.

I'm really surprised that manufacturers don't use it. It would be nice to have an option to buy a ready pair of tokens which are set up in this way, but alas. A guy from YubiKey support, James A., even said to me that the backup the way I want is “not possible with the way U2F is designed”. Well, not that impossible, luckily.

In case you're interested in purchasing a few pre-made u2f-zeros, here are links:

• Europe: https://u2fzero.ch/
• US/Canada: https://www.amazon.com/U2F-Zero/dp/B01L9DUPK6

Donate
Discuss on Hacker News, Reddit, Lobsters, or right here: