Attacking elliptic curve cryptosystems with special-purpose hardware

ABSTRACT

Since their invention in the mid 1980s, Elliptic Curve Cryptosystems (ECC) have become an alternative to common Public-Key (PK) cryptosystems such as, e.g., RSA. The utilization of Elliptic Curves (EC) in cryptography is very promising because of their resistance against powerful index-calculus attacks. Providing a similar level of security as RSA, ECC allows for efficient implementation due to a significantly smaller bit size of the operands. It is widely accepted that the only feasible way to attack actual cryptosystems, if at all, is the application of dedicated hardware. In times of continuous technological improvements and increasing computing power, the question of the security of ECC against attacks based on special-purpose hardware and, in particular based on recently emerged low-cost FPGAs, arises.This work presents the first architecture with a corresponding FPGA implementation of an attack against ECC over prime fields. We describe an FPGA-based multi-processing hardware architecture for the Pollard-Rho method which is, to our knowledge, currently the most efficient attack against ECC. The implementation is running on a contemporary low-cost FPGA which allows for a much better cost-performance ratio than conventional CPUs. With the implementation at hand, a fairly accurate estimate about the cost of an FPGA-based attack can be given. We will extrapolate the results on actual ECC key lengths (128 bits and above) and estimate the expected runtimes for a successful attack. Since FPGA-based attacks are out of reach for key lengths exceeding 128 bits, we provide estimates for an ASIC design.Based on our results, currently used elliptic curve cryptosystems (160 bit and above) are infeasible to break with available computational and financial resources. However, some of the security standards proposed by the SECG in [2, 3] become subject to attacks based on low-cost FPGAs.

REFERENCES

• 1: Certicom. Certicom ECC Challenge, 1997. Available at http://www.certicom.com.
• 2: Certicom research. Standards for Efficient Cryptography -- SEC 1: Elliptic Curve Cryptography. Available at http://www.secg.org/secg_docs.htm, September 2000. Version 1.0.
• 3: Certicom research. Standards for Efficient Cryptography -- SEC 1: Recommended Elliptic Curve Domain Parameters. Available at http://www.secg.org/secg_docs.htm, September 2000. Version 1.0.
• 4: A. Daly, W. Marnane, T. Kerins, and E. Popovici. An FPGA implementation of a GF(p) ALU for encryption processors. Elsevier -- Microprocessors and Microsystems, 28(5-6):253--260, 2004.
• 5: A. Daly, L. Marnaney, and E. Popovici. Fast Modular Inversion in the Montgomery Domain on Reconfigurable Logic. Technical report, University College Cork, Cork, Ireland, 2004.
• 6: W. Diffie and M. Hellman. New directions in cryptography. IEEE Trans. Inf. Theory, 22:644--654,
• 7: T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory, 31:469--472, 1985.
• 8: J. Franke, T. Kleinjung, C. Paar, J. Pelzl, and C. P. C. Stahlke. SHARK -- A Realizable Special Hardware Sieving Device for Factoring 1024-bit Integers. In J. R. Rao and B. Sunar, editors, Cryptographic Hardware and Embedded Systems -- CHES 2005, 7th International Workshop, Edinburgh, UK, August 29 - September 1, 2005, Proceedings, volume 3659 of LNCS, pages 119--130. Springer-Verlag, August 2005.
• 9: N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48:203--209, 1987.
• 10: S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, M. Schimmler, Breaking Ciphers with COPACOBANA -- A Cost-Optimized Parallel Code Breaker. In Cryptographic Hardware and Embedded Systems -- CHES 2006, 8th International Workshop, Yokohama, Japan, Proceedings. LNCS, Springer-Verlag, October 10-13, 2006.
• 11: A. Lenstra and E. Verheul. Selecting Cryptographic Key Sizes. Journal of Cryptology, 14(4):255--293, 2001.
• 12: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 13: 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
• 14: G. Orlando and C. Paar. A scalable GF(p) elliptic curve processor architecture for programmable hardware. volume 2162, pages 356--371, 2001.
• 15: S. Érs, L. Batina, B. Preneel, and J. Vandewalle. Hardware implementation of elliptic curve processor over GF (?). pages 433--443, 2003.
• 16: J. Pollard. Monte Carlo methods for index computation mod p. Mathematics of Computation, 32(143):918--924, July 1978.
• 17: A. Shamir and E. Tromer. Factoring Large Numbers with the TWIRL Device. In Advances in Cryptology -- Crypto 2003, volume 2729 of LNCS, pages 1--26. Springer, 2003.
• 18: P. van Oorschot and M. Wiener. Parallel collision search with cryptanalytic applications. Journal of Cryptology, 12:1--28, 1999.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Algorithms, Performance, Security

Keywords:
Pollard's Rho, cryptanalysis, discrete logarithm, elliptic curve cryptosystem