The Return of Coppersmith's Attack: Practical Factorization of
Widely Used RSA Moduli

D 2017

The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli

NEMEC, Matúš, Marek SÝS, Petr ŠVENDA, Dušan KLINEC, Václav MATYÁŠ et. al.

Basic information

Original name

The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli

Authors

NEMEC, Matúš (703 Slovakia, belonging to the institution), Marek SÝS (703 Slovakia, belonging to the institution), Petr ŠVENDA (203 Czech Republic, belonging to the institution), Dušan KLINEC (703 Slovakia, belonging to the institution) and Václav MATYÁŠ (203 Czech Republic, belonging to the institution)

Edition

New York, NY, USA, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, p. 1631-1648, 18 pp. 2017

Publisher

ACM

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

RIV identification code

RIV/00216224:14330/17:00095054

Organization unit

Faculty of Informatics

ISBN

978-1-4503-4946-8

ISSN

DOI

http://dx.doi.org/10.1145/3133956.3133969

UT WoS

000440307700102

Keywords in English

RSA; factorization; smartcard; Coppersmith's algorithm

Abstract

V originále

We report on our discovery of an algorithmic flaw in the construction of primes for RSA key generation in a widely-used library of a major manufacturer of cryptographic hardware. The primes generated by the library suffer from a significant loss of entropy. We propose a practical factorization method for various key lengths including 1024 and 2048 bits. Our method requires no additional information except for the value of the public modulus and does not depend on a weak or a faulty random number generator. We devised an extension of Coppersmith's factorization attack utilizing an alternative form of the primes in question. The library in question is found in NIST FIPS 140-2 and CC EAL 5+ certified devices used for a wide range of real-world applications, including identity cards, passports, Trusted Platform Modules, PGP and tokens for authentication or software signing. As the relevant library code was introduced in 2012 at the latest (and probably earlier), the impacted devices are now widespread. Tens of thousands of such keys were directly identified, many with significant impacts, especially for electronic identity documents, software signing, Trusted Computing and PGP. We estimate the number of affected devices to be in the order of at least tens of millions. The worst cases for the factorization of 1024 and 2048-bit keys are less than 3 CPU-months and 100 CPU-years on single core of common recent CPUs, respectively, while the expected time is half of that of the worst case. The attack can be parallelized on multiple CPUs. Worse still, all susceptible keys contain a strong fingerprint that is verifiable in microseconds on an ordinary laptop -- meaning that all vulnerable keys can be quickly identified, even in very large datasets.

Links

GA16-08565S, research and development project

Name: Rozvoj kryptoanalytických metod prostřednictvím evolučních výpočtů

Investor: Czech Science Foundation

MUNI/A/0992/2016, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKOMU)

Investor: Masaryk University, Category A

Citovat

NEMEC, Matúš, Marek SÝS, Petr ŠVENDA, Dušan KLINEC and Václav MATYÁŠ. The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli. Online. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York, NY, USA: ACM, 2017, p. 1631-1648. ISBN 978-1-4503-4946-8. Available from: https://dx.doi.org/10.1145/3133956.3133969.

@inproceedings{1392142,
   author = {Nemec, Matúš and Sýs, Marek and Švenda, Petr and Klinec, Dušan and Matyáš, Václav},
   address = {New York, NY, USA},
   booktitle = {Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security},
   doi = {http://dx.doi.org/10.1145/3133956.3133969},
   keywords = {RSA; factorization; smartcard; Coppersmith's algorithm},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {New York, NY, USA},
   isbn = {978-1-4503-4946-8},
   pages = {1631-1648},
   publisher = {ACM},
   title = {The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli},
   url = {https://dl.acm.org/citation.cfm?id=3133969},
   year = {2017}
}

TY  - JOUR
ID  - 1392142
AU  - Nemec, Matúš - Sýs, Marek - Švenda, Petr - Klinec, Dušan - Matyáš, Václav
PY  - 2017
TI  - The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli
PB  - ACM
CY  - New York, NY, USA
SN  - 9781450349468
KW  - RSA
KW  - factorization
KW  - smartcard
KW  - Coppersmith's algorithm
UR  - https://dl.acm.org/citation.cfm?id=3133969
L2  - https://dl.acm.org/citation.cfm?id=3133969
N2  - We report on our discovery of an algorithmic flaw in the construction of primes for RSA key generation in a widely-used library of a major manufacturer of cryptographic hardware. The primes generated by the library suffer from a significant loss of entropy. We propose a practical factorization method for various key lengths including 1024 and 2048 bits. Our method requires no additional information except for the value of the public modulus and does not depend on a weak or a faulty random number generator. We devised an extension of Coppersmith's factorization attack utilizing an alternative form of the primes in question. The library in question is found in NIST FIPS 140-2 and CC EAL 5+ certified devices used for a wide range of real-world applications, including identity cards, passports, Trusted Platform Modules, PGP and tokens for authentication or software signing. As the relevant library code was introduced in 2012 at the latest (and probably earlier), the impacted devices are now widespread. Tens of thousands of such keys were directly identified, many with significant impacts, especially for electronic identity documents, software signing, Trusted Computing and PGP. We estimate the number of affected devices to be in the order of at least tens of millions. The worst cases for the factorization of 1024 and 2048-bit keys are less than 3 CPU-months and 100 CPU-years on single core of common recent CPUs, respectively, while the expected time is half of that of the worst case. The attack can be parallelized on multiple CPUs. Worse still, all susceptible keys contain a strong fingerprint that is verifiable in microseconds on an ordinary laptop -- meaning that all vulnerable keys can be quickly identified, even in very large datasets.
ER  -

NEMEC, Matúš, Marek SÝS, Petr ŠVENDA, Dušan KLINEC and Václav MATYÁŠ. The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli. Online. In \textit{Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security}. New York, NY, USA: ACM, 2017, p.~1631-1648. ISBN~978-1-4503-4946-8. Available from: https://dx.doi.org/10.1145/3133956.3133969.

Detailed Information on Publication Record