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

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 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.

Coding

In this case we capture the cipher with M (which starts with \x00\x02), and then play it back with the addition of s^e, and then detect when there is a success in the cipher code:

import sys

e=79
d=1019
N=3337

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

print '==Initial values ===='
print 'e=',e,'d=',d,'N=',N
print '\n============='
 
pad = '\x00\x02\x55\x55'

val = int(pad.encode('hex'), 16)
print 'Padding is:',pad,' Int:',val

cipher = val**e % N

print 'Cipher is: ',cipher

for s in range(0,255):
	cipher_dash = (cipher*(s**e)) % N
	decode = cipher_dash **d % N
	result = int_to_bytes(decode,2)
	print s,
	if (result[0]==0 and result[1]==2):
		print '\n\\x00\\x02 Found it at s=',s
		break

Key calculation

Let’s select:

P=47 Q=71

The calculation of n and PHI is:

n=P × Q = 13 × 11 = 3337
PHI = (p-1)(q-1) = 3220

We can select e as:

e = 79

Next we can calculate d from:

(79 × d) mod 3220 = 1 [Link]
d = 1019
Encryption key [3337,79]
Decryption key [3337,1019]

Then, with a message of 688, we get:

Cipher=(688)^79 mod 3337=1570

Decoded=(1570)^1019 mod 3337=688

A sample run is [here]:

==Initial values ====
e= 79 d= 1019 N= 3337

=============
Padding is: �UU Int: 152917
Cipher is: 2652
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 
\x00\x02 Found it at s= 233

Conclusions

TLS 1.3 finally closes the door (hopefully) on the Bleichenbacher’s attack. Your organisation should aim to migrate to TLS 1.3, and switch have already switched off SSL v2, SSL v3, and TLS 1.0, but should be looking to migrate away from TLS 1.1. Honestly … you wouldn’t believe the number of sites which still support SSL v2 and SSL v3, and are open to Freak, Poople, and others.

Here is a fun trick: