This article is written by Shaun Smith, an engineering fellow at ExpressVPN. It was originally published on October 26, 2016.
A recent vulnerability, dubbed Sweet 32 after the common phrase for a 16th birthday (Sweet 16), has some scratching heads due to its reliance on a paradox called the birthday problem. But it’s not quite as complicated as it seems, and ExpressVPN has the solution.
Reading the news these days, it feels that there is a new security risk every week. Exploits and flaws are often surrounded by a lot of confusion, broad statements, and fixes that could have been pre-empted by the people supplying the software.
Security alerts can be scary, especially when we don’t quite understand what the problem is, or whether the products we are using day-to-day are taking sufficient measures to protect us and our online privacy
What’s so sweet about Sweet 32?
They say your 30s are the new 20s, which is pretty sweet. But, more importantly, we need to answer the question: What is the birthday problem?
The answer is best highlighted with an analogous question: If there are 20 people at a party, what is the probability that two people will share the same birthday?
Small, you might think. But actually, the answer is around 40%.
Increase the number of people to 30, and the probability quickly rises to 70%. When there are 70 people (less than a quarter of the number of days in the year), there is a 99.9% probability of any two people sharing the same birthday.
The math behind the birthday problem is rooted in probability theory. Rather than trying to calculate the probability of two people sharing a birthday directly, we can simplify the math using the concept that the total probability of something happening or not will always be 1.
Therefore, the birthday problem can be expressed as “what is the probability that n people in the room do not share the same birthday.”
Working out the birthday problem
For brevity, the following calculation does not concern leap years or the chance that some birthdays might be more common than others.
If one person were at a party alone, there is a 100% chance of them having a unique birthday (365/365). A second person, however, could only have a unique birthday if it fell on one of the 364 days the first party-goer doesn’t have their birthday (364/365). Subsequently, a third person only has 363 unique days available for their birthday, a fourth only 362 days, and so on.
In a party of three, we can multiply the probability of each person having a unique birthday together to arrive at the total probability of all three having different birthdays.
(365/365) * (364/365) * (363/365) = 0.9918 or 99.18%
To get the probability that all three people share the same birthday, simply subtract the chances of them not sharing a birthday from 100%.
100-99.18 = 0.82%
Furthering the same calculation, the chances of 20 people at a party sharing a birthday can be formulated as such:
((365/365) * (364/365) * (363/365) . . . (346/365)) = 0.589
1 – 0.589 = 0.411 = 41.1%
How does the birthday problem relate to internet security?
If we consider the number of days in the year as the block size and people at the party as blocks of data, then the birthday problem can be applied to encrypted data.
The more blocks of data encrypted with the same key, the higher the probability that two blocks of data will share the same output (in the same way that more people at a party increases the probability that two people will share a birthday).
Two data blocks sharing the same output is known as a collision and, as we know, collisions are rarely good…
Data collisions and the birthday bound
VPN traffic is commonly encrypted using a method known as a block cipher, which works with a fixed amount (or block) of data as opposed to a constant stream of data.
There are three widely used block ciphers for VPN:
- Blowfish – uses 64-bit blocks
- 3DES – uses 64-bit blocks
- AES – uses 128-bit blocks
It is generally considered safe to encrypt 2^([block size]/2) blocks with a single encryption key, but after this, the chance of collisions becomes greater than 50%. This increased probability of collision defines what is known as the birthday bound.
For Blowfish and 3DES, which are 64-bit (8 bytes) block ciphers, this would equate to 2^32 blocks or 32GB of data (hence the name, Sweet 32). Meaning that there is a greater than 50% chance of a collision after 32GB of data has been transferred–which is not so much data for a VPN connection that may last several days.
Compare this with 128-bit (16 bytes) block ciphers, such as AES, where the birthday bound is 2^64 blocks, or a massive 274 billion GB of data.
Why you should be worried about data collisions
In cryptography, collisions could give an attacker some indication of the underlying plaintext (the data before encryption). It isn’t quite as simple as it sounds, as the attacker would need to inject some known-plaintext (perhaps through a malicious website) and then cause the target to transfer a large amount of data (to raise the probability of multiple collisions).
However difficult, it is still feasible for an attacker to learn a plaintext secret (such as an authentication cookie for a website) from encrypted data ascertained through multiple collisions. In fact, researchers studying Sweet 32 were able to retrieve a cookie from inside an encrypted Blowfish session within just 20 hours.
So it’s not so easy to exploit Sweet 32?
In short, no.
But it is practical, and that’s reason enough to consider such encryption unsafe for secure communications.
It’s also worth noting that computers, download speeds, and file sizes are getting faster and bigger, making a Sweet 32 attack more feasible. It’s always best to mitigate such attacks before they are available “out in the wild” and used against you.
Better protection with ExpressVPN’s encryption
ExpressVPN connections are encrypted with an AES-256 key (128-bit block cipher), which would take around 714,000 years to transfer enough data (with a fairly pacey 100mbps connection) to reach the birthday bound. And that’s assuming the same encryption key is used for thousands of years, which is not the case. ExpressVPN changes the key regularly, even while you are connected.
In addition to this, ExpressVPN doesn’t log anything related to your use of the VPN, and continually analyze new threats to ensure the most secure VPN on the planet.
With ExpressVPN you really can have your birthday cake, and eat it too!
