What is the keyspace of 2-key 3DES?

Question

I am assuming that 2-key 3DES is equivalent to 2DES. I know the key size is 2x56 = 112 bits.

Is this key size the same as the keyspace? e.g. Would the keyspace be 112 bits ($2^{112}$)?

Answer 1

Yes, two-key triple DES has a 112-bit keyspace. That is to say, it has 2¹¹² distinct possible keys, each of them made up of two arbitrarily chosen 56-bit single DES keys.*

Note that, for historical reasons, DES keys are typically represented as strings of 8 bytes, with each byte containing 7 key bits and one parity bit, for a total of 56 + 8 = 64 bits. But since the parity bits cannot be freely chosen (they are calculated based on the key bits) and are not used for any cryptographic purpose, they are not counted as part of the effective key length. As 3DES keys are made up of single DES keys, they inherit this historical peculiarity. Thus, a two-key 3DES key would typically be stored as 16 bytes containing a total of 112 key bits and 16 parity bits.

It's also worth noting that the keyspace size is not necessarily the same as the security level of a cipher, even though both are commonly measured in bits — they are only the same if there is no known way to break the cipher faster than by exhaustive brute force enumeration of the key space. Two-key 3DES does have known attacks that are faster than brute force, which is why, despite its 112 bit key length, its security level (as estimated by NIST) is only about 80 bits. That is to say, breaking two-key 3DES encryption using the best known attacks is estimated to require about as much computing power as exhaustively testing an 80-bit keyspace by brute force would require.

And no, as Christoph Egger notes, two-key triple DES is not the same thing as double DES. While both have the same keyspace size, double DES is vulnerable to even worse attacks than two-key triple DES, and its security level is not significantly higher than the approximately 56-bit security level of plain old single DES.

^{*) Sufficiently pedantic readers might quibble about whether all of those 2112 keys should really be considered valid. Certainly one could argue that keys where both 56-bit halves happen to be identical, or where both halves happen to be weak, should be avoided. But that really makes no difference either way, since such questionable keys only make up a vanishingly small fraction of the full keyspace.}

Answer 2

First, 2-key-3DES is significantly different from 2DES (which provides little additional security over DES because of Meet-in-the-Middle attacks). 2-key-3DES does encrypt with key1, Decrypt with key2 and encrypt with key1 again (instead of a fresh key).

Now DES indeed uses arbitrary bitstrings as keys (possibly filtered for the know weak keys and a 2-key 3DES uses a pair of these bitstrings which means you'll end up with something close to $\{0,1\}^{112}$.