Re: [Cfrg] Internal collisions

["D. J. Bernstein" <[e-mail]>]

http://ed25519.cr.yp.to/cfrg/signatures.py now includes 'ford'.

Bryan Ford writes:
> I would like to hear your thoughts on how these security considerations change
> when H is not a traditional hash but a sponge-based hash, where the internal
> “pipe” state consists of both the ‘rate’ bits and the always-internal
> ‘capacity’ bits (say, chosen to be twice the security parameter).

The big picture is that H(M,R) is never collision-resilient. In more
detail:

   * Sponge hashes and other wide-pipe hashes: H(M,R) is resilient only
     to _external_ collisions, not to _internal_ collisions.

   * Traditional hashes: There's no meaningful difference between
     internal collisions and external collisions. (There's a formal
     difference: when the hash-function state includes the length, a
     full internal collision requires messages of the same length. This
     isn't a meaningful difference: cryptanalysis naturally finds
     collisions of the same length, and attackers can usually do a ton
     of damage without changing the message length.)

I'm not saying that there's a large risk of collisions in either SHA-2
or SHA-3. I'm saying that people who are worried about this risk and
want to mitigate it should not accept H(M,R) as a substitute for H(R,M);
H(R,M) is a serious defense, while H(M,R) is only marginally safer than
the fast H(M) options.

I commented at the Prague meeting that security issues will take more
time to understand than implementation issues. H(M,R) is one of several
examples; Dan Brown's suggestion (basically, using H(M,R)/f(R) as a
hash) is another example. I understand that the chairs would like to
select something quickly but I'm concerned about the possibility that
rushing will compromise security.

---Dan