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

Daniel J.  Bernstein; Yun-An Chang; Chen-Mou Cheng; Li-Ping Chou; Nadia Heninger; Tanja Lange; Nicko van Someren

Paper 2013/599

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

Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, and Nicko van Someren

Abstract

An attacker can efficiently factor at least 184 distinct 1024-bit RSA keys from Taiwan's national "Citizen Digital Certificate" database. The big story here is that these keys were generated by government-issued smart cards that were certified secure. The certificates had all the usual buzzwords: FIPS certification from NIST (U.S. government) and CSE (Canadian government), and Common Criteria certification from BSI (German government). 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in ASIACRYPT 2013
Keywords: RSA smart cards factorization Coppersmith lattices
Contact author(s): tanja @ hyperelliptic org
History: 2013-09-19: received
Short URL: https://ia.cr/2013/599
License: CC BY

BibTeX

@misc{cryptoeprint:2013/599,
      author = {Daniel J.  Bernstein and Yun-An Chang and Chen-Mou Cheng and Li-Ping Chou and Nadia Heninger and Tanja Lange and Nicko van Someren},
      title = {Factoring {RSA} keys from certified smart cards: Coppersmith in the wild},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/599},
      year = {2013},
      url = {https://eprint.iacr.org/2013/599}
}