Has AES-128 been fully broken?

Question

Has AES-128 been broken over the full 10 rounds? If so, by what means? By a commercial entity? By a supercomputer?

If not, why is AES-256 used to replace AES-128 so frequently?

Answer 1

AES is a block cipher and is supposed to be a pseudorandom permutation. It can achieve IND-CPA or IND-CCA or authenticated encryption by using the appropriate mode of operation together with AES. Let see what can be achieved or not.

Has AES been fully (10-rounds) broken? by what means? (commercial? supercomputer?)

• Direct brute-forcing

• The total BitCoin miners reached $\approx 2^{92}$ double SHA-256 calculations in a year. So you need on average

  • $2^{35}$ multiple power of this monstrous computing power to break AES-128
  • or wait for $2^{35}$ years.

• The Summit in Oak Ridge can reach $2^{71}$ SHA-1 in a year so no threat there.

In short, there is no threat from here.

• Best Known Cryptographic Attacks

  The key of AES-128 can be recovered with a computational complexity of $2^{126.1}$ shown in Biclique Cryptanalysis of the Full AES by Bogdanov et. al, using the biclique attack, achieved in 2016. Note this is not the related-key-recovery attack from the same authors and that such attacks are not practical since we are generating the keys randomly. The attack requires $2^{88}$ data complexity and $2^8$ memory complexity.

In short, theoretically, one can say it is broken since the attack requires less than the brute force. However, the attack time and data complexity are not practical, either. From the paper; As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

The other theoretical attacks on AES-128 are based on the Biclique Cryptanalysis;

2011. Biclique Cryptanalysis of the Full AES, Bogdanov et al.
2012. Better than Brute-Force - Optimized Hardware Architecture for Efficient Biclique Attacks on AES-128, Bogdanov et al.
2013. Sieve-in-the-Middle: Improved MITM Attacks, Canteaut et al.
2014. A Framework for Automated Independent-Biclique Cryptanalysis, Abed et al.
2015. Bicliques with Minimal Data and Time Complexity for AES, Bogdanov et al.
2016. Improving the Biclique Cryptanalysis of AES Tao et al.

\begin{array}{|c|c|c|c|c|r|}\hline \text{data} & \text{w/o SIM} & \text{Mem. Bytes} & \text{with SIM} & \text{Mem. Bytes} & \text{reference} \\ \hline 2^{88}& 2^{126.21}& 2^{14.32}& - & - & \text{Bogdanov et al. 2011}\\ \hline 2^{4}& 2^{126.89}& 2^{14.32}& - & - & \text{Bogdanov et al. 2012}\\ \hline - & - & - & 2^{126.01} & 2^{64} & \text{Canteaut et al. 2013}\\ \hline 2^{72}& 2^{126.72}& 2^{14.32}& - & - & \text{ Abed et al. 2014}\\ \hline 2 & 2^{126.67} & 2^{14.32} & 2^{126.59} & 2^{64} & \text{Bogdanov et al. 2015}\\ \hline 2^{64} & 2^{126.16} & 2^{14.32} & 2^{126.01} & 2^{64} & \text{" "}\\ \hline 2^{56} & 2^{126.13} & 2^{22.07} & 2^{125.99} & 2^{64} & \text{Tao et al. 2016}\\ \hline 2^{72} & 2^{126.01} & 2^{26.14} & 2^{125.87} & 2^{64} & \text{Tao et al. 2016}\\ \hline \end{array}

Where SIM is Sieve-In-the-Middle technique

• Multi-Target attack

  If you had plaintext-ciphertext pairs with different encryption keys then with a multi-target attack you can find some keys faster. The expected cost of finding a key from $t$ targets is $2^{128}/t$. If you have a billion targets that you will be able to find the first key much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$. This applies not only to AES but all block ciphers.

• Post-Quantum Crypto

  Due to Grover's seminal work we know that the security of any block-cipher is halved in key size and it is shown to be asymptotically optimal.

  Thus, AES-128 will have 64, and AES-256 will have 128-bit security if someone can build the QC. If you consider your assets valuable, the reasonable choice is to double the key size.

  One can also use Grover's algorithm in parallel like in classical parallelization. One, however, will get $\sqrt{K}$ speed gain with $K$ copies.

why has 256 bit key based encryption is used so much to replace it?

Therefore, to mitigate the attacks that exist now or in a possible future, you need to double the key size. In AES, this makes AES-256. If you consider the overhead of using the AES with 256-bit key, in which we need 14 rounds, in CPU this makes around 40% percentage overhead. So, as stated in comments by Prof. Lindell, in marketing AES-256 sounds better, and becomes the standard.

The 256-bit marketing also may come from the US/NATO military regulations which use several distinct security levels (e.g. confidential =128, secret =192, top-secret =256). The 17 years old document from June 2003 states top-secret must be used 192 or 256 bits keys;

The design and strength of all key lengths of the AES algorithm (i.e., 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use

---

In a side note, according to leaked documents by Snowden, NSA looking for tau statics to break AES. After this revelation, consistent and strong encryption is required from governments. After 5 years, nothing has been related to tau statics and AES appeared in academics area.

Current Nist Recommendation NIST as of March 2019 disallows less than 112-bit security for block cipher in SP 800-131A Rev. 2:

The use of keys that provide less than 112 bits of security strength for key agreement is now disallowed.

---

Validation of the 40% overhead of AES-256 with AES-NI

The below numbers are from a laptop with a i7-6700HQ CPU to validate the performance overhead with AES-NI.

$openssl speed -evp aes-128-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-128-ctr     509191.01k  1592361.66k  3090684.67k  4237894.66k  4708169.05k  4763506.01k


$openssl speed -evp aes-256-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-256-ctr     439608.45k  1479537.77k  2478394.14k  3129161.54k  3255877.41k  3396628.62k

Answer 2

No, AES-128 has not been broken by any means in any practical sense.

Answer 3

The AES algorithm is not broken.

With a single or a few fault injections during encryption, it is easy to recover the key in a matter of seconds/minutes/hours depending of the position of the faults and your computation material.

So in that sense it is broken, but the AES algorithm is not broken in its practical use.