Welcome to the resource topic for 2020/1059
Title:
Incorrectly Generated RSA Keys: How To Recover Lost Plaintexts
Authors: Daniel Shumow
Abstract:When generating primes p and q for an RSA key, the algorithm specifies that they should be checked to see that p-1 and q-1 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.
ePrint: https://eprint.iacr.org/2020/1059
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .