Subject: [Cfrg] Fwd: Hash-Based Key Derivation

From: David McGrew <[email-masked]>
Date: Tue, 25 Oct 2005 09:55:51 -0700

FYI

Begin forwarded message:

> From: Russ Housley <[email-masked]>
> Date: October 25, 2005 9:44:42 AM PDT
> To: [email-masked]
> Subject: Hash-Based Key Derivation
>
>
> I wanted call your attention to an individual draft on "Hash-Based  
> Key Derivation."
>
>       http://www.ietf.org/internet-drafts/draft-dang-nistkdf-00.txt
>
> This draft specifies a soon to be NIST-approved algorithm for  
> deriving secret key material from a shared secret using a hash  
> algorithm.  This algorithm is in the NIST draft SP 800-56.
>
> I encourage review and comment.  If you have concerns with this  
> document, then the concerns probably apply to he NIST draft SP  
> 800-56 document too.
>
> I am considering sponsoring this document as an Informational RFC.   
> Please let me know if you have any concerns with this proposed action.
>
> Thanks,
>   Russ

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

---

From: "Scott Fluhrer" <[email-masked]>
Date: Tue, 25 Oct 2005 10:49:13 -0700

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of David McGrew
> Sent: Tuesday, October 25, 2005 9:56 AM
> To: [email-masked]
> Subject: [Cfrg] Fwd: Hash-Based Key Derivation
> 
> FYI
> 
> Begin forwarded message:
> 
> > I wanted call your attention to an individual draft on 
> "Hash-Based Key 
> > Derivation."
> >
> > This draft specifies a soon to be NIST-approved algorithm 
> for deriving 
> > secret key material from a shared secret using a hash 
> algorithm.  This 
> > algorithm is in the NIST draft SP 800-56.
> >

Well, one concern I have is that the strength of this hash derivation
function depends on the difficulty of recovering a preimage of a hash
function given a large set of hashes of related preimages.  If the attacker
can recover that, then he could recover the secret value (assuming he is
able to somehow get his hands on a number of derived keying materials).
This is a nonstandard assumption on hash functions, and one that to the best
of my knowledge has never been analyzed.

I would suggest instead is that they construct the hash derivation function
out of a MAC (such as HMAC).  That is, instead of doing setp 4.a:

        a. Compute Hash-i = H (counter || SV {|| algorithmID} || 
          contextID {|| SharedInfo}). 

they instead do:

        a. Compute Mac-i = MAC(SV, counter {|| algorithmID} ||
          contextID {|| SharedInfo})

(where the first parameter to the MAC is the key).  By doing this, we are
relying on the designed property of the MAC (which implies that you cannot
recover the key even with a large number of MAC/Plaintext pairs).

---

From: "Simon Blake-Wilson" <[email-masked]>
Date: Tue, 25 Oct 2005 14:23:05 -0400

Is it really true that you can build a KDF like this based on standard
assumptions about a MAC?

To my mind, the key goal behind a KDF is to take an unpredictable value
(the shared secret)(ie. A value an attacker can't guess) and turn it into
a pseudorandom value (the session key)(ie a value an attacker can't
distinguish from a random value). MACs are by design secure only if the
key is pseudorandom, aren't they?

It's amazing to me that no formal theory of KDF design seems to have
emerged yet, despite many years of use in practice.

Best regards. Simon

> Behalf Of Scott Fluhrer
> Sent: Tuesday, October 25, 2005 1:49 PM
> To: 'David McGrew'; [email-masked]
> Subject: RE: [Cfrg] Fwd: Hash-Based Key Derivation
> 
> 
>  
> 
> Well, one concern I have is that the strength of this hash 
> derivation function depends on the difficulty of recovering a 
> preimage of a hash function given a large set of hashes of 
> related preimages.  If the attacker can recover that, then he 
> could recover the secret value (assuming he is able to 
> somehow get his hands on a number of derived keying 
> materials). This is a nonstandard assumption on hash 
> functions, and one that to the best of my knowledge has never 
> been analyzed.
> 
> I would suggest instead is that they construct the hash 
> derivation function out of a MAC (such as HMAC).  That is, 
> instead of doing setp 4.a:
> 
> (where the first parameter to the MAC is the key).  By doing 
> this, we are relying on the designed property of the MAC 
> (which implies that you cannot recover the key even with a 
> large number of MAC/Plaintext pairs).
> 
> > >

---

From: "Tom Shrimpton" <[email-masked]>
Date: Tue, 25 Oct 2005 11:57:58 -0700

> Is it really true that you can build a KDF like this based on 
> standard assumptions about a MAC?

Technically speaking, I believe you need a PRF, not a MAC.   (A PRF is
a MAC, but not the other way around.)  A MAC is *not* required to provide
any sort of secrecy or "randomness", only authenticity.  Say MAC_K(X) is a 
good MAC, and let MAC'_K(X) = 0^{128} || MAC_K(X).  The tags created by
MAC' won't look anything like random bits, but it's still hard to forge
a new tag.

I believe that David is suggesting to construct a good PRF, although he
doesn't
say so in his post.

-Tom

---

From: "Simon Blake-Wilson" <[email-masked]>
Date: Tue, 25 Oct 2005 15:27:31 -0400

Hi Tom,

But a PRF also assumes random or pseudorandom, rather than merely
unpredictable input, doesn't it?

Best regards. Simon

> Behalf Of Tom Shrimpton
> Sent: Tuesday, October 25, 2005 2:58 PM
> To: 'Simon Blake-Wilson'; [email-masked]
> a MAC, but not the other way around.)  A MAC is *not* 
> required to provide any sort of secrecy or "randomness", only 
> authenticity.  Say MAC_K(X) is a 
> good MAC, and let MAC'_K(X) = 0^{128} || MAC_K(X).  The tags 
> created by MAC' won't look anything like random bits, but 
> it's still hard to forge a new tag.
> 
> I believe that David is suggesting to construct a good PRF, 
> although he doesn't say so in his post.
> 
> -Tom  
> 
>

---

From: "Tom Shrimpton" <[email-masked]>
Date: Tue, 25 Oct 2005 13:58:15 -0700

> But a PRF also assumes random or pseudorandom, rather than 
> merely unpredictable input, doesn't it?

Actually, a PRF makes no assumptions about the distribution of the inputs,
but it does assume that the key is random and secret.  In some
constructions,
like the one that David suggested F(S,X) = SHA256-HMAC(SHA256(S), X) the key
S
effectively is part of the "input", so maybe this is what you mean?

Cheers,
Tom

---

From: "Simon Blake-Wilson" <[email-masked]>
Date: Tue, 25 Oct 2005 17:11:23 -0400

Right ... like I said at the start of this thread, I think the hard part
of KDF design is "the thing that turns an unpredictable value into a
pseudorandom value". Neither a PRF nor a MAC achieves this as far as I can
see ... The only thing which does it that has come up so far is a random
oracle ...

But a random oracle assumption seems like a pretty unsatisfactory solution
to the problem to me ... It feels like taking a heavy weight tool to solve
a light weight problem. And I suspect that both H(S|X) and PRF(H(S),X) are
good KDFs if H is a random oracle, so it doesn't help distinguish among
solutions as much as I'd like.

Best regards. Simon

> From: Tom Shrimpton [mailto:[email-masked]]
> Sent: Tuesday, October 25, 2005 4:58 PM
> Actually, a PRF makes no assumptions about the distribution
> of the inputs, but it does assume that the key is random and
> secret.  In some constructions, like the one that David
> suggested F(S,X) = SHA256-HMAC(SHA256(S), X) the key S