Paper 2020/1059
Incorrectly Generated RSA Keys: How To Recover Lost Plaintexts
Daniel Shumow
Abstract
When generating primes $p$ and $q$ for an RSA key, the algorithm specifies that they should be checked to see that $p1$ and $q1$ are relatively prime to the public exponent $e$, and regenerated if this is not the case. If this is not done, then the calculation of the decrypt exponent will fail. However, what if a software bug allows the generation of public parameters $N$ and $e$ of an RSA key with this property and then it is subsequently used for encryption? Though this may seem like a purely academic question, a software bug in the RSA key generation implementation in the CNG API of a preview release of the Windows 10 operating system makes this question of more than purely hypothetical value. Without a well defined decrypt exponent, plaintexts encrypted to such keys will be undecryptable thus potentially losing user data, a serious software defect. Though the decrypt exponent is no longer well defined, it is in fact possible to recover the plaintext, or a small number of potential plaintexts if the prime factors $p$ and $q$ of the public modulus $N$ are known. This paper presents an analysis of what steps fail in the RSA algorithm and use this to give a plaintext recovery algorithm. The runtime of the algorithm scales linearly in the magnitude of the public exponent, in practice this is manageable as there are only a few small public exponents that are used. This algorithm has been implemented in a publicly available python script. We further discuss the software bug that lead to this and derive lessons that can be used while testing randomized functions in cryptographic software. Specifically, we derive an explicit formula that describes the trade off between number of iterations of tests of a randomized cryptographic functions and the potential number of users affected by a bug dependent on the random values.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 RSApublickey cryptographyimplementationcryptographic softwaresoftware bugs
 Contact author(s)
 danshu @ microsoft com
 History
 20200902: last of 3 revisions
 20200901: received
 See all versions
 Short URL
 https://ia.cr/2020/1059
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1059, author = {Daniel Shumow}, title = {Incorrectly Generated RSA Keys: How To Recover Lost Plaintexts}, howpublished = {Cryptology ePrint Archive, Paper 2020/1059}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1059}}, url = {https://eprint.iacr.org/2020/1059} }