In Part 1 of this article series, we established that a brute-force attack on AES-256 is simply impractical, even on a supercomputer.
In Part 2 we discussed future technological advances and their effect on AES security, including the effects of Moore’s Law and Quantum Computing.
Now we’ll see if there are any other weaknesses in AES itself that could jeopardise security.
Cracking AES faster than brute force – is it possible?
We’ve established that a brute force attack against AES-256 won’t work because the key space is far too big. So are there any known attacks on AES that can do better than brute force?
The answer is yes, and let’s examine them now.
Biclique attacks
A biclique attack is a variant of the meet-in-the-middle (MITM) attack that can reduce the security of a cipher by reducing the search space. However, current biclique attacks are quite ineffective compared to those on other cipher types – as we discuss now.
The original meet-in-the-middle attack was proposed in 1997 by Diffie and Hellman, and could reduce the security of DES, double-DES and triple-DES, as summarized:
Cipher | Key size | Security after MITM attack | Benefit |
---|---|---|---|
DES | 56 bits | 2^{56} | |
Double-DES | 2 * 56 bits (112 bits) | 2^{56} + 2^{56} = 2^{57} | 55 bits – 36,028 trillion times faster attack |
Triple-DES | 3 * 56 bits (168 bits) | 2^{56} + 2^{56} * 2^{56} ≈ 2^{112} | 56 bits – 72,058 trillion times faster attack |
The best biclique cryptanalysis of AES, available in the 2011 paper “Biclique Cryptanalysis of the Full AES” is effective in only reducing the security of AES by a few bits, as summarised here:
Cipher | Original security | Security after biclique attack | Benefit |
---|---|---|---|
AES-128 | 2^{128} | 2^{126.1} | 1.9 bits – 3.7 times faster attack |
AES-192 | 2^{192} | 2^{189.7} | 2.3 bits – 4.9 times faster attack |
AES-256 | 2^{256} | 2^{254.4} | 1.6 bits – 3.0 times faster attack |
For AES-256, the best attack is 3 times faster. Therefore, on the world’s fastest supercomputer:
Original time to brute-force AES-256
27,337,893 trillion trillion trillion trillion years
Time with biclique attack
9,112,631 trillion trillion trillion trillion years
This does not pose a significant threat to the security of AES-256.
Related key attacks
A related key attack is one where there is some mathematical relationship connecting encryption keys, and an attacker can observe the operation of a cipher under several different keys.
There are a number of known attacks on AES that are better than brute force, under some particular conditions.
ScramBox is not vulnerable to related key attacks because each AES encryption key was carefully designed to be completely unrelated to each other.
- Each key that encrypts data is generated directly from the user’s computer’s cryptographically secure pseudo-random number generator)
- Metadata is derived from the user’s ScramKey using a pseudorandom function with effective input and output space of 2^{256}. The ScramKey is, in turn, an XOR of three sources of randomness:
- the computer’s cryptographically secure pseudo-random number generator;
- random entropy downloaded from random.org, and
- a mixture of user-generated random entropy generated by the Fortuna cryptographically secure pseudorandom number generator with input entropy accumulator fed with noise measured by the user’s webcam, microphone, mouse and keyboard input.
Nonetheless, the best related key cryptanalysis of AES-256 has 2^{99.5} time and data complexity, as described in the paper, Related-key Cryptanalysis of the Full AES-192 and AES-256.
This attack requires the following conditions (we use the terms “challenger” and “adversary” to denote the user, and an attacker:
- A key, K_{A} is created by challenger
- The adversary forces the challenger to create three additional related keys (K_{B}, K_{C}, K_{D}) under a complex but deterministic way (refer to pages 8 and 9 of the paper).
- The adversary forces the challenger to encrypt specifically chosen blocks of data with the two keys K_{A} and K_{B}, and to decrypt specific ciphertexts using keys K_{C} and K_{D}. This needs to repeat 225.5 times. (47,453,132 times). The adversary performs a considerable number of computations to gradually recover the bits of Key K_{A}.
- By now, the attacker can recover 85 bits of key K_{A}. with 299.5 data and time complexity, and 277.5 memory. A further 107 bits can be found using one of many other approaches, and the remaining 64 bits can be found using exhaustive search.
The memory requirements are that 2^{77.5} AES blocks of plaintexts and ciphertexts need to be stored in the precomputation stage of the attack – a total of 2^{78.5} AES blocks in total. Each AES block is 16 bytes (2^{4} bytes), yields a required memory of 2^{82.5} bytes, which is:
6.838717160008074 * 10^{24} bytes, or expressed in other ways:
- 6,838,717 exabytes
- 6,838,717,160,008 TB
Cleary, this huge memory requirement makes this attack impractical. That’s over 6 times the size of the Internet in 2014, which was estimated at 1 million exabytes.
Another way of viewing the space requirement is to look at the cost of buying enough hard drives to cover the space requirement. The cheapest storage is in the vicinity of US$10 per TB. Thus, to attack AES-256 in this way will cost over $68 trillion for storage – which is 17 times the size of the US budget.
This related key attack is only a theoretical attack, not a practical one that ScramBox is vulnerable to, given that:
- ScramBox never generates related keys in the way required.
- ScramBox never uses the same key to encrypt data more than 6,400 times (100 KiB of data)
- The memory requirements for this search is on a scale of exabytes and is clearly not practical.
As famous cryptographer Bruce Schneier noted, “as long as you use AES properly, related-key attacks are not possible.”
What are the most likely attacks in practice?
The most likely attacks remain social engineering and side channel attacks that involve obtaining your key directly.
However, these attacks are a topic for another article. (And yes, here at Scram we have thought about these too.)
Conclusion
If you ever wondered about the security of AES-256, and the true security of it, we can summarise:
- Brute-force attacks on AES-256 will not be possible in our lifetimes.
- Quantum computers do pose a threat to several kinds of cryptography, but not those used in ScramBox.
- There are other attacks on AES but these are theoretical attacks that require more memory and computing power than is available, and require specific artificial conditions that are not possible in ScramBox.