Subject: [Cfrg] Re: Cfrg Digest, Vol 16, Issue 43

From: John Kelsey <[email-masked]>
Date: Sat, 29 Oct 2005 08:08:38 -0700 (GMT-07:00)

>Date: 28 Oct 2005 22:15:39 -0000
>From: "D. J. Bernstein" <[email-masked]>
>Subject: Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)

...
>In other words, there's no justification for the religious notion
>that ``encryption functions'' are safe while ``hash functions'' are
>to be avoided. Sure, MD5 is a disaster, but 4-round AES is a disaster
>for the same reasons. If you want to know whether a primitive is
>safe, you have to look at the details of the primitive; the
>high-level packaging is almost irrelevant.

I think the thing you're both missing here is the ways these
primitives can be attacked.  Hash functions are easier to attack,
because in general, you can't assume any secrets from the attacker,
and because the maximum number of queries an attacker may make to the
hash function is limited by his computing power, where in the block
cipher case, the maximum practical number of queries is limited by how
much work the attacker can get his victim to do.  (A 2^{64} adaptive
chosen plaintext attack on AES requiring 2^{64} work would make a nice
publication, but it would have no practical impact.  The same
parameters on a hash function attack are potentially devastating--as
witness the reactions to the most recent Wang results on SHA1.)

This is a potential problem with shifting over to an AES-based hash
construction as a response to Wang's breaks on MD5, RIPEMD, SHA0, and
SHA1.  I don't think there's been much attention paid to attacks in
which the attacker gets to choose key bits, and gets to know
everything going on inside AES when planning his next set of inputs.
This is a really different attack model.  

Interestingly, the problem works the other direction--you can
apparently have a pretty good hash function (at least in the
collision-resistant sense) that gets broken when someone tries to use
the underlying block cipher component for encryption.  Different
attack models, different defenses applied.  (For the SHA256 underlying
block cipher, you normally can't choose plaintext blocks except by
brute-force search, and you never run it in the decryption direction,
so attacks that could work if you had that kind of access can
more-or-less be ignored.)  

And in the KDF case, the situation is a bit different, because in this
application, there are secret values.  (If there aren't some secrets
from the attacker, the KDF won't give us secure keys, though it may
still give us random-looking keys.)  

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

--John Kelsey 
(I'm new to this conversation, so forgive me if I'm restating
something that's already been said.)  

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 29 Oct 2005 22:52:36 -0000

> because in general, you can't assume any secrets from the attacker,

No. The thing you're missing here---see the subject line---is that we
are talking about how to build key-derivation functions. When MD5 or
SHA-256 or an AES-based function is used to derive keys, there _is_ an
input kept secret from the attacker, namely a Diffie-Hellman g^xy.

The security of a key-derivation function is _not_ equivalent to
collision resistance. It is _not_ equivalent to the PRF property. It is
_not_ equivalent to universality, randomness extraction, etc. All of
these are interesting topics, but they are distractions from the topic
at hand, namely key derivation.

Certainly the cryptographic community has had some spectacular failures
to design collision-resistant hash functions. But secure key derivation
is a completely different problem. Statements such as ``many of our hash
functions aren't collision-resistant, so they aren't safe key-derivation
functions'' are obviously silly.

You're adding to the confusion if you use the ambiguous word ``secure''
and say things like ``secure hash functions are hard to design'' rather
than ``collision-resistant hash functions are hard to design.'' People
saying things like ``secure hash functions are hard to design, so we
can't use hash functions for key derivation'' don't seem to realize that
they're bouncing between two completely different security notions.