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

From: David Wagner <[email-masked]>
Date: Fri, 28 Oct 2005 15:04:03 -0700 (PDT)

Dan Bernstein writes:
>David Wagner writes:
>> The hash function also has to be independent of the adversary's choices.
>
>No, that sort of assumption is always wrong for public hash functions.

Exactly my point.  I'm saying the assumption is necessary for provable
security under the Leftover Hash Lemma; but as you say, the assumption
is false for public hash functions.  The obvious conclusion: public hash
functions are generally incompatible with provable security under the
Leftover Hash Lemma.  Is there some flaw in this reasoning?

>> If you pick and reveal the hash function first, and the adversary chooses
>> their values afterwards (and those values are processed with the hash
>> function you picked), all bets are off.  Did I get that right?
>
>If you're trying to say that the attacker can perhaps produce non-random
>behavior in the secret that he shares with you, that's true. In fact, he
>always knows the entire value! But this has no relevance to his attempts
>to determine the secret that you share with someone else.

That's not what I'm concerned about.  I'm not concerned about other
sessions; I'm concerned about the very session that the adversary is
participating in.  Read this:
  http://www1.ietf.org/mail-archive/web/cfrg/current/msg01095.html
That message gives scenarios where everything falls apart, because the
adversary can choose some inputs to the KDF that make the session key
*for this session* predictable.  (One quick example: if the KDF is used
to derive a MAC key that is used to authenticate the other party, then
spoofing may become possible.)

And no, it is not necessarily true that the adversary already knows
the entire value of the secret that is supposedly "shared".  There are
protocols where if both parties are honest, then both parties will know
the value of the shared secret -- but it is a security condition that
if one participant tries to spoof someone else's identity, then that
malicious participant does not learn the value of the "shared" secret.
The URL quoted above gives examples.

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 29 Oct 2005 10:34:03 -0000

David Wagner writes:
> security under the Leftover Hash Lemma

No. Your false hypothesis is not an assumption of the lemma. You clearly
understand that the lemma applies to public hash functions used for one
message; I have no idea why you think that the multiple-message case is
different. Anyway, I already cited a Shoup page that explains all this
in detail.

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