Matus Nemec
Petr Svenda
ABSTRACT
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.
Supplemental Material
- Trüb Baltic AS. 2017. Estonian Electronic ID card application specification, EstEID v. 3.5. http://www.id.ee/public/TB-SPEC-EstEID-Chip-App-v3.5-20170314.pdf. [2017-08-28].Google Scholar
- Axalto and Zetes. 2004. Public user specification BelPic application v2.0. http://www.foo.be/eID/opensc-belgium/BEID-CardSpecs-v2.0.0.pdf. [2017-08-28].Google Scholar
- Luciano Bello. 2008. DSA-1571--1 openssl -- predictable random number generator. (2008). http://www.debian.org/security/2008/dsa-1571. [2017-08-28].Google Scholar
- Elwyn R. Berlekamp. 1967. Factoring Polynomials Over Finite Fields. Bell System Technical Journal Vol. 46, 8 (1967), 1853--1859. 1990. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory Vol. 36 (1990), 553--558.Google ScholarCross Ref
- David Wong. 2015. Implementation of Coppersmith attack (RSA attack using lattice reductions). (2015). https://www.cryptologie.net/article/222/implementation-of-coppersmith-attack-rsa-attack-using-lattice-reductions/shownotecit. [2017-08--28].Google Scholar
- Oded Yacobi and Yacov Yacobi 2005. A New Related Message Attack on RSA. In Public Key Cryptography -- PKC 2005 (Lecture Notes in Computer Science), Vol. Vol. 3386. Springer-Verlag, 1--8. Google ScholarDigital Library
- Yubico 2017. PGP, Importing keys. https://developers.yubico.com/PGP/Importing_keys.htmlshownotecit. [2017-08--28].Google Scholar
Index Terms
- The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli
Recommendations
Proxy-protected signature secure against the undelegated proxy signature attack
The proxy signature scheme enables an original signer to delegate his/her signing capability to a designated proxy signer, thereby the proxy signer can sign messages on behalf of the original signer. Recently, Zhou et al. proposed two proxy-protected ...
Cryptanalysis of RSA with more than one decryption exponent
In this paper, we analyze the security of the RSA public key cryptosystem where multiple encryption and decryption exponents are considered with the same RSA modulus N. We consider N=pq, where p, q are of the same bit size, i.e., q =2. Our result ...
Instantiability of RSA-OAEP Under Chosen-Plaintext Attack
We show that the widely deployed RSA-OAEP encryption scheme of Bellare and Rogaway (Eurocrypt 1994), which combines RSA with two rounds of an underlying Feistel network whose hash ( i.e., round) functions are modeled as random oracles, meets ...
Comments