Special-Purpose Hardware for Solving the Elliptic Curve Discrete Logarithm Problem

ABSTRACT

The resistance against powerful index-calculus attacks makes Elliptic Curve Cryptosystems (ECC) an interesting alternative to conventional asymmetric cryptosystems, like RSA. Operands in ECC require significantly less bits at the same level of security, resulting in a higher computational efficiency compared to RSA. With growing computational capabilities and continuous technological improvements over the years, however, the question of the security of ECC against attacks based on special-purpose hardware arises. In this context, recently emerged low-cost FPGAs demand for attention in the domain of hardware-based cryptanalysis: the extraordinary efficiency of modern programmable hardware devices allow for a low-budget implementation of hardware-based ECC attacks---without the requirement of the expensive development of ASICs.

With focus on the aspect of cost-efficiency, this contribution presents and analyzes an FPGA-based architecture of an attack against ECC over prime fields. A multi-processing hardware architecture for Pollard's Rho method is described. We provide results on actually used key lengths of ECC (128 bits and above) and estimate the expected runtime for a successful attack.

As a first result, currently used elliptic curve cryptosystems with a security of 160 bit and above turn out to be infeasible to break with available computational and financial resources. However, some of the security standards proposed by the Standards for Efficient Cryptography Group (SECG) become subject to attacks based on low-cost FPGAs.

REFERENCES

• 1: Ian F. Blake , G. Seroussi , N. P. Smart, Elliptic curves in cryptography, Cambridge University Press, New York, NY, 1999
• 2: Certicom. 1997. Certicom ECC Challenge. http://www.certicom.com.
• 3: Certicom research. 2000a. Standards for Efficient Cryptography---SEC 1: Elliptic Curve Cryptography v1.0. http://www.secg.org/secg_docs.htm.
• 4: Certicom research. 2000b. Standards for Efficient Cryptography---SEC 1: Recommended Elliptic Curve Domain Parameters v1.0. http://www.secg.org/secg_docs.htm.
• 5: Daly, A., Marnane, W., Kerins, T., and Popovici, E. 2004. An FPGA implementation of a GF(p) ALU for encryption processors. Elsevier Microproces. Microsyst. 28, 5--6, 253--260.
• 6: Daly, A., Marnaney, L., and Popovici, E. 2004. Fast modular inversion in the Montgomery Domain on reconfigurable logic. Tech. rep., University College Cork, Cork, Ireland.
• 7: de Dormale, G., Bulens, P., and Quisquater, J. 2007. Collision search for elliptic curve discrete logarithm over GF (2^m) with FPGA. In Proceedings of Workshop on Cryptograpic Hardware and Embedded Systems (CHES'07). LNCS Vol. 4727. Springer, 378.
• 8: Diffie, W. and Hellman, M. 1976. New directions in cryptography. IEEE Trans. Inform. Theory 22, 644--654.
• 9: ElGamal, T. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory 31, 469--472.
• 10: Franke, J., Kleinjung, T., Paar, C., Pelzl, J., Priplata, C., and Stahlke, C. 2005. SHARK---A realizable special hardware sieving device for factoring 1024-bit integers. In Proceedings of Workshop on Cryptograpic Hardware and Embedded Systems (CHES'05). Lecture Notes in Computer Science, vol. 3659. Springer, 119--130.
• 11: Tim Gueneysu , Christof Paar , Jan Pelzl, Attacking elliptic curve cryptosystems with special-purpose hardware, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216953]
• 12: Darrel Hankerson , Alfred J. Menezes , Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 13: Koblitz, N. 1987. Elliptic curve cryptosystems. Math. Comput. 48, 203--209.
• 14: Kumar, S., Paar, C., Pelzl, J., Pfeiffer, G., and Schimmler, M. 2006. Breaking ciphers with COPACOBANA - A cost-optimized parallel code breaker. In Proceedings of Workshop on Cryptograpic Hardware and Embedded Systems (CHES'06). Springer-Verlag.
• 15: Lenstra, A. and Verheul, E. 2001. Selecting Cryptographic key sizes. J. Cryptol. 14, 4, 255--293.
• 16: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 17: Victor S Miller, Use of elliptic curves in cryptography, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.417-426, June 1986, Santa Barbara, California, United States
• 18: Gerardo Orlando , Christof Paar, A Scalable GF(p) Elliptic Curve Processor Architecture for Programmable Hardware, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.348-363, May 14-16, 2001
• 19: Örs, S., Batina, L., Preneel, B., and Vandewalle, J. 2003. Hardware implementation of elliptic curve processor over GF(p). In Proceedings of the Application-Specific Systems, Architectures, and Processors (ASAP), 433--443.
• 20: Pollard, J. 1978. Monte Carlo methods for index computation mod p. Math. Comput. 32, 143, 918--924.
• 21: Shamir, A. and Tromer, E. 2003. Factoring large numbers with the TWIRL device. In Advances in Cryptology---(Crypto'03). Lecture Notes in Computer Science, vol. 2729. Springer, 1--26.
• 22: Edlyn Teske, Speeding Up Pollard's Rho Method for Computing Discrete Logarithms, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.541-554, June 21-25, 1998
• 23: van Oorschot, P. and Wiener, M. 1999. Parallel collision search with cryptanalytic applications. J. Cryptol. 12, 1--28.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.0 General

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Algorithms, Performance, Security

Keywords:
Discrete logarithm, Pollard's rho, cryptanalysis, elliptic curve cryptosystem