[curves] Ed448-Goldilocks (sponges and collision resistance)

[Michael Hamburg]

Top replying!  I believe that the birthday attack still applies.

The state is divided into two pieces, of sizes $rate and $capacity = $statesize - $rate.  The message blocks are xor’d into the $rate-sized piece, but the $capacity-sized piece is not changed.

If the attacker can find two messages mA and mB which cause a collision on the $capacity-sized piece, he can set the message blocks for the next round to set the $rate-sized pieces of stateA and stateB to anything he wants (in particular, to the same thing), thereby causing a collision on the entire state.

This birthday attack requires 2^($capacity/2) work and storage.  There’s probably also a rho attack which requires less storage.

So postfixing with the nonce or key doesn’t help.

Cheers,
— Mike

On Jul 16, 2014, at 5:46 PM, David Leon Gil <coruus at gmail.com> wrote:

> > Certainly not if you hash the message first.  That drops security to 128
> > bits vs collision attacks.  Even if those attacks aren’t realistic, that’s
> > pretty far below the design security of the system.
> The use of sponge functions in keyed modes
> 
> So, as I understand it, this isn't true for sponge functions: a collision in message hashs does not imply a collision in nonce-postfixed message hashs.
> 
> Here's why (very informally):
> 
> (Apologies for the detail, but I figure that it might be useful to users on the list less familiar with this area.)
> 
> Background: Merkle-Damgard
> 
> Merkle-Damgard. Each update step consumes a message block and outputs an IV for the next message block.
> 
> Thus, if H(m) == H(n), then H(m || g) == H(n || g). (So a message collision implies a collision in nonce-postfixed messages if len(m) == len(n).)
> 
> So, this is why, if I did this reordering with SHA2-512, the resulting signature scheme would not be collision-resistant.
> 
> Sponge functions. Just to recall the definitions, in Python-like pseudocode for clarity (and omitting the padding rule),
> 
> class Sponge(object):
>   def __init__(permutation, rate):
>     state = zeros(permutation.blocksize)
>     capacity = permutation.blocksize - rate
>     position = 0
>   def absorb(bytes):
>     i = 0
>     while i < len(bytes):
>       if position == (rate - 1):
>          permutation(state)
>          position = 0
>       state[position] ^= bytes[i]
>       i++; position++
>   def squeeze(length):
>     i = 0
>     out = ''
>     while i < length:
>       if position == (rate - 1):
>         permutation(state)
>         position = 0
>       i++; out += state[position]
>     return out
> So, note what's happening here: Each block of the message is absorbed into at most rate bytes of the sponge. Every time rate bytes is filled, the permutation is applied. When the sponge is squeezed, at least capacity bytes of the sponge's state is hidden.
> 
> Sponge functions
> 
> Hash collisions
> 
> Let's define a hash collision in the usual way; two messages for which the hash output is the same value. So, here's how a sponge derives a hash:
> 
> msponge = Sponge(keccak, 200 - 64)           # shake128
> msponge.absorb(message)
> mhash = sponge.squeeze(64)
> (And so, in this case, the resulting hash has 256-bits of collision resistance.)
> 
> So, if what I did with the sponge was this,
> 
> csponge = challenge_sponge = Sponge(keccak, 200 - 64)
> csponge.absorb(mhash)
> csponge.absorb(gnonce)
> challenge = sponge.squeeze(64)
> a message collision would, just as in the MD-case, imply a challenge collision.
> 
> (Call the colliding message mess.)
> 
> Collision-resistant signatures
> 
> But here's what's happening in the code (simplified to omit the pubkey and DS):
> 
> sponge = Sponge(keccak, 200 - 64)  # shake256
> sponge.absorb(message)
> sponge.absorb(gnonce)
> challenge = sponge.squeeze(64)
> (The sponge retains its full 200 byte state between absorb calls.)
> 
> If
> 
> (sponge.absorb(message).absorb(gnonce)
>  == sponge.absorb(mess).absorb(gnonce))
> then the states must collide, i.e.,
> 
> sponge.absorb(message).state == sponge.absorb(mess).state
> But the state is 200 bytes; the probability of a message that produces a hash collision also producing a state collision is extremely small.
> 
> (There are obviously generic attacks with cost 2^512 in this case that find a colliding squeezed output.)
> 
> So this is essentially the argument for Shake256 providing 2^512 security strength in this mode of operation; and for Shake128 providing 2^256 security strength.
> 
> I, too, am somewhat conservative: Shake256 is fast enough for most applications. (It is, I believe, still somewhat faster than SHA2-512.) So, happy with that.
> 
> And I'll follow up with some citations to the security proofs that are less-handwavy, but more mathemetical in the next couple of days.
> 
> So...does this make sense?
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140716/41b81155/attachment.html>