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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2005/189}},
      url = {https://eprint.iacr.org/2005/189}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.