Sweet32: Time to retire 3DES?

The DES encryption algorithm was designed in the early 1970s by researchers at IBM. It was adopted as a FIPS standard in 1977. The algorithm uses 56-bit keys, which were long enough to be secure at the time. However, as it became feasible to brute-force 56-bit keys, 3DES was adopted as a standard in the 1990s. 3DES involves performing three DES operations to encrypt/decrypt each 64-bit block of data using either two or three distinct 56-bit keys. The result is an encryption algorithm with an effective key strength of 112 bits, which is still considered secure against brute-force attacks today.

Although a 112-bit key strength is sufficient to protect against brute-force attacks, 3DES suffers from a potential problem: it operates on 64-bit blocks of data. What does this mean in terms of security?

Sweet32 attack

Now, let’s take a look at the Sweet32 attack as it applies to HTTPS connections. A typical HTTP request looks like this:

GET / HTTP/1.1
Host: www.synopsys.com
User-Agent: ...
Cookie: SessionID=SecretValue

As with many other attacks against HTTPS, Sweet32 requires an attacker that can inject JavaScript code into any page open in a user’s browser and observe network traffic generated by the browser executing the injected JavaScript code. The JavaScript code makes requests to the target site, the browser automatically includes the secret Cookie and/or Authorization header for the site in each request to allow the server to authenticate it, and the attacker collects the resulting encrypted HTTPS traffic. The attacker then attempts to compute the unknown Cookie and/or Authorization header for the target site in order to impersonate the user to that site.

Let’s assume that the browser and server agreed to use a 3DES cipher suite to protect a TLS connection. All TLS cipher suites that use 3DES use it in cipher block chaining (CBC) mode. 3DES encrypts 64-bit blocks of data. Because of how CBC mode works and because to the birthday paradox, we would expect to see ciphertext block collisions after observing approximately 2^32 blocks (i.e., 2^35 bytes or approximately 34 GB) of data. CBC mode encrypts each block of plaintext by performing an XOR operation with the previous ciphertext block before encrypting it. That is, if the plaintext is divided into m blocks: P_1, P_2, …, P_m, then the ciphertext for each block is C_i = Encrypt(P_i XOR C_(i − 1)), where C_0 is the initialization vector.

So what does a ciphertext block collision mean?

If C_i = C_j for distinct i and j encrypted using the same key, then

Encrypt(P_i XOR C_(i − 1)) = Encrypt(P_j XOR C_(j − 1)).

Since the DES encrypt function is a permutation (i.e., each input corresponds to exactly one output), this means

P_i XOR C_(i − 1) = P_j XOR C_(j − 1).

That is:

P_i XOR P_j = C_(i − 1) XOR C_(j − 1).

Here, C_(i − 1) and C_(j − 1) are known ciphertext blocks. By XORing them together, we obtain the XOR of two plaintext blocks. If one of the plaintext blocks is known, we can compute the other.

How does this apply to Sweet32?

When the attacker’s JavaScript code that is running in a victim’s browser makes a request to a vulnerable site, the attacker knows all parts of the request except for the secret value in the Cookie or Authorization header. The attacker can also adjust the length of the URL. This ensures that the secret value starts on a 64-bit 3DES block boundary. Let’s make some reasonable assumptions: Let’s assume that the request is 512 bytes long and the secret value in the Cookie or Authorization header is 16 bytes long such that out of every 64 blocks of 3DES encrypted data sent by the browser, 62 blocks of plaintext are known and 2 blocks are unknown.

Now, the attacker simply sends the same request from the user’s browser over and over again until the attacker observes a ciphertext collision. Recall that this is expected to happen after about 2^32 blocks of ciphertext have been observed.

Now, there are three possibilities. The ciphertext collision is for:

• Two known plaintext blocks.
• Two unknown plaintext blocks.
• A known and an unknown plaintext block.

In the third scenario, the attacker can compute the unknown plaintext block and obtain 8 bytes of the secret.

How much data does the attacker need to collect to successfully obtain the complete 16-byte secret? The researchers that invented the Sweet32 attack found that they needed to collect about 785 GB of data over 38 hours in a lab environment to find the two required collisions.

Are you vulnerable?

The Sweet32 attack requires several preconditions to succeed (in the context of HTTPS):

1. The client and the server need to agree to use a 3DES cipher suite. According to the researchers that invented Sweet32, this happens in about 1%–2% of TLS connections on the Internet.
2. The target server must have sessions that remain valid for long periods of time (38+ hours in the researchers’ lab setup; however, the exact amount of time that the attack requires depends on the length of the cookies used by the server, as well as network performance). While many social media applications have sessions that last this long, most web applications don’t.
3. The target server must allow a large number of requests to be sent within a single TLS session. The researchers noted that Apache and Nginx limit the number of requests within a TLS session to 100 by default. So their default configuration is not vulnerable.

Due to these preconditions, most HTTPS servers are not vulnerable to Sweet32.