Discrepancy with reported key size for EDE ciphers in Qualys SSL Labs

Question

The following two cipher suites were reported by Qualys SSL Labs as being 112-bit:

• SSL_CK_DES_192_EDE3_CBC_WITH_MD5
• TLS_RSA_WITH_3DES_EDE_CBC_SHA

However, all other references I can find say that they are 168-bit, which aligns with my understanding of 3DES EDE: three independent 56-bit keys.

I trust Qualys to be correct on the matter, and I presume that they have some sort of justification for classifying these suites as 112-bit rather than 168-bit, but I don't know enough about the SSL and TLS implementation of EDE to understand why.

I also have no idea why the CK_DES suite has a 192 in the name.

Are they correct? What's the deal with the discrepancies?

Answer 1

First, note that $192=3\cdot64$, so the real key length of 3DES is $192$ bits. However, since $8$ bits in each subkey are parity bits, this reduces to $3\cdot56=168$ bits of non-redundant key material.

Now, the reason that 3DES' effective key length is usually classified as $2\cdot56=112$ bits is that 3DES is susceptible to a meet-in-the-middle attack: When an attacker has access to a pair $(p,c)$ of plaintext and corresponding ciphertext, he can obtain the key using only roughly $2^{112}$ operations as follows:

1. For all DES keys $k_3$, compute $t:=D_{k_3}(c)$ and store the relation $t \mapsto k_3$ in a lookup table $L$.
2. For all pairs of DES keys $(k_1,k_2)$, compute $t:=D_{k_2}(E_{k_1}(p))$ and check whether $t$ is in the table $L$. If it is, yielding a subkey $k_3$, then $(k_1,k_2,k_3)$ is a 3DES key that encrypts $p$ to $c$.

Note that the runtime is dominated by the second step which iterates over $2^{2\cdot56}=2^{112}$ potential keys, hence the number of operations required is roughly $2^{112}$. This is exactly the reasoning behind the strength estimate of $112$ bits.

The lookup table $L$ requires enough memory to store $2^{56}$ pairs, which is quite a lot, but not absolutely unrealistic.

Answer 2

DES has been specified to take a 64 bit key, but only 56 of them are used. The remainder are parity bits.

The key ostensibly consists of 64 bits; however, only 56 of these are actually used by the algorithm. Eight bits are used solely for checking parity, and are thereafter discarded. Hence the effective key length is 56 bits

For 3DES the nominal key size is $3 \cdot 64 = 192$ bits and $3 \cdot 56 = 168$ of them are used.

The 3DES construction suffers from a meet-in-the-middle attack, which reduces the cost of breaking it to about $2^{112}$ operations, leading to an effective security of 112 bits.