[openssl-dev] Potential timing problems in OpenSSL RSA implementation

[Hanno Böck]

Hi,

As many have probably seen some people (including me) recently published
the so-called ROBOT attack [1], which is the re-birth of the old
Bleichenbacher attack against RSA in TLS.

We mostly focussed on non-timing issues and OpenSSL is not among the
vulnerable implementations. However during various conversations I
learned something about timing problems that affects OpenSSL (but very
likely also almost every other TLS library out there).

The problem is the use of the bignum library, which is variable size.
This means that numbers with leading zeros will take up slightly less
space and thus could cause a timing signal. A more detailed description
below.

For RSA this means if the result of an RSA operation has one or several
leading zeros this means copying around the data will be slightly
faster. Thus an attacker can learn something about the decrypted value.
In the end this could be turned into an attack very similar to a
Bleichenbacher attack.

I'd like to stress that this is highly speculative, it may very well be
that this is not exploitable in any practical way. But I thought it's
important enough that it should be public knowledge. (Also "This leaves
a small timing channel, [...] but it is not believed to be large
enough to be exploitable" said TLS 1.2 when it described what later
became Lucky13.)

Fixing this would likely require changing the bignum library in a
way that it knows fixed size types that allow e.g. treating a 256 byte
number in the same way as a 255 byte number.


---------------------------

Here
<https://github.com/openssl/openssl/blob/OpenSSL_1_0_2-stable/ssl/s3_srvr.c#L2278>
is
the top-level RSA-decrypt for OpenSSL 1.0.2's TLS impl. It calls
RSA_private_decrypt, which ends up here
<https://github.com/openssl/openssl/blob/OpenSSL_1_0_2-stable/crypto/rsa/rsa_eay.c#L483>.
Note that that function calls
<https://github.com/openssl/openssl/blob/OpenSSL_1_0_2-stable/crypto/rsa/rsa_eay.c#L580>
BN_bn2bin
to convert from the resulting BIGNUM to a big-endian buffer. That
<https://github.com/openssl/openssl/blob/OpenSSL_1_0_2-stable/crypto/bn/bn_lib.c#L646>
function
works based on the number of bytes in the BIGNUM. Since BIGNUMs can
never have a most-significant zero limb, if the RSA result starts with
32 (or 64) leading zero bits, there'll be a timing signal there. Also,
if it starts with 8 leading zero bits, there'll be a timing signal in
BN_bn2bin. BoringSSL solves
<https://boringssl.googlesource.com/boringssl/+/296a61d6007688a1472798879b81517920e35dff/crypto/fipsmodule/bn/bytes.c#208>
the
latter problem, but not the former.



[1] https://robotattack.org/

-- 
Hanno Böck
https://hboeck.de/

mail/jabber: hanno at hboeck.de
GPG: FE73757FA60E4E21B937579FA5880072BBB51E42