Parallel collision search with cryptanalytic applications (Q1284011)

It is known that a broad range of cryptanalytic problems can be reduced to the problem of finding two distinct inputs \(a\) and \(b\) to a function \(f\) such that \(f(a) = f(b)\). Thus, \textit{collision search} clearly belong to a set of important cryptanalytic tools. Unfortunately, the most efficient (known) techniques for finding collisions cannot be directly parallelized efficiently. In the paper a technique for efficient parallelization of collision search is presented. First, previous methods for collision search are reviewed and their inefficient direct parallelization discussed. Particularly, the generalized \textit{rho-method} is discussed in some details. Unfortunately, the original Pollard's rho-method is inherently serial in nature and direct approaches to its parallelization do not yield linear speedup. Then, the new technique -- the general parallel collision search algorithm is presented. Two cases are considered -- finding only a small number of (random) collisions, and finding a large number of collisions. Run-time analysis of both cases is given as well. The new technique is then applied to computing discrete logarithms in cyclic groups, finding hash function collisions and to general meet-in-the-middle attack. To illustrate the use of parallel collision search for practical cryptanalytic problems, the authors also considered designs of custom machines. They have shown that within the 10 million dollars limit to build a custom machine one can find elliptic curve logarithms in \(GF(2^155)\) in expected time 32 days, to find MD5 collisions in expected time 21 days, and to perform known-plaintext attack on double-DES in expected time 4 years, i.e. about four orders of magnitude faster than the conventional approach. Based on the new attack one can conclude that double-DES offers only about 17 bits more security than single-DES.