Third rewrite

[UppaJung]

I rewrote the spec (now key-derivation.md in this PR) to make it accessible to readers who are unfamiliar with the details of WebAuthN and FIDO2 and as I walked through everything carefully in detail.

The structure of credentialId hasn't changed, but a few things have.

• All inputs are now named to better match WebAuthN and extensively documented with pointers to the WebAuthN spec.
• There is no longer a need to derive subkeys from the seed, which should simplify both the spec and possibly the implementation.
• There are fewer restrictions on how the 32 byte unique identifier within the credential ID is derived, as inspection revealed it has no impact on other authenticator's ability to authenticate with the same credential ID.
• Per @nickray's request, I simplified the external seed state so that the spec is indifferent to how it uses its first byte
• The specification now addresses which errors will result when validations fail.

[UppaJung]

@nickray Sorry -- one commit didn't make it into the original PR. Please look at updated one the file to look at is key-derivation.md

[nickray]

I'll look into reviewing this properly, a bit time pressed.

[nickray]

I'm reading through key-derivation.md top to bottom, adding my remarks. I'm skipping typos. Once we have all the details nailed, I think a rewrite might be useful to add back "flow".

These are opinions, please disagree where applicable.

Also apologies for this being lengthy! I'm a mathematician so I like things stripped down, logical and minimal...

• we should state that we only handle the 2FA / non-resident key case, where we are supplied with a trusted userId (and add this to the "Inputs" section) - with no intention of covering the resident key case via some impossibility argument
• on byte string null termination: I think this is only pertinent for the domain separators, so may become irrelevant (see below). However, when in doubt I'd suggest not adding aka stripping null, as this is a C-ism with no value when used with constants. The other way would make a Rust implementation slightly more painful. I think this is also consistent with how rpId and userId are handled?
• I would strongly prefer to have three keys directly derived from the seedKey as per my original suggestion, so e.g. (quoting you, but see changes below) uniqueId = SHA256HMAC(SHA256HMAC(seedKey, b"uniqueId"), rpId || userId || hash) instead of uniqueId = SHA256HMAC(seedKey, b"uniqueId" || rpId|| userId || hash). This has the advantage that the three keys can be precomputed, so the seedKey itself never has to actually be loaded into memory, and e.g. if the credential key is leaked, then this "uniqueId key" is not. Conceptually and in implementation, we'd have three nameable keys, with different purposes (this is the stronger reason for me than the somewhat far-fetched leakage argument).The only disadvantage I see is that an implementation that wishes to store only the seedKey has to do two HMACs per operation.
• If you agree, I think we should name these three keys, e.g. "unique ID key", "MAC key" and "key derivation key". I'm not sure about the naming here and need to think about it more, it should be concise, precise and memorable.
• To reduce the amount of bikesheddable string constants that need to be stored, how about we just use one byte constants 0x1, 0x2, 0x3? This also resolves the null-termination question above.
• I'm not sure what the "hash is a parameter passed to authenticatorMakeCredential" you use in uniqueId is; looking at my original suggestion this was probably an abbreviation for rpIdHash, so would be redundant here
• great that you dug out the requirement to set signature counter to zero, I didn't know that was specified - thanks!
• also very important to specify the necessary verification procedures during getAssertion as you do!

To introduce notation, with HMAC = SHA256HMAC and H = SHA256, I'd set (I use seed for your seedKey)

idKey = HMAC(seed, 0x1)
macKey = HMAC(seed, 0x2)
derivationKey = HMAC(seed, 0x3)

and so far we'd have (I use "keyId" for your "uniqueId")

rpHash = H(rpId)
userHash = H(userId)

keyId = HMAC(idKey, rpHash || userHash) 
# irreversiblyEncryptedKeyId, really - rpHash || userHash is "the" key ID

credentialMac = HMAC(macKey, rpHash || 0x1 || keyId || extState)
credentialId = 0x1 || keyId || extState || credentialMac

Using hashes here makes the components fixed length (except extState), so e.g. prevents RP/user confusion. The order of version/uniqueId/extState in credentialMac and credentialId is chosen to be the same for mnemonic ease; I keep rpHash at the beginning in credentialMac as it's fixed length but leave credentialMac at the end in credentialId so the first byte can already be checked easily for future iterations. In other words, we can set (just new notation for emphasis, nothing new)

unauthenticatedAndUnboundCredentialId = 0x1 || keyId || extState
credentialMac = HMAC(macKey, rpHash || unauthenticatedAndUnboundCredentialId)
credentialId = unauthenticatedAndUnboundCredentialId || credentialMac

OK, so now we can generate key IDs, store them + state at the RP as anonymous, versioned credential IDs, and verify they were generated by us, for the RP in question, via the MAC. So we can simply set

privateKeySeed = HMAC(derivationKey, keyId)  # no more rpID

AFAIK there is no "generally shared" map: 32 bytes (privateKeySeed) -> P256 private key. If there is some RFC, let's use that, if not, we have to specify one. One procedure I could think of ("rejection sampling with iterated hashing", but this we should ask a cryptographer about) is:

1. interpret the 32 bytes as little-endian integer S between 0 and 2^256 - 1
2. if 1 <= S < order of the P256 group, use S to set private key = S * canonical generator (multiplication as Z-module)
3. if not, set S = SHA256(S), and goto 1.

--

ADDENDUM: From a privacy perspective, we should not follow the "minimalism gone too far" approach sketched below, as this allows "cross-site user tracking" since all RPs have access to the same encryptedUserId value.

MINIMALISM GONE TOO FAR: Reviewing both this and my original proposal, from a minimalism perspective what I was thinking was that we could further simplify:

• set just keyId = HMAC(idKey, userHash)
• use privateKeySeed = HMAC(derivationKey, credentialMac)

This still gives unique private keys because rpId is mixed into the credentialMac, and allows a high-level interpretation of "userId is the key", idKey as (irreversible) "(key) encryption key" (kek), macKey is a "(key) authentication key" (kak), and derivationKey is a "(key) derivation key" (kdk).

Then the constructions would collapse to:

kek = HMAC(seed, 0x1)  # or 0x65 for ASCII 'e' to avoid an unnatural "order"
kak = HMAC(seed, 0x2)  # or 0x61 for ASCII 'a'
kdk = HMAC(seed, 0x3)  # or 0x64 for ASCII 'd'
encryptedUserId = HMAC(kek, userHash)
unauthenticatedCredentialId = 0x1 || encryptedUserId || extState
bindingMac = HMAC(kak, rpHash || unauthenticatedCredentialId)
credentialId = bindingMac || unauthenticatedCredentialId
privateKeySeed = HMAC(kdk, bindingMac)
privateKey, publicKey = defined-procedure(privateKeySeed)

[nickray]

I implemented the core functionality pertaining to the spec as per my preceding comment as a possible reference: https://colab.research.google.com/drive/1liWfrX5J04pWqHo-cGIu0NZYrsUH51CT

[UppaJung]

I think we're mostly aligned except the three keys, which is unnecessary when you examine how HMACs work. Please check out these changes to the PR.

[UppaJung]

I believe the goal you're trying to accomplish by having multiple keys is a goal the designers of HMAC anticipated, built into how HMAC works, and so there's no need for additional keys/hashing. Adding another layer gets you zero additional security but additional implementation complexity.

In our application, with a 256-bit K

HMAC(K, m) = (H (K XOR opad) || H( K XOR ipad) || message)
                                --------------

Hashing the key before passing it to the HMAC is unnecessary because the second term in the outer hash function is already a hash derived from the key. So long as keys are unique, you're good.

[nickray]

On the three keys, I'm aware that they're not necessary vis a vis the properties of HMAC (the same would hold true if we took raw SHA-3 or any other hash that isn't vulnerable to length extension attacks).

However:

• philosophically I prefer a setup with three independent keys (as a related principle, while e.g. P256 lets you both sign and key agreement via DH, for Ed25519/X25519 it is advised not to share the same key for different purposes)

• practically I like the idea of not actually storing the seed on the device (see a possible rollover approach below), and

  offline:  seed  ----on loss--> e.g. HMAC(seed, 1), or whatever, can write "HMAC(seed, 1)" in extState
          |                          |
          v                          v
  device:  three keys              three new keys

• operationally in my envisioned implementation it's actually slightly less complex to implement.

• here's a version without nested HMAC: https://colab.research.google.com/drive/1mfx2g3oTDpJZS-_1bQ_1xJTSkV9ZrdQW. As you can see, the constants are littered throughout the code, instead of cleanly separating the tasks of "derive key for given purpose", "apply operation with this key to data at hand".

Perhaps we could add that as a question to Joe, together with the 32B->P256 key issue?

Regarding extState, I've been wondering: If we store this in unencrypted form on each RP, they can all extract it and collude to track cross-site, assuming this state is sufficiently unique. Probably not an issue in practice, but I wanted to hear your thoughts. ~Fixing this would involve "reversible" encryption, so assumedly adding AES to the mix (it would be nice to avoid a second primitive), roughly AES-encrypt(HMAC(seed, rpHash), extState).~ EDIT: Never mind, I realized for your envisioned use case of "I don't know how to regenerate my seed" you won't.. have the seed, so if extState is encrypted, you're busted.

[nickray]

Regarding my dislike of the kind of intricate constructions you suggest, it might help if I explain how the "crypto core" service in our new firmware will work:

• Client "apps" (like FIDO) can make "system calls" with general operations like "GenerateRandomKey(algorithm) -> key_handle", "Sign(key_handle, data) -> signature", "DeriveKey(key_handle, algorithm, parameters) -> new key_handle", etc.
• At no time does the client have direct access to the secret key material (except well for the inital step where a key is generated from a given byte sequence, instead of via a software or hardware RNG), this is all handled by the crypto service.
• I really think this is how crypto in general should work in such a firmware setup (it's modeled after PKCS#11 as the standard for a high-level crypto API), so doing something intricate and nonstandard like "something XOR (something OPERATION something)" requires custom methods, and in a way, breaking the abstraction.

[UppaJung]

Regarding my dislike of the kind of intricate constructions you suggest, it might help if I explain how the "crypto core" service in our new firmware will work:

• Client "apps" (like FIDO) can make "system calls" with general operations like "GenerateRandomKey(algorithm) -> key_handle", "Sign(key_handle, data) -> signature", "DeriveKey(key_handle, algorithm, parameters) -> new key_handle", etc.
• At no time does the client have direct access to the secret key material (except well for the inital step where a key is generated from a given byte sequence, instead of via a software or hardware RNG), this is all handled by the crypto service.
• I really think this is how crypto in general should work in such a firmware setup (it's modeled after PKCS#11 as the standard for a high-level crypto API), so doing something intricate and nonstandard like "something XOR (something OPERATION something)" requires custom methods, and in a way, breaking the abstraction.

Got it. So the requirement here is that the there is a small constant number of inputs to the key field that are all derivable from only the initial key. I'll revise to do that.

I'll separate the formulas from calculating all the fields from implementation details, such as the fact that you can precompute all the inputs to the key function.

[UppaJung]

We had three conceptual keys here. One was used to generate the unique id for the CredentialID. The only reason not to use the seedKey is to avoid creating an oracle by which an attacker can try to guess the seedKey. The new suggestion for deterministic calculating of a uniqueId accomplishes that.

I don't see why we need a different key for the MAC calculation and the random bit stream, but if you see a reason why it's necessary, one could make the mac key SHA256(seedKey). The formulas in the current proposal would change only in that

credentialMac = SHA256HMAC( SHA256(seedKey), rpId || version || uniqueId || extState)

and there would be an implementation note that you can pre-calculate SHA256(seedKey) and store it in safe key storage if you're worried about intermediate values being compromised.

[conorpp]

Sorry for the late review on this. I want to ask about the 256 associated data -- could we make this much smaller? 256 bytes more than doubles the minimum state needed for Solo. While it could work, I think it's a bit of a hefty requirement for embedded devices and would be much better if we could do with less, say, in the 32-64 byte range.