Subject: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)

From: David Wagner <[email-masked]>
Date: Sat, 29 Oct 2005 22:42:37 -0700 (PDT)

John Wilkinson writes:
>Getting back to the original topic of the NIST HKDF proposal, several
>people suggested that they were uncomfortable with the construction
>H_i = H( i || SV || contextID ), which is the one suggested in the
>HKDF proposal, with some optional arguments suppressed.
>
>Most of these same people suggested instead something along the lines
>of K_i = PRF( H(SV), i || contextID ), where H(SV) is the key input to
>the PRF, and ( i || contextID ) is the "message" input to the PRF.
>HMAC and CMAC were both suggested as suitable PRFs.
>
>Neither HMAC, nor CMAC retains any security guarantee as a PRF if the
>key is not chosen uniformly at random. If we assume that H(SV) is
>uniformly random, given that SV may not be, then we should have no
>concern with the NIST HKDF.

I don't agree with the last statement.  As I have written before (I
apologize for repeating myself), H(i || SV || ...) puts more stress on
the hash than PRF(H(SV), i || ...) does.  For the latter, we only need
H() to be good at producing uniformly random output *once*, and for the
case when *the attacker has limited (or no) control over the input to
the hash*.  For the former, we need H() to be good at producing uniformly
random output *on many closely related inputs*, and *when large parts
of the input can be entirely controlled by the attacker*.  Dealing with
producing many uniformly random outputs is precisely what PRFs are
good at.  And dealing with (non-secret) inputs that can be controlled
by the attacker is also exactly what PRFs are good at.  PRF(H(SV), i ||
...) uses the H() and PRF() primitives for what they are best at, not
what they are worst at.  For this reason, I would think that PRF(H(SV),
i || ...) would be a better design.

Basically, I'm talking about limiting how much we rely on the random
oracle model -- or, almost equivalently, limiting how much stress we put
on the hash function to behave well in scenarios it wasn't necessarily
designed for.

I think the NIST KDF is sub-optimal, and could be improved.  I don't
understand the argument that would be better to leave it unchanged.
But hey, I don't want to overstate the case.  It's not the end of
the world to leave the NIST KDF as is.  It's probably secure as it is.
My comment is only that one can do better: one can reduce the likelihood
of security failure, through more thoughtful design.  But if the powers
that be decide they prefer the current form, it's not a big deal.
Frankly, it's pretty rare for the crypto to be the weakest point in any
real system anyway, so even if the crypto isn't the very best it could
be, that might still be ok.

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: John Wilkinson <[email-masked]>
Date: Sun, 30 Oct 2005 07:21:26 -0500

On Oct 30, 2005, at 1:42 AM, David Wagner wrote:
> I think the NIST KDF is sub-optimal, and could be improved.

I have never implemented a KDF similar to NIST's proposal; I have  
always used (without really thinking about why) a "pre-hash" of the  
shared secret value H(SV) as the key input to a PRF.

Since I tend to be conservative, I would probably be more inclined to  
use the HKDF proposal if it were like the (already suggested)  
construction:

H_i = HMAC( H(SV), i || contextID )

I thought that some were objecting to this construction on  
implementation difficulty or efficiency grounds, and since I couldn't  
really see anything quantifiably *wrong* with the NIST proposal, I  
suggested leaving the NIST proposal as is. If, however, everyone is  
happy with the above "pre-hash and HMAC" construction, it would  
certainly get my vote.

-John

---

From: "D. J. Bernstein" <[email-masked]>
Date: 31 Oct 2005 06:07:43 -0000

David Wagner writes:
> *the attacker has limited (or no) control over the input to the hash*

I disagree. It is highly dangerous to model Diffie-Hellman shared
secrets g^xy as uniform random group elements. For example, the attacker
can feed the geometric progression g^xy g^x, g^xy g^2x, ... to the hash.
Sure, this is more complicated than an arithmetic progression 0,1,2,...,
but describing it as ``limited (or no) control'' is unreasonable.

> H(i || SV || ...) puts more stress on
> the hash than PRF(H(SV), i || ...) does.  

I disagree. This ``stress'' hasn't even succeeded in breaking wimpy
MD5-based constructions from a decade ago. The ``many simple rounds''
philosophy for building unbroken secret-key ciphers, and for trying to
build collision-resistant hash functions, has been 100% successful at
building unbroken key-derivation functions.

There don't seem to be speed pressures telling us to reduce the number
of rounds in a key-derivation function; there aren't security pressures
telling us to increase the number of rounds; there _are_ code-size
pressures telling us to reuse existing cryptographic components in the
simplest possible way.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago