It has been around for 20 years … and it’s still a problem

The Bleichenbacher’s attack [here] has been known for 20 years, and has been the core of many attacks on SSL. It returned back in 2017 in the form of ROBOT (Return Of Bleichenbacher’s Oracle Threat https://robotattack.org/).

A demo of the principles covered here is here.

Outline

Let’s say that Eve is attacking the server. In the message she sends, there’s padding of the pre-shared key (as it is much smaller than the public modulus — n). In PKCS#1 v1.5 padding we then have two bytes at the start:

0x00 0x02

Eve then captures the cipher in the handshake and which contains the SSL pre-shared key (M):

C=M^e (mod N)

She then plays it back to the server, but adds an ‘s’ value (where she multiplies the cipher © by s to the power of e (mod N)):

C′=C×(s^e) (mod N)

where e and N are the known public key elements. The server decrypts and gets:

M′=(C(s^e)) ^d (mod N)=C d×s^{ed} (mod N)=M×s (mod N)

M=C′s

When the server reads this, the first two bytes are likely to be incorrect, so it responds to say “Bad Crypto!”. Eve then keeps trying with different s values, until the…