Subject: [Cfrg] Internal collisions

From: "D. J. Bernstein" <[email-masked]>
Date: 26 Jul 2015 19:43:06 -0000

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

---

From: Dan Brown <[email-masked]>
Date: Mon, 27 Jul 2015 15:48:16 +0000

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:[email-masked]] On Behalf Of D. J. Bernstein
> Sent: Sunday, July 26, 2015 3:43 PM
> To: [email-masked]
> Subject: [Cfrg] 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.
> 
you can
> break these hash functions inside H(M,R) signatures as follows:
> 
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.
> 
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
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
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.)
> 
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:
> 
> 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.
> 
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 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.
> 
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
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: David Jacobson <[email-masked]>
Date: Mon, 27 Jul 2015 10:49:34 -0700

On 7/27/15 8:48 AM, Dan Brown wrote:
> [ snip ]
[ snip ]

Why all this worry about IUF?  Industry is going to demand IUF so we 
have to provide it somehow.  Why can't we just bless making M be the 
hash of the message and use some otherwise non-IUF signature schemes?  I 
suspect that if we do that we need some way to prevent cross scheme 
forgeries.  Maybe we could have ASN.1 OIDs for the scheme and the names 
could be something like FOO and FOO_WITH_SHA512_PREHASH, etc and we 
could work the ASN.1 OID into the algorithm.  If we are worried about 
length extension attacks on the prehash, we could let M = 
length(message) || prehash(message).

This would get this issue of compatibility with IUF out of the debate 
about the security of the various proposals.

    --David Jacobson

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 27 Jul 2015 21:01:48 +0300

On Mon, Jul 27, 2015 at 10:49:34AM -0700, David Jacobson wrote:
> Why all this worry about IUF?  Industry is going to demand IUF so we have to
> provide it somehow.  Why can't we just bless making M be the hash of the
> message and use some otherwise non-IUF signature schemes? 

Well, three of the proposals do IUF exactly this way.

> I suspect that if we do that we need some way to prevent cross scheme
> forgeries. 

Well, two of the three have "hash firewalling" for exactly this. Note
that 'identity' is especially dangerous here.

> Maybe we
> could have ASN.1 OIDs for the scheme and the names could be something like
> FOO and FOO_WITH_SHA512_PREHASH, etc and we could work the ASN.1 OID into
> the algorithm. 

Well, my proposal does something like that. And the reason why I used ASN.1
OID is:
- Most hashes have those.
- You can virtually always just dump a static octet string.
- You never need to decode it.

(If either of the last two failed, using ASN.1 wouldn't be a good idea).

> If we are worried about length extension attacks on the
> prehash, we could let M = length(message) || prehash(message).

I don't think length extension is a threat, since it just lets one
calculate hashes with unknown prefixes, and those hashes are still
different (if they weren't, the hash would be broken anyway).

-Ilari

---

From: Dan Brown <[email-masked]>
Date: Mon, 27 Jul 2015 18:38:58 +0000

> From: David Jacobson [mailto:[email-masked]]
> 
> Why all this worry about IUF?  

[DB] I wouldn't call it worry, but anyway.

First, see your own answer about the industry demand.  

Second, CFRG already had a poll on IUF. But, I'm not quite sure how to
interpret the results: can EC signatures provide a non-IUF mode?

> Industry is going to demand IUF so we have to
> message and use some otherwise non-IUF signature schemes?  I suspect that
if

[DB] There are some security concerns are about how good the prehash is. 

In particular, the prehashing proposals try to _specify a prehash_ rather
than just bless a using from any old hash to prehash the message.   

The EdDSA proposal goes further: it recommends that the prehash be the
identity, because it provides collision-resilience.  Are you against that
recommendation?

The ECDSA_CFRG proposal computes H(M||R), which is 
(i) close in cost to prehashing M,  
(ii) mandates using the one common wide-pipe hash, in a single call for the
verifier,
(iii) in the ideal random oracle model provides some theoretical security.
That's not so different from pre-hashing, is it?

If we are really confident in wide-pipe hashes, then the random oracle in
(iii) is quite plausible.

The prehashed prefix proposals H(R||H(M)) can _also_ claim the random oracle
model benefits (iii) above, since for sequential hashes H(M||R) is usually
quite similar to H(H(M)||R).

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 30 Jul 2015 11:12:23 +0000

Hi Dan,

On 27/07/2015 19:38, "Cfrg on behalf of Dan Brown" <[email-masked]

>interpret the results: can EC signatures provide a non-IUF mode?

The decision was to go with IUF only. See my message from June 19th, here:

http://www.ietf.org/mail-archive/web/cfrg/current/msg06964.html

Cheers

Kenny

---

From: "D. J. Bernstein" <[email-masked]>
Date: 31 Jul 2015 16:36:36 -0000

David Jacobson writes:
> Why can't we just bless making M be the hash of the

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

---

From: Dan Brown <[email-masked]>
Date: Fri, 31 Jul 2015 20:08:49 +0000

> From: D. J. Bernstein
>      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.

>      against the possibility of collisions in H.

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

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