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

[Michael Hamburg]

On Jul 17, 2014, at 6:44 AM, David Leon Gil <coruus at gmail.com> wrote:

> And, just to make sure I'm understanding this right:
> 
> Assume a 32B protokey and Shake256 as the hash function. The best generic attacks on the signature scheme:
> 
> - Time: 2^256
>   - Distinguish Goldilock keys from random elements of q448
>   - Recover protokeys from public keys or signature nonces
> - Time: 2^256
>   - Find a pair of messages such that S(m0) == S(m1'), such that,
>     if m0 and m1 are messages chosen to satisfy properties P0 and P1,
>     m1' == m1||p1, where p1 is a block of 'rate' bytes indistinguishable from       random bytes.
> - Time: ~2^224
>   - Solve discrete logarithm problem in q448

This looks right, though I don’t know what properties P0 and P1 are.

> So I think that I'm fairly happy with Shake256 (but obviously wouldn't be with Shake128), even if the scheme doesn't provide additional collision resistance.
> 
> (SHA3-224 is standardized, but there's no equivalent Shake instance. Since signatures don't need more than 56 bytes of output, it would be fine to use that instead of Shake256.)
> 
> ----
> 
> There's a rather speculative potential benefit to deriving nonceg as
> 
>      H(privatekey || message)
> 
> which is that -- if a non-generic attack on Shake256 can produce collisions with cost <<< 2^224 -- you could then prove that you *didn't* sign one half of a colliding message by revealing the private key.
> 
> The probability of such an attack existing seems too low for this dubious benefit.

I think this is pretty speculative, since you can always make an exception to your nonce computation for that one risky message.

Also, if you compute the challenge as H(nonceg || pubkey || message) or similar, then a collision attack isn’t enough.  This is a nice property even though the generic collision attack is slower than DL.

> -----
> 
> The advantage of doing everything message-first I forgot to mention: Suppose that you put private keys in a crypto coprocessor of some sort (or on another server). You can sign messages of arbitrary length by only transmitting 200 bytes of data (the sponge state after absorbing the message).

Hm, that’s a good point.

— Mike

> On Wed, Jul 16, 2014 at 10:07 PM, David Leon Gil <coruus at gmail.com> wrote:
> Thank you! I stand corrected (and also saved the trouble of writing a note retracting my silly argument).
> 
> (And thank you for the links.)
> 
> Best,
> 
> David
> —
> Sent using alpine: an Alternatively Licensed Program for Internet News and Email
> 
> 
> On Wed, Jul 16, 2014 at 8:57 PM, Michael Hamburg <mike at shiftleft.org> wrote:
> 
> 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/20140717/47fda4ea/attachment.html>