Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)

David Wagner writes:
> You may recall that Dan Bernstein wrote:
>   How do we build PRFs? By hashing the key and the input.
  [ ... ]
> My response was that, if you want a PRF, Bernstein's scheme is a poor
> choice.

``Bernstein's scheme''? All I said was that we build ``PRFs'' by hashing
the key and the input. For example, AES_k(m) is a hash of (k,m).

In case you've forgotten the context here: We're talking about the
construction of key-derivation functions. _I_ didn't say that we want a
PRF; _Krawczyk_ said that we want a PRF. I quite explicitly _eliminated_
this PRF distraction by rewriting Krawczyk's function as a hash.

> What also seems relevant is that the recent results on hash functions
> cast doubt in my mind on the security of hashing when used for, say,
> pseudorandom functions.  Hash functions weren't (primarily) designed
> for that kind of purpose.

That depends on the hash function!

What you're trying to say, apparently, is that some hash functions were
designed purely for collision resistance. It's certainly true that we
see mixed results when those functions are reviewed for their merits as
stream ciphers. But some of them have held up. Meanwhile, other hash
functions were designed from the start to be useful for stream ciphers.
Four examples:

   (1) Finding collisions in the Chaum-van Heijt-Pfitzmann hash function
       provably requires finding a huge discrete log. The same hash
       function is useless as a stream cipher. (It's also very slow.)

   (2) MD5 has failed at its original goal of being collision-resistant,
       but it nevertheless seems to hash its input thoroughly enough to
       be usable for stream ciphers. Nobody has reported a successful
       distinguisher for the (fairly slow, roughly 40 cycles per byte)
       stream MD5(k,0),MD5(k,1),... when k is a secret uniform random
       256-bit key and 0,1,... are 256-bit nonces.

   (3) The Salsa20 hash function, like AES, was designed from the start
       to be secure when used as a stream cipher. It doesn't resist
       collisions; it doesn't even compress its input! There are several
       reasonable ways to use Salsa20 to build a collision-resistant
       variable-length-input hash function, but I wouldn't expect that
       to set speed records.

   (4) The Zobrist hash function and UMAC's hash function UHASH are
       useless as stream ciphers. They also don't resist collisions. Of
       course, they have other interesting properties.

Hashing is an extremely broad concept. For each application, perhaps a
particular hash function H is useful, and perhaps it isn't; one can't
tell without looking at the details of H.

Getting back to key derivation: There are many plausible ways to build a
safe key-derivation function. History shows a notable lack of success in
breaking key-derivation proposals, even wimpy MD5-based constructions.
Furthermore, one can easily afford to spend thousands of CPU cycles on
key derivation. On the other hand, especially in hardware, one often
can't afford to fritter away code space. So a sensible designer will
build a key-derivation function by grabbing any component that's already
in the system---AES, for example, or SHA-256---and reusing it.

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

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