[tahoe-dev] Avoiding multicollision attacks against Elk Point

[David-Sarah Hopwood]

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