Hacker News Reader

Comment by harshreality | Hacker News Reader

> U2F Tokens do not have a key limit

They must have some limit. EC Keys are roughly 32 (256 bit) or 48 (384 bit) bytes (x2 to store the public half, right?), and most of these devices don't have MB of storage afaik... I think they have security chips with like 64-256kb of secure storage. So once you get into the range of thousands of sites, wouldn't you run out of room?

ETA: thanks akerl, I didn't realize that's what they (or most of them) were doing; I didn't even realize deterministically generating an EC key from a seed was efficient enough to do it quickly on a tiny embedded chip.

View on HN

In theory, yes. In practice, the way that most U2F tokens (for example, Yubikeys) work is to storage a single device-specific secret key on the token, which never changes. Then, when “adding” a key for a site, they take the provided details from the server as inputs, along with the secret key, to derive a new, site-specific private key, which is used for U2F. That allows them to “store” an unlimited number of site keys. Note that this method isn’t mandated by the U2F spec, so it’s not guaranteed that any key which implements U2F will do so in this way.

The OpenSSH protocol doc alludes to this requirement when they talk about why U2F needed a custom method for interfacing with SSH: the site’s handle needs to be provided as input to the key, so that it can re-derive the site-specific private key, and that communication channel didn’t already exist in ssh-agent.

Critically this isn't quite correct.

The handle (IIRC the FIDO spec calls it a cookie but that doesn't matter) is NOT chosen by the relying party (in this case a SSH server you're logging into). It's chosen by the token itself during the enrollment process and given to the relying party with the other results of enrollment to be stored.

The token will use local random data in addition to random data supplied by the relying party for choosing a private key (and thus in the design you describe, the handle). This is a common design choice in cryptographic systems because it means if either Alice OR Bob really used random numbers the results are truly random, things only go badly if both parties defect.

In WebAuthn this means if you use your token to enroll with Google, and Facebook, and say Twitter, so long as the people who built the token did a good job it won't matter if both Google and Facebook are trying to betray you and deliberately didn't use random data, they can't attack your Twitter account this way.

Edit: refer to the device as a "token" not a key for clarity

I feel like a much simpler correction might have been “you meant application ID instead of key handle”, given that the application ID is based on the individual server (it’s generally partly the URL and a server-provided challenge), and is combined with the token secret key to create the full handle.

Nothing in my comment implied that if google betrayed you, it would leak your facebook token.

Er no? I think you're still not getting it. The essential trick is that the token gets to randomly pick the value for this cookie, it isn't depending on the application ID.

One example way you can do this goes like this:

* Token has a Secret Key S baked inside it

* During enrollment the token makes a random private key P1 and a corresponding public key K1

* It makes a Cookie C1 by encrypting P1 using S

* It signs a message Ma with P1 to produce Za

* It sends C1, K1 and Za

The relying party gets to influence Ma but they do NOT get to pick any of these other values like P1, C1, K1.

The relying party verifies that Za is indeed a signature of Ma with K1 and if so enrollment worked, store C1 and K1

Now, after enrollment the relying party can produce new challenge messages Mb Mc Md and so on for ever, and each time it supplies the token with C1.

Given C1 and Mb, the token can decrypt C1 with S to get back P1, and then it can sign Mb with P1 to produce Zb. It sends that back.

The relying party can confirm that Zb is a signature of Mb with K1 and so this must be the genuine token that was enrolled previously.

Does such approach as desribed by you mean that token needs to store P1/K1 for every site?

AFAIK It does not.

And if it does not, your explanation contains bigger errors about enrollment/process.

@akrel described it much better.

In my description I specifically explain that the token gets P1 back by decrypting C1 with S so that it needn't be stored.

You've become fixated on the part akerl_ (not @akrel) got right, that tokens don't store the private key but missed the _essential_ element they got wrong which is how this key is generated.

One really obvious consequence of things working as I explained rather than as akerl_ (presumably mistakenly not maliciously) explained is what happens if we do enrollment again with the same token for the same Relying Party, for example maybe Alice and Bob are a couple sharing a token.

In reality, as in my explanation, these enrollments produce completely different results, the token will pick a random P1 (thus K1, C1, etc.) when Alice enrolls and a different random P2 (thus K2, C2, etc.) when Bob enrolls, and for the Relying Party everything is different between these two enrollments, just as if the token was different.

In akerl_'s description Alice and Bob would get the same application ID, same results, and now a Relying Party can tell that Alice and Bob are using the same token.

The U2F protocol uses a master secret that signs a KDF. Essentiall you generate a keypair given a certain input and sign the output. You can produce virtually unlimited keys from a single source.

In RSA you need to pick primes, if you pick random numbers RSA doesn't work. But the elliptic curve public key systems work with more or less arbitrary numbers so you can just use any random number as a key. Some magic numbers like zero may not work depending on the algorithm, but

(a) you can exclude those explicitly with a tiny amount of effort

AND

(b) probability of picking any such number for a 128-bit key is insignificant

Aren't the keys are generated dynamically every time, based on the devices secret and the pub key id.

Reply on news.ycombinator.com