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

We report on our discovery of an algorithmic aw in the construction of primes for RSA key generation in a widely-used library of a major manufacturer of cryptographic hardware. e primes generated by the library su er from a signi cant 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 a ack utilizing an alternative form of the primes in question. e library in question is found in NIST FIPS 140-2 and CC EAL 5+ certi ed devices used for a wide range of real-world applications, including identity cards, passports, Trusted Platform Modules, PGP and tokens for authentication or so ware 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 identi ed, many with signi cant impacts, especially for electronic identity documents, so ware signing, Trusted Computing and PGP. We estimate the number of a ected devices to be in the order of at least tens of millions. e 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. e a ack can be parallelized on multiple CPUs. Worse still, all susceptible keys contain a strong ngerprint that is veri able in microseconds on an ordinary laptop -meaning that all vulnerable keys can be quickly identi ed, even in very large datasets.