Happy Birthday to… Wait, Who’s This Guy?

By Jacob Ansari, Manager, Schellman

How many arbitrary people do you have to get into a room before two of them share the same birthday? Probability theory has considered this problem for so long that no one is quite certain who first posed the so-called “birthday problem” or “birthday paradox.” What we do know is that this occurs with many fewer people than we might have guessed. In fact, there’s a 50% chance that two people will share a birthday (month and date) with only 23 people. That confidence goes up to 99% with 75 people.

Beyond just awkward situations about who gets the first slice of cake, this idea has applications in cryptography and security situations. The short of the idea is that things that seem unpredictable or unlikely are often much more likely than we would think. For a security system based on random numbers and unpredictability, this can pose a few dangerous security problems. Some researchers from the French Institute for Research in Computer Science and Automation (INRIA) recently published some work that shows significant weaknesses with practical exploits in 64-bit block ciphers, particularly 3DES and Blowfish, and in their most common uses in HTTPS and VPN connections.

Most modern ciphers that use a symmetric key, that is a key that both parties need to have to encrypt and decrypt messages, are what cryptographers call “block ciphers.” They encrypt blocks of data, rather than bit by bit. Often, the block length is the size of the key, but in some cases it isn’t. So a 3DES cipher, which performs three cryptographic operations using 64-bit blocks and 64-bit keys (technically 56-bit keys with eight bits used for error checking) divides up its message into 64-bit segments and encrypts each one. The problem related to the birthday paradox is this: when you have a 64-bit key, an exhaustive attack would potentially need to try 264 guesses at the key value to see if it could decrypt the encrypted message (this is what we call a brute-force attack).

In practice, however, block ciphers use what are called modes of operation, which link blocks of messages together. In these situations, with a 64-bit block length, encrypting more than 2 (block length/2) or 232 bits of data presents a well-known cryptographic danger. The operation will inevitably repeat enough data for patterns to emerge and for an attack to determine the key from these patterns. Thus, good design prevents more than 232 bits of data encrypted by the same key, and cryptographers refer to this as the birthday bound.

This attack goes from theoretical to practical in two significant applications: HTTPS using 3DES (typically with TLS 1.0 or earlier), and OpenVPN, which uses Blowfish (which has 64-bit blocks) as its default cipher. With 64-bit blocks, the birthday bound is approximately 32GB of data transfer, which is something a reasonably fast connection can handle in about an hour. Thus, the practicality of collecting these data and attacking the key is an entirely reasonable prospect. Further, modern uses of HTTPS and VPN connections often find cases where the session lasts for long periods of time, and thus continues to use the same key for those long periods, making both the recovery of the key and its use in an attack practical and effective.

Ultimately, the solution for this kind of attack is to replace the use of 64-bit block ciphers with 128-bit block ciphers like AES. In many cases, the capability to do this already exists and organizations facing this threat can do so with reasonable expedience. In some cases, particularly when supporting legacy connections such as TLS 1.0 and the corresponding support for 3DES ciphers, this becomes more complicated. While many organizations have made advances in moving to more secure block ciphers, others have compatibility and legacy support issues. These kinds of advances in attacks make those transitions all the more urgent.

Organizations currently in transition should strongly consider accelerating those efforts and eliminating the use of ciphers like 3DES and Blowfish entirely.