Biclique Cryptanalysis AES User Manual

Page 1

Biclique Cryptanalysis of the Full AES

Andrey Bogdanov⋆, Dmitry Khovratovich , and Christian Rechberger

K.U. Leuven, Belgium; Microsoft Research Redmond, USA; ENS Paris and Chaire France Telecom, France

Abstract. Since Rijndael was chosen as the Advanced Encryption Standard, improving upon 7-round attacks on the 128-bit key variant or upon 8-round attacks on the 192/256-bit key variants h as been one of the most diﬃcult challenges in the cryptanalysis of block ciphers for more than a decade. In this paper we present a novel technique of block cipher cryptanalysis with bicliques, which leads to the following results:

– The ﬁrst key recovery attack on the full AES-128 with computational complexity 2 – The ﬁrst key recovery attack on the full AES-192 with computational complexity 2 – The ﬁrst key recovery attack on the full AES-256 with computational complexity 2 – Attacks with lower complexity on the reduced-round versions of AES not considered before,

including an attack on 8-round AES-128 with complexity 2

– Preimage attacks on compression functions based on the full AES versions. In contrast to most shortcut attacks on AES variants, we do not need to assume related-keys. Most of our attacks only need a very small part of the codebook and have small memory requirements, and are practically veriﬁed to a large extent. As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way. Keywords: block ciphers, bicliques, AES, key recovery, preimage

124.9

⋆

126.1

189.7

254.4

. . .

1 Introduction

The block cipher AES (Advanced Encryption Standard) is a worldwide standard and one of the most popular cryptographic primitives. Designed in 1997, AES has survived numerous cryptanalytic eﬀorts. Though m any 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]. For all versions of AES, the number of cryptanalyzed rounds did not increase since then (7 for AES-128, 8 for AES-192 and AES-

256), only a decrease in the computational complexity of the key recovery was achieved. In general, the last ten years saw some p rogress in the cryptanalysis of block ciphers. 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. The former standard DES has not seen a major improvement since Matsui’s seminal paper in 1993 [34].

In contrast, the area of hash function cryptanalysis is growing quickly, encouraged by the cryptanalysis MD5 [43], of SHA-0 [6, 13] and SHA-1 [42], followed by a practical attack on protocols using MD5 [39, 40], preimage attacks on Tiger [26] and MD5 [38], etc. As diﬀerential cryptanalysis [7], a technique originally developed for ciphers, was carried over to hash function analysis, cryptanalysts are now looking for the opposite: a hash analysis method that would give new results on block ciphers. So far the most well-known attempt is the an alysis of AES with local collisions [8–11], but it is only applicable to the relatedkey model. In the latter model an attacker works with plaintexts and ciphertexts that are produced under not only the unknown key, but also under other keys related to the ﬁrst one in a way chosen by the adversary. Such a strong requirement is rarely practical and, thus, has not been considered to be a threat for the use of AES. Also, there has been no evidence

⋆

The authors were visiting Microsoft Research Redmond while working on these results.

Page 2

that the local collision approach can facilitate an attack in the more practical and relevant single-key model.

State of the art for attacks on AES. AES with its wide-trail strategy was designed to withstand diﬀerential and linear cryptanalyses [15], so pure versions of these techniques have limited applications in attacks. With r espect to AES, probably the most powerful singlekey recovery methods designed so far are impossible diﬀerential cryptanalysis [5, 33] and Square attacks [14, 20]. The imp ossible diﬀerential cryptanalysis yielded the ﬁrst attack on 7-round AES-128 with non-marginal data complexity. The Square attack and its variations such as integral attack and multiset attack resulted in the cryptanalysis of round-reduced AES variants with lowest computational complexity to date, while the ﬁrst attack on 8-round AES-192 with non-marginal data complexity has appeared only recently [20].

The s itu ation is diﬀerent in weaker attack models, where the related-key cryptanalysis was applied to the full versions of AES-192 and AES-256 [9], and the rebound attack demonstrated a non-random property in 8-round AES-128 [25,30]. However, there is little evidence so far that carrying over these techniques to the most practical single-secret-key m odel is feasible.

Meet-in-the-middle atta cks with bicliques. Meet-in-the-middle attacks on block ciphers did get less attention (exceptions are [12, 19, 22, 27, 44]) than the diﬀerential, linear, impossible diﬀerential, and integral approaches. However, they are probably the most practical in terms of data complexity. A simple meet-in-the-middle attack requires only a single plaintext/ciphertext pair. The limited use of these attacks must be attributed to the requirement for large parts of the cipher to be independent of particular key bits. For the ciphers with nonlinear key schedule, like AES and most AES candidates, this requirement is apparently strong. As a result, the number of rounds broken with this technique is rather small [19], which seems to prevent it from producing r esults on yet unbroken 8-, 9-, and 10-round (full) AES. We also mention that the collision attacks [17, 18] use some elements of the meet-in-the-middle framework.

In this paper we demonstrate that the meet-in-the-middle attacks on blo ck ciphers have great potential if enhanced by a new concept called bicliques. Biclique cryptanalysis was ﬁrst introduced for hash cryptanalysis [29]. The new approach originates from the so-called spliceand-cut framework [1, 2,26] in th e h ash function cryptanalysis, more speciﬁcally its element called initial structure. Formally introduced in [29], bicliques led to the best p reimage attacks on the SHA family of hash functions, including the attack on 50 rounds of SHA-512, and the ﬁrst attack on a round-reduced Skein hash function. We show how to carry over the concept of b icliques to block cipher cryptanalysis and get even more signiﬁcant results, including the ﬁrst key recovery method for the full AES faster than brute-force.

A b iclique is characterized by its length (number of rounds covered) and dimension. The dimension is related to the cardinality of the biclique elements and is one of the factors that determines the advantage over brute-force. Moreover, the construction of long bicliques of high dimension appears to be a very diﬃcult task for primitives with fast diﬀusion [37].

Two paradigms for key recove ry with bicliques. Taking the biclique properties into account, we propose two diﬀerent approaches, or paradigms, for the key-recovery attack. Suppose that the ciph er admits the basic meet-in-the-middle attack on m (out of r) rounds. The ﬁrst paradigm, the long biclique, aims to constr uct a biclique for the remaining r − m rounds. Though the dimension of the biclique decreases as r grows, small-dimension bicliques

Page 3

can be constructed with numerous tools and methods from diﬀerential cryptanalysis of block ciphers and hash functions: rebound attacks, trail backtracking, local collisions, etc. Also from an information-theoretic point of view, bicliques of dimension 1 are likely to exist in a cipher, regardless of the number of rounds.

The s econd paradigm, the independent biclique, aims to construct bicliques of high dimension for smaller b < r − m number of rounds eﬃciently and cover the remaining rounds with a new method of matching with precomputations. Smaller number of rounds also makes use of simp ler tools for the biclique construction. This paradigm is best suited for ciphers with diﬀusion that is slow with respect to r − m rounds, surprisingly, including AES.

Results on AES. The biclique cryptanalysis successfully applies to all full versions of AES and compared to brute-force pr ovides 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 attacks with lowest computational complexities follow the paradigm of independent bicliques and have success rate 1. We also provide complexities for ﬁnding compression function preimages for all full versions of AES when considered in hash mode. Our results on AES are summarized in Table 2, and an attempt to give an exhaustive overview with earlier results is given in Table 6 in the Appendix.

Table 1. Biclique key recovery for AES

rounds data computations/succ.rate memory biclique length in rounds

AES-128 secret key recovery

124.97

125.64

125.34

126.18

AES-192 secret key recovery

188.8

189.74

AES-256 secret key recovery

253.1

251.92

254.42

102

5 5 3 3

4 4

6 4 4

8 2 8 2 8 2

10 2

9 2

12 2

9 2 9 2

14 2

126.33

127

120

Table 2. Biclique cryptanalysis of AES in hash modes

rounds computations succ.rate memory biclique length in rounds

AES-128 compression function preimage, Miyaguchi-Preneel

10 2

12 2

14 2

125.83

AES-192 compression function preimage, Davies-Meyer

125.71

AES-256 compression function preimage, Davies-Meyer

126.35

0.632 2

Page 4

2 Biclique Cryptanalysis

2.1 Basic Meet-in-the-Middle Attacks

An adversary chooses a p artition of the key space into groups of keys of cardinality 22deach for some d. A key in a group is indexed as an element of a 2d× 2dmatrix: K[i, j]. The adversary selects an internal variable v in the data trans form of the cipher such that

– as a function of a plaintext and a key, it is identical for all keys in a row:

K[i,·]

−−−→

– as a function of a ciphertext and a key, it is identical for all keys in a column:

←−−−

where f1and f2are the corresponding parts of the cipher.

Given a pair (P, C), an adversary computes 2dpossible values−→v and 2dpossible values

←−

v from the plaintext and from the ciphertext, respectively. A matching pair−→vi=←−vjyields a key candidate K [i,j]. The number of key candidates depends on the bit size |v| of v and is given by the formula 2

2d−|v|

. For |v| close to d and larger an attack has advantage of about

2dover brute force search as it tests 22dkeys w ith less than 2dcalls of the full cipher.

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. We show how to bypass this obstacle with the concept of a biclique.

K[·,j]

2.2 Bicliques

Now we introduce the notion of a biclique. Let f be a subcipher th at maps an internal state S to the ciphertext C : fK(S) = C . According to (2), f connects 2dinternal states {Sj} to 2dciphertexts {Ci} with 22dkeys {K [i,j]}:





K[0, 0] K[0, 1] . . . K[0, 2d− 1]

{K[i, j]} =



. . .



K[2d− 1, 0] K[2d− 1, 1] . . . K [2d− 1, 2d− 1]

The 3-tuple [{Ci}, {Sj}, {K[i, j]}] is called a d-dimensional biclique, if

Ci= f

(Sj) for all i, j ∈ {0, . . . , 2d− 1}. (1)

K[i,j]

In other words, in a biclique, the key K[i, j] maps the internal state Sito the ciphertext C and vice versa. This is illustrated in Figure 1.

2.3 The Flow of Biclique Cryptanalysis

Preparation. An adversary chooses a partition of the key space into groups of keys of

cardinality 22deach for some d and considers the block cipher as a composition of two subciphers: e = f ◦ g, where f follows g. A key in a group is indexed as an element of a 2d× 2dmatrix: K[i, j].

Page 5

S0S

K[0, 0] K[2d− 1, 2d− 1]

C0C

Fig. 1. d-dimensional biclique

. . .

2d−1

Step 1. For each group of keys the adversary builds a str ucture of 2dciphertexts Ciand 2dintermediate states Sjwith r espect to the group of keys {K [i,j]} so that the partial decryption of Ciwith K[i, j] yields Sj. In other words, the structure satisﬁes the following condition:

∀i, j : S

K[i,j]

−−−→fCi. (2)

Step 2. The adversary asks the oracle to decrypt ciphertexts Ciwith the secret key K

secret

and obtains the 2dplaintexts Pi:

decryption oracle

−−−−−−−−−−→

−1

Step 3. If one of tested keys K [i, j] is the secret key K

Pi. (3)

, then it maps intermediate state

secret

Sjto the plaintext Pi. Therefore, the adversary checks if

∃i, j : P

K[i,j]

−−−→gSj, (4)

which proposes a key candidate.

3 New Tools and Techniques for Bicliques

In here we describe two approaches to construct bicliques, and propose a precomputation technique that can speed-up the application of bicliques for key-recovery. The exposition is mainly independent of any concrete cipher.

3.1 Bicliques from Independent Related-Key Diﬀerentials

A straightforward approach to ﬁnd a d-dimensional biclique would be to ﬁx 2dstates and 2 ciphertexts, and derive a key for each pair to satisfy (2). This would require at least 22dkey recovery attempts for f . A much more eﬃcient way for th e adversary is to choose the keys in advance and require them to conform to speciﬁc diﬀerentials as follows.

Let the key K[0, 0] map intermediate state S0to ciphertext C0, and consider two sets of

2drelated key diﬀerentials each over f with respect to the base computation S

K[0,0]

−−−−→ C0:

– ∆i-diﬀerentials. A diﬀerential in the ﬁrst set maps input diﬀerence 0 to an output

diﬀerence ∆iunder key diﬀerence ∆

∆

7−−→f∆iwith ∆

= 0 and ∆0= 0. (5)

Page 6

– ∇j-diﬀerentials. A diﬀerential in the second set maps an input diﬀerence ∇jto ou tput

diﬀerence 0 under key diﬀerence ∇

∇

7−−→f0 with ∇

= 0 and ∇0= 0. (6)

The tuple (S0, C0, K[0, 0]) conforms to both sets of diﬀerentials by deﬁn ition. If the trails of ∆i-diﬀerentials do not share active nonlinear components (such as active S-boxes in AES)

with the trails of ∇j-diﬀerentials, then the tuple also conforms to 22dcombined (∆i, ∇j)diﬀerentials:

∆

⊕∇

7−−−−−−→f∆ifor i, j ∈ {0, . . . , 2d− 1}. (7)

∇

The proof follows from the theory of boomerang attacks [41] and particularly from the concept of the S-box switch [9] and a sandwich attack [21]. 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.

Substituting S0, C0, and K[0, 0] to the combined diﬀerentials (7), one obtains:

⊕∇

S0⊕ ∇

K[0,0]⊕∆

−−−−−−−−−−→fC0⊕ ∆i. (8)

Finally, we put

Sj= S0⊕ ∇j, Ci= C0⊕ ∆i, and K[i, j] = K[0, 0] ⊕ ∆

K i

⊕ ∇

K j

and get exactly the deﬁnition of a d-dimensional biclique (1). If all ∆i6= ∇j, then all keys K[i, j] are diﬀerent. The construction of a biclique is thus reduced to the computation of ∆

and ∇j, which requires no more than 2 · 2dcomputations of f .

The independency of the related-key diﬀerentials allows one to eﬃciently construct higherdimensional bicliques and simpliﬁes the coverage of the key space with such bicliques. Though this approach turns out to be eﬀective in case of AES, it is exactly the independency of differentials that limits the length of the biclique constructed.

3.2 Bicliques from Interleaving Related-Key Diﬀerential Trails

To construct longer bicliques, we drop the diﬀerential independency requirement imposed above and reduce the dimension of the resulting biclique. The diﬀerential trails share some active nonlinear components now. This yields conditions on values that need to be satisﬁed in a biclique search.

We outline here how bicliques of dimen sion 1 can be constructed in terms of diﬀerentials and diﬀerential trails with a procedure resembling the rebound attack [35]. We are also able to amortize the construction cost of a biclique by producing many more out of a single one. The construction algorithm is outlined as follows for a ﬁxed key group {K[0, 0], K[0, 1], K[1, 0], K[1, 1]}, see also Figure 2:

– Intermediate state T . Choose an intermediate state T in subcipher f (over which the

biclique is constructed). The position of T splits f into two parts : f = f2◦ f1. f1maps

from Sjto T . f2maps from T to Ci.

Page 7

– ∆- and ∇-trails. Choose some truncated related-key diﬀerential trails: ∆-trails over f

? ?

0,0

1,1

1,0

0,1

Guess

diﬀerence

in computations

Resolve in the middle

Construct solutions

1 2 (a-c) 2 (d-e)

and ∇-trails over f2.

– Inbound phase. Guess the diﬀerences in the diﬀerential trails up to T . Get the values

of T th at satisfy the input and output diﬀerences over f .

– Outbound phase. Use the remaining degrees in freedom in the state to sustain diﬀerence

propagation in trails.

– Output the states for the biclique.

For longer keys some bicliques are ﬁltered out. Having found a biclique, we produce new ones out of it for other key groups.

Numerous optimizations of the outlined biclique construction algorithm are possible. For instance, it is not necessary to guess all diﬀerences in the trail, but only part of them, and subsequently ﬁlter out the solutions. Instead of ﬁxing the key group, it is also possible to ﬁx only the diﬀerence between keys and derive actual values dur ing the attack (the disadvantage of this approach is that key groups are generated online, and we have to take care of possible repetitions).

We stress here that when ever we speak of diﬀerences between keys, these describe diﬀerences inside the group of keys that are guessed. We never need access to decryptions under keys that are related by those diﬀerences, i.e. the attacks we describe are always in the single-key model.

Fig. 2. Construction of a 1-dimensional biclique from dependent related-key diﬀerential trails: Guess diﬀerence between computations and derive states Sjand ciphertext Cias conforming elements.

3.3 Matching with Precomputations

Here we describe the idea of matching with precomputations that can provide signiﬁcant computational advantage due to amortized complexity. This can be seen as an eﬃcient way of checking equation (4) in the basic ﬂow of biclique cryptanalysis.

First, the adversary computes and stores in memory 2 · 2dfull computations

for all i P

K[i,0]

−−−→−→v and for all j←−v

up to some matching variable v, which can be a small part of the internal cipher s tate. Then for particular i, j he recomputes only those parts of the cipher that diﬀer from the s tored ones:

K[0,j]

←−−−− S

Page 8

The amount of recalculation depends on the diﬀu sion properties of both internal rounds and the key schedule of the cipher. The relatively slow diﬀusion in the AES key schedule allows the adversary to skip most recomputations of the key schedule operations.

4 Two Paradigms of Key Recovery

We have introduced diﬀerent approaches to construct bicliques and to perform matching with precomputations. One may ask which approach is optimal and relevant. We have studied several block ciphers and hash functions, including diﬀerent variants of AES, and it turns out that the optimal choice depends on a primitive, its diﬀusion properties, and features of the key schedule. This prepares the case to introduce two paradigms for key recovery, which diﬀer both methodologically and in their use of tools.

To put our statement in context, let us consider the basic meet-in-the-middle attack (Section2.1) and assume that it can be applied to m rounds of a primitive, while we are going to attack r > m rounds.

4.1 Long Bicliques

Our ﬁrst paradigm aims to construct a biclique at the remaining (r − m) rounds so that the basic meet-in-the-middle attack can be applied with negligible modiﬁcation. The ﬁrst 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. If the dimension is inevitably s mall due to the diﬀusion, then we use the second advantage: the biclique construction methods based on diﬀerential cryptanalysis of block ciphers and hash fu nctions.

The disadvantage of this paradigm is that the construction of bicliques for many rounds is very diﬃcult. Therefore, we are limited in the total number of rounds th at we can attack. Furthermore, the data complexity can be very large since we use all the d egrees of freedom to constr uct a biclique and may have nothing left to impose restrictions on the plaintexts or ciphertexts.

Nevertheless, we expect this paradigm to beneﬁt from the further development of diﬀerential cryptanalysis and the inside-out strategy and predict its applicability to many other ciphers.

Hence, to check (4) the adversary selects an internal variable v ∈ V that can be computed as follows for each key group {K[i, j]}:

K[i,·]

−−−→

K[·,j]

←−−−

S. (9)

Therefore, the computational complexity of matching is upper bounded by 2dcomputations of the cipher.

Page 9

key

plaintext ciphertext

K[4, 4]

K[1, 1]

K[i, ∗] K[∗, j]

K[i, j]

K[∗, 4]

K[∗, 1]

Decryption

oracle

K[4, ∗]

K[1, ∗]

Fig. 3. Long biclique attack with four states an d four ciphertexts.

Complexity of Key Recovery Let us evaluate the full complexity of the long biclique approach. Since the full key recovery is merely the application of Steps 1-3 2

n−2d

times, we

get the following equation:

= 2

n−2d

biclique

+ C

match

+ C

falsepos

] ,

full

where

– C

biclique

is the complexity of constructing a single biclique. Since the diﬀerential-based method is time-consuming, one has to amortize the construction cost by selecting a proper set of neutral bytes that do not aﬀect the biclique equations.

– C

is the complexity of the computation of the internal variable v 2dtimes in each

match

direction. It is upper bounded by 2dcalls of E.

– C

falsepos

is the complexity generated by false positives, which have to be matched on

other variables. If we match on a single byte, the number of false positives is ab ou t

2d−8

. Each requ ires only a few operations to re-check.

Generally, the complexity is dominated by C

and hence has an advantage of at least 2

match

over brute-force. The memory complexity depends on the biclique construction procedure.

4.2 Independent Bicliques

Our second paradigm lets the attacker exploit the diﬀusion properties rather than diﬀerential, and does not aim to construct the longest biclique. In contrast, it proposes to construct shorter bicliques with high dimension by tools like independent related-key diﬀerentials (Section 3.1).

This approach has clear advantages. First, the data complexity can be made quite low.

Since the biclique area is small, the attack designer h as more freedom to impose constraints on the ciphertext and hence restrict it to a particular set. Secondly, the attack gets a compact and small description, since the independent trails are generally short and self-explaining.

For the further explanation, we r ecall the decomposition of the cipher:

E : P −→

V −→

S −→

Page 10

In (4), th e adversary detect the right key by computing an intermediate variable v in both directions:

K[i,j]

−−−→

−→

v?=←−v

K[i,j]

←−−−

Sj. (10)

Since the meet-in-the-middle attack is no longer applicable to the E2◦ E1, we apply the matching with precomputations (Section 3.3).

As in the long b iclique paradigm, 22dkeys are tested using only 2dintermediate cipher

states. Th e precomputation of about 2

d+1

matches allows for a signiﬁcant complexity gain and is the major source of the computational advantage of our attacks on AES. The advantage comes from th e fact that in case of high dimension th e basic computation has negligible cost, and the full complexity is determined by the amount of precomputation. By a careful choice of key groups, one is able to redu ce the precomputation proportion to a very small factor, e.g. factor 1/15 in attacks on reduced-round versions of AES-256.

Complexity of Key Recovery The full complexity of the independent biclique approach is evaluated as follows:

= 2

n−2d

biclique

+ C

precomp

+ C

recomp

+ C

falsepos

] ,

full

where

– C

precomp

is the complexity of the precomputation in Step 3. It is equivalent to less than

2druns of the subcipher g.

– C

recomp

is the complexity of the recomputation of the internal variable v 22dtimes. It

strongly depends on the diﬀusion properties of the cipher. For AES this value varies from

2d−1.5

to 2

2d−4

The biclique construction is quite cheap in this p arad igm. The method in Section 3.1 enables construction of a biclique in only 2 complexity is dominated by 2

n−2d

d+1

calls of subcipher f. Therefore, the full key recovery

· C

. We give more details for the case of AES in

recomp

further sections. The memory complexity of the key recovery is upper-bounded by storing 2dfull computations of the cipher.

5 Description of AES

AES is a block cipher with 128-bit internal state and 128/192/256-bit key K (AES-128, AES-192, AES-256, respectively). The internal state is represented by a 4 × 4 byte matrix, and the key is represented by a 4 × 4/4 × 6/4 × 8 matrix.

The encryption works as follows. The plaintext is xored with the key, and then undergoes a sequence of 10/12/14 round s. Each round consists of f ou r transformations: nonlinear bytewise SubBytes, the byte permutation S hiftRows, linear transformation MixColumns, and the addition with a subkey AddRoundKey. MixColumns is omitted in the last round.

SB is a nonlinear transformation operating on 8-bit S-boxes with maximum diﬀerential probability as low as 2−6(for most cases 0 or 2−7). The ShiftRows rotates bytes in row r by r positions to the left. The MixColumns is a linear transformation with branch number 5, i.e. in the column equation (y0, y1, y2, y3) = MC(x0, x1, x2, x3) only 5 and more variables can be non-zero.

We address two internal states in each round as follows in AES-128: #1 is the state before SubBytes in round 1, #2 is the state after MixColumns in round 1, #3 is the state before

Page 11

SubBytes in round 2, . . ., #19 is the state before SubBytes in round 10, #20 is the state

after ShiftRows in round 10 (MixColumns is omitted in the last round). The states in the last round of AES-192 are addressed as #23 and #24, and of AES-256 as #27 an d #28.

The su bkeys come out of the key schedule procedure, which slightly diﬀers for each version of AES. The key K is expanded to a sequence of keys K0, K1, K2, . . . , K10, which form a 4×60 byte array. Then the 128-bit subkeys $0, $1, $2, .. . , $14 come out of the sliding window with a 4-column step. The keys in the expanded key are formed as follows. First, K0= K . Then, column 0 of Kris the column 0 of K the last column of K and of column i of K

r−1

. Subsequently, column i of Kris the xor of column i − 1 of K

r−1

. In AES-256 column 3 undergoes SubBytes transformation while

r−1

xored with the nonlinear fun ction (SK) of

r−1

forming column 4.

Bytes within a state and a subkey are enumerated as follows

Byte i in state Q is addressed as Qi.

6 Independent Bicliques: Key Recovery for the Full AES-128

Table 3. Parameters of the key recovery for the full AES-128

f Biclique

Rounds Dimension ∆Kbytes ∇Kbytes Time Memory

8-10 8 $88, $812$81, $8

Matching

g Precomputation Recomputation

Rounds v Workload Memory SubBytes: forward SubBytes: backward

1-7 #5

8−ε

0.875 2.625

Total complexity

Memory C

biclique

precompCrecomp

14.14

f alsepos

126.18

f ull

6.1 Key Partitioning

For more clarity we deﬁne the key groups with respect to the subkey $8 of round 8 and enumerate the groups of keys by 2

112

base keys. Since the AES-128 key schedule bijectively

maps each key to $8, the enumeration is well-deﬁned. The base keys K [0,0] are all possible

112

16-byte values with two bytes ﬁxed to 0 whereas the remaining 14 bytes run over all

values:

The keys {K[i, j]} in a grou p are enumerated by all possible byte diﬀerences i and j with respect to the base key K[0, 0]:

Page 12

This yields the partition of the round-8 subkey space, and hence the AES key space, into

112

the 2

groups of 216keys each.

6.2 3-Round Biclique of Dimension 8

We constr uct a 3-round biclique from combined related-key diﬀerentials as described in Section 3.1. The parameters of th e key recovery are sum marized in Table 3. The adversary

−1

ﬁxes C0= 0 and derives S0= f the diﬀerence ∆

in $8, and ∇j-diﬀerentials are based on the diﬀerence ∇

∆

($8) =

(C0) (Figure 13, left). The ∆i-diﬀerentials are based on

K[0,0]

and ∇

($8) =

K j

in $8:

Both sets of diﬀerentials are depicted in Figure 13 in the truncated form. As they share no active S-boxes, the resulting combined diﬀerentials yield a biclique of dimension 8.

Since the ∆i-diﬀerential aﬀects only 12 bytes of the ciphertext, all the ciphertexts share the same values in bytes C

. Furthermore, since ∆

0,1,4,13

($1010) = ∆

($1014), the ciph er text

bytes C10and C14are also always equal. As a result, the data complexity does not exceed

288.

base

computation

Step 2. Add ∆ito the key

SB SR MC

SB SR

key schedulekey schedule

$10

Step 1. Start with C0= 0

∆i-diﬀerentials ∇j-diﬀerentials

∆

SB SR MCMC

key schedulekey schedule

SBSB SRSR

Step 3. Add ∇jto the key

∇

key schedulekey schedule

SBSB SRSR

MCMC

SB SR

Sj, #15

#16

#17

#18

#19

#20

Fig. 4. AES-128 biclique from combined diﬀerentials: base computation as well as ∆i- and ∇j-diﬀerentials.

Page 13

biclique

$6$7

∆

recomputed

#5#6#7#8#9#10#11#12#13#14#15

←−

K j

Forward computation. Now we ﬁgure out how the computation P

stored one P

K[i,0]

−−−→−→vi. Similarly, it is determined by the inﬂu ence of the diﬀerence between

Fig. 5. Recomputation in the backward direction: AES-128

K[i,j]

−−−→−→v diﬀers from the

keys K[i, j ] and K [i,0], now applied to the plaintext. Thanks to the low diﬀusion of the AES key schedule and sparsity of the key diﬀerence in round 8, the whitening subkeys of K[i, j] and K[i, 0] diﬀer in 9 bytes only. The diﬀerence is no longer a linear function of j as it is in the computation of←−v , but still requires only three s-boxes in the key schedule to recompute. The areas of internal states to be recomputed (with 13 S-boxes) are depicted in Figure 6.

biclique

oracle &

decryption

MCMCSRSRSB

Fig. 6. Recomputation the forward direction: AES-128

#5#4#3#2#1

∇

recomputed

−→

6.3 Matching over 7 Rounds

Now we check whether the secret key K to Section 3.3. We make 2

d+1

precomputations of v and store values as well as the interme-

belongs to the key group {K[i, j]} according

secret

diate states and subkeys in memory. Then we check (10) for every i, j by recomputing only those variables that diﬀer from the ones stored in memory. Now we evaluate the amount of recomputation in both directions.

Backward direction. Let us ﬁgure out how the computation←−v

stored one←−v

K[0,j]

←−−−− Sj. It is determined by the inﬂuence of the diﬀerence between keys

K[i,j]

←−−− Sjdiﬀers from the

K[i, j] and K[0, j] (see the deﬁnition of the key group in Section 6.1). The diﬀerence 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). The full area to be recomputed, which includes 41 S-boxes, is depicted in Figure 5. Note that the diﬀerence in the relevant subkeys is a linear fu nction of i, and hence can be precomputed and stored.

Forward computation. Now we look at how the computation P

stored one P

K[i,0]

−−−→−→vi. Similarly, it is determined by the inﬂu ence of the diﬀerence between

K[i,j]

−−−→−→v diﬀers from the

keys K[i, j ] and K [i,0], now applied to the plaintext. Thanks to the low diﬀusion of the AES key schedule and sparsity of the key diﬀerence in round 8, the whitening subkeys of K[i, j] and K [i,0] diﬀer in 9 bytes only. The diﬀerence is no longer a linear function of j as it is involved into the computation of←−v , but still requires only three S-boxes in the key schedule to recompute. This eﬀect and the areas of internal states to be recomputed (with 13 S-boxes) are depicted in Figure 6.

Page 14

6.4 Complexities

Since only a portion of the round function is recomputed, one has to be highly accurate in evaluating the complexity C

. A r ou gh division of AES-128 into 10 rounds is not precise

recomp

enough. For a more exact evaluation, we count the number of S-boxes in each SubBytes operation that we have to recompute, the number of active variables in MixColumns, the number of output variables that we need from MixColumns, and, ﬁnally, the number of S-boxes to recompute in the key schedule.

Altogether, we need an equivalent of 3.4375 SubBytes operations (i.e., 55 S-boxes), 2.3125 MixColumns operations, and a negligible amount of XORs in the key schedule. The number of SubBytes computations clearly is a larger summand. S-boxes are also the major contributor to the practical complexity of AES both in hardware and software. Therefore, if we aim for a single number that refers to the complexity, it makes sense to count the number of Su bBytes operations that we need an d compare it to that in the full cipher. The latter number is 10 + 2.5 = 12.5 as we have to take the key schedule nonlinearity into account. As a result,

recomp

and C

is equivalent to 216·3.4375/12.5 = 2

precomp

together do not exceed 28calls of the full AES-128.

14.14

runs of the full AES-128. The values C

biclique

The full computational complexity amounts to about



112

28+ 2

14.14

+ 2



126.18

= 2

The memory requirement is upper-bounded by the storage of 28full computations of g. Since the coverage of the key space by groups around base keys is complete, the success probability is 1.

This approach for 8-round AES-128 yields a key recovery with computational complexity about 2

125.34

, data complexity 288, memory complexity 28, and success probability 1. Similarly, preimage search for the compression function of the full AES-128 in Miyaguchi-Preneel mode requires about 2

125.83

computations, 28memory, and has a success prob ab ility of about

0.6321.

7 Indepent Bicliques for the Full AES-192

7.1 Key Partitioning

We deﬁne the key groups with respect to the expanded key block K6, which consists of the subkey $9 and left two columns of the subkey $10 (further denoted by $10L) and enumerate the groups of keys by 2 key to $9||$10L, the enumeration is well-deﬁned. The base keys K[0, 0] are all possible 2 24-byte values with two bytes ﬁxed to 0 whereas the remaining 22 bytes run over all values:

176

base keys. Since the AES-192 key schedule bijectively maps each

176

The keys {K[i, j]} in a group are enumerated by all p ossible byte diﬀerences i and j with

respect to the base key K[0, 0]:

∆

($9||$10L) =

and ∇

($9||$10L) =

j j

Page 15

where (i1, i2) are all possible columns that have one byte zero after applying MixColumns−1:













= MixColumns









∗









. (11)





∗

This yields the partition of the AES-192 key space by the 2

176

groups of 216keys each.

7.2 4-Round Biclique

The parameters of the key recovery are outlined in Table 4. The biclique is deﬁned analogously to the biclique for AES-128. Thanks to the longer key, we are able to construct a biclique over 4-round f , so that S0= #17. Again, the ∆i- and ∇j-diﬀerential trails share no active S-boxes (Figure 7).

Table 4. Parameters of the key recovery in the full AES-192

f Biclique

Rounds Dimension ∆Kbytes ∇Kbytes Time Memory

9-12 8 $617, $618$611, $6

Matching

g Precomputation Recomputation

Rounds v Workload Memory SubBytes: forward SubBytes: backward

1-8 #7

8−ε

Total complexity

Memory C

biclique

precompCrecomp

13.68

1.1875 1.625

f alsepos

189.68

f ull

Since the ∆i-diﬀerential aﬀects only 12 bytes of the ciphertext, all the ciphertexts share

the same values in bytes C

($1213), we have the following property for the ciphertext bytes:

∆

. Furthermore, since ∆

3,6,7,10

($120) = ∆

($1212) and ∆

($129) =

C0= C12and C9= C13.

As a result, the data complexity does not exceed 280.

7.3 Matching over 8 Rounds

The partial matching procedure is very similar to that in AES-128. The areas to be recomputed in the backward direction are depicted in Figure 8, and in the forward direction in Figure 9. In the backward direction we save two S-boxes, since the ∆K($9||$10L) is the expansion of 3-byte diﬀerence by MixColumns (Equation (11)). As a result, only six (instead of eight) S-boxes needs recomputing in state #15 (round 8). Regarding the forward direction, the whitening subkeys $0 diﬀer in 4 bytes only, which makes only four S-boxes to recompute. Note that the diﬀerence in the relevant subkeys is a linear function of i and j, respectively, and hence can be precomputed and stored.

Page 16

base

computation

key schedule

$10

$11

key schedule

$12

Step 1. Start with C0= 0

Fig. 7. Two key modiﬁcations for AES-192 biclique

Step 2. Add ∆ito the key

SB SR MC

SB SR

∆i-diﬀerential

∆

key schedulekey schedule

SB SR MCMC

SBSB SRSR

Step 3. Add ∇jto the key

∇j-diﬀerential

∇

key schedule

SBSB SB SRSR SR

MCMC MC

SBSB SRSR

MCMC

SB SR

Sj, #17

#18

#19

#20

#21

#22

#23

#24

biclique

Fig. 8. Recomputation in the backward direction: AES-192

biclique

oracle &

decryption

#2#1

...

∇

recomputed

∆

recomputed

#7#8#9#10#13#14#15#16#17

←−

−→

K j

#7#6#5#4

Fig. 9. Recomputation the forward direction: AES-192

Page 17

7.4 Complexities

Again, we aim to count the nonlinear operations as both a larger summand and the bottleneck of most implementations. 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). As a result, C

recomp

is equivalent to 216· 2.8125/14 = 2

13.68

runs of the full AES-192. The full

computational complexity amounts to about

172

·29+ 2

13.68



= 2

189.74

The memory requirement is upper-bounded by the storage of 28full computations of g. Since the coverage of the key space by groups around base keys is complete, the success probability is 1.

This approach for 9-round AES-192 yields a key recovery with computational complexity

about 2

188.8

, data complexity 280, memory complexity 28, and success probability 1. Similarly, preimage search for the compression function of the full AES-192 in Davies-Meyer mode requires about 2

125.71

computations, 28memory, and has success rate 0.6321.

8 Independent Bicliques for the Full AES-256

Table 5. Parameters of the key recovery in the full AES-256

f Biclique

Rounds Dimension ∆Kbytes ∇Kbytes Time Memory

11-14 8 $12

$13

Matching

g Precomputation Recomputation

Rounds v Workload Memory SubBytes: forward SubBytes: backward

1-10 #7

0.625 4.8125

Total complexity

Memory C

biclique

precompCrecomp

14.64

f alsepos

254.64

f ull

8.1 Key Partitioning

We deﬁne the key groups with respect to the expanded key block K6= $12||$13 and enumerate the groups of keys by 2

240

base keys. Since the AES-256 key schedule bijectively maps

each key to $12||$13, the enumeration is well-deﬁned. The base keys K[0, 0] are all possible

240

32-byte values with two bytes ﬁxed to 0 whereas the remaining 30 bytes run over all

values:

The keys {K[i, j]} in a group are enumerated by all p ossible byte diﬀerences i and j with

respect to the base key K[0, 0]:

Page 18

∆

($12||$13) =

and ∇

($12||$13) =

This yields the partition of the AES-256 key space into the 2

240

groups of 216keys each.

8.2 4-Round Biclique

The parameters of the key recovery are outlined in Table 5. The biclique is deﬁned analogously to the biclique for AES-128. Thanks to the longer key, we are able to construct a biclique over 4-round f , so that S0= #21. Again, the ∆i- and ∇j-diﬀerential trails share no active S-boxes (Figure 15).

base

computation

$11

key schedule

$12

$13

key schedule

$14

Step 1. Start with C0= 0

Fig. 10. Two key modiﬁcations for AES-256 biclique

Step 2. Add ∆ito the key

SB SR MC

SB SR

∆i-diﬀerential

∆

key schedulekey schedule

SB SR MCMC

SBSB SRSR

Step 3. Add ∇jto the key

∇j-diﬀerential

∇

key schedule

SBSB SB SRSR SR

MCMC MC

SBSB SRSR

MCMC

SB SR

Sj, #21

#22

#23

#24

#25

#26

#27

#28

The ∆i-diﬀerential aﬀects only 7 bytes of the ciphertext, and the key diﬀerence is equal

in all non-zero bytes of $14. Therefore, the data complexity does not exceed 240.

8.3 Matching over 10 Rounds

The partial matching procedure is again similar to that in AES-128. The areas to be recomputed in the backward direction are depicted in Figure 11, and in the forward direction

Page 19

biclique

$10

...

∆

recomputed

#7#8#9#10#17#18#19#20#21

←−

K j

Fig. 11. Recomputation in the backward direction: AES-256

oracle &

biclique

decryption

#2#1

#7#6#5#4

∇

recomputed

−→

Fig. 12. Recomputation the forward direction: AES-256

in Figure 12. The whitening subkeys diﬀer in 1 byte only. Note that the diﬀerence in the relevant subkeys is a linear function of i and j, respectively, and hence can be precomputed and stored.

8.4 Complexities

Again, we aim to count the non-linear operations as both a larger summand and the bottleneck of most implementations. Altogether, we need an equivalent of 5.4375 SubBytes operations compared to the equivalent of 17.25 in the full cipher (there are 6.5 key schedule rounds). As a result, C

recomp

is equivalent to 216· 5.625/17.25 = 2

14.383

runs of th e full

AES-256. The full computational complexity amounts to about

240

·29+ 2

14.383



= 2

254.42

The memory requirement is upper bounded by the storage of 28full computations of g. S ince the coverage of the key space by groups arou nd base keys is full, the success probability is 1.

This approach for 9-round AES-256 yields a key recovery with computational complex-

ity about 2

251.92

, data complexity 2

120

, memory complexity 28, and success probability 1. Similarly, preimage search for the compression function of the full AES-256 in Davies-Meyer mode requires about 2

126.35

computations, 28memory, and works with success probability

0.6321.

9 Long Bicliques: Key Recovery for 8-Round AES-128

We view the sequence SB ◦ AK ◦ M C ◦ SR ◦ SB as a layer of four p arallel 32-bit super boxes [16], each parameterized with the corresponding column of the subkey. We decided to

include SR to the Super Box for more clarity.

9.1 Attack

Following the long biclique paradigm, we construct a biclique for the maximum number of rounds – 5. We have to set dimension to 1 and use heavily dependent diﬀerential trails (Section 3.2).

Page 20

Step 1. A biclique of dimension 1 involves two states, two ciphertexts, and a group of four keys, which is deﬁned as follows:

The keys in the group are deﬁned via the diﬀerences in subkeys $4 and $6:, i.e. like in a

related-subkey boomerang attack:

K[0, 1] : $4(K [0, 1]) ⊕ $4(K[0, 0]) = ∆K;

K[1, 0] : $6(K [1, 0]) ⊕ $6(K[0, 0]) = ∇K;

K[1, 1] : $4(K [1, 1]) ⊕ $4(K[0, 1]) = ∆K.

The diﬀerences ∆K and ∇K are deﬁned columnwise:

∆K = (A, 0, 0, 0); ∇K = (B, 0, B, 0),

where

Let us note that ∇K in round 8 (∇$8) is equal to (B,

A =









∗





= MixColumns





∗ ∗







0 0

∗ ∗





; B =



0, 0, 0).













0 0

Instead of ﬁxing the full keys in the group, we ﬁx only three key bytes in the last column

of $5 so that we know the key diﬀerence in the ∆-trail in roun d 6.

We split the 8-round AES-128 as follows:

– E1is round 1. – E2is rounds 2-3. – E3is rounds 4-8.

Step 2. An illustration of the biclique construction in steps 2(a) - 2(e) is given in Fig. 13.

Step 2 (a). The intermediate state in E3is the Super-Box layer in rounds 6-7. We construct

truncated diﬀerential trails in rounds 5 based on the injection of ∆K after round 4 (Fig. 13, left), and in rounds 7-8 based on the injection of ∇($8) after round 8 (Fig. 13, right). Given the keys in the group, we know the key diﬀerences in trails.

Step 2 (b). We guess the actual diﬀerences in the truncated trails. We have three active S-boxes in round 5 and one active S-boxes in round 8. In total we make 2

7·4·2

= 256guesses.

Step 2 (c). First, for Super-boxes in columns 0 and 1 we construct all possible solutions that conform to the input and ou tput diﬀerences. We note that the $6 bytes not ad jacent to active S-boxes in the ∇-trail in round 7 do not aﬀect the ∇-trail, and thus can be left undeﬁned. Therefore, we construct 2

64−32

= 232solutions. Similarly, we construct all possible solutions for Super-boxes in columns 2 and 3. We get only 224solutions since we have restricted three bytes of $5.

Page 21

ShiftRows MixColumns

ShiftRows

MixColumns

ShiftRows

SubBytes

ShiftRows MixColumns

ShiftRows

SubBytes

∇K

Guess

ResolveT :

Round

∆K

Fig. 13. Biclique construction in AES-128.

Step 2 (d). Outbound phase: we combine the solutions for pairs of Super-boxes and ﬁlter out those that are incompatible with the S-box behavior guessed in rounds 6 and 8. In round 8 we have a full 14-bit ﬁlter, and in round 6 we have only a portion of ﬁlter via the diﬀerences in the extended ∇-trails. For the latter, the ﬁlter is 6 bit per active S-box, with the remaining 8bit ﬁlter to be fulﬁlled by adjusting the key. Therefore, we have 2

32+24−14−6·3

= 224solutions. In those solutions we have ﬁxed 64 bits of $6 and 24 bits of $5, which gives 80 bits in total due to dependencies. Finally, we additionally ﬁx 24 key bits to sustain the diﬀerence propagation in round 6. Taking the guess of diﬀerences into account, we have constructed 280bicliques with 104 key bits ﬁxed. The r emaining 126 −104 = 22 key bits that deﬁne the key group can be chosen arbitrarily, so we amortize the construction of a biclique. As a result, we construct

102

bicliques for each value of the three bytes of $5 we have ﬁxed in advance.

. We compute v in both directions and check for the match

2,3

Step 2 (e). We do not restrict the ciphertexts.

Step 3-5. We ask for the decryption of two ciphertexts and get two plaintexts. The matching

position (v) is the state S (Figure 14).

Step 6. We construct 222bicliques out of one by choosing 22 bits of the key (deﬁned in Step 2 (d)) so that diﬀerence propagation in the guessed parts remains untouched. The simplest change that does not aﬀect the trails is the ﬂip in two bytes of K6not adjacent to the active S-boxes and simultaneously in four bytes of K5so that three active S-boxes in round 5 are stable.

Page 22

9.2 Complexity

ShiftRows MixColumns

SubBytes

ShiftRows MixColumns

SubBytes

Match

SB−2

Biclique

Solutions for the Super-boxes are constructed online by substituting 232input pairs to the super-box transformation and ﬁltering out incorrect quartets. This gives the time complexity 232and the memory complexity 216. Therefore, Step 2 (c) has complexity 232. It also dominates the complexity of other steps, so we construct 280bicliques with 104 ﬁxed key bits in 2

56+32

= 288, and 2

102

bicliques in 288plus the time required to construct a new biclique (Step 6). Again, in th e complexity evaluation we count the number of recomputed S-boxes. Step 6 requires 3/8 SubBytes operations in round 5, 1 in round 4, 1/8 in round 7, 1/2 in round 8 per biclique ciphertext, hence 4 SubBytes operations per biclique. In the matching phase we compute 9 S-boxes in rounds 1-3, i.e. 1.125 S ubBytes operations per biclique. Additionally, Step 6 requires four S-boxes in the key schedule to recalculate, of which only two are relevant for the matching. Recall that AES-128 has 40 S-boxes in the key schedule, or equivalent of 2.5 SubBytes operations.

The chance of getting a false positive is 4 · 2−8= 2−6per biclique. Most of false positives require on ly round 2 to recompute, which gives 2−9AES calls overhead on aver age, which is negligible compared to the matching phase. Therefore, the total complexity of the attack with 2

126

bicliques is about



126

4/10.5 + 2−9+ 1.125/10.5= 2

124.97

with 232memory and 2

127

data.

Fig. 14. Matching in the 8-round attack on AES-128.

Page 23

9.3 Success rate

Our attack always outputs the right key as soon as it belongs to one of the quartets produced in the attack. As the key bits are adaptively chosen in the attack, the algorithm does not guarantee that the quartets are pairwise diﬀerent. On the other hand, each quartet has equal chance to be produced. Therefore, we estimate that the algorithm generates a natural proportion of (1−1/e) = 63% quartets. If we keep track of quartets in the loop after the guess of three bytes of K5, then the memory complexity grows to 2 of 63% the second variant of the attack produces 2

126.33

chosen ciphertexts. The workload/success rate ratio is thus 2

125.33

102

. For a success pr ob ab ility

bicliques in 2

124.97

124.3

time, and needs

10 Long Bicliques: 9-Round AES-256

Our attack is diﬀerential-based biclique attack (Section 3.2).

Step 1. A biclique of dimension 1 involves two states, two ciphertexts, and a group of four keys. The keys in the group are deﬁned via the diﬀerence in subkeys:

K[0, 1] : $5(K [0, 1]) ⊕ $5(K[0, 0]) = ∆K;

K[1, 0] : $6(K [1, 0]) ⊕ $6(K[0, 0]) = ∇K;

K[1, 1] : $6(K [1, 1]) ⊕ $6(K[0, 1]) = ∇K.

The diﬀerences ∆K and ∇K are deﬁned columnwise:

∆K = (A, 0, 0, 0); ∇K = (B, B, 0, 0),

where

A = MixColumns







0 0 2 0





; B =













= MixColumns









Let us note that the key relation in the next expanded key is still linear:

$4(K [1, 0]) ⊕ $4(K[0, 0]) = $4(K[1, 1]) ⊕ $4(K[0, 1]) = (B,

Evidently, the groups do not intersect and cover the full key space.

We split the 9-round AES-256 as follows:

– E1is round 1. – E2is rounds 2-4. – E3is rounds 5-9.

Step 2. An illustration of steps 2(a) - 2(e) is given in Fig. 15.



∗



∗





0 0

0, 0, 0).

Step 2 (a). The intermediate state T in E3is the S-box layer in round 7. We construct tru n- cated diﬀerential trails in rounds 5-6 based on the injection of ∆K after round 5 (Figure 15, left), and in rounds 7-9 based on the injection of ∇K before round 9 (Figure 15, right).

Page 24

SubBytes

ShiftRows MixColumns

SubBytes

ShiftRows MixColumns

SubBytes

ShiftRows

SubBytes

ShiftRows MixColumns

SubBytes

ShiftRows MixColumns

SubBytes

ShiftRows

SubBytes

Resolve

Guess diﬀerence

Guess

diﬀerence

T :

Round

Fig. 15. Biclique construction in AES-256. ∆-trail (left) and ∇-trail (right).

Step 2 (b). We guess the diﬀerences in the truncated trails up to T . We have four active S-boxes in round 6 and two active S-boxes in round 8. We also require ∆-trails be equal. In total we make 2

7·(4+2·2)

= 256guesses.

Step 2 (c). For each S-box in round 7 that is active in both trails (eight in total) we take a quartet of values that conform to the input and output diﬀerences, being essentially the boomerang quartet for the S-box (one solution per S-box on average). For the remaining 8 S-boxes we take all possible values. Therefore, we have 264solutions for each guess in the inbound phase, or 2

Step 2 (d). Outbound phase: we ﬁlter out the solutions that do not conform to the diﬀerential trails in rounds 6 and 8. We have four active S-boxes in each ∆-trail, and two active

120

solutions in total.

S-boxes in each ∇-trail, hence 12 in total. Therefore, we get a 84-bit ﬁlter, and leave with 236bicliques.

Step 2 (e). Now we keep only the bicliques with byte C

equal to zero in both ciphertexts.

0,0

This is a 16-bit ﬁlter, which reduces the number of bicliques to 220. We need only one.

Step 3-5. We ask for the decryption of two ciphertexts and get two plaintexts. The matching position (v) is the byte #3

. As demonstrated in Fig. 16, it is equal as a function of the

0,0

Page 25

plaintext for keys with diﬀerence ∆K (not aﬀected by lightblue cells), and is also equal as a function of S for keys with diﬀerence ∇K (not aﬀected by red cells). We compute v in both directions and check for the match.

Step 6. We can produce suﬃciently many bicliques out of one to amortize the construction cost. Let us lo ok at the subkey $6 in the outbound phase. We can change its value to any of the 296speciﬁc values so that the active S-boxes in round 6 during the outbound phase are not aﬀected. On the other hand, any change in bytes in rows 1,2,3 aﬀects only those rows in the subkeys $8 and $9 and hence does not aﬀect C

. Therefore, we have 128 − 32 − 32 = 64

0,0

neutral bits in $6.

Similarly, we identify 9 bytes in $7 that can be changed so that $6, the active S-boxes in round 8, and the byte C

are unaﬀected. Those are bytes in the ﬁrst three columns not on

0,0

the main diagonal. Therefore, we have 72 neutral bits in $7, and 136 neutral bits in total.

Complexity. A single biclique with the C

100

and 28memory for table lookups at Step 2 (c). However, 136 neutral bits in the key

= 0 is constructed with complexity 2

0,0

120−20

reduce the amortized construction cost signiﬁcantly. Let us compute the cost of constructing a new biclique according to Step 6. A change in a single byte in K7needs 5 S-boxes, 1 MixColumn and several XORs recomputing for each ciphertext, which gives us the complexity of 10/16 AES rounds. This change also aﬀects two bytes of K5, so we have to recompute one half of round 5, with the resulting complexity of 1 AES round per biclique. The total amortized complexity is 1.625 AES rounds.

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. In total we need

4.75 AES rounds per biclique, i.e. 2 by false positives is at most 2−6rounds per biclique. We need 2 complexity is 2

The data complexity is 2

253.1

120

−0.92

9-round AES-256 calls. The complexity generated

254

bicliques, so the total

since one ciphertext byte is always ﬁxed. The success rate of

the attack is 1, since we can generate many bicliques for each key group.

11 On practical veriﬁcation

Especially for the type of cryptanalysis described in this paper were carring out an attack in full is computationally infeasible, practical veriﬁcation of attack details and steps is important in order to conﬁdence in it. To address this, we explicitly state the following:

– We veriﬁed all truncated diﬀerentials through 8-round and 10-round AES-128 key-schedules,

and through 9-round AES-256 key-schedule.

– We implemented the technically most complex part of one of our attacks: the long-biclique

construction (for the AES-256 attack). We veriﬁed the complexity estimate, and also give

an example of a biclique in Table 7 in the Appendix.

– We checked the distribution of super-box output diﬀeren ces. We checked that it is random

enough where we require ran domness, though some non-random behavior was detected

and might be important for constructing bicliques of high dimension over super-boxes.

Note that we avoid doing this in the independent-biclique approach.

– We veriﬁed that some diﬀerence guesses must be equ al like in the AES-256 attack due

to the branch number of MixColumns that results in the correlation of diﬀerences in the

outbound phase.

Page 26

SubBytes

ShiftRows MixColumns

ShiftRows

SubBytes

ShiftRows MixColumns

SubBytes

ShiftRows MixColumns

SubBytes

Biclique

Fig. 16. Matching in AES-256. Byte S

after round 1 can be computed in each direction.

0,0

Page 27

12 Discussion and Conclusions

We propose the concept of bicliques for block cipher cryptanalysis and give various application to AES, including a key recovery method for the full versions of AES-128, AES-192, and AES-256. For the latter, we allow a small portion of the cipher to be recomputed in every key test. 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 288, 280and 240plaintext-ciphertext pairs, respectively. Arguably no known generic ap proach to key recovery allows for that gain. We notice that the data complexity of key recovery can be signiﬁcantly reduced by sacriﬁcing only a small factor of computational advantage.

To conclude, we discuss the properties of AES that allowed us to cover more rounds than in previous cryptanalysis, discuss the attained computational advantage, and list a number of problems to consider for future work.

12.1 What properties of the AES allowed to obtain these new results

Our approach heavily relies on the existence of high-probability related-key d iﬀerentials over a part of the cipher. More speciﬁcally:

– The round transformation of AES is not designed to have strong resistance against several

classes of attacks for a smaller number of rounds. The fact that our approach allows to

split up the cipher into three parts exposes these properties even when consider ing the full

cipher. Also, as already observed in [19,37], the fact that the MixColumn tr an sformation

is omitted in the last round of AES helps to design attacks for more rounds.

– In the key schedule, we especially take advantage of the relatively slow backwards diﬀu-

sion. Whereas using key-schedule properties in related-key attacks is natural, there seem

only a few examples in the literature w here this is used in the arguably more relevant

single-key setting. This includes the attack on the self-synchronized stream cipher Mous-

tique [28], the lightweight block cipher KTANTAN [12], and recent improvements upon

attacks on 8-round s of AES-192 and AES-256 [20].

12.2 On the computational advantage of the biclique techniques

Most computational complexities in this paper are relatively close to those of generic attacks. In here we discuss why we think the complexity advantage is meaningful.

– The attacks with independent bicliques – which lead to the key recovery for the full AES

– allow us to be very precise about the required computations. In all cases we arrive at

a computational complexity that is considerably lower than generic attacks.

– For the attacks with long bicliques, whenever it is diﬃcult to be precise about certain

parts of our estimates, we choose to be conservative, potentially resulting in an under-

estimate of the claimed improvement. Again, in all cases we arrive at a computational

complexity that is considerably lower than generic attacks.

– Improved AES implementations (that may e.g. be used to speed-up brute force key

search) will very likely also improve the biclique techniques we propose.

– To the best of our knowledge, there are no generic methods known that would speed-up

key-recovery attacks given a part of the codebook.

Page 28

12.3 Open Problems

There are a number of other settings this approach may be applied to. It will be interesting to study other block ciphers like the AES ﬁnalists or more recent proposals with respect to this class of attacks. Also, we may decide to drop the requirement of the biclique to be complete, i.e. instead of a complete bipartite graph consider a more general graph. There may be cases where diﬀerent tradeoﬀs between success probability, complexity requirements, and even number of rounds are obtainable. Alternatively, this paper may inspire work on more generic attacks on block ciphers th at tr y to take advantage of the fact that a small part of the codebook, or some memory, is available.

Acknolwedgements

We thank Joan Daemen and Vincent Rijmen for their h elpful feedback. Part of this work was done while Andrey Bogdanov was visiting MSR Redmond and while Christian Rechberger was with K.U.Leuven and visiting MSR Redmond. This work was supported in part by the European Commission under contract ICT-2007-216646 (ECRYPT II).

References

1. Kazumaro Aoki and Yu Sasaki. Preimage attacks on one-block MD4, 63-step MD5 and more. In Selected Areas in Cryptography’08, volume 5381 of Lecture Notes in Computer Science, pages 103–119. Springer,

2008.

2. Kazumaro Aoki and Yu Sasaki. Meet-in-the-middle preimage attacks against reduced SHA-0 and SHA-1. In CRYPTO’09, volume 5677 of Lecture Notes in Computer Science, pages 70–89. Springer, 2009.

3. Behran Bahrak and Mohammad Reza Aref. A novel impossible diﬀerential cryptanalysis of AES. In Proceedings of the Western European Workshop on Research in Cryptology 2007 (WEWoRC’07), pages 152–156, 2007.

4. Behran Bahrak and Mohammad Reza Aref. Impossible diﬀerential attack on seven-round aes-128. IET Inf. Secur., 2(2):28–32, June 2008.

5. Eli Biham, Alex Biryukov, and Adi Shamir. Miss in the middle attacks on IDEA and Khufu. In FSE’99, volume 1636 of Lecture Notes in Computer Science, pages 124–138. Springer, 1999.

6. Eli Biham, Raﬁ Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet, and William Jalby. Collisions of SHA-0 and reduced SHA-1. In EUROCRYPT’05, volume 3494 of Lecture Notes in Computer Science, pages 36–57. Springer, 2005.

7. Eli Biham and Adi Shamir. Diﬀerential Cryptanalysis of DES-like Cryptosystems. J. Cryptology, 4(1):3– 72, 1991.

8. Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, and Adi Shamir. Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds. In EUROCRYPT’10, volume 6110 of Lecture Notes in Computer Science, pages 299–319. Springer, 2010.

9. Alex Biryukov and Dmitry Khovratovich. Related-Key Cryptanalysis of the Full AES-192 and AES-256. In ASIACRYPT’09, volume 5912 of Lecture Notes in Computer Science, pages 1–18. Springer, 2009.

10. Alex Biryukov, Dmitry Khovratovich, and Ivica Nikoli´c. Distinguisher and related-key attack on the full AES-256. In CRYPTO’09, volume 5677 of Lecture Notes in Computer Science, pages 231–249. Springer,

2009.

11. Alex Biryukov and Ivica Nikoli´c. Automatic Search for Related-Key Diﬀerential Characteristics in Byt eOriented Block Ciphers: Application to AES, Camellia, Khazad and Ot hers. In EUROCRYPT’10, volume 6110 of Lecture Notes in Computer Science, pages 322–344. Springer, 2010.

12. Andrey Bogdanov and Christian Rechberger. A 3-Subset Meet-in-the- Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN. In SAC’10, volume 6544 of Lecture Notes in Computer Science, pages 229–240. Springer, 2010.

13. Florent Chabaud and Antoine Joux. Diﬀerential collisions in SHA-0. In CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 56–71. Springer, 1998.

14. Joan Daemen, Lars R. Knudsen, and V incent Rijmen. The Block Cipher Square. In Eli Biham, editor, FSE’97, volume 1267 of Lecture Notes in Computer Science, pages 149–165. Springer, 1997.

Page 29

15. Joan Daemen and Vincent Rijmen. The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, 2002.

16. Joan Daemen and Vincent Rijmen. Understanding two-round diﬀerentials in AES. In Roberto De Prisco and Moti Yung, editors, SCN’06, volume 4116 of Lecture Notes in Computer Science, pages 78–94. Springer, 2006.

17. H¨useyin Demirci and Ali Aydin Sel¸cuk. A meet-in-the-middle attack on 8-round AES. In FSE’08, volume 5086 of Lecture Notes in Computer Science, pages 116–126. Springer, 2008.

18. H¨useyin Demirci, Ihsan Taskin, Mustafa C¸ oban, and Adnan Baysal. Improved Meet-in-the-Middle Attacks on AES. In INDOCRYPT’09, volume 5922 of Lecture Notes in Computer Science, pages 144–156. Springer, 2009.

19. Orr Dunkelman and Nathan Keller. The eﬀects of the omission of last round’s MixColumns on AES. Inf. Process. Lett., 110(8-9):304–308, 2010.

20. Orr Dunkelman, Nathan Keller, and Adi Shamir. Improved Single-Key Attacks on 8-Round AES-192 and AES-256. In ASIACRYPT’10, volume 6477 of Lecture Notes in Computer Science, pages 158–176. Springer, 2010.

21. Orr Dunkelman, Nathan Keller, and Adi Shamir. A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony. In CRYPTO’10, volume 6223 of Lecture Notes in Computer Science, pages 393–410. Springer, 2010.

22. Orr Dunkelman, Gautham Sekar, and Bart Preneel. Improved meet-in-the-middle attacks on reducedround DES. In INDOCRYPT’07, volume 4859 of Lecture Notes in Computer Science, pages 86–100. Springer, 2007.

23. Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Michael Stay, David Wagner, and Doug Whiting. Improved cryptanalysis of Rijndael. In FSE’00, volume 1978 of Lecture Notes in Computer Science, pages 213–230. Springer, 2000.

24. Henri Gilbert and Marine Minier. A Collision Attack on 7 Rounds of Rijndael. In AES Candidate Conference, pages 230–241, 2000.

25. Henri Gilbert and Thomas Peyrin. Super-Sbox cryptanalysis: Improved attacks for AES-like permutations. In FSE’10, volume 6147 of Lecture Notes in Computer Science, pages 365–383. Springer, 2010.

26. Jian Guo, San Ling, Christian Rechberger, and Huaxiong Wang. Advanced Meet-in-the-Middle Preimage Attacks: First R esults on Full Tiger, and Improved Results on MD4 and SHA-2. In ASIACRYPT’10, volume 6477 of Lecture Notes in Computer Science, pages 56–75. Springer, 2010.

27. Takanori Isobe. A single-key attack on the full GOST block cipher. In FSE’11 Preproceedings, 2011.

28. Emilia K¨asper, Vincent Rijmen, Tor E. Bjørstad, Christian Rechberger, Matthew J. B. Robshaw, and Gautham Sekar. Correlated Keystreams in Moustique. In AFRICACRYPT’08, volume 5023 of Lecture Notes in Computer Science, pages 246–257. Springer, 2008.

29. Dmitry Khovratovich, Christian Rechberger, and Alexandra Savelieva. Bicliques for preimages: attacks on Skein-512 and the SHA-2 family. available at http://eprint.iacr.org/2011/286.pdf, 2011.

30. Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen, and Martin Schl¨aﬀer. Rebound Distinguishers: Results on the Full Whirlpool Compression Function. In ASIACRYPT’09, volume 5912 of Lecture Notes in Computer Science, pages 126–143. Springer, 2009.

31. Jiqiang Lu, Orr Dunkelman, Nathan Keller, and Jongsung Kim. New impossible diﬀerential attacks on AES. In INDOCRYPT’08, volume 5365 of Lecture Notes in Computer Science, pages 279–293. Springer,

2008.

32. Stefan Lucks. Attacking seven rounds of Rijndael under 192-bit and 256-bit keys. In AES Candidate Conference, pages 215–229, 2000.

33. Hamid Mala, Mohammad Dakhilalian, Vincent Rijmen, and Mahmoud Modarres-Hashemi. Improved Impossible Diﬀerential Cryptanalysis of 7-Round AES-128. In INDOCRYPT’10, volume 6498 of Lecture Notes in Computer Science, pages 282–291. Springer, 2010.

34. Mitsuru Matsui. Linear cryptanalysis method for DES cipher. In EUROCRYPT’93, volume 765 of Lecture Notes in Computer Science, pages 386–397. Springer, 1993.

35. Florian Mendel, Christian Rechberger, Martin Schl¨aﬀer, and S øren S. Thomsen. The rebound attack: Cryptanalysis of reduced Whirlpool and Grøstl. In FSE’09, volume 5665 of Lecture Notes in Computer Science, pages 260–276. Springer, 2009.

36. Raphael Chung-Wei Phan. Impossible diﬀerential cryptanalysis of 7-round advanced encryption standard (AES). Inf. Process. Lett., 91(1):33–38, 2004.

37. Yu Sasaki. Meet-in-the-Middle Preimage Attacks on AES Hashing Modes and an Application to Whirlpool. In FSE’11 Preproceedings, 2011.

38. Yu Sasaki and Kazumaro Aoki. Finding Preimages in Full MD5 Faster Than Ex haustive Search. In EUROCRYPT’09, volume 5479 of Lecture Notes in Computer Science, pages 134–152. Springer, 2009.

Page 30

39. Marc Stevens, Arjen K. Lenstra, and Benne de Weger. Chosen-preﬁ x collisions for MD5 and colliding X.509 certiﬁ cates for diﬀerent identities. In EUROCRYPT’07, volume 4515 of Lecture Notes in Computer Science, pages 1–22. Springer, 2007.

40. Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen K. Lenstra, David Molnar, Dag Arne Osvik, and Benne de Weger. Short chosen-preﬁx collisions for MD5 and the creation of a rogue ca certiﬁcate. In CRYPTO’09, volume 5677 of Lecture Notes in Computer Science, pages 55–69. Springer, 2009.

41. David Wagner. The boomerang attack. In FSE’99, volume 1636 of Lecture Notes in Computer Science, pages 156–170. Springer, 1999.

42. Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Finding collisions in the full SHA-1. In CRYPTO’05, volume 3621 of Lecture Notes in Computer Science, pages 17–36. Springer, 2005.

43. Xiaoyun Wang and Hongbo Yu. How to break MD5 and other hash functions. In EUROCRYPT’05, volume 3494 of Lecture Notes in Computer Science, pages 19–35. Springer, 2005.

44. Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. Improved meet-in-the-middle cryptanalysis of KTANTAN. Cryptology ePrint Archive, Report 2011/201, 2011. http://eprint.iacr.org/.

45. Wentao Zhang, Wenling Wu, and Dengguo Feng. New results on impossible diﬀerential cryptanalysis of reduced AES. In ICISC’07, volume 4817 of Lecture Notes in Computer Science, pages 239–250. Springer,

2007.

Page 31

Table 6. Summary of previous results on AES in the single-key model

rounds data workload memory method reference

AES-128 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2

127.997

117.5

115.5

112.2

106.2

103

113+2123

112

107.1

120

128−ǫ

123

119

117.2

+ 2

MA 2

precomp. 2

117.2

+ 2

116

MA 2

100

109

? impossible [31] 2008

122

94.2

116

Square [23], 2000

Square-functional [24], 2000

impossible [3], 2007 impossible [45], 2007 impossible [4], 2008

MitM [18], 2009

impossible [33], 2010

Square-multiset [20], 2010

AES-192

127.997

7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 8 2 8 2

115.5

91.2

113.8

34+n274+n+2208−n

103

127.997

113

113+2123

120

155

182

140

186

119

162

139.2

118.8

MA 2

precomp. 2

116

188

172

153

89.2

206−n

122

116

129

Square [23], 2000 Square [23], 2000 Square [32], 2000

Square-functional [24], 2000

Impossible [36], 2004

impossible [45], 2007 impossible [45], 2007 impossible [31] 2008 impossible [31] 2008

MitM [17], 2008 MitM [18], 2009

Square-multiset [20], 2010

Square [23], 2000

Square-multiset [20], 2010

AES-256 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 8 2 8 2 8 2 8 2 8 2 8 2 8 2

127.997

92.5

115.5

113.8

34+n274+n+2208−n

127.997

116.5

89.1

111.1

34+n2202+n+2208−n

113

113+2123

172

120

200

184

250.5

119

118.8

MA 2

163

MA 2

precomp. 2

204

247.5

229.7

MA 2

227.8

MA 2

precomp. 2

241

196

140

153

89.2

206−n

122

1044

112.1

206−n

123

129

Square [23], 2000 Square [23], 2000 Square [32], 2000

Square-functional [24], 2000

Impossible [36], 2004

impossible [45], 2007 impossible [31] 2008 impossible [31] 2008

MitM [17], 2008 MitM [18], 2009

Square [23], 2000 impossible [45], 2007 impossible [31] 2008 impossible [31] 2008

MitM [17], 2008 MitM [18], 2009

Square-multiset [20], 2010

Page 32

SB SR MC

SB SR

SB SR MC

#10

#11

#12

#13

#14

#15

#16

#17

#18

#19

#20

SB SR MC

SB SR

SB SR MC

#10

#11

#12

#13

#14

#15

#16

#17

#18

#19

#20

SB SR MC

SB SR

SB SR MC

#10

#11

#12

#13

#14

#15

#16

#17

#18

#19

#20

$10

Recomputation

in subkeys

Recomputation

in states

Inﬂuence

on backward matching

Inﬂuence

on forward matching

Biclique

∆-diﬀerential

Biclique

∇-diﬀerential

- full recomputation

- not needed for matching

Fig. 17. Biclique diﬀerentials and matching in A ES-128. Recomputation parts are derived as follows: formally overlap pink and blue schemes, then interleaving parts must be recomputed (darkgray cells). The lightgray cells are those excluded from recomputation since we do not match on the full state.

Page 33

40 8a ba 52 30 4a 10 52 34 b6 84 52

b8 fe aa 52

7d 8a d8 a4 30 e8 0 0 12 a8 f9 31 5a 42 0 0 12 55 cd 0b 32 d6 0 0 58 66 d8 cf 54 f8 0 0

7d 8a d8 a4 30 e8 0 0

10 aa f9 31 5a 42 0 0 ab ec cd 0b 32 d6 0 0 5a 64 d8 cf 54 f8 0 0

44 d2 66 7b 32 34 6e f7 36 f4 b0 7a b8 ba 71 3a

[3]

0,0

[3]

1,0

79 18 c0 8e 67 ac 89 9e 2e 39 52 84 3c fd 40 26

5d 08 b5 ac

e5 bd d3 54 a0 ac d9 8a 09 6a 55 1e

[3]

0,1

7d 8a d8 a4 34 ec 4 4 12 a8 f9 31 58 40 2 2 12 55 cd 0b 30 d4 2 2 58 66 d8 cf 52 fe 6 6

[3]

1,1

7d 8a d8 a4 34 ec 4 4 10 aa f9 31 58 40 2 2 ab ec cd 0b 30 d4 2 2 5a 64 d8 cf 52 fe 6 6

Table 7. Example of a biclique for A ES-256. Siare states after MixColumns in round 5, Ciare ciphertexts.