Cryptology ePrint Archive: Report 2015/1000

Factoring as a Service

Luke Valenta and Shaanan Cohney and Alex Liao and Joshua Fried and Satya Bodduluri and Nadia Heninger

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.

Category / Keywords: public-key cryptography / RSA, factoring, cloud computing

Date: received 14 Oct 2015, last revised 18 Oct 2015

Contact author: nadiah at cis upenn edu

Available format(s): PDF | BibTeX Citation

Note: Corrected a reference.

Version: 20151018:210404 (All versions of this report)

Short URL: ia.cr/2015/1000

Discussion forum: Show discussion | Start new discussion