Invited talk by Marek Sýs

Factorization of widely used RSA moduli

abstract: Recently published algorithmic flaw in the construction of primes for RSA key generation affects millions of devices in several domains (electronic identity documents, software signing, Trusted Computing and PGP). The primes generated by the widely-used Infineon's library suffer from a significant loss of entropy. Library generates primes (and moduli) of the specific algebraic form. Keys generated by the library contain a strong fingerprint that is verifiable in microseconds on an ordinary laptop. All vulnerable keys can be quickly identified, even in very large datasets. Moreover public RSA moduli of common key sizes 1024 or 2048 bits can be practically factorized (3~CPU months resp. 100~CPU years) which allows directly to compute corresponding private keys. Our factorization method is based on the Coppersmith's attack typically used in situations when partial information (about private key or message) is known. The talk will cover an idea of the Coppersmith's attack and our heuristic search for an alternative form of the primes since the direct application of Coppersmith's attack is not feasible. Optimisation of our approach and the parameter selection will be discussed together with limitations of our method.

Relevant papers

https://crocs.fi.muni.cz/public/papers/rsa_ccs17 (ACM CCS 2017)

bio

Marek Sýs is a lecturer at Masaryk University in Brno, Czech Republic and Slovak Technical University in Bratislava, Slovak Republic. Marek is a member of Centre for Research on Cryptography and Security (Crocs) at Masaryk University aiming to improve security and privacy through applied research (often in cooperation with industry) and advanced education of future security professionals. His research interests cover randomness testing and public key cryptography. He is one of the contributors of two Crocs projects. The EACirc project focuses on randomness testing using genetic algorithms. The optimized version of NIST STS testing suite was implemented within second project focusing on improving the implementation of standard empirical test of randomness. Crocs team recently discovered serious cryptography weakness known as ROCA vulnerability. The significance of their work underlines award for the Real-World Impact obtained at prestige Conference on Computer and Communications Security.