Products + All Products + Software Integrity + Semiconductor IP + Verification + Design + Silicon Engineering
Posted by Amit Sethi on November 21, 2016
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?
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:
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.
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
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.
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)
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]
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:
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.
The Sweet32 attack requires several pre-conditions to succeed (in the context of HTTPS):
Due to these pre-conditions, most HTTPS servers are not vulnerable to Sweet32.
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.