Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / RSA, OAEP

Date: received 22 Jun 2005, last revised 6 Jul 2005

Contact author: dbrown at certicom com

Available formats: PDF | BibTeX Citation

Note: Clarification of SSL/TLS example.

Version: 20050706:153625 (All versions of this report)

Discussion forum: Show discussion | Start new discussion