Re: [saag] Re: [Cfrg] KDF: Randomness extraction vs. key expansion

[canetti <canetti at watson.ibm.com>]

Dan, we seem to be in violent agreement, at least on the main point of this
thread.  You say:

> too weak or too strong. You do _not_ have, and you will never have, a
> key-derivation function that's provably secure assuming AES security.

Exactly. Being a block cipher is not a strong enough property for randomness
extraction (or, key derivation if you prefer this name). In contrast, being
a block cipher is a perfect fit for key expansion. So let's separate the
two tasks!

BTW. In spite of the date, I dont share your pessimistic view that key
derivation/randomness extraction is doomed to be a vague notion where
sorcery rules forever. I think we do have tools to make mathematical
sense of it and to make concrete security claims. But I certainly agree
that it's a very different (and harder) task than key expansion.


Ran



On Mon, 31 Oct 2005, D. J. Bernstein wrote:

> canetti writes:
> > But then, as you point out, we're left with one main analytical tool:
> > the vague notion of a "serious cryptographic function".
>
> The security of a key-derivation function is _always_ a vague notion.
> You _must_ combine key derivation with a Diffie-Hellman group to produce
> a clear security notion, namely HDH. _Every_ key-derivation function can
> have its security destroyed by a poor choice of Diffie-Hellman function.
> In fact, _every_ key-derivation function, no matter how many buzzwords
> were used in its construction, can potentially have security destroyed
> by a choice of Diffie-Hellman function that would have been secure with
> most key-derivation functions. Even worse, if you make a sufficiently
> poor choice of key-derivation function, then your security _will_ be
> destroyed by _standard_ choices of Diffie-Hellman functions.
>
> You've made a contrary claim, namely that you can build a conjecturally
> secure key-derivation function by combining any randomness extractor and
> any conjectured PRG. That claim is _false_. Your construction can lose
> all the security that would have been produced by the NIST KDF. Your
> construction fails to prevent related-key attacks. The last two
> paragraphs of my previous message explain this in detail.
>
> You could try to fix your security mistake by replacing ``randomness
> extractor'' with a stronger notion---but if you continue trying to avoid
> vague notions then you'll inevitably end up with something that's either
> too weak or too strong. You do _not_ have, and you will never have, a
> key-derivation function that's provably secure assuming AES security.
>
> ---D. J. Bernstein, Professor, Mathematics, Statistics,
> and Computer Science, University of Illinois at Chicago
> _______________________________________________
> saag mailing list
> saag at mit.edu
> https://jis.mit.edu/mailman/listinfo/saag
>

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg