EN

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

NEMEC, Matúš, Marek SÝS, Petr ŠVENDA, Dušan KLINEC a Václav MATYÁŠ. The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York, NY, USA: ACM, 2017. s. 1631-1648, 18 s. ISBN 978-1-4503-4946-8. doi:10.1145/3133956.3133969.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli
Autoři NEMEC, Matúš (703 Slovensko, domácí), Marek SÝS (703 Slovensko, domácí), Petr ŠVENDA (203 Česká republika, domácí), Dušan KLINEC (703 Slovensko, domácí) a Václav MATYÁŠ (203 Česká republika, domácí).
Vydání New York, NY, USA, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, od s. 1631-1648, 18 s. 2017.
Nakladatel ACM
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor Computer sciences, information science, bioinformatics
Stát vydavatele Spojené státy americké
Utajení není předmětem státního či obchodního tajemství
Forma vydání elektronická verze "online"
WWW 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
Kód RIV RIV/00216224:14330/17:00095054
Organizační jednotka Fakulta informatiky
ISBN 978-1-4503-4946-8
ISSN 1543-7221
Doi http://dx.doi.org/10.1145/3133956.3133969
Klíčová slova anglicky RSA; factorization; smartcard; Coppersmith's algorithm
Štítky firank_1
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 27. 4. 2018 11:05.
Anotace
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.
Návaznosti
GA16-08565S, projekt VaVNázev: Rozvoj kryptoanalytických metod prostřednictvím evolučních výpočtů
Investor: Grantová agentura ČR, Standardní projekty
MUNI/A/0992/2016, interní kód MUNázev: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)
Investor: Masarykova univerzita, Grantová agentura MU, Kategorie A - Specifický výzkum - Studentské výzkumné projekty
VytisknoutZobrazeno: 18. 1. 2019 19:06

Další aplikace