Abstract
The difficulty of integer factorization is fundamental to modern cryptographic security using RSA encryption and signatures. Although a 512-bit RSA modulus was first factored in 1999, 512-bit RSA remains surprisingly common in practice across many cryptographic protocols. Popular understanding of the difficulty of 512-bit factorization does not seem to have kept pace with developments in computing power. In this paper, we optimize the CADO-NFS and Msieve implementations of the number field sieve for use on the Amazon Elastic Compute Cloud platform, allowing a non-expert to factor 512-bit RSA public keys in under four hours for $75. We go on to survey the RSA key sizes used in popular protocols, finding hundreds or thousands of deployed 512-bit RSA keys in DNSSEC, HTTPS, IMAP, POP3, SMTP, DKIM, SSH, and PGP.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adrian, D., Bhargavan, K., Durumeric, Z., Gaudry, P., Green, M., Halderman, J.A., Heninger, N., Springall, D., Thomé, E., Valenta, L., VanderSloot, B., Wustrow, E., Zanella-Béguelin, S., Zimmermann, P.: Imperfect forward secrecy: how Diffie-Hellman fails in practice. In: 22nd ACM Conference on Computer and Communications Security (CCS 2015) (2015)
Allman, E., Callas, J., Delany, M., Libbey, M., Fenton, J., Thomas, M.: DomainKeys identified mail (DKIM) signatures (2007). http://www.ietf.org/rfc/rfc6376.txt
Arends, R., Austein, R., Larson, M., Massey, D., Rose, S.: DNS security introduction and requirements. RFC 4033, Internet Society, March 2005. http://www.ietf.org/rfc/rfc4033.txt
Auble, D., Jette, M., et al.: Slurm documentation. http://slurm.schedmd.com/. Accessed 19 Sept 2015
Beurdouche, B., Bhargavan, K., Delignat-Lavaud, A., Fournet, C., Kohlweiss, M., Pironti, A., Strub, P.Y., Zinzindohoue, J.K.: FREAK: Factoring RSA export keys (2015). https://www.smacktls.com/#freak
Beurdouche, B., Bhargavan, K., Delignat-Lavaud, A., Fournet, C., Kohlweiss, M., Pironti, A., Strub, P.Y., Zinzindohoue, J.K.: A messy state of the union: taming the composite state machines of TLS. In: IEEE Symposium on Security and Privacy (2015)
Bureau of Industry and Security: Export administration regulations (2015). http://www.bis.doc.gov/index.php/regulations/export-administration-regulations-ear
Cavallar, S., et al.: Factorization of a 512-Bit RSA modulus. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 1–18. Springer, Heidelberg (2000). doi:10.1007/3-540-45539-6_1
Childers, G.: NFS@home. http://escatter11.fullerton.edu/nfs/
Coppersmith, D.: Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Math. Comput. 62(205), 333–350 (1994)
Cox, B.: Auditing GitHub users SSH key quality. https://blog.benjojo.co.uk/post/auditing-github-users-keyscollected
Crandall, R., Pomerance, C.B.: Prime Numbers: A Computational Perspective, vol. 182. Springer Science & Business Media, New York (2006)
DeHaan, M.: Ansible. http://www.ansible.com
Durumeric, Z., Adrian, D., Mirian, A., Bailey, M., Halderman, J.A.: A search engine backed by Internet-wide scanning. In: Proceedings of the 22nd ACM Conference on Computer and Communications Security, October 2015
Durumeric, Z., Adrian, D., Mirian, A., Kasten, J., Bursztein, E., Lidzborski, N., Thomas, K., Eranti, V., Bailey, M., Halderman, J.A.: Neither snow nor rain nor MITM... an empirical analysis of email delivery security. In: Proceedings of Internet Measurement Conference (IMC 2015) (2015)
Durumeric, Z., Kasten, J., Bailey, M., Halderman, J.A.: Analysis of the HTTPS certificate ecosystem. In: Proceedings of the 13th Internet Measurement Conference, October 2013
Durumeric, Z., Wustrow, E., Halderman, J.A.: ZMap: fast Internet-wide scanning and its security applications. In: Proceedings of the 22nd USENIX Security Symposium, August 2013
Gabriel, E., et al.: Open MPI: goals, concept, and design of a next generation MPI implementation. In: Kranzlmüller, D., Kacsuk, P., Dongarra, J. (eds.) EuroPVM/MPI 2004. LNCS, vol. 3241, pp. 97–104. Springer, Heidelberg (2004). doi:10.1007/978-3-540-30218-6_19
Harkins, D., Carrel, D.: The Internet Key Exchange (IKE). RFC 2409, RFC Editor, November 1998. http://www.rfc-editor.org/rfc/rfc2409.txt
Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J.A.: Mining your Ps and Qs: detection of widespread weak keys in network devices. In: Proceedings of the 21st USENIX Security Symposium, August 2012
Hughes, E.: How to give a math lecture at a party (2000). https://web.archive.org/web/20010222192642/http://www.xent.com/FoRK-archive/oct00/0429.html
Kleinjung, T., et al.: Factorization of a 768-Bit RSA modulus. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333–350. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14623-7_18
Kleinjung, T., Lenstra, A.K., Page, D., Smart, N.P.: Using the cloud to determine key strengths. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 17–39. Springer, Heidelberg (2012). doi:10.1007/978-3-642-34931-7_3
Kolkman, O.M., Mekking, W.M., Gieben, R.M.: DNSSEC operational practices, Version 2. RFC 6781, Internet Society, December 2012. http://www.ietf.org/rfc/rfc6781.txt
Lenstra, A.K., Lenstra Jr., H.W., Manasse, M.S., Pollard, J.M.: The number field sieve. In: Lenstra, A.K., Lenstra, H.W. (eds.) The development of the number field sieve. LNM, vol. 1554, pp. 11–42. Springer, Heidelberg (1993). doi:10.1007/BFb0091537
Monico, C.: GGNFS. http://www.math.ttu.edu/~cmonico/software/ggnfs/
Montgomery, P.L.: A block Lanczos algorithm for finding dependencies over GF(2). In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 106–120. Springer, Heidelberg (1995). doi:10.1007/3-540-49264-X_9
Papadopoulos, J.: Msieve. http://www.boo.net/~jasonp/qs.html
Paterson, K.G., Poettering, B., Schuldt, J.C.N.: Big bias hunting in Amazonia: large-scale computation and exploitation of RC4 biases (invited paper). In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 398–419. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45611-8_21
Pomerance, C.: A tale of two sieves. Not. Am. Math. Soc. (1996). http://www.ams.org/notices/199612/pomerance.pdf
van Rijswijk-Deij, R., Jonker, M., Sperotto, A., Pras, A.: The Internet of names: a DNS big dataset. SIGCOMM Comput. Commun. Rev. 45(5), 91–92 (2015)
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Smith, D.: All TI signing keys factored, September 2009. http://www.ticalc.org/archives/news/articles/14/145/145273.html
Team, T.C.D.: CADO-NFS, an implementation of the number field sieve algorithm (2015). http://cado-nfs.gforge.inria.fr/
Yoo, A.B., Jette, M.A., Grondona, M.: SLURM: Simple Linux Utility for Resource Management. In: Feitelson, D., Rudolph, L., Schwiegelshohn, U. (eds.) JSSPP 2003. LNCS, vol. 2862, pp. 44–60. Springer, Heidelberg (2003). doi:10.1007/10968987_3
Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: cluster computing with working sets. In: Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, vol. 10, p. 10 (2010)
Zetter, K.: How a Google headhunter’s e-mail unraveled a massive net security hole. http://www.wired.com/2012/10/dkim-vulnerability-widespread/
Acknowledgements
We thank Daniel Bernstein, Tanja Lange, Pierrick Gaudry, Emmanuel Thomé, and Paul Zimmermann for helpful comments and discussion. Nicole Limtiaco, Toma Pigli, Zachary Ives, and Sudarshan Muralidhar contributed to early versions of this project. We thank Osman Surkatty for help with Amazon services. We are grateful to Zakir Durumeric, Roland van Rijswijk-Deij, and Ryan Castellucci for providing data. We thank Ian Goldberg for suggesting additional references [21] and Lionel Debroux for a correction. This work is based upon work supported by the National Science Foundation under grant no. CNS-1408734, a gift from Cisco, and an AWS Research Education grant.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 International Financial Cryptography Association
About this paper
Cite this paper
Valenta, L., Cohney, S., Liao, A., Fried, J., Bodduluri, S., Heninger, N. (2017). Factoring as a Service. In: Grossklags, J., Preneel, B. (eds) Financial Cryptography and Data Security. FC 2016. Lecture Notes in Computer Science(), vol 9603. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-54970-4_19
Download citation
DOI: https://doi.org/10.1007/978-3-662-54970-4_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-54969-8
Online ISBN: 978-3-662-54970-4
eBook Packages: Computer ScienceComputer Science (R0)