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

doi:10.1007/978-3-642-42045-0_18

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

University of Illinois at Chicago
Eindhoven University of Technology
Academia Sinica - Research Center for Information Technology Innovation
Chinese Culture University
University of Pennsylvania
Good Technology Inc

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

78 Scopus citations

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.

Original language	English
Title of host publication	Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Pages	341-360
Number of pages	20
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-42045-0_18
State	Published - 2013
Externally published	Yes
Event	19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2013 - Bengaluru, India Duration: 01 12 2013 → 05 12 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	8270 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2013
Country/Territory	India
City	Bengaluru
Period	01/12/13 → 05/12/13

Keywords

Coppersmith
RSA
factorization
lattices
smart cards

Access to Document

10.1007/978-3-642-42045-0_18

Cite this

Bernstein, D. J., Chang, Y. A., Cheng, C. M., Chou, L. P., Heninger, N., Lange, T., & Van Someren, N. (2013). Factoring RSA keys from certified smart cards: Coppersmith in the wild. In Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (PART 2 ed., pp. 341-360). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8270 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-42045-0_18

Bernstein, Daniel J. ; Chang, Yun An ; Cheng, Chen Mou et al. / Factoring RSA keys from certified smart cards : Coppersmith in the wild. Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. PART 2. ed. 2013. pp. 341-360 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{a205374888014b6fb10175c52c205319,

title = "Factoring RSA keys from certified smart cards: Coppersmith in the wild",

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 = "Coppersmith, RSA, factorization, lattices, smart cards",

author = "Bernstein, \{Daniel J.\} and Chang, \{Yun An\} and Cheng, \{Chen Mou\} and Chou, \{Li Ping\} and Nadia Heninger and Tanja Lange and \{Van Someren\}, Nicko",

year = "2013",

doi = "10.1007/978-3-642-42045-0\_18",

language = "英语",

isbn = "9783642420443",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 2",

pages = "341--360",

booktitle = "Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

edition = "PART 2",

note = "19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2013 ; Conference date: 01-12-2013 Through 05-12-2013",

}

Bernstein, DJ, Chang, YA, Cheng, CM, Chou, LP, Heninger, N, Lange, T & Van Someren, N 2013, Factoring RSA keys from certified smart cards: Coppersmith in the wild. in Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 8270 LNCS, pp. 341-360, 19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2013, Bengaluru, India, 01/12/13. https://doi.org/10.1007/978-3-642-42045-0_18

Factoring RSA keys from certified smart cards: Coppersmith in the wild. / Bernstein, Daniel J.; Chang, Yun An; Cheng, Chen Mou et al.
Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. PART 2. ed. 2013. p. 341-360 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8270 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Factoring RSA keys from certified smart cards

T2 - 19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2013

AU - Bernstein, Daniel J.

AU - Chang, Yun An

AU - Cheng, Chen Mou

AU - Chou, Li Ping

AU - Heninger, Nadia

AU - Lange, Tanja

AU - Van Someren, Nicko

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Coppersmith

KW - RSA

KW - factorization

KW - lattices

KW - smart cards

UR - https://www.scopus.com/pages/publications/84892388375

U2 - 10.1007/978-3-642-42045-0_18

DO - 10.1007/978-3-642-42045-0_18

M3 - 会议稿件

AN - SCOPUS:84892388375

SN - 9783642420443

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 341

EP - 360

BT - Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

Y2 - 1 December 2013 through 5 December 2013

ER -

Bernstein DJ, Chang YA, Cheng CM, Chou LP, Heninger N, Lange T et al. Factoring RSA keys from certified smart cards: Coppersmith in the wild. In Advances in Cryptology, ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. PART 2 ed. 2013. p. 341-360. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-42045-0_18

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this