Re: [Cfrg] Internal collisions

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: D. J. Bernstein
>      reading twice through the message---so a stateless deterministic
>      IUF interface requires a variable-length buffer or a limited
>      message length. 

[DB] If CFRG will support message-length buffered IUF signers that can fall
back to pre-hashing whenever needed, then, as I said before, I would amend
my proposal to make it similar to the other proposals. I.e., to use H(R,M)
falling back to H(M,R), or just to pre-hashing H(R,H(M)) for alignment with
the other proposals.  

The reason my proposal has H(M,R) is because I interpreted the various CFRG
polls to _require_:
- IUF signer (i.e. message streaming/buffering),
- fixed-length buffer (for signer and verifier), i.e. a buffer shorter than
the message length,
- stateless signer, 
- deterministic signer.
The H(R,M) proposals are _incompatible_ with this interpretation.

>    * H(seed,M) followed by H(R,M): Collision-resilient. Serious defense
>      against the possibility of collisions in H.
> 

[DB] Yes, but incompatible with CFRG requirements as I understand them.

>    * H(seed,M) and in parallel H(M,R): _Not_ collision-resilient;
>      resilient only to external collisions, not internal collisions.

[DB] You didn't mention that my proposal requires a wide-pipe hash. 

Wide pipe hashes are a _serious_ defense against the possibility of
collisions.  

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. 


>      This is not much safer than simply using H(M).

[DB] In my ECDSA_CFRG proposal, there are two security benefits of H(M,R)
over H(M):
- Pointcheval-Stern security analysis in the random oracle model
- External collision resilience.

Oops, in Watson Ladd's proposal: H(M,R) has no known feasible attacks, but
changing this to H(M) makes it forgeable: the verification equation would
only have R appearing once, so you can just solve for R. 

> 
>    * H(M): Not collision-resilient.

[DB] As I interpret the CFRG requirements, the H(R,M) proposals will be
forced to pre-hash and fall into this situation: they are _not_
collision-resilient.

Ok, the H(M,R) proposal may only be "slightly safer" than H(M) (ignoring
Watson's proposal), especially if you doubt the random oracle like promises
of the SHA3 competition.  So, maybe this slight safety gain does not warrant
the dual hashing of H(M,R).  

If H(M,R) signers are just too slow, then either pre-hash, or if desperate
for collision-resilience, secretly maintain a stateful PRG and feed its
output into the PRF input.  If you're worried CFRG will find out, then try
to ensure some message control that ensures you never sign the same message
twice.

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

[DB] The Wikipedia page for MD5 mentions a 2^24 collision attack, which is
2^(64-40), so MD5 can be viewed as 2^40 times weaker than a generic hash of
the same size.  Alternatively, this is 2^(64  * 3/8), so there MD5 has only
3/8 of the "bits" of collision security that a generic hash would have.

In a naïve risk assessment, I would attempt to extrapolate along these
lines, estimating collision resistance of SHA-X for X=256 or X=512 to be
2^((X/2)-w)  or 2^((X/2) * v), on the basis that SHA-256 and SHA-512 have
similar designs and thus similar values of w and v, and probably somewhat
better than the corresponding values of MD5.   This approach yields an
assessment that SHA-512 is much safer, and well beyond feasible.

But perhaps I did not fully comprehend your reduced-round examples.  Sorry.
Maybe a better risk assessment of  SHA-512's collision resistance is the
same as SHA-256.   Is that what the reduced-round attacks are indicating: no
difference between SHA-512 and SHA-256? What about for SHA-3?

If the SHA-2 designs are such that reduced-round attacks indicate that
SHA-512 larger's state has no benefit, then I'd worry about their design
considerably.  In that case, I'd probably amend my proposal to require
SHA-3.