Abstract
Current techniques for collision search with feasible memory requirements
involve pseudo-random walks through some space where one must wait for the
result of the current step before the next step can begin. These techniques are
serial in nature, and direct parallelization is inefficient. We present a
simple new method of parallelization collisions that greatly extends the reach
of practical attacks. The new method is illustrated with applications to hash
functions and discrete logarithms in cyclic groups. In the case of hash
functions, we begin with two messages; the first is a message that we want
our target to digitally sign, and the second is a message that the target is
willing to sign. Using collisions search adapted for hashing collisions, one
can find slightly altered versions of these messages such that the two new
messages give the same hash result. As a particular example, a $10 million
custom machine for applying parallel collision search to the MD5 has function
could complete an attack with an expected run time of 24 days. This machine
would be specific to MD5, but could be used for any pair of messages. For
discrete logarithms in cyclic groups, ideas from Pollard's rho and lambda
methods for index computation are combined to allow efficient parallel
implementation using the new method. As a concrete example, we consider
an elliptic curve cryptosystem over GF(2^155) with the order of the curve
having largest prime factor of approximate size 10^36. A $10 million machine
custom built for this finite field could compute a discrete logarithm with an
expected run time of 36 days.
