A "multicollision attack" is an attack that can find many collisions for a hash function, in only logarithmically greater time than a single collision. The following paper:
Antoine Joux, "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions" <http://web.cecs.pdx.edu/~teshrim/spring06/papers/general-attacks/multi-joux.pdf> describes how to do this for iterated hashes, including Merkle-Damgård hashes such as SHA-* (the attack is quite simple and easy to understand). [Some improvements are described in <http://www.131002.net/data/papers/Aum08a.pdf>, although the newest attack described in that paper isn't applicable.] The Elk Point protocol uses essentially the following construction: R = hash_r(V, K1) T = hash_t(encrypt[R](K1), V) which is intended to be as secure (for collision, preimage, and second-preimage resistance) as a single hash on V and K1 with output size r+t bits. Here's the problem: suppose that hash_r is an iterated hash with an r-bit chaining value. Then Joux's paper shows how to perform a multicollision attack on hash_r, finding 2^(t/2) collisions, with only approximately (2^(r/2)).t/2 work. Then it is likely that two of those 2^(t/2) collisions will also collide in T (note that this doesn't depend at all on how T is computed, just that it is some t-bit function of R, K1 and V). So the overall cost of a collision attack on the combined hash is only (2^(r/2)).t/2, not 2^((r+t)/2). For example, if r = 128 and t = 128, the cost of a collision attack is only 2^64 * 64 = 2^70, rather than the expected 2^128. However, note that this attack depends completely on the fact that hash_r uses an r-bit chaining value. If hash_r is actually a truncation of a hash with a z-bit chaining value, then the attack requires 2^(z/2) work. More precisely, it requires whatever work is needed for a collision attack on the untruncated hash, provided that the attack works with sufficient probability for an arbitrary chaining value. Therefore, to avoid the attack we only need to ensure that z >= r+t (preferably with some margin, in case there is a better attack on the untruncated hash than brute force). If hash_r is SHA-256 or SHA-512 truncated to r bits, for example, then this multicollision attack is not a weak point, as long as untruncated SHA-256 or SHA-512 has no collision attack easier than 2^((r+t))/2). The preimage attack of section 4.2 of Joux's paper also applies. Again, it is foiled completely by the larger chaining value when using a truncated hash. (Note that hash_t was already defined as a truncated hash.) As a belt-and-suspenders defense, it may be a good idea to ensure that the input to the hash fits in a single block. This would completely eliminate the possibility of attacks that rely on the Merkle-Damgård structure. The maximum whole number of bytes that will fit in one SHA-512 block (taking into account padding) is 111 bytes. If KC_verify is an ECDSA public key then the input will fit, but non-elliptic-curve keys would not. I will include an intermediate hash in the next version of the protocol, so that there is no limitation on the public key size. Incidentally, this actually makes me a little more confident in the security of the protocol. Being able to construct a longer hash from a short one this easily, seemed a bit too much like getting something for nothing (if it were so easy to construct long hashes from short ones, why are no existing hashes built that way?) When using truncated hashes for hash_r and hash_t, OTOH, we are not attempting to get any greater collision or preimage resistance than the hash we started with. I have added a note about this attack to <http://allmydata.org/trac/tahoe/wiki/NewCaps/WhatCouldGoWrong>. -- David-Sarah Hopwood ⚥ http://davidsarah.livejournal.com _______________________________________________ tahoe-dev mailing list [email protected] http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
