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
