Crypto Groundhog Day — The Bleichenbacher Attack

Cryptography Groundhog Day — The Bleichenbacher Attack

In Groundhog Day, we repeated each day, and nothing actually changed. With the Bleichenbacker attack, we have a vulnerability that just won’t go away, and our systems are just as exposed as they were two decades ago. Luckily, if we drop support for TLS 1.2 and below, it will go ahead. But, before then, we are still exposed to a serious attack on a wide range of systems … in fact, any system that still supports PKCS#1 v1.5.

The Bleichenbacher attack [here][1] has been known about for over 24 years and has been the core of many attacks on TLS/SSL and VPN networks:

In 2017, it transformed into ROBOT (Return Of Bleichenbacher’s Oracle Threat https://robotattack.org/). And then there have been attacks against VPNs, including a paper published in USENIX (15–17 August 2018) and involves researchers from Ruhr-University Bochum and the University of Opole [paper]:

An attack defined as the Bleichenbacher Oracle Attack [2] operates by sending errors to the VPN server, and where the server replies with corrupted messages. These returned messages allow the intruder to discover a bit more of the information each time and then can mimic one of the parties involved in the secure tunnel.

Bleichenbacher’s attack

If you are interested, I have created a small demonstration in Python here.

The core problem that PKCS#1 addresses is that we need padding in RSA - in order to create a message which is the same size at the modulus (N). When we encrypt, we perform:

and then to decrypt, we perform:

M = C^d (mod N)

If M is too short, we can use inverse logs to discover M from C. With PKCS#1 v1.5, we pad the message before it is encrypted, and then can unpad after we decrypt. In PKCS#1 v1.5 padding we then have two bytes at the start:

0x00 0x02

We then follow this with random data which does not contain any zero bytes, and then by a zero byte, and the message. This gives:

padded=0x00 || 0x02 || random [(with zero bytes)] || 0x00 || message

If you want to see an example of this, try here.

In the attack, Eve the captures the cipher in the handshake and which contains the TLS/SSL pre-shared key (M):

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

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

In coding, the last statement is implemented with an inverse mod operation:

Decipher=(cipher_dash*libnum.invmod(s,N))%N

Eve then probes for a value of s that will not give an error, and will pick values of s. When the server reads these, 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 server gives her a positive response, and she’s then on her way to finding the key. As we have 16 bits at the start, it will take us between 30,000 (1 in 215 which is 1-in-32,728) and 130,000 attempts (1 in 217 which is 1-in-131,073) to get a successful access.

We use padding to make sure that M (the pre-shared key) is the same length as the modulus (n). As M is only 48 bytes, we need to pad to give a length equal to n (256 bytes for a 2048-bit key).

In the end, we just need to divide the original cipher by the value we have found, and we get M. The coding is [here]:

from Crypto.Util.number import *
from Crypto import Random
from Crypto.Util.number import ceil_div
from Crypto.Util.py3compat import *
import Crypto.Util.number
import os
import sys
import libnum

def int_to_bytes(val, num_bytes):
    return [(val & (0xff << pos*8)) >> pos*8 for pos in range(num_bytes)]

msg="Hello"
bits=128

if (len(sys.argv)>1):
    msg=str(sys.argv[1])
if (len(sys.argv)>2):
    bits=int(sys.argv[2])

message=  msg.encode()

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
randFunc=Crypto.Random.get_random_bytes

N=p*q
e=65537
PHI=(p-1)*(q-1)
d=libnum.invmod(e,PHI)

print (f"d={d}, e={e}, N={N}\n")
modBits = Crypto.Util.number.size(N)
k = ceil_div(modBits,8) # Number of bytes in modulus
mLen = len(message)
    
if mLen > k-11:
	print("Plaintext is too long.")
	sys.exit(1)

ps = tobytes(randFunc(k-mLen-3))

em = b('\x00\x02') + ps + bchr(0x00) + message 

C=pow(int.from_bytes(em, byteorder='big'),e,N)

print("Input=",em.hex())
print("Padding length: ",len(em))

print("C=",C)
print("Searching...")

for s in range(2,10000):
    cipher_dash=(C*pow(s,e,N)) % N
    decrypt = pow(cipher_dash,d,N)
    
    result=bytes(int_to_bytes(decrypt,k) )  
    if (result[0]==0 and result[1]==2):
        Decipher=(cipher_dash*libnum.invmod(s,N))%N
        print("Found at s=",s)
        print("The attacker now knows that the first two bytes of M.s is '00 02'")
        print("We need to now search for message. The decoded value is: ",bytes(int_to_bytes(Decipher,k)).hex())
        sys.exit(1)
        
print("Cannot find in the range of s. Try again ... ")

and a sample run for 128-bit prime numbers is [here]:

d=7080182149736814534773441517425252334483382992275685611087645790669468441233, e=65537, N=38481829287386101688957292812033402077441459403764554103448744762845128973423

Input= 0002222b3cc7e0e95776cc04569332b52889c774957181579bd60068656c6c6f
Padding length:  32
C= 740933176017456084246878264929631493121161652931607853313463434507403553013
Searching...
Found at s= 7680
The attacker now knows that the first two bytes of M.s is '00 02'
We need to now search for message. The decoded value is:  f729b3cbaa873cae1ddfee4b7e12f8aa944421c1f4ca4c2c3d2a3249823c4109

We have a value of s, we then know the range that the M.s is in, and can then probe for the rest of the message. You can try a sample here:

https://asecuritysite.com/rsa/rsa_ble

Conclusions

TLS 1.3 finally closes the door (hopefully) on the Bleichenbacher’s attack, and where the shared key is not passed through RSA. In TLS 1.3, there will be no support for RSA key exchange, and where ECDHE will be the preferred method. If you can, too, drop the usage of PKCS#1 v1.5, and use the more secure padding method of RSA-OAEP (Optimal Asymmetric Encryption Padding):

https://asecuritysite.com/rsa/node_rsa

References

[1] Bleichenbacher, D. (1998, August). Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS# 1. In Annual International Cryptology Conference (pp. 1–12). Springer, Berlin, Heidelberg.

[2] Ronen, E., Gillham, R., Genkin, D., Shamir, A., Wong, D., & Yarom, Y. (2019, May). The 9 lives of bleichenbacher’s cat: New cache attacks on tls implementations. In 2019 IEEE Symposium on Security and Privacy (SP) (pp. 435–452). IEEE.