On Jul 17, 2014, at 6:44 AM, David Leon Gil <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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? >> > > >
_______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
