### So what are you talking about?

3DES (also called Triple-DES, DES-EDE, etc) is the term for using the DES block cipher in such a way that increases the total key space of the cipher. This technique was originally conceived by Whitfield Diffie, Martin Hellman and Walt Tuchmann in 1978 after concerns arose that DES's 56-bit key length was insufficient for long term security.

3DES encrypts using DES three times in succession: first encrypting with one key, then decrypting with a second, and finally encrypting again with a third key. This leads to a total key length of 168 bits, which is more than enough for most situations.

To decrypt, first decrypt using the third key, then encrypt with the second, and lastly decrypt with the first key.

### Attacks on 3DES

There is actually a

time-memory tradeoff attack which uses 2

^{112} time and 2

^{56} blocks of memory. Given projected CPU and memory technology over the next decade, this attack is not practical. This attack does not rely on any specific property of DES, only that it has a 56-bit key; other ciphers used in a similiar manner would be equally vulernerable to this attack. The only change would be the amount of time and memory required; if the cipher had a keylength of x, 2

^{2x} operations and 2

^{x} blocks of memory would be required for the attack.

Sometimes 3DES is used with only two keys, one for encrypting and a second for the inner decryption procedure. This is an unwise usage of 3DES, because the same time-memory tradeoff means that 3DES can be attacked in 2^{56} time and 2^{56} memory; this, while also (currently) impractical, is a bit too close for comfort. A related attack can be used to break Double DES.

There are some attacks which are possible due to the 64-bit block size of DES and 3DES, which is why the DES replacement, AES, uses a 128-bit block size. These attacks affect all 64-bit block ciphers.

### Why EDE and not something else?

Security is not the reason for the encrypt-decrypt-encrypt pattern of 3DES. Back in the day, IBM wanted to introduce something with higher security than regular DES. Doing triple encryption with DES is the obvious choice, since that could use pre-existing DES hardware, and because they wouldn't have to go through the long and painful process of creating a new algorithm.

But many applications were already using vanilla single-DES, so backwards compatibility was a must. By using an EDE scheme, you can make 3DES backwards compatible with regular DES by setting all three keys to the same value.

This technique is still in common use, especially in banking standards, where old and new systems must interoperate for years or even decades. For example, both ANSI X9.9 and ANSI X9.19 specifies the use of CBC MAC with regular DES. To prevent exhaustive key search attacks on DES, there is an optional extension to X9.19 which involves first decrypting the final result with a second key, and then encrypting again with the first key. By setting the two keys to the same bitstring, these operations cancel out, giving compatibility with the X9.9 MAC algorithm.

### Who uses this crazy thing?

3DES is a mandatory-to-implement algorithm in wide variety of standardized encryption formats and protocols in use today, including OpenPGP, SSL/TLS, S/MIME, and IPsec.

Confidence in 3DES is stronger than in any other algorithm known. DES has been studied for over 20 years now, and, while it's not perfect, we can be fairly sure that it is, in fact, a strong algorithm. 3DES only increases this confidence, thanks to it's simple design and structure.

### Performance of 3DES, and optimization tricks

DES was originally designed for fast hardware implementation. The fastest software implementations (such as in OpenSSL) can reach about 20 to 30 megabytes per second on current commodity processors. Since 3DES requires three encryptions for every block, this limits the speed to perhaps 6 or 7 megabytes a second. Block ciphers optimized for software, like CAST-128 and Blowfish, can do 4 or 5 times that.

There is a simple and "cute" optimization for 3DES. The DES algorithm starts out with an unkeyed "initial permutation" (IP) and ends with a "final permutation" (FP). These move individual bits around inside the block, and tend to be quite slow. But, IP and FP are inverses of one other (that is, x = FP(IP(x)) = IP(FP(x)) is a tautology). So the FP of the first DES encryption is completely canceled out by the IP of the DES decryption, and similarly the FP of the middle decryption and the IP of the last encryption cancel out. Thus we can omit them completely without changing the algorithm. This tends to result in a 3DES algorithm that takes 2.75 times as long as DES to encrypt or decrypt a block, versus the 3 times one might expect.

A thank you to ariels for encouraging me to flesh out this writeup.