After Schrodinger’s Cat Meet Bleichenbacher’s CAT

The Bleichenbacher attack refuses to go away, and involves sending errors to a server and observing the results. After 10 of thousands of…

After Schrodinger’s Cat Meet Bleichenbacher’s CAT

The Bleichenbacher attack refuses to go away, and involves sending errors to a server and observing the results. After 10 of thousands of replies, the adversary has a high chance of performing a downgrade attack on the server. The new attack brings several new vulnerabilities: CVE-2018–12404, CVE-2018–19608, CVE-2018–16868, CVE-2018–16869, CVE-2018–16870.

A core weakness in TLS relates to the handshaking of the session key which is used within the tunnel. With the RSA key exchange method, the server passes its public key to the server, and the client creates a new session key and then encrypts this with the server’s public key. When returned, the server decrypts it with its private key, and both the client and server have the same symmetric key (normally using AES). This method of key passing, though, is not well liked, and only around 6% of TLS connections use the RSA key exchange method, but intruders can still use it as a downgrade attack. In TLS 1.3, the RSA key exchange method has been removed.

Most current implementations of TLS use ECDH (Elliptic Curve Diffie Hellman), and which has a more secure method of generating the shared key. Unfortunately many servers still support the RSA key exchange method, and where an adversary can implement a downgrade attack.

Along with a breach of the private key of the server, the Bleichenbacher attack [here] on TLS 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 then in 2018 it was the core of a new VPN vulnerability.

But, now researchers have identified that most of the implementations of TLS are still vulnerable to side channel attacks:

Overall they were able to break 7 out of 9 of the most popular TLS implementations (OpenSSL, Amazon s2n, MbedTLS, Apple CoreTLS, Mozilla NSS, WolfSSL, and GnuTLS) using Cache-like ATacks (CATs) to implement a downgrade attack against any TLS connection on a vulnerable server. This used a BEAST-like Man-in-the-Browser attack to perform the exploit.

They implemented a method that allows for thousands of oracle queries in parallel, and which overcame the timeout for a browser session. This parallelisation occurs using a cluster of TLS servers which share the same public key certificate. In their proof-of-concept, the research team were able to perform a downgrade attack in less than 30 seconds using just five TLS servers.

The main recommendations of their work are:

  • Deprecation of RSA Key Exchange. Companies need to get rid of the RSA Key Exchange method and use ECDH.
  • Certificate Separation. Companies should use a dedicated public key for key exchange and which cannot be used for signing. If multiple servers are used, they should each use a separate public key, in order to thwart a parallelization attack.
  • Constant-Time Code and Safe API. The decryption code should take a constant-time to run, and should run checks on the expected size of the plaintext.
  • Use Large RSA Keys. With this RSA keys of larger than 2,048 will make the attack more difficult.
  • Handshake Timeouts. Clients should implement a short TLS timeout.
  • Speed Limitation. This involves reducing the resources allocated to the RSA key exchange, in order to slow the attack down.
  • Dedicated Hardware for Sensitive Cryptographic Code. This involves making sure there are no leaks due to side channels.

IPSec attack

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

The VPN 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:

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, and where the RSA key exchange method has been removed, and this new vulnerability is perhaps the final nail in the coffin for the RSA key exchange method in TLS. Now is the time to switch off TLS 1.0, and quickly migrate to TLS 1.3.