Top

Published in:

2017 | OriginalPaper | Chapter

Factoring as a Service

Authors : Luke Valenta, Shaanan Cohney, Alex Liao, Joshua Fried, Satya Bodduluri, Nadia Heninger

Published in: Financial Cryptography and Data Security

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Explicit Optimal Binary Pebbling for One-Way Hash Chain Reversal

next chapter The Self-blindable U-Prove Scheme from FC’14 Is Forgeable (Short Paper)

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 CrossRef

Childers, G.: NFS@home. http://escatter11.fullerton.edu/nfs/

10.

Coppersmith, D.: Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Math. Comput. 62(205), 333–350 (1994)MathSciNetMATH

11.

Cox, B.: Auditing GitHub users SSH key quality. https://blog.benjojo.co.uk/post/auditing-github-users-keyscollected

12.

Crandall, R., Pomerance, C.B.: Prime Numbers: A Computational Perspective, vol. 182. Springer Science & Business Media, New York (2006)MATH

13.

DeHaan, M.: Ansible. http://www.ansible.com

14.

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

15.

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)

16.

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

17.

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

18.

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 CrossRef

19.

Harkins, D., Carrel, D.: The Internet Key Exchange (IKE). RFC 2409, RFC Editor, November 1998. http://www.rfc-editor.org/rfc/rfc2409.txt

20.

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

21.

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

22.

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 CrossRef

23.

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 CrossRef

24.

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

25.

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 CrossRef

26.

Monico, C.: GGNFS. http://www.math.ttu.edu/~cmonico/software/ggnfs/

27.

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

28.

Papadopoulos, J.: Msieve. http://www.boo.net/~jasonp/qs.html

29.

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

30.

Pomerance, C.: A tale of two sieves. Not. Am. Math. Soc. (1996). http://www.ams.org/notices/199612/pomerance.pdf

31.

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)CrossRef

32.

Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRefMATH

33.

Smith, D.: All TI signing keys factored, September 2009. http://www.ticalc.org/archives/news/articles/14/145/145273.html

34.

Team, T.C.D.: CADO-NFS, an implementation of the number field sieve algorithm (2015). http://cado-nfs.gforge.inria.fr/

35.

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 CrossRef

36.

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)

37.

Zetter, K.: How a Google headhunter’s e-mail unraveled a massive net security hole. http://www.wired.com/2012/10/dkim-vulnerability-widespread/

Title: Factoring as a Service
Authors: Luke Valenta
Shaanan Cohney
Alex Liao
Joshua Fried
Satya Bodduluri
Nadia Heninger
Publisher: Springer Berlin Heidelberg
Book: Financial Cryptography and Data Security
Print ISBN: 978-3-662-54969-8

Electronic ISBN: 978-3-662-54970-4

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-662-54970-4_19

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner