[cryptography] OAEP for RSA signatures?

Thierry Moreau thierry.moreau at connotech.com
Tue Jan 29 10:16:53 EST 2013

Peter Gutmann wrote:
> Thierry Moreau <thierry.moreau at connotech.com> writes:
>> The Bleichenbacher attack adaptation to OAEP is non-existent today and would
>> be an even more significant academic result. I must assume that
>> Bleichenbacher would have published results in this direction if his research
>> would have given those.
> Bleichenbacher didn't, but Manger did more than a decade ago:
>   However, the design of RSAES-OAEP makes it highly likely that
>   implementations will leak information between the decryption and integrity
>   check operations making them susceptible to a chosen ciphertext attack that
>   requires many orders of magnitude less effort than similar attacks against
>   PKCS #1 v1.5 block type 2 padding. 
>   -- "A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding
>      (OAEP) as Standardized in PKCS #1 v2.0"

Thanks for the pointer. Indeed. In [1], Dan Boneh's article on SAEP 
(simplified OAEP) agrees as well:

"During decryption invalid ciphertexts can be rejected in Steps 2 and 3 
as well as in Step 7. Manger [10] points out the importance of 
preventing an attacker from distinguishing between rejections at the 
various steps, say, using timing analysis. Implementors must ensure that 
the reason a ciphertext is rejected is hidden from the outside world. 
Indeed, our proof of security fails if this is not the case."

It's the "spot the oracle lesson" once again.

[1] Simplified OAEP for the RSA and Rabin functions, 

The original post was about digital signatures, where "spot the oracle" 
implies "never let some remote party control what the digital signature 
primitive will sign". In practice, session encryption uses a digital 
signature operation on a session key hash (or something similar). It is 
important that the local system played a role (without an insider agent 
playing tricks) in the session key value determination.

The TLS mode where the client selects a session key and encrypts it for 
the server is simply no good (I forgot the name for this mode -- easy to 
recognize as a bad thing upon encountering it again).

It is thus left as an exercise for a pure PK encryption implementer to 
appreciate the Bleichenbacher oracle threat versus the OAEP/SAEP oracle 
threat. They may not be identical.

That's life with public key cryptography since the Rabin-Williams 
theoretical foundation has been established (its formal proof came with 
an early warning of the oracle pitfall). Nowadays the practical 
attacks/defenses front line often lie right where the oracle pitfall 

Interesting times ...

- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, QC, Canada H2M 2A1

Tel. +1-514-385-5691

More information about the cryptography mailing list