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

[David Leon Gil]

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

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.

-----

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


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/0a8aec20/attachment.html>