Parallel Collision Search with Cryptanalytic Applications |
| |
Authors: | Paul C van Oorschot Michael J Wiener |
| |
Affiliation: | (1) Entrust Technologies, 750 Heron Road, Ottawa, Ontario, Canada K1V 1A7, CA |
| |
Abstract: | A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is
presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions.
General constructions are given showing how to adapt the technique to finding discrete logarithms in cyclic groups, finding
meaningful collisions in hash functions, and performing meet-in-the-middle attacks such as a known-plaintext attack on double
encryption. The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known
to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic
curve cryptosystems; hash functions such as MD5, RIPEMD, SHA-1, MDC-2, and MDC-4; and double encryption and three-key triple
encryption. The practical significance of the technique is illustrated by giving the design for three $10 million custom machines
which could be built with current technology: one finds elliptic curve logarithms in GF(2155) thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected
time 21 days, and the last recovers a double-DES key from two known plaintexts in expected time 4 years, which is four orders
of magnitude faster than the conventional meet-in-the-middle attack on double-DES. Based on this attack, double-DES offers
only 17 more bits of security than single-DES.
Received 21 December 1995 and revised 24 September 1996 |
| |
Keywords: | , Parallel collision search, Cryptanalysis, Discrete logarithm, Hash collision, Meet-in-the-middle attack, Double,,,,,encryption, Elliptic curves, |
本文献已被 SpringerLink 等数据库收录! |
|