Subject: KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]

From: David Wagner <[email-masked]>
Date: Thu, 27 Oct 2005 19:42:12 -0700 (PDT)

David McGrew writes:
>On Oct 25, 2005, at 5:25 PM, David Wagner wrote:
>> One practical problem with randomized KDFs is that it can be a little
>> tricky to figure out how to pick R.
>> If two parties want to agree on a
>> session key, derived using the KDF, they both need the same value  
>> of R.
>> The obvious thing is to have R be chosen by one party and then sent in
>> the clear to the other.  That works if R was chosen honestly.   
>> However,
>> if R is chosen maliciously by one of the parties, I think everything
>> could blow up and all security could be lost.
>
>I agree that caution is needed, but I'm not sure that this is such a  
>problem.  If we assume that Alice doesn't reveal a secret key, then  
>it seems safe to assume that she will honestly choose the KDF- 
>randomizer used to derive that key.

I don't think this is safe at all.  I think there can be real-world
scenarios with real security holes (not just a theoretical inability
to prove the scheme secure).  Suppose Alice is sending a message to Bob.
Let me consider confidentiality and message authentication separately.

Message authentication: If Alice chooses the randomizer R, then I think
all security can be lost.  Mallory might choose the randomizer R in a way
that makes it easy for her to predict the resulting session key, and then
Mallory will be able to forge messages that look like they came from Alice.

For example, consider the following protocol where Alice sends M to Bob:
  A->B: A, R, M, MAC(k,M)   where k = UH(R, g^{ab})
where Alice has a static Diffie-Hellman exponent g^a and Bob has g^b,
where UH((\alpha,\beta), X) = \alpha * X + \beta mod p for some fixed
prime p, and where Alice chooses R = (\alpha,\beta) randomly.

This protocol is broken.  Mallory can send impersonate Alice:
  M->B: A, (0,0), M, MAC(0,M)
Bob will think that M came from Alice, since UH((0,0), X) = 0 for
all X, and consequently the session key Bob derives is predictable.

Confidentiality: If Bob chooses the randomizer R, then I think all
security can be lost.  Mallory might choose the randomizer R in a way
that makes it easy for her to predict the resulting session key, and
then Mallory will be able to read messages Alice is trying to send to Bob.

For example, consider the following protocol where Alice sends M to Bob:
  B->A: B, R
  A->B: Encrypt(k,M)   where k = UH(R, g^{ab})
where everything is as above, except this time Bob picks R.

This protocol is broken.  Mallory can snoop on Bob's traffic:
  M->A: B, (0,0)
  A->M: Encrypt(k,M)   where k = UH((0,0), g^{ab})
Mallory will be able to recover M, since she can predict that k=0 and
thus she can decrypt the ciphertext that Alice sent.

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