Re: [Cfrg] Internal collisions

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

David Jacobson writes:
> Why can't we just bless making M be the hash of the
> message and use some otherwise non-IUF signature schemes?

As Ilari mentioned, that's how three of the proposals are structured.
However, using a prehash in this way isn't satisfactory for people who
are concerned about the possibility of hash-function collisions; that's
why the same three proposals also offer collision-resilient options
where the prehashing is skipped.

Signing long messages always has one of the following bottlenecks,
depending on which proposal we're talking about:

   * H(M).
   * H(seed,M) and in parallel H(M,R).
   * H(seed,M) followed by H(R,M).

Speed evaluation:

   * H(M): Obviously best.

   * H(seed,M) and in parallel H(M,R): Two hash calls per block. Also a
     data-flow constraint, namely knowing the seed in advance.

   * H(seed,M) followed by H(R,M): Two hash calls per block. Also
     data-flow constraints, namely knowing the seed in advance and
     reading twice through the message---so a stateless deterministic
     IUF interface requires a variable-length buffer or a limited
     message length. (Ilari's proposal has an easily fixable bug here,
     reading three times through the message, as I mentioned briefly at
     the CFRG meeting.)

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.

What three proposals actually do is take the "H(seed,M) followed by
H(R,M)" approach for maximum security, optionally wrapped in the H(M)
prehashing approach for people who need maximum performance and aren't
worried about collisions. The other two proposals focus on the middle
option, which I see as an unhappy combination of close-to-worst speed
and close-to-worst security.

Dan Brown writes:
> If 2^256 is the best/expected number of steps for an internal
> collision on 256-bit wide pipe hash

Do 24 rounds of SHA-512 provide 2^128 times more security than 24 rounds
of SHA-256? Does MD5 have security level 2^64? This metric isn't useful.

>From a risk-assessment perspective, there's no difference between
generic attacks taking time 2^128 and generic attacks taking 2^256;
they're simply not going to happen. What matters are the _non-generic_
attacks, and those produce internal collisions by the same techniques as
external collisions.

> Quantitatively, if H proves to be weaker than expected, then replace
> the 2^256 steps above by 2^(256-w) steps for some relative weakness
> measure w.

I explained earlier that existing feasible collision attacks against 24
rounds of SHA-512 are IV-independent, so they break 24 rounds of, e.g.,
SHA-384(M,R). They don't break 24 rounds of SHA-512(R,M).

You're now suggesting that downgrading the competition from SHA-512(R,M)
to SHA-256(R,M) will produce a comparable level of "weakness". But if
this is true then where's the attack against 24 rounds of SHA-256(R,M)?

---Dan