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 . 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.
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.
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.
If you’d like to try our Analyzer on an application to look for 3DES and other weak crypto, get in touch. 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.