Paper 2005/189
A Weak-Randomizer Attack on RSA-OAEP with e = 3
Daniel R. L. Brown
Abstract
Coppersmith's heuristic algorithm for finding small roots of bivariate modular equations can be applied against low-exponent RSA-OAEP if its randomizer is weak. An adversary that knows the randomizer can recover the entire plaintext message, provided it is short enough for Coppersmith's algorithm to work. In practice, messages are symmetric cipher keys and these are potentially short enough for certain sets of key sizes. Weak randomizers could arise in constrained smart cards or in kleptographic implementations. Because RSA's major use is transporting symmetric keys, this attack is a potential concern. In this respect, OAEP's design is more fragile than necessary, because a secure randomizer is critical to prevent a total loss of secrecy, not just a loss of semantic security or chosen-ciphertext security. Countermeasures and more robust designs that have little extra performance cost are proposed and discussed.
Note: Clarification of SSL/TLS example.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- RSAOAEP
- Contact author(s)
- dbrown @ certicom com
- History
- 2005-07-06: revised
- 2005-06-22: received
- See all versions
- Short URL
- https://ia.cr/2005/189
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2005/189,
author = {Daniel R. L. Brown},
title = {A Weak-Randomizer Attack on {RSA}-{OAEP} with e = 3},
howpublished = {Cryptology {ePrint} Archive, Paper 2005/189},
year = {2005},
url = {https://eprint.iacr.org/2005/189}
}
