Re: [Cfrg] [TLS] NIST crypto group and HKDF (and therefore TLS 1.3)

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

After some private discussion with Hugo and analyzing my use case, it appears that I won’t need to reverse the HKDF inputs after all.


To recap my use case: I have an HSM with pre-loaded/pre-shared symmetric keys (of good quality). 

I need to:
  a. derive new symmetric keys from those pre-shared, using non-secret non-random input
  b. derive new symmetric keys from the output of ephemeral (asymmetric) Key Exchange

HSM doesn't directly support KDF of any kind, but supports HMAC. So my best hope for KDF is HKDF that I construct manually from the HSM-provided primitive (HMAC).

For (a) I can construct HKDF by manually invoking (this description is a simplification) HSM HMAC(key=pre-shared-key, data=my-non-random-data). That would be compliant with RFC 5869 because I'm deriving from a strong key - therefore it's OK to skip HKDF-Extract step and proceed directly to HKDF-Extract (all the HKDF security proofs apply).

For (b) I construct HKDF by manually invoking HSM HMAC(key=pre-shared-key, data=EDH-output) - with more invocations, of course, but that's the essence. In the HKDF-Extract step I'm replacing random salt (or salt of all zeroes) with a strong secret - which is even better than using random salt. Again, all the security proofs apply.

If my pre-shared keys weren't strong, the above would not work wrt. the current KHDF security assumptions & proofs.

TNX!





From: Cfrg <[e-mail]> on behalf of Uri Blumenthal <[e-mail]>

Date: Thursday, May 14, 2020 at 11:01

To: Hugo Krawczyk <[e-mail]>, "Dang, Quynh H. (Fed)" <[e-mail]>

Cc: "[e-mail]" <[e-mail]>

Subject: Re: [Cfrg] [TLS] NIST crypto group and HKDF (and therefore TLS 1.3)



When the IKM is longer than 1 block, it gets hashed iteratively by the compression function in Merkle-Damgard fashion (the hash function). Then, this hashed result is padded to become a full block, then Xor with opad and ipad (making input blocks are "independent"/different blocks/keys.  One of these Xored values is hashed with the salt, then its result and the other Xored value get hashed one more time by the iterative MD-hash function. 



I dont understand why any extraction property that you get from the traditional extraction gets lost by this alternative method. 



The only way I know to justify this step in general is to assume the underlying hash function is a RO which is general is not, due to extension attacks. 



Can you please explain: what is the significance of extension attacks in this context? 

KDF is not a MAC. And while it’s nice to have a construction as generic as possible – sometimes it helps to narrow the applicability scope, because the generic version may be too limiting for that specific use case.



This would make the analysis fully dependent on RO while the analysis of HKDF can use less stringent modeling depending on particular cases.



Thank you. One conclusion I draw form this is – since extension attacks do not seem to apply/matter for the Key Derivation, it is reasonably safe to model the entire hash function as RO. Therefore, the proposed option appears to be safe.



For me, it is less important to stay generic than to be able to employ currently-available commercial HSM. For that use case, modeling hash function (even SHA-2) as RO seems OK.



I don't know how you do that if the only input to the function is an initial hash value of the IKM.



When the IKM is not more than an input block, then each of  the 2 Xored values gets processed by 1 compression function call which is modeled as a RO. I dont understand why this alternative method losses some extraction property from the traditional extraction function.



When the key is no longer than hash block then you would need to assume what the compression function is a PRF when keyed via a non-uniform key, essentially assuming what you need to prove.  



You can go ahead and use the reverse construction as an ad-hoc construction. However, if you want a detailed analysis such as in the case of HKDF , which is careful about lowering cryptographic assumptions, builds on the Merkle Damgard iterations (that are the basis of HMAC as PRF), is based on rich statistical extraction literature of 30+ years,  justifies the use of the function for many different settings (reflected very well in the use of HKDF in practical protocol, cf. TLS 1.3), and provides usage guidance, then I am not sure you can do it with the ad-hoc construction.



At the risk of repeating myself: while I appreciate what you’re explaining here, in my case staying with the lowest theoretic-proven cryptographic assumptions makes stuff undeployable in practice. 



I really recommend you read the paper.  As I said at the beginning of this thread, I don't want to convert this into an exposition on HKDF. For that I wrote a full paper



I think I said that I have read that paper (I suspect that Quynh did too), and (in my case) found it targeting a different audience. No offence meant – but if it were more readable, I wouldn’t have to ask my questions here.