Biclique Cryptanalysis of the Full AES

The analysis of AES with local collisions is only applicable to the related-key model.

“So far the most well-known attempt is the analysis of AES with local collisions [8][9][10][11], but it is only applicable to the relatedkey model.”

• cites [8] Biryukov, A., Dunkelman, O., Keller, N., Khovratovich, D., Shamir, A.: Key Recovery Attacks of Practical Complexity on AES-256 Variants with up to 10 Rounds. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 299–319. Springer, Heidelberg (2010) sourceNot checked — no full text of the source
• cites [9] Biryukov, A., Khovratovich, D.: Related-Key Cryptanalysis of the Full AES-192 and AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 1–18. Springer, Heidelberg (2009) sourcePartly supported

  The Introduction and Conclusions describe the paper’s local-collision attacks on AES-192 and AES-256 as related-key attacks. Section 4.1 explains the related-key model used. The paper does not establish the broader claim that analysis of AES with local collisions is only applicable in that model; page numbers are unavailable in our copy. (LLM, conf=0.85)

  Experimental — accuracy not yet measured
• cites [10] Biryukov, A., Khovratovich, D., Nikolić, I.: Distinguisher and Related-Key Attack on the Full AES-256. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 231–249. Springer, Heidelberg (2009) sourceDisputed

  The Introduction (page not provided) says the authors use local collisions to construct a chosen-key distinguisher for AES-256, not only a related-key attack. Section 2 (page not provided) likewise presents a chosen-key distinguisher, contradicting the claimed restriction to the related-key model. (LLM, conf=0.90)

  Checked by a reasoning model — may be wrong.

  Experimental — accuracy not yet measured
• cites [11] Biryukov, A., Nikolić, I.: Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 322–344. Springer, Heidelberg (2010) sourcePartly supported

  The Introduction describes related-key differential analysis of AES, including characteristics used in an AES-256 attack. It does not identify that analysis as using local collisions or say that local-collision analysis of AES is only applicable in the related-key model. (LLM, conf=0.78)

  Experimental — accuracy not yet measured

The fastest single-key attacks on round-reduced AES variants so far are only slightly more powerful than those proposed 10 years ago.

“Though many papers have been published on the cryptanalysis of AES, the fastest single-key attacks on round-reduced AES variants [20,33] so far are only slightly more powerful than those proposed 10 years ago [23,24].”

• cites [20] Demirci, H., Taşkın, İ., Çoban, M., Baysal, A.: Improved Meet-in-the-Middle Attacks on AES. In: Roy, B., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 144–156. Springer, Heidelberg (2009) sourceNot checked — no full text of the source
• cites [33] Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schläffer, M.: Rebound Distinguishers: Results on the Full Whirlpool Compression Function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 126–143. Springer, Heidelberg (2009) sourceCould not verify

  The Introduction (p. 2) mentions known-key distinguishers for seven-round AES, but does not compare the fastest single-key attacks with attacks from ten years earlier. Searches for that comparison and for single-key attacks on reduced-round AES found no passage addressing it in our copy. (LLM, conf=0.75)

  Experimental — accuracy not yet measured
• cites [23] Dunkelman, O., Keller, N., Shamir, A.: A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 393–410. Springer, Heidelberg (2010) sourceCould not verify

  The Introduction and Summary discuss related-key attacks on KASUMI, not the relative strength of single-key attacks on round-reduced AES. A reference lists a reduced-round AES attack, but our copy does not compare AES attacks with those proposed ten years earlier (searched for single-key AES attacks and that comparison). (LLM, conf=0.76)

  Experimental — accuracy not yet measured
• cites [24] Dunkelman, O., Sekar, G., Preneel, B.: Improved Meet-in-the-Middle Attacks on Reduced-Round DES. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 86–100. Springer, Heidelberg (2007) sourceNot checked — no full text of the source

With respect to AES, the most powerful single-key recovery methods designed so far are impossible differential cryptanalysis and Square attacks.

“With respect to AES, probably the most powerful singlekey recovery methods designed so far are impossible differential cryptanalysis [5,33] and Square attacks [14,20].”

• cites [5] Biham, E., Biryukov, A., Shamir, A.: Miss in the Middle Attacks on IDEA and Khufu. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 124–138. Springer, Heidelberg (1999) sourceSupported
• cites [33] Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schläffer, M.: Rebound Distinguishers: Results on the Full Whirlpool Compression Function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 126–143. Springer, Heidelberg (2009) sourceCould not verify

  The Introduction (p. 2) mentions known-key distinguishers for reduced-round AES, not single-key recovery methods. The Rebound Attack section (p. 3) discusses AES-based hash functions. Searches for impossible differential cryptanalysis, Square attacks, and AES key recovery found no passage assessing the claimed methods. (LLM, conf=0.73)

  Experimental — accuracy not yet measured
• cites [14] Bouillaguet, C., Derbez, P., Fouque, P.-A.: Automatic Search of Attacks on Round-Reduced AES and Applications. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 169–187. Springer, Heidelberg (2011) sourceNot checked — no full text of the source
• cites [20] Demirci, H., Taşkın, İ., Çoban, M., Baysal, A.: Improved Meet-in-the-Middle Attacks on AES. In: Roy, B., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 144–156. Springer, Heidelberg (2009) sourceNot checked — no full text of the source

The omission of the MixColumn transformation in the last round of AES helps to design attacks for more rounds.

“Also, as already observed in [19,37], the fact that the MixColumn transformation is omitted in the last round of AES helps to design attacks for more rounds.”

• cites [19] Demirci, H., Selçuk, A.A.: A Meet-in-the-Middle Attack on 8-Round AES. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 116–126. Springer, Heidelberg (2008) sourcePartly supported

  Section 2 (page unavailable) says that AES has no MixColumn operation in its final round. Section 5.2 (page unavailable) describes extending the attack to eight rounds by searching the last-round key, but does not say that omitting MixColumn enables the extension. The claimed causal link is therefore not established by our copy. (LLM, conf=0.83)

  Experimental — accuracy not yet measured
• cites [37] Matsui, M.: Linear Cryptanalysis Method for DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) sourceNot checked — no full text of the source

The paper provides preimage attacks on compression functions based on the full AES versions.

“-Preimage attacks on compression functions based on the full AES versions.”

The paper provides the first key recovery attack on the full AES-256 with computational complexity 2 254.4.

“-The first key recovery attack on the full AES-256 with computational complexity 2 254.4 .”

The paper provides the first key recovery attack on the full AES-192 with computational complexity 2 189.7.

“-The first key recovery attack on the full AES-192 with computational complexity 2 189.7 .”

The paper provides the first key recovery attack on the full AES-128 with computational complexity 2 126.1.

“-The first key recovery attack on the full AES-128 with computational complexity 2 126.1 .”

It yields advantages of up to factor 15 for the key recovery of round-reduced AES variants with numbers of rounds higher than those cryptanalyed before.

“The biclique cryptanalysis successfully applies to all full versions of AES and compared to brute-force provides an advantage of about a factor 3 to 5, depending on the version, Also, it yields advantages of up to factor 15 for the key recovery of round-reduced AES variants with numbers of rounds higher than those cryptanalyed before.”

The paper provides complexities for finding compression function preimages for all full versions of AES when considered in hash mode.

“We also provide complexities for finding compression function preimages for all full versions of AES when considered in hash mode.”

Since ∆K_i($10^10) = ∆K_i($10^14), the ciphertext bytes C10 and C14 are also always equal.

“Furthermore, since ∆ K i ($10 10 ) = ∆ K i ($10 14 ), the ciphertext bytes C 10 and C 14 are also always equal.”

C_recomp for AES-128 is equivalent to 2^16 • 3.4375/12.5 = 2^14.14 runs of the full AES-128.

“As a result, C recomp is equivalent to 2 16 •3.4375/12.5= 2 14.14 runs of the full AES-128.”

This yields the partition of the round-8 subkey space, and hence the AES key space, into the 2^112 groups of 2^16 keys each.

“This yields the partition of the round-8 subkey space, and hence the AES key space, into the 2 112 groups of 2 16 keys each.”

• AssumptionRests on an assumption: The AES-128 key schedule bijectively maps each key to subkey $8.

In the 8-round AES-128 long biclique attack, 2^80 bicliques with 104 fixed key bits are constructed in 2^88.

“It also dominates the complexity of other steps, so we construct 2 80 bicliques with 104 fixed key bits in 2 56+32 = 2 88 , and 2 102 bicliques in 2 88”

The 9-round AES-256 key recovery has computational complexity about 2^251.92.

“This approach for 9-round AES-256 yields a key recovery with computational complexity about 2 251.92 , data complexity 2 120 , memory complexity 2 8 , and success probability 1.”

The full cipher AES-128 has 10 + 2.5 = 12.5 SubBytes-equivalent operations when key schedule nonlinearity is taken into account.

“The latter number is 10 + 2.5 = 12.5 as we have to take the key schedule nonlinearity into account.”

As a result, the data complexity for the AES-192 attack does not exceed 2^80.

“As a result, the data complexity does not exceed 2 80 .”

Preimage search for the compression function of full AES-256 in Davies-Meyer mode requires 2^8 memory.

“Similarly, preimage search for the compression function of the full AES-256 in Davies-Meyer mode requires about 2 126.35 computations, 2 8 memory, and works with success probability 0.6321.”

As the ∆i and ∇j differentials share no active S-boxes, the resulting combined differentials yield a biclique of dimension 8.

“As they share no active S-boxes, the resulting combined differentials yield a biclique of dimension 8.”

In the 8-round AES-128 attack, each quartet has equal chance to be produced.

“On the other hand, each quartet has equal chance to be produced.”

The values C_biclique and C_precomp together do not exceed 2^8 calls of the full AES-128.

“The values C biclique and C precomp together do not exceed 2 8 calls of the full AES-128.”

Again, the ∆i- and ∇j-differential trails for AES-192 share no active S-boxes.

“Again, the ∆ i -and ∇ j -differential trails share no active S-boxes (Figure 7).”

In the 8-round AES-128 long biclique attack, the chance of getting a false positive is 2^-6 per biclique.

“The chance of getting a false positive is 4 • 2 -8 = 2 -6 per biclique.”

Since the ∆i-differential affects only 12 bytes of the ciphertext, all the ciphertexts share the same values in bytes C0,1,4,13.

“Since the ∆ i -differential affects only 12 bytes of the ciphertext, all the ciphertexts share the same values in bytes C 0,1,4,13 .”

The 8-round AES-128 attack does not guarantee that the quartets are pairwise different because the key bits are adaptively chosen.

“As the key bits are adaptively chosen in the attack, the algorithm does not guarantee that the quartets are pairwise different.”

The full area to be recomputed in the backward direction for AES-128 includes 41 S-boxes.

“The full area to be recomputed, which includes 41 S-boxes, is depicted in Figure 5.”

In the 8-round AES-128 long biclique attack, 2^102 bicliques are constructed in 2^88.

“It also dominates the complexity of other steps, so we construct 2 80 bicliques with 104 fixed key bits in 2 56+32 = 2 88 , and 2 102 bicliques in 2 88”

The total complexity of the 8-round AES-128 attack with 2^126 bicliques is about 2^124.97.

“Therefore, the total complexity of the attack with 2 126 bicliques is about 2 126 4/10.5 + 2 -9 + 1.125/10.5 = 2 124.97 .with 2 32 memory and 2 127 data.”

C_recomp for AES-192 is equivalent to 2^16 • 2.8125/14 = 2^13.68 runs of the full AES-192.

“As a result, C recomp is equivalent to 2 16 • 2.8125/14 = 2 13.68 runs of the full AES-192.”

For the AES-256 4-round biclique, the data complexity does not exceed 2^40.

“Therefore, the data complexity does not exceed 2 40 .”

The paper constructs a 3-round biclique from combined related-key differentials as described in Section 3.1.

“We construct a 3-round biclique from combined related-key differentials as described in Section 3.1.”

In the AES-256 4-round biclique key recovery, C_recomp is equivalent to 2^14.383 runs of the full AES-256.

“As a result, C recomp is equivalent to 2 16 • 5.625/17.25 = 2 14.383 runs of the full AES-256.”

In the 8-round AES-128 long biclique attack, Step 2(c) has time complexity 2^32.

“This gives the time complexity 2 32 and the memory complexity 2 16 .”

This yields the partition of the AES-256 key space into the 2^240 groups of 2^16 keys each.

“This yields the partition of the AES-256 key space into the 2 240 groups of 2 16 keys each.”

• AssumptionRests on an assumption: The AES-256 key schedule bijectively maps each key to $12||$13.

For a success probability of 63%, the second variant of the 8-round AES-128 attack produces 2^125.33 bicliques.

“For a success probability of 63% the second variant of the attack produces 2 125.33 bicliques in 2 124.3 time, and needs 2 126.33 chosen ciphertexts.”

In the backward direction for AES-128, the difference in subkey $5 is non-zero in only one byte, so one has to recompute as few as four S-boxes in round 5 (state #13).

“The difference in the subkey $5 is non-zero in only one byte, so we have to recompute as few as four S-boxes in round 5 (state #13).”

In the backward direction for AES-192, only six (instead of eight) S-boxes need recomputing in state #15 (round 8).

“As a result, only six (instead of eight) S-boxes needs recomputing in state #15 (round 8).”

Preimage search for the compression function of full AES-256 in Davies-Meyer mode requires about 2^126.35 computations.

“Similarly, preimage search for the compression function of the full AES-256 in Davies-Meyer mode requires about 2 126.35 computations, 2 8 memory, and works with success probability 0.6321.”

For a success probability of 63%, the second variant of the 8-round AES-128 attack runs in 2^124.3 time.

“For a success probability of 63% the second variant of the attack produces 2 125.33 bicliques in 2 124.3 time, and needs 2 126.33 chosen ciphertexts.”

Preimage search for the compression function of full AES-256 in Davies-Meyer mode works with success probability 0.6321.

“Similarly, preimage search for the compression function of the full AES-256 in Davies-Meyer mode requires about 2 126.35 computations, 2 8 memory, and works with success probability 0.6321.”

In the 8-round AES-128 long biclique attack, Step 2(c) has memory complexity 2^16.

“This gives the time complexity 2 32 and the memory complexity 2 16 .”

The full computational complexity of the AES-256 4-round biclique key recovery amounts to about 2^254.42.

“The full computational complexity amounts to about 2 240 • 2 9 + 2 14.383 = 2 254.42 .”

By a careful choice of key groups, one is able to reduce the precomputation proportion to a very small factor, e.g. factor 1/15 in attacks on reduced-round versions of AES-256.

“By a careful choice of key groups, one is able to reduce the precomputation proportion to a very small factor, e.g.factor 1/15 in attacks on reduced-round versions of AES-256.”

If quartets are tracked after the guess of three bytes of K5, the memory complexity of the 8-round AES-128 attack grows to 2^102.

“If we keep track of quartets in the loop after the guess of three bytes of K 5 , then the memory complexity grows to 2 102 .”

As a result, the data complexity for the AES-128 attack does not exceed 2^88.

“As a result, the data complexity does not exceed 2 88 .”

In the 8-round AES-128 long biclique attack, solutions for the Super-boxes are constructed online by substituting 2^32 input pairs to the super-box transformation and filtering out incorrect quartets.

“Solutions for the Super-boxes are constructed online by substituting 2 32 input pairs to the super-box transformation and filtering out incorrect quartets.”

The 9-round AES-256 key recovery has success probability 1.

“This approach for 9-round AES-256 yields a key recovery with computational complexity about 2 251.92 , data complexity 2 120 , memory complexity 2 8 , and success probability 1.”

In the 8-round AES-128 long biclique attack, Step 2(c) has complexity 2^32.

“Therefore, Step 2 (c) has complexity 2 32 .”

For the AES-256 4-round biclique, the ∆i-differential affects only 7 bytes of the ciphertext.

“The ∆ i -differential affects only 7 bytes of the ciphertext, and the key difference is equal in all non-zero bytes of $14.”

The 8-round AES-128 attack uses 2^127 data.

“Therefore, the total complexity of the attack with 2 126 bicliques is about 2 126 4/10.5 + 2 -9 + 1.125/10.5 = 2 124.97 .with 2 32 memory and 2 127 data.”

The 9-round AES-256 key recovery has data complexity 2^120.

“This approach for 9-round AES-256 yields a key recovery with computational complexity about 2 251.92 , data complexity 2 120 , memory complexity 2 8 , and success probability 1.”

The memory requirement for the AES-192 attack is upper-bounded by the storage of 2^8 full computations of g.

“The memory requirement is upper-bounded by the storage of 2 8 full computations of g.”

C_recomp is the complexity of the recomputation of the internal variable v 2^{2d} times; for AES this value varies from 2^{2d-1.5} to 2^{2d-4}.

“-C recomp is the complexity of the recomputation of the internal variable v 2 2d times.It strongly depends on the diffusion properties of the cipher.For AES this value varies from 2 2d-1.5 to 2 2d-4 .”

The full computational complexity of the AES-128 attack amounts to about 2^112(2^8 + 2^14.14 + 2^8) = 2^126.18.

“The full computational complexity amounts to about 2 112 2 8 + 2 14.14 + 2 8 = 2 126.18 .”

This yields the partition of the AES-192 key space by the 2^176 groups of 2^16 keys each.

“This yields the partition of the AES-192 key space by the 2 176 groups of 2 16 keys each.”

• AssumptionRests on an assumption: The AES-192 key schedule bijectively maps each key to $9||$10 L.

Altogether, for AES-192, one needs an equivalent of 2.8125 SubBytes operations compared to the equivalent of 14 in the full cipher (there are 8 key schedule rounds).

“Altogether, we need an equivalent of 2.8125 SubBytes operations compared to the equivalent of 14 in the full cipher (there are 8 key schedule rounds).”

The 8-round AES-128 attack algorithm generates a natural proportion of (1-1/e)=63% quartets.

“Therefore, we estimate that the algorithm generates a natural proportion of (1-1/e) = 63% quartets.”

The memory requirement for the AES-128 attack is upper-bounded by the storage of 2^8 full computations of g.

“The memory requirement is upper-bounded by the storage of 2 8 full computations of g.”

The 9-round AES-256 key recovery has memory complexity 2^8.

“This approach for 9-round AES-256 yields a key recovery with computational complexity about 2 251.92 , data complexity 2 120 , memory complexity 2 8 , and success probability 1.”

The memory requirement of the AES-256 4-round biclique key recovery is upper bounded by the storage of 2^8 full computations of g.

“The memory requirement is upper bounded by the storage of 2 8 full computations of g.”

The full computational complexity of the AES-192 attack amounts to about 2^172 • 2^9 + 2^13.68 = 2^189.74.

“The full computational complexity amounts to about 2 172 • 2 9 + 2 13.68 = 2 189.74 .”

In the 8-round AES-128 long biclique attack, most false positives require only round 2 to recompute, giving 2^-9 AES calls overhead on average.

“Most of false positives require only round 2 to recompute, which gives 2 -9 AES calls overhead on average, which is negligible compared to the matching phase.”

The 8-round AES-128 attack uses 2^32 memory.

“Therefore, the total complexity of the attack with 2 126 bicliques is about 2 126 4/10.5 + 2 -9 + 1.125/10.5 = 2 124.97 .with 2 32 memory and 2 127 data.”

Thanks to the low diffusion of the AES key schedule and sparsity of the key difference in round 8, the whitening subkeys of K[i,j] and K[i,0] differ in 9 bytes only.

“Thanks to the low diffusion of the AES key schedule and sparsity of the key difference in round 8, the whitening subkeys of K[i, j] and K[i, 0] differ in 9 bytes only.”

In Step 6 of the 9-round AES-256 attack, there are 72 neutral bits in $7.

“Therefore, we have 72 neutral bits in $7, and 136 neutral bits in total.”

In Step 6 of the 9-round AES-256 attack, there are 64 neutral bits in $6.

“Therefore, we have 128 -32 -32 = 64 neutral bits in $6.”

In total, 4.75 AES rounds per biclique are needed in the 9-round AES-256 attack.

“In total we need 4.75 AES rounds per biclique, i.e. 2 -0.92 9-round AES-256 calls.”

In Step 2(c) of the 9-round AES-256 attack, there are 2^120 solutions in total.

“Therefore, we have 2 64 solutions for each guess in the inbound phase, or 2 120 solutions in total.”

In the matching part of the 9-round AES-256 attack, 3.125 full rounds are spent per biclique.

“In the matching part we compute a single byte in two directions, thus spending 9/16 of a round in rounds 1-3, and full round 4, i.e. 3.125 full rounds per biclique.”

The use of bicliques with matching with precomputation results in recomputation in the innermost loop varying from about 1/3 to approximately 1/5 of the cipher depending on key size.

“The use of bicliques in combination with the technique of matching with precomputation, results in a surprisingly low recomputation in the innermost loop, varying from about 1/3 to approximately 1/5 of the cipher depending on the key size, while having data complexities of 2 88 , 2 80 and 2 40 plaintext-ciphertext pairs, respectively.”

The workload/success rate ratio of the 8-round AES-128 attack is 2^124.97.

“The workload/success rate ratio is thus 2 124.97 .”

The 9-round AES-256 attack needs 2^254 bicliques.

“We need 2 254 bicliques, so the total complexity is 2 253.1 .”

In Step 6 of the 9-round AES-256 attack, there are 136 neutral bits in total.

“Therefore, we have 72 neutral bits in $7, and 136 neutral bits in total.”

In Step 2(d) of the 9-round AES-256 attack, there is an 84-bit filter.

“Therefore, we get a 84-bit filter, and leave with 2 36 bicliques.”

In Step 2(c) of the 9-round AES-256 attack, there are 2^64 solutions for each guess in the inbound phase.

“Therefore, we have 2 64 solutions for each guess in the inbound phase, or 2 120 solutions in total.”

The total complexity of the 9-round AES-256 attack is 2^253.1.

“We need 2 254 bicliques, so the total complexity is 2 253.1 .”

For a success probability of 63%, the second variant of the 8-round AES-128 attack needs 2^126.33 chosen ciphertexts.

“For a success probability of 63% the second variant of the attack produces 2 125.33 bicliques in 2 124.3 time, and needs 2 126.33 chosen ciphertexts.”

In Step 2(b) of the 9-round AES-256 attack, the total number of guesses is 2^56.

“In total we make 2 7•(4+2•2) = 2 56 guesses.”

The complexity generated by false positives in the 9-round AES-256 attack is at most 2^-6 rounds per biclique.

“The complexity generated by false positives is at most 2 -6 rounds per biclique.”

In Step 2(d) of the 9-round AES-256 attack, 2^36 bicliques are left.

“Therefore, we get a 84-bit filter, and leave with 2 36 bicliques.”

In Step 2(e) of the 9-round AES-256 attack, a 16-bit filter reduces the number of bicliques to 2^20.

“This is a 16-bit filter, which reduces the number of bicliques to 2 20 .”

The 9-round AES-256 attack needs the equivalent of 2^-0.92 9-round AES-256 calls per biclique.

“In total we need 4.75 AES rounds per biclique, i.e. 2 -0.92 9-round AES-256 calls.”

The attacks do not threaten the practical use of AES in any way.

“As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.”

The paper presents a novel technique of block cipher cryptanalysis with bicliques.

“In this paper we present a novel technique of block cipher cryptanalysis with bicliques, which leads to the following results:”

AES is almost as secure as it was 10 years ago in the strongest and most practical model with a single unknown key.

“However, the block cipher standard AES is almost as secure as it was 10 years ago in the strongest and most practical model with a single unknown key.”

In contrast to most shortcut attacks on AES variants, the attacks do not need to assume related-keys.

“In contrast to most shortcut attacks on AES variants, we do not need to assume related-keys.”

The relatively slow diffusion in the AES key schedule allows the adversary to skip most recomputations of the key schedule operations.

“The relatively slow diffusion in the AES key schedule allows the adversary to skip most recomputations of the key schedule operations.”

Since ∆i- and ∇j-trails share no active non-linear elements, a boomerang based on them returns from the ciphertext with probability 1 as the quartet of states forms the boomerang rectangle at every step.

“Since ∆ i -and ∇ j -trails share no active non-linear elements, a boomerang based on them returns from the ciphertext with probability 1 as the quartet of states forms the boomerang rectangle at every step.”

The computational complexity of matching is upper bounded by 2^d computations of the cipher.

“Therefore, the computational complexity of matching is upper bounded by 2 d computations of the cipher.”

If matching on a single byte, the number of false positives is about 2^{2d-8}.

“If we match on a single byte, the number of false positives is about 2 2d-8 .”

The basic meet-in-the-middle attack has clear limitations in block cipher cryptanalysis since an internal variable with the required properties can be found for a very small number of rounds only.

“The basic meet-in-the-middle attack has clear limitations in the block cipher cryptanalysis since an internal variable with the properties listed above can be found for a very small number of rounds only.”

If all ∆i = ∇j, then all keys K[i,j] are different.

“If all ∆ i = ∇ j , then all keys K[i, j] are different.”

For |v| close to d and larger, a basic meet-in-the-middle attack has advantage of about 2^d over brute force search as it tests 2^{2d} keys with less than 2^d calls of the full cipher.

“For |v| close to d and larger an attack has advantage of about 2 d over brute force search as it tests 2 2d keys with less than 2 d calls of the full cipher.”

The paper demonstrates that meet-in-the-middle attacks on block ciphers have great potential if enhanced by a new concept called bicliques.

“In this paper we demonstrate that the meet-in-the-middle attacks on block ciphers have great potential if enhanced by a new concept called bicliques.”

The full key recovery in the long biclique approach is the application of Steps 1-3 2^{n-2d} times.

“Since the full key recovery is merely the application of Steps 1-3 2 n-2d times, we get the following equation:”

The independency of differentials limits the length of the biclique constructed.

“Though this approach turns out to be effective in case of AES, it is exactly the independency of differentials that limits the length of the biclique constructed.”

If the trails of ∆i-differentials do not share active nonlinear components with the trails of ∇j-differentials, then the tuple conforms to 2^{2d} combined (∆i, ∇j)-differentials.

“If the trails of ∆ i -differentials do not share active nonlinear components (such as active S-boxes in AES) with the trails of ∇ j -differentials, then the tuple also conforms to 2 2d combined (∆ i , ∇ j )differentials:”

In the long biclique paradigm, theoretically one can get the same advantage as the basic attack if one manages to construct a biclique of appropriate dimension.

“The first advantage of this approach is that theoretically we can get the same advantage as the basic attack if we manage to construct a biclique of appropriate dimension.”

In the long biclique paradigm, data complexity can be very large since all degrees of freedom are used to construct a biclique and may have nothing left to impose restrictions on plaintexts or ciphertexts.

“Furthermore, the data complexity can be very large since we use all the degrees of freedom to construct a biclique and may have nothing left to impose restrictions on the plaintexts or ciphertexts.”

The construction cost of a biclique can be amortized by producing many more out of a single one.

“We are also able to amortize the construction cost of a biclique by producing many more out of a single one.”

Having found a biclique, new ones can be produced out of it for other key groups.

“Having found a biclique, we produce new ones out of it for other key groups.”

The amount of recalculation in matching with precomputations depends on the diffusion properties of both internal rounds and the key schedule of the cipher.

“The amount of recalculation depends on the diffusion properties of both internal rounds and the key schedule of the cipher.”

Matching with precomputations can provide significant computational advantage due to amortized complexity.

“Here we describe the idea of matching with precomputations that can provide significant computational advantage due to amortized complexity.”

Generally, the complexity of the long biclique approach is dominated by C_match and hence has an advantage of at least 2^d over brute-force.

“Generally, the complexity is dominated by C match and hence has an advantage of at least 2 d over brute-force.”

C_match is upper bounded by 2^d calls of E.

“-C match is the complexity of the computation of the internal variable v 2 d times in each direction.It is upper bounded by 2 d calls of E.”

Since the coverage of the key space by groups around base keys is complete, the success probability for the AES-128 attack is 1.

“Since the coverage of the key space by groups around base keys is complete, the success probability is 1.”

Since the meet-in-the-middle attack is no longer applicable to E2 • E1, matching with precomputations is applied.

“Since the meet-in-the-middle attack is no longer applicable to the E 2 • E 1 , we apply the matching with precomputations (Section 3.3).”

The memory complexity of the key recovery in the independent biclique paradigm is upper-bounded by storing 2^d full computations of the cipher.

“The memory complexity of the key recovery is upper-bounded by storing 2 d full computations of the cipher.”

C_precomp is equivalent to less than 2^d runs of the subcipher g.

“-C precomp is the complexity of the precomputation in Step 3. It is equivalent to less than 2 d runs of the subcipher g.”

Since the biclique area is small, the attack designer has more freedom to impose constraints on the ciphertext and hence restrict it to a particular set.

“Since the biclique area is small, the attack designer has more freedom to impose constraints on the ciphertext and hence restrict it to a particular set.”

In the independent biclique paradigm, 2^{2d} keys are tested using only 2^d intermediate cipher states.

“As in the long biclique paradigm, 2 2d keys are tested using only 2 d intermediate cipher states.”

Therefore, the full key recovery complexity in the independent biclique paradigm is dominated by 2^{n-2d} • C_recomp.

“Therefore, the full key recovery complexity is dominated by 2 n-2d • C recomp .”

The biclique construction is quite cheap in the independent biclique paradigm.

“The biclique construction is quite cheap in this paradigm.”

In the independent biclique paradigm, data complexity can be made quite low.

“First, the data complexity can be made quite low.”

The data complexity of key recovery can be significantly reduced by sacrificing only a small factor of computational advantage.

“We notice that the data complexity of key recovery can be significantly reduced by sacrificing only a small factor of computational advantage.”

The round transformation of AES is not designed to have strong resistance against several classes of attacks for a smaller number of rounds.

“The round transformation of AES is not designed to have strong resistance against several classes of attacks for a smaller number of rounds.”

In all cases, the computational complexity of the attacks with long bicliques is considerably lower than generic attacks.

“Again, in all cases we arrive at a computational complexity that is considerably lower than generic attacks.”

• AssumptionRests on an assumption: No generic methods are known that would speed up key-recovery attacks given a part of the codebook.

The biclique approach heavily relies on the existence of high-probability related-key differentials over a part of the cipher.

“Our approach heavily relies on the existence of high-probability related-key differentials over a part of the cipher.”

The authors verified the complexity estimate of the long-biclique construction.

“We verified the complexity estimate, and also give an example of a biclique in Table 7 in the Appendix.”

In all cases, the computational complexity of the attacks with independent bicliques is considerably lower than generic attacks.

“In all cases we arrive at a computational complexity that is considerably lower than generic attacks.”

• AssumptionRests on an assumption: No generic methods are known that would speed up key-recovery attacks given a part of the codebook.

The authors verified that some difference guesses must be equal like in the AES-256 attack due to the branch number of MixColumns that results in the correlation of differences in the outbound phase.

“-We verified that some difference guesses must be equal like in the AES-256 attack due to the branch number of MixColumns that results in the correlation of differences in the outbound phase.”

In the AES key schedule, there is relatively slow backwards diffusion.

“In the key schedule, we especially take advantage of the relatively slow backwards diffusion.”