Software Integrity

 

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?

Birthday paradox

To understand this, we need to also understand the birthday paradox. The birthday paradox is about the probability of at least two people sharing the same birthday in a room containing N people who are chosen at random. Given several assumptions (e.g., all birthdays are equally likely, ignoring leap years, etc.), it turns out that for N=23, the probability of a shared birthday is 50 percent. This turns out to be much lower than most people would intuitively believe. Here is a chart that shows the probability of shared birthdays for N between 2 and 70:
sweet32

In general, given a set of randomly selected objects, each with a property that can have one of 2^n values that are equally likely, we have a 50% likelihood of seeing multiple objects with the same property after selecting approximately 2^(n/2) objects.

Applying this to 3DES (or any 64-bit block cipher) operating in CBC mode, this means that after observing only about 2^32 (i.e. 4.3 billion) blocks of ciphertext, we are likely to see two identical blocks of ciphertext.

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.
[tweetthis remove_hidden_hashtags=”true”]3DES suffers from a potential problem: it operates on 64-bit blocks of data. #swsec implications:[/tweetthis]

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 pre-conditions 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 pre-conditions, most HTTPS servers are not vulnerable to Sweet32.

Is it time to retire 3DES?

Not necessarily. The Sweet32 attack requires a special set of circumstances to succeed. It requires a large amount of data encrypted using the same key where a large percentage of the plaintext is known and the attacker wants to compute a small percentage of frequently repeating plaintext that is unknown. This is not a scenario you’re likely to run into very often. However, avoid using 3DES unless you know for sure that these types of attacks will not apply to you. It’s safer to use an algorithm such as AES that is secure in all scenarios (given what we know today) rather than an algorithm such as 3DES that is secure in most scenarios.

Also, note that all block ciphers with a block length shorter than 128 bits (when used in CBC and CTR modes) are vulnerable to this type of attack. As such, consider avoiding other 64-bit block ciphers like Blowflish as well.

Get practical guidance for fixing and avoiding vulnerabilities.