Subject: Re: [Cfrg] Internal collisions

From: Bryan Ford <[email-masked]>
Date: Tue, 4 Aug 2015 11:00:33 +0200

Hi Dan,

> On Jul 31, 2015, at 6:36 PM, D. J. Bernstein <[email-masked]> wrote:
> 
> Security evaluation:
> 
>   * H(seed,M) followed by H(R,M): Collision-resilient. Serious defense
>     against the possibility of collisions in H.
> 
>   * H(seed,M) and in parallel H(M,R): _Not_ collision-resilient;
>     resilient only to external collisions, not internal collisions.
>     This is not much safer than simply using H(M).
> 
>   * H(M): Not collision-resilient.

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).

In particular, I’d like to hear your thoughts on the security properties of my earlier ‘edshake’ proposal (see http://www.ietf.org/mail-archive/web/cfrg/current/msg07112.html <http://www.ietf.org/mail-archive/web/cfrg/current/msg07112.html>).  It seems to have nice performance characteristics for both small and large messages, and intuitively seems to have nice internal collision-resistance properties due to the sponge design, but I’m not an expert on security analysis of symmetric ciphers.

Thanks
Bryan

---

From: "D. J. Bernstein" <[email-masked]>
Date: 4 Aug 2015 12:06:49 -0000

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