Re: [Cfrg] Internal collisions

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

Dan Brown writes:
> For consistency, if CFRG views prefixed wide-pipe hashes as a serious
> general-purpose PRF construct, thereby obviating the need for HMAC's
> extension-resilience, then it is not much of stretch to say that a
> wide-pipe hash obviates the need for H(R,M)'s collision-resilience.

I have no idea why you call this "consistency"; it doesn't match what
the cryptanalytic literature actually says about the security levels of
these constructions.

As a concrete example, 24 steps are broken in the SHA-384(M,R) construct
that you're using. What matters here is that the attacker knows internal
collisions.

It is far more difficult to break 24 steps of SHA-384(R,M), or 24 steps
of SHA-512(R,M). I explained in an earlier message why the randomization
is a huge obstruction for state-of-the-art collision-finding techniques.

For similar reasons, it is far more difficult to break 24 steps of
reduced SHA-512(seed,M) as a PRF, never mind the fact that in this
context the attacker doesn't have direct access to the output.

> Is that what the reduced-round attacks are indicating: no
> difference between SHA-512 and SHA-256? What about for SHA-3?

SHA-256 and SHA-512 are broken for essentially the same number of steps,
in essentially the same way. For SHA-3, the very different amounts of
truncation in SHA3-256 and SHA3-512 produce a gap of 1 or 2 rounds (out
of 24), depending on which attack strategy you look at.

> Oops, in Watson Ladd's proposal: H(M,R) has no known feasible attacks,
> but changing this to H(M) makes it forgeable

Please retract this statement.

I clearly specified the three possibilities here as the long-message
bottlenecks in the existing proposals. The proposals that have H(M) as a
bottleneck are of course using R in a subsequent (non-bottleneck) stage
of the signing process.

You are instead referring to the absurd idea of throwing R away. This is
not what any of the proposals do, and bringing it up isn't helpful for
the discussion. Also, please retract your false suggestion that the
proposals vary in the applicability of Pointcheval--Stern.

---Dan