How does Yubico’s implementation of U2F claim to be able to support any number of services with unique key pairs when we have limited storage? And do this in a way that is secure and respects your privacy?
First off, a refresher on how this is described in the U2F specification: “U2F tokens might not store private key material, and instead might export a wrapped private key as part of the key handle” (from the implementation considerations document).
What does exporting a wrapped private key mean? Basically this (somewhat simplified): When a U2F device is registered, an elliptic curve key-pair (using the secp256r1 curve, as specified in the U2F standard) is generated on the device itself. The private key is then encrypted using a device master secret, forming the key handle, which is then sent together with the public key to be stored on the RP (Relying Party) server. To authenticate, the RP sends a challenge together with the key handle, and the U2F device decrypts the private key to be able to produce a valid signature for the challenge.
Now this is a sound approach, and is secure when done correctly. It does have its drawbacks, however. One is that it feels less secure, as even though the private key is encrypted, it does leave the device. In practice as long as the encryption used for the wrapping is strong, this isn’t a problem. Another issue is that it introduces additional complexity to the protocol, as we now have a new cryptographic primitive (encryption), with possible pitfalls.
Rather than dealing with these issues, we at Yubico chose to use the following approach (still fully compliant with the U2F specs): instead of randomly generating the key-pair and then encrypting the private key, we deterministically generate a key-pair based on several inputs, so that we can re-create the same key later on when it’s needed, without needing to store it anywhere.
This is how we achieve it (slightly simplified):
When a user registers one of our U2F devices with a new service, the service provides an AppID (this is tied to the URL of the site and prevents phishing). The U2F device generates a random Nonce. We then take the AppID and the Nonce and run them through HMAC-SHA256 (a one-way keyed function), using a device-specific secret as the key. This device-specific key is generated on-chip at the time of manufacturing (just like the master key would be, if we were using regular key wrapping). The output of the hash function becomes the private key, and the Nonce value, together with a MAC (message authentication code), becomes our key handle. During authentication, the MAC helps to ensure that a key handle is only valid for the particular combination of device and AppID that it was created for during registration.
From the outside these two approaches are indistinguishable from each other, and for practical purposes either should be fine. However, we think that our approach offers some benefits: most obviously, the private keys never leave the U2F device, in any form. And since we’re re-using the SHA256 primitive that is already used elsewhere in the U2F protocol, we avoid introducing another cryptographic algorithm into the system. Fewer algorithms means lower potential for mistakes.
Key derivation during registration