Re: [Cfrg] Internal collisions

[Dan Brown <[e-mail]>]

Hi Dan,

I agree with your points about internal collisions. 

But, just to be clear: you are _not_ saying that for a wide-pipe hash H of
output length 256 bits and internal state (width) 512 bits (e.g. in
SHA-512/256), the best known (or expected) internal collision attack takes
far fewer than 2^256 steps (let alone actually much closer to 2^128 steps),
right?  

Otherwise, I've had a large misunderstanding of the wide-pipe promise.

If 2^256 is the best/expected number of steps for an internal collision on
256-bit wide pipe hash, then for sake of comparison, consider H(R,M)
signatures, but with a narrow-pipe H (to isolate the benefit of prefixing
from the benefit of wide pipes).  In that case, an adversary should take
2^256 steps to find M' such that H(R,M') = H(R,M), and thus a forgery.

Seen this way, wide-pipe H and prefixing (alone, i.e. with a narrow-pipe H)
provide very similar level of protection, _both_ requiring a 2^256 step
H-attack just to get a forgery of M' by asking the signer to sign M.  This
is hugely more than the 2^128 steps to solve the log to find the signing key
from the verification key.

But maybe your arguments favor prefixing: we really expect to never have any
weakness in prefixed hashes, but we do expect an eventual weakness in
wide-pipe internal collisions.  Is that right?  Is that the implication I
the challenge at the end of your email?  If so, then I wonder how much of
that expectation is because people have just not tried to attack prefixing.

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.
As long as w < 128, the signatures should be okay, i.e. using a wide-pipe H
or a prefixed narrow-pipe.  A relative weakness w = 64 would serve as one
early warning sign (a canary).  Another early warning sign would be
reduced-round hashes, and MD5.  

The EdDSA proposal uses _both_ wide-pipe H and prefix H(R,M), so it has
_redundant_ protections. Generally, I strongly _agree_ with redundant
protections, provided they are inexpensive.    If these protections
accumulate, then even better!  

Unfortunately, prefixing means non-IUF.

Side note: I think you've some good points against IUF-streamed signature
verification, but what about IUF-streamed signing?  Does not the signer wish
to avoid creating signatures on a partial stream, even signatures marked as
partial, on a stream until the entire stream is seen?

The ECDSA_CFRG proposal uses a wide-pipe H, but with a suffix H(M,R) to
obtain IUF.  If CFRG is also going to recommend non-IUF options, (which I
thought was option 3 in the poll) then in non-IUF mode, ECDSA_CFRG should
instead use H(R,M), more like PureEdDSA.  (Perhaps H(R,M,R) would help, but
likely not.)

Anyway, in a pure IUF mode, the wide-pipe H(M,R) signature in ECDSA_CFRG
provides the following security protections:
- wide-pipe protects against internal collisions,
- H(M,R) protects against external collisions (as you explain).

I think you've argued that external collisions are not the real threat here,
so the real protection ECDSA_CFRG is from the wide-pipe.  

On terminology, if one defined "collision-resilience" to mean
"internal-collision-resilience", then the wide-pipe does not provide this
"collision-resilience" but rather the simpler concept of
"collision-resistance".  Taking collision-resilience to mean
"external-collision-resilience", then H(M,R) signatures provides
"collision-resilience".

One could also argue that the H(M,R) in ECDSA_CFRG provides no substantial
benefit over wide-pipe ECDSA, because the threat of external collisions is
not very substantial.  But: 

- H(M,R) with H a random oracle, essentially makes ECDSA_CFRG a kind of
Pointcheval-Stern signature, with the random oracle proof that many
academics value (e.g. Koblitz and Menezes).

So, there seems to some benefit to including R in H in ElGamal signatures,
and various people have proposed it over the years. 

Best regards,

Dan


> -----Original Message-----
> From: Cfrg [mailto:[e-mail]] On Behalf Of D. J. Bernstein
> Sent: Sunday, July 26, 2015 3:43 PM
> To: [e-mail]
> Subject: [Cfrg] Internal collisions
> 
> This message elaborates on Tanja's comment about "internal collisions"
> at the CFRG meeting. The quick summary is that Schnorr's H(R,M) adds real
> protection against the possibility of collisions in H, while the
alternative H(M,R)
> doesn't, even when H is a wide-pipe hash function.
> 
> As a concrete example, take H to be 24 rounds of SHA-512/256 or SHA-384.
> Both of these functions have
> 
>    * outputs that are too big for brute-force collision attacks, and
>    * even wider pipes.
> 
> However, internally these functions process messages the same way as
> SHA-512 (starting from different IVs and truncating the output), and so
you can
> break these hash functions inside H(M,R) signatures as follows:
> 
>    * Start from 2008 Sanadhya--Sarkar, which showed how to very quickly
>      find distinct 1024-bit blocks B,B' that produce colliding 512-bit
>      states after 24 rounds starting from the initial SHA-512 state.
> 
>    * Notice that the Sanadhya--Sarkar method also works for (e.g.) the
>      initial SHA-384 state.
> 
>      I'm not saying that these particular blocks B,B' have a noticeable
>      chance of producing collisions for other starting states. This
>      would be an impressive break of the SHA-512 data flow, a
>      "differential attack without message modification", a technique
>      that has trouble breaking MD5.
> 
>      What I'm saying is that, _given_ any starting state h (e.g., the
>      initial SHA-384 state or the initial SHA-512/256 state), the method
>      _computes_ distinct 1024-bit blocks B,B' that produce colliding
>      512-bit states after 24 rounds starting from h.
> 
>    * Notice that 24 rounds of SHA-384 now collide on any inputs of the
>      form (B,X) and (B',X), since the states after B and B' are the
>      same---this is what's called an "internal collision".
> 
>    * Find an X such that (B,X) is an innocent message that the signer is
>      willing to sign while (B',X) is a dangerous message. Obtain the
>      signer's signature (R,S) on the innocent message (B,X).
> 
>    * Forge the message (B',X) with the same signature (R,S). This is a
>      valid signature since H(B',X,R) = H(B,X,R).
> 
> What went wrong here is that H(M,R) isn't resilient to _internal_
collisions in H.
> It wasn't useful to watch for collisions in H as a canary for potential
security
> problems in H(M,R)---the victim died a moment after the canary did.
> 
> H(M,R) for wide-pipe H has the weak property of being resilient to mere
> _output_ collisions---for example, if someone manages to find an H
collision by
> brute force, then there's no reason to think that appending R to the
inputs will
> also produce a collision---but brute force isn't the real threat against
any
> reasonably large hash output. The way that cryptanalysts have found
collisions
> much more quickly than brute force
> 
>    * in MD5, and
>    * in 76 out of 80 steps of the SHA-1 compression function, and
>    * in 38 out of 64 steps of the SHA-256 compression function, and
>    * in 4 out of 24 rounds of SHA3-256,
> 
> is by finding ways that small input differences can stay on a path of
small
> differences through the entire hash computation---it's hard to imagine how
> differences would have a noticeable chance of disappearing otherwise!
Output
> truncation has very little effect on this type of
> attack: it can remove a few conditions from the end of the computation,
but
> most of the attack cost comes from many more conditions needed to control
> diffusion in many earlier rounds of the computation.
> 
> (Probably even more than 24 rounds of SHA-384 etc. are feasible to break.
> There has been considerable progress since 2008, and the latest collision
> attacks break 38 out of 80 rounds of the SHA-512 compression function,
> although breaking 38 rounds of the SHA-512 _hash_ function will require
> hooking the SHA-512 initial state to the two initial states used in this
> compression-function collision.)
> 
> For comparison, what happens to this attack if H(M,R) is replaced by
Schnorr's
> H(R,M)? This time R immediately affects the hash processing, and this
change
> in data flow creates serious obstacles for the attacker.
> Here's what happens:
> 
>    * _Given_ R, the attacker computes two extensions (R,M) and (R,M')
>      that produce an internal collision.
> 
>    * But wait---why is this collision useful? To forge M' as a
>      substitute for M, the attacker needs a signature involving H(R,M).
> 
>    * So the attacker asks the signer to sign M.
> 
>    * The signer now generates a signature of M---but this signature
>      involves a new R' that the attacker has never seen before.
> 
> There's no reason to think that H(R',M) and H(R',M') will collide when R'
is
> chosen randomly. Asking for this to happen is asking for something much
> stronger than a collision---as above, this would be an impressive break of
the
> SHA-512 data flow. The attacker really wants to see R before generating M
and
> M', but the signer won't generate R without seeing M.
> 
> So the attacker starts by computing just one message M, then sees R from
the
> signer, and then tries to compute a second message M' with H(R,M') =
H(R,M).
> The usual techniques for trying to find preimages much more quickly than
> brute force are again to take M' close to M and hope that the differences
stay
> under control. However, the fact that M can't change during the second
> computation makes this preimage search much more difficult than a
collision
> search:
> 
>    * The attacker can't simply use the best difference M'-M: if this M'
>      doesn't work, then the attacker has to move on to the second-best
>      difference, then the third-best, etc. In collision attacks the
>      attacker was free to keep trying the best difference with many
>      choices of M.
> 
>    * The attacker can't apply "message modification", working backwards
>      from as many of the path conditions as possible to a subset of M
>      that's feasible to enumerate.
> 
> The attacker can of course try to modify M during the first computation so
> that the path conditions are more likely to be satisfied, but this has to
be done
> in a way that gets past the obstacle of R being subsequently randomized.
> 
> In short, the fact that H(R,M) is resilient to _internal_ collisions
reflects a real
> gap in difficulty between finding H collisions and breaking H(R,M). Anyone
who
> disputes this should be able to demonstrate feasible attacks on H(R,M)
using
> MD5, using 24 rounds of SHA-384, and using 4 rounds of SHA3-256, all of
> which are broken for H(M,R).
> 
> ---Dan
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg