This Attack Has Been Around for 20 Years — And It’s Back Again With The Bleichenbacher Oracle…

The Bleichenbacher attack [here] just refuses to go away. It has been known about for 20 years, and has been the core of many attacks on…

This Attack Has Been Around for 20 Years — And It’s Back Again With The Bleichenbacher Oracle Attack on VPNs

The Bleichenbacher attack [here] just refuses to go away. It has been known about for 20 years, and has been the core of many attacks on SSL. It also returned in 2017 in the form of ROBOT (Return Of Bleichenbacher’s Oracle Threat https://robotattack.org/), and now at the core of a new VPN vulnerability.

Introduction

We have a long legacy within cryptography, and where our tunnels are set up by the client selecting from a number of possible methods that the server provides. Unfortunately, this can leave a race to the bottom, where an intruder can force a downgrade attack, and where they pick the cryptography suites which are known to be weak. These include MD5, RC4, DES and others.

Now the IPSec protocol — which creates VPNs and is often the core foundation of corporate security — has been shown to have a vulnerability with the IKEv1 key exchange method. This vulnerability allows an intruder to listen to the secure communications. While an upgraded protocol — IKEv2 — was meant to replace IKEv1, it is still supported on many networks.

The paper has been published in USENIX (15–17 August 2018) and involves researchers from Ruhr-University Bochum and the University of Opole [paper]:

Bleichenbacher Oracle Attack

The new attack is defined as the Bleichenbacher Oracle Attack (rated with a CVSS score of 5.9 — and a medium risk). Just like the original attack (which is outlined in the next section), it 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.

The vulnerability is not based on the standard, but on poor implementation from vendors. At the current time, four vendors have been shown to be weak against the attack:

Cisco (CVE-2018–0131). Cisco are already sending out patches for the Cisco IOS and IOS XE Software (IOS XE versions 16.3.6, 16.6.3, and 16.7.1. T.).
Huawei (CVE-2017–17305)
Clavister (CVE-2018–8753)
ZyXEL (CVE-2018–9129).

Another part of the paper outlines that both the IKEv1 and IKEv2 methods are weak when using a Pre-Shared Key (PSK).

Let’s first under outline the basic principles of the Bleichenbacher’s attack.

Bleichenbacher’s attack

A demo of the core principles are here.

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ᵉ (mod N)

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)):

C′=C×(sᵉ) (mod N)

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

M′=(C(sᵉ))ᵈ (mod N)=C d×sᵉᵈ (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.

In this case we capture the cipher with M (which starts with \x00\x02), and then play it back with the addition of sᵉ, 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

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)⁷⁹ mod 3337=1570

Decoded=(1570)¹⁰¹⁹ 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. But the attack refuses to go away, and where it has now identified as a significant vulnerability on VPN systems.

Here is a bit of fun with the attack: