The End of Triple DES

Graham Steel
July 21, 2017

The US National Institute of Standards and Technology (NIST) has just announced withdrawal of approval for triple DES (also known as 3DES, TDEA and sometimes DES EDE) in common protocols such as TLS and IPSec. In other applications, they propose a restriction to just 8MB of data before changing keys. Why are they doing this and what are the consequences?

It's my birthday too

The 3DES cipher suffers from a fundamental weakness linked to its small (64-bit) blocksize, i.e. the size of plaintext that it can encrypt. In the common mode of operation CBC, each plaintext block is XORed with the previous ciphertext before encryption. This means if you encrypt a lot of data and by chance you and get the same ciphertext block twice, an attacker can learn the XOR of the two corresponding blocks of plaintext (he obtains this by XORing the two preceding ciphertexts together). What's the use of learning the XOR of two plaintext blocks? Actually it's pretty useful. If one of the plaintexts are known, the attacker can immediately calculate the second one, and even if neither are known but the plaintexts are known to be non-random (e.g. they encode some natural language), this can be enough to attack both. How much data do you need to encrypt before a collision becomes likely? The calculation is closely related to the birthday problem. This is a classic puzzle where you ask someone how many people you need to put in a room before the probability of two of them having the same birthday becomes 50%, assuming birthdays are uniformly distributed across the 366 possible dates [1]. A lot of people will guess 183. The real answer is just 23. The number is much lower than 183 because you don't mind what particular date the shared birthday is. The same phenomenon applies to collisions in block cipher streams. For this reason NIST already advised (in SP 800-67, Revision 1) that 3DES should not be used to encrypt more than 2^32 blocks. However last year at ACM CCS, INRIA researchers Karthik Bhargavan and Gaëtan Leurent showed that this bound is too high  - with this many blocks, you already have about a 39% chance of a collision. Moreover, they showed that in real world deployments of common protocols like IPsec and TLS, these limits can be reached in a couple of days. Finally, they showed practical attacks where malicious Javascript keeps generating traffic and the collision found is used to obtain credentials.

Lowering the bar

In response, the new NIST recommendation lowers the limit before rekeying to a mere 2^20 blocks. Each block is 8 bytes, so that gives us 8 * 2^20 bytes, or 8 * 2^10 kilobytes, or 8 megabytes as a limit. Since this is so small, they advise that 3DES is removed completely from network protocols such as IPSec and TLS.

Hunting 3DES

We often see 3DES in TLS configurations at our crypto protocol scan site. It is usually the server's least preferred ciphersuite, and included for compatibility with old versions of Windows XP that don't support AES suites. We also see it often in Java applications audited by Cryptosense Analyzer, in business logic code as well as application framework components and libraries, including standard keystores.  

Read our Java cryptography white paper to find out more, and to see if you have 3DES in your applications contact us for an Analyzer demo.

---

[1] Of course birthdays are not really uniformly distributed. February 29th is a long way behind. Distribution is also influenced by scheduled medical interventions such as caesareans as well as seasonal factors. In France, the most likely day is May 7th, right before the fixed May 8th bank holiday.