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

Introduction

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.

Contributors (alphabetical order)

Daniel J. Bernstein, University of Illinois at Chicago, USA, and Technische Universiteit Eindhoven, Netherlands

Yun-An Chang, Academia Sinica, Taiwan

Chen-Mou Cheng, Academia Sinica, Taiwan

Li-Ping Chou, Chinese Culture University, Taiwan

Nadia Heninger, University of Pennsylvania, USA

Tanja Lange, Technische Universiteit Eindhoven, Netherlands

Nicko van Someren, Good Technology, USA

Research papers

[smartfacts] 20pp. (PDF) Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, Nicko van Someren. Factoring RSA keys from certified smart cards: Coppersmith in the wild. Asiacrypt 2013, to appear. URL: http://cr.yp.to/papers.html#smartfacts. Date: 2013.09.16.

Research talks

• 2013.07.01 Tanja Lange. Number Theory, Geometry and Cryptography meeting, University of Warwick.
• 2013.08.20 Nadia Heninger. Crypto 2013 rump session, University of California at Santa Barbara.
• 2013.12.05 Nadia Heninger and Tanja Lange. Asiacrypt 2013, Bangalore, India.

Acknowledgments

This work was supported by the U.S. National Science Foundation under grant 1018836. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation."

This work was supported by the Netherlands Organisation for Scientific Research (NWO) under grants 639.073.005 and 040.09.003.

This work was supported by the National Science Council of Taiwan under NSC 101-2915-I-001-019.

Cheng worked on this project while at Technische Universität Darmstadt under the support of Alexander von Humboldt-Stiftung.

Heninger worked on this project while at Microsoft Research New England.