Factoring RSA keys from certified smart cards : Coppersmith in the wild

D.J. Bernstein, Y.A. Chang, C.M. Cheng, L.P. Chou, N. Heninger, T. Lange, N. Someren, van

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

52 Citations (Scopus)
2 Downloads (Pure)

Abstract

This paper explains how an attacker can efficiently factor 184 distinct RSA keys out of more than two million 1024-bit RSA keys downloaded from Taiwan’s national "Citizen Digital Certificate" database. These keys were generated by government-issued smart cards that have built-in hardware random-number generators and that are advertised as having passed FIPS 140-2 Level 2 certification. These 184 keys include 103 keys that share primes and that are efficiently factored by a batch-GCD computation. This is the same type of computation that was used last year by two independent teams (USENIX Security 2012: Heninger, Durumeric, Wustrow, Halderman; Crypto 2012: Lenstra, Hughes, Augier, Bos, Kleinjung, Wachter) to factor tens of thousands of cryptographic keys on the Internet. The remaining 81 keys do not share primes. Factoring these 81 keys requires taking deeper advantage of randomness-generation failures: first using the shared primes as a springboard to characterize the failures, and then using Coppersmith-type partial-key-recovery attacks. This is the first successful public application of Coppersmith-type attacks to keys found in the wild. Keywords: RSA; smart cards; factorization; Coppersmith; lattices
Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2013 (19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013. Proceedings)
EditorsK. Sako, P. Sarkar
Place of PublicationBerlin
PublisherSpringer
Pages341-360
Volume3
ISBN (Print)978-3-642-42044-3
DOIs
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
Volume8270
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Factoring RSA keys from certified smart cards : Coppersmith in the wild'. Together they form a unique fingerprint.

Cite this