3
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ That depends on the number of your target. What is a multi-target attack?. They use because, they may consider this multi-target attack and a possible Quantum Computer Security levels in NIST Post-quantum project: e.g. AES-128 vs SHA-256. $\endgroup$ – kelalaka Dec 31 '19 at 8:58
  • 10
    $\begingroup$ @kelalaka I think the main reason they use it is because in most applications the difference in speed is insignificant, and it looks better to say AES-256 on marketing charts. Stated differently - it sounds better and industry seems to feel that AES-256 is the gold standard, and so people just do it. $\endgroup$ – Yehuda Lindell Dec 31 '19 at 14:00
20
$\begingroup$

AES is a block cipher and is supposed to be a pseudorandom permutation. It can achieve IND-CPA or IND-CCA or authenticated encryption using AES, 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;

  1. Biclique Cryptanalysis of the Full AES, Bogdanov et al.
  2. Better than Brute-Force - Optimized Hardware Architecture for Efficient Biclique Attacks on AES-128, Bogdanov et al.
  3. Sieve-in-the-Middle: Improved MITM Attacks, Canteaut et al.
  4. A Framework for Automated Independent-Biclique Cryptanalysis, Abed et al.
  5. Bicliques with Minimal Data and Time Complexity for AES, Bogdanov et al.
  6. 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 et. al'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
|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ I've edited with correct performance numbers on a beefy but old laptop. kelalaka, you got 110MB/sec of AES-256 and you didn't think "that must be wrong"? ChaCha20 runs at 1.7GB/sec! $\endgroup$ – Z.T. Jan 1 at 0:36
  • 1
    $\begingroup$ AES is certainly not IND-CPA. AES is a block cipher and is supposed to be a pseudorandom permutation. You can achieve IND-CPA or IND-CCA or authenticated encryption using AES, by using the appropriate mode of operation together with AES. $\endgroup$ – Yehuda Lindell Jan 1 at 6:20
  • $\begingroup$ @YehudaLindell thanks a lot. I've updated it. $\endgroup$ – kelalaka Jan 1 at 6:56
  • $\begingroup$ @Z.T. you are right. I think I've forgotten the -evp. Thanks. $\endgroup$ – kelalaka Jan 1 at 12:39
  • 1
    $\begingroup$ @fgrieu I've updated with the works before 2016 and table based on the Tao et al.'. I think that is the current consensus between you and me. $\endgroup$ – kelalaka Jan 15 at 13:28
16
$\begingroup$

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

|improve this answer|||||
$\endgroup$
0
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • 4
    $\begingroup$ This is a problematic answer. This is also true of RSA, ECC and more. This does not mean that it's broken in any way at all. $\endgroup$ – Yehuda Lindell Dec 31 '19 at 13:59
  • $\begingroup$ @YehudaLindell This is exactly what I said. $\endgroup$ – corpsfini Dec 31 '19 at 14:06
  • 8
    $\begingroup$ @corpsfini What you believe you said, and what you said are two different things. AES as an algorithm is not broken; however, you are conjecting attacks that could break it, which is out of the scope of the question. Furthermore, most people have no idea that AES is based in Rijndael. $\endgroup$ – b degnan Dec 31 '19 at 14:44
  • 2
    $\begingroup$ Also, whether a specific implementation is vulnerable to fault attacks depends on the details of the implementation. One can certainly build an AES implementation that is resistant to fault attacks... $\endgroup$ – poncho Dec 31 '19 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.