Timing Attack against RSA OAEP Code

[Tom Ritter]

I'm not sure if libgcrypt has a policy of attempting to prevent timing
attacks, but I noticed one in the new RSA OAEP code and developed a
proof of concept.  On the latest revision of pubkey.c[1] line 1180 is
an if statement that will exit decoding early if the high byte is
non-zero.  This allows arbitrary decryption of plaintext[2] *depending
on the application using the library*.  I created a simple application
doing RSA OAEP and was able to detect the timing difference locally to
decrypt the ciphertext.  The code is published on github [3] showing
the attack with background [4], and how to demonstrate the timing
difference.  The full code to exploit the timing difference is not
included - partly because I'm embarrassed by my statistical code, and
partly because I'm not aware of any public timing attack libraries and
have no desire to be the first.

The patch for this would be to do something similar to OpenSSL [5] -
where the entire decoding process is run through regardless of the
high-byte error, but a flag is set and the error returned at the end
of the function.

Since this code is trunk and not a versioned release, I don't consider
there any risk of releasing this information prior to informing the
list - if you want to debate disclosure, please contact me personally.

-tom


[1] http://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=blob;f=cipher/pubkey.c;h=0d8b082197d3b4e5f36bce4212211db3a4af1b85;hb=c228af82b3485ff9de2b76b66acb5305aa1a5019
[2] A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption
Padding (OAEP) as Standardized in PKCS #1 v2.0
http://portal.acm.org/citation.cfm?id=704143
[3] https://github.com/GDSSecurity/mangers-oracle
[4] http://www.gdssecurity.com/l/b/2011/06/02/mangers-oracle/
[5] openssl-1.0.0d/crypto/rsa/rsa_oaep.c  Search for 'Manger'