Parallel collision search with application to hash functions and discrete logarithms

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 parallelizing collision searches 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 collision 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 hash 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(2155) with the order of the curve having largest prime factor of approximate size 1036. A $10 million machine custom built for this finite field could compute a discrete logarithm with an expected run time of 36 days.

REFERENCES

• 1: G.B. Agnew, R.C. Mullin, and S.A. Vanstone. "An implementation of elliptic curve cryptosystems over F2155", IEEE J. Selected Areas in Communications, vol. 11, no. 5 (June 1993), pp. 804-813.
• 2: G.B. Agnew, R.C. Mullin, and S.A. Vanstone. "On the Development of a Fast Elliptic Curve Cryptosystem", Lecture Notes in Computer Science 658: Advances in Cryptology- Eurocrypt '92 Proceedings, Springer- Verlag, pp. 482-487.
• 3: Eric Bach, Toward a theory of Pollard's rho method, Information and Computation, v.90 n.2, p.139-155, Feb. 1991 [doi>10.1016/0890-5401(91)90001-I]
• 4: Bell-Northern Research, Internal study of MD5 Silicon Implementation, 1994.
• 5: R. P. Brent, Parallel algorithms for integer factorisation, Number theory and cryptography, Cambridge University Press, New York, NY, 1991
• 6: Keith W. Campbell , Michael J. Wiener, DES is not a Group, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.512-520, August 16-20, 1992
• 7: "Data Encryption Standard", National Bureau of Standards (U.S.), Federal Information Processing Standards Publication (FIPS PUB) 46, National Technical Information Service, Springfield VA, 1977.
• 8: Brandon Dixon , Arjen K. Lenstra, Factoring integers using SIMD sieves, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.28-39, January 1994, Lofthus, Norway
• 9: Roger A. Golliver , Arjen K. Lenstra , Kevin S. McCurley, Lattice sieving and trial division, Proceedings of the First International Symposium on Algorithmic Number Theory, p.18-27, May 06-09, 1994
• 10: Philippe Flajolet , Andrew M. Odlyzko, Random mapping statistics, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.329-354, November 1990, Houthalen, Belgium
• 11: R. Heiman. "A note on discrete logarithms with special structure". Lecture Notes in Computer Science 658: Advances in Cryptology- E, urocrypt '92, Springer-Verlag, pp. 454-457.
• 12: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 13: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 14: A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard, "The Factorization of the ninth Fermat Number", Math. Comp. vol. 61 (1993), pp. 319-349.
• 15: Arjen K. Lenstra , Mark S. Manasse, Factoring by electronic mail, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.355-371, November 1990, Houthalen, Belgium
• 16: K.S. McCurley. "The discrete logarithm problem", pp. 49-74 in Cryptology and Computational Number Theory, Proc. Symp. Applied Math., vol. 42 (1990), American Math. Society.
• 17: K. Nishimura , M. Sibuya, Probability to meet in the middle, Journal of Cryptology, v.2 n.1, p.13-22, 1990 [doi>10.1007/BF02252867]
• 18: S.C. Pohlig and M.E. Hellman. "An improved algorithm for computing discrete logarithms over GF(p) and its cryptographic significance", IEEE-IT, vol. 24 (1978), pp. 106-110.
• 19: J.M. Pollard, "A Monte Carlo method for factorization". BIT, vol. 15 (1975), pp. 331-334.
• 20: J.M. Pollard, "Monte Carlo Methods for Index Computation (mod p)", Math.Comp. vol. 32, no. 143, July 1978, pp. 918-924.
• 21: Jean-Jacques Quisquater , Jean-Paul Delescaille, How easy is collision search? Application to DES, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.429-434, November 1990, Houthalen, Belgium
• 22: R. Rivest, "The MD5 Message-Digest Algorithm", Internet RFC 1321, April 1992.
• 23: R. Sedgewick, T.G. Szymanski, and A.C. Yao, "The complexity of finding cycles in periodic functions", Siam J. Computing, vol. 11, no. 2, 1982, pp. 376-390.
• 24: M.J. Wiener, "Efficient DES Key Search", TR-244 (May 1994), School of Computer Science, Carleton University, Ottawa, Canada. (Presented at the Rump Session of Crypto '93.)
• 25: G. Yuval, "How to Swindle Rabin", Cryptologia, vol. 3 (3) (July 1979), pp. 187-189.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory