# Collision Attacks on AES-192/256, Crypton-192/256, mCrypton-96/128, and Anubis

Authors: Jinkeon Kang; Kitae Jeong; Jaechul Sung; Seokhie Hong; Kyungho Lee
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

At AES’00, a collision attack on 7-round reduced AES was
proposed. In this paper, we apply this idea to seven SPN block ciphers,
AES-192/256, Crypton-192/256, mCrypton-96/128, and Anubis. Applying
our attacks on AES-192/256, we improve the attack result based on
meet-in-the-middle attack (AES-192) and the attack result proposed in
AES’00 (AES-256), respectively. Our attack result on Anubis is superior
to known cryptanalytic result on it. In the cases of Crypton-192/256
and mCrypton-96/128, our attacks are applicable to 8-round reduced versions.
The attack results on mCrypton-96/128 are more practical than
known cryptanalytic results on them.


---

## Body

## 1. Introduction

Recently, meet-in-the-middle attack has received attention. The attack procedure of meet-in-the-middle attack can be summarized as follows. Letℳ be the message space and 𝒦 the key space. Suppose that GK and HK:ℳ×𝒦→ℳ are two block ciphers and let FK=HK∘GK. In this attack, an attacker tries to deduce K from a given plaintext/ciphertext pair c=FK(p) by trying to solve GK(p)=HK-1(c). In some cases, the equation is not tested for all the bits of the intermediate encryption value, but rather for only some of them. So far, many meet-in-the-middle attack results on block cipher have been proposed [1, 2]. On the other hand, Gilbert and Minier proposed a collision attack on 7-round of AES in [3]. This attack is a type of meet-in-the middle attack and exploits a 4-round distinguisher. In general, block cipher is completely deterministic, that is, if it is run again with the exact same input values, identical output values will be produced. Similarly, the different input values result in the different output values. However, it is possible that the different input values result in the output values of which the specific parts are the same. We call this case a collision.In this paper, we apply the main idea of [3] to seven SPN block ciphers, such as AES-192/256 [4], Crypton [5], mCrypton-96/128 [6], and Anubis [7]. Table 1 shows our attack results on them. Rijndael was announced as the Advanced Encryption Standard (AES) in 2001. After DES, it is one of the most widely used and analyzed ciphers in the world. AES is a 128-bit block cipher and accepts key sizes of 128,192, and 256 bits. These versions of AES are called AES-128/192/256 and the number of rounds for these versions is 10,12, and 14, respectively. Our attacks on AES-192/256 require a computational complexity of 269.2 encryptions with 232 chosen plaintexts and 274 memory bytes, respectively. Though our attacks on them are not applicable to the full AES-192/256, these are superior to the attack results of [1] (AES-192) and [3] (AES-256), respectively.Table 1
Our attack results on AES-192/256, Crypton-192/256, mCrypton-96/128, and Anubis.
Target Algorithm
Attack
Number of rounds
Data complexity
Computational complexity
AES-192
MitM [1]
7
2
40
2
80
RKABA [10]
12
2
123
2
176
CA (This paper)
7
2
32
2
69.2
AES-256
CA [3]
7
2
32
2
140
RKBA [10]
14
2
99.5
2
99.5
CA (This paper)
7
2
32
2
69.2
Crypton-192/256
TDC [8]
8
2
126
2
126.2
CA (This paper)
8
2
96
2
161.6
mCrypton-96
RKIDC [9]
9
2
59.9
2
74.9
CA (This paper)
8
2
48
2
81.6
mCrypton-128
RKIDC [9]
9
2
59.7
2
66.7
CA (This paper)
8
2
48
2
81.6
Anubis
CA [11]
7
2
32
2
140
Square [11]
7
2
128~2119
2
120
CA (This paper)
8
2
96
2
161.6
MitM: meet-in-the-middle attack.
TDC: truncated differential cryptanalysis.
RKABA: related-key amplified boomerang attack.
RKBA: related-key boomerang attack.
RKIDC: related-key impossible differential cryptanalysis.
CA: collision attack.Crypton is a128-bit block cipher submitted as a candidate for the AES proposal of NIST. This algorithm has a 12-round SPN structure with 128/192/256-bit secret keys. According to the length of the secret keys, we call them Crypton-128/192/256, respectively. Our attack is applicable to 8-round reduced Crypton-192/256. To our knowledge, truncated differential cryptanalysis on 8-round reduced Crypton-192/256 has the best results on them, so far [8]. The attacks on an 8-round reduced Crypton-192/256 need the computational complexity of 2161.6 encryptions with 296 chosen plaintexts and 2138 memory bytes, respectively. Compared to the attack results of [8], our attacks decrease the data complexity but increase the computational complexity.A64-bit block cipher mCrypton was designed as a reduced version of Crypton for a ubiquitous environment. It provides low-resource hardware implementation, which is suitable for low-end devices such as RFID tags and wireless sensor network. Several security aspects related to RFID tags and wireless sensor network have already been studied. mCrypton has 12 rounds and supports the 64/96/128-bit secret keys. Our attack is applicable to mCrypton-96/128. We require the computational complexity of 281.6 encryptions with 248 chosen plaintexts and 265 memory bytes. However, this is not the best result on them, since related-key impossible differential cryptanalysis on 9-round reduced mCrypton-96/128 was proposed in [9]. However, considering the attack assumption of a related-key attack, our attacks are more practical than it.Anubis is a block cipher submitted to the NESSIE project and operates on data blocks of128 bits, accepting keys of length 32N bits (N=4,…,10). It is a Rijndael variant that uses involutions for the various operations. Our attack is applicable to Anubis where the length of the secret key is longer than 192 bits. We need the computational complexity of 2161.6 encryptions with 296 chosen plaintexts and 2138 memory bytes. This result is superior to known cryptanalytic results on this algorithm.The rest of this paper is organized as follows. In Section2, we propose collision attacks on AES-192/256. Collision attacks on Crypton-192/256 and mCrypton-96/128 are introduced in Section 3. In Section 4, we present a collision attack on Anubis. In each section, we start with a brief description of the block cipher concerned. Finally, we give our conclusion in Section 5.


## 2. Collision Attacks on 7-Round Reduced AES-192/256

First, we briefly present AES-192/256. And then we introduce collision attacks on AES-192/256. Note that the attack procedure on AES-192 is the same as that on AES-256. Thus, for the simplicity of notations, we just call them AES-192/256 AES.


### 2.1. AES-192/256

AES-192/256 are 128-bit block ciphers with 192/256-bit secret keys. According to the length of the secret key, the number of rounds is 12 and 14, respectively. Each internal state is treated as a byte matrix of size 4×4, where each byte represents a value in GF(28) (see Figure 1).Figure 1
Internal state of AES-192/256 and Anubis.In roundr, input/output values and round key are denoted by Ir,Or, and RKr, respectively (r=1,…,12 (AES-192) or 14 (AES-256)). A whitening key is denoted by RK0. The round function of AES-192/256 applies the following four operations to the state matrix:(i)
SubBytes (SB): applying the same8×8 invertible S-box 16 times in parallel on each byte of the state;(ii)
ShiftRows (SR): cyclic shift of each row (theith row is shifted by i bytes to the left);(iii)
MixColumns (MC): multiplication of each column by a constant4×4 matrix over GF(28);(iv)
AddRoundKey (ARK): XORing the state with a128-bit round key.The SB, SR, MC, and ARK transformations are applied to each round except that MC is omitted in the last round. Besides, before the first round, an extra ARK is applied, which we call a whitening key step. For the more detailed descriptions of AES-192/256, we refer to [4]. We omit the key schedules of them, as they do not affect our attacks.


### 2.2. Finding a 4-Round Distinguisher of AES

In our attack on AES, we use a4-round distinguisher of round 2~5. We consider an input value I2 of round 2 in AES which is constructed as follows:(i)(I002,I102,I202,I302): four 8-bit variables;(ii)Iij2: a fixed 8-bit constant (0≤i≤3,1≤j≤3).By usingI2, we can construct the following equations on I3(i=0,…,3). Here, aij means the entry of the coefficient matrix of MC (j=0,…,3):
(1)Ii03=ai0∘SB[I002]⊕ai1∘SB[I112]⊕ai2∘SB[I222]⊕ai3∘SB[I332]⊕RKi02,Ii13=ai0∘SB[I012]⊕ai1∘SB[I122]⊕ai2∘SB[I232]⊕ai3∘SB[I302]⊕RKi12,Ii23=ai0∘SB[I022]⊕ai1∘SB[I132]⊕ai2∘SB[I202]⊕ai3∘SB[I312]⊕RKi22,Ii33=ai0∘SB[I032]⊕ai1∘SB[I102]⊕ai2∘SB[I212]⊕ai3∘SB[I322]⊕RKi32.Note that eachIi03, Ii13, Ii23, and Ii33 depends on only one 8-bit variable and one 8-bit round key: (I002,RKi02),(I302,RKi12),(I202,RKi22), and (I102,RKi32).Applying the above procedure repeatedly, as shown in (2), we can obtain an equation on an input value I005 of round 5 by using I2. Here, bold characters indicate (I102,I202,I302)(2)I005=a00∘SB[a00∘SB(a00∘SB[I002]⊕a01∘SB[I112]⊕a02∘SB[I222]⊕a03∘SB[I332]⊕RK002)⊕a01∘SB(a10∘SB[I012]⊕a11∘SB[I122]⊕a12∘SB[I232]⊕a13∘SB[I302]⊕RK112)⊕a02∘SB(a20∘SB[I022]⊕a21∘SB[I132]⊕a22∘SB[I202]⊕a23∘SB[I312]⊕RK222)⊕a03∘SB(a30∘SB[I032]⊕a31∘SB[I102]⊕a32∘SB[I212]⊕a33∘SB[I322]⊕RK332)⊕RK003]⊕a01∘SB[a10∘SB(a00∘SB[I012]⊕a01∘SB[I022]⊕ai2∘SB[I232]⊕a03∘SB[I302]⊕RK012)⊕a11∘SB(a10∘SB[I022]⊕a11∘SB[I132]⊕a12∘SB[I202]⊕a13∘SB[I312]⊕RK122)⊕a12∘SB(a20∘SB[I032]⊕a21∘SB[I102]⊕a22∘SB[I212]⊕a23∘SB[I322]⊕RK232)⊕a13∘SB(a30∘SB[I002]⊕a31∘SB[I112]⊕a32∘SB[I222]⊕a33∘SB[I332]⊕RK302)⊕RK113]⊕a02∘SB[a20∘SB(a00∘SB[I022]⊕a01∘SB[I132]⊕a02∘SB[I202]⊕a03∘SB[I312]⊕RK022)⊕a21∘SB(a10∘SB[I032]⊕a11∘SB[I102]⊕a12∘SB[I212]⊕a13∘SB[I322]⊕RK132)⊕a22∘SB(a20∘SB[I002]⊕a21∘SB[I112]⊕a22∘SB[I222]⊕a23∘SB[I332]⊕RK202)⊕a23∘SB(a30∘SB[I012]⊕a31∘SB[I122]⊕a32∘SB[I232]⊕a33∘SB[I302]⊕RK312)⊕RK223]⊕a03∘SB[a30∘SB(a00∘SB[I032]⊕a01∘SB[I102]⊕a02∘SB[I212]⊕a03∘SB[I322]⊕RK032)⊕a31∘SB(a10∘SB[I002]⊕a11∘SB[I112]⊕a12∘SB[I222]⊕a13∘SB[I332]⊕RK102)⊕a32∘SB(a20∘SB[I012]⊕a21∘SB[I122]⊕a22∘SB[I232]⊕a23∘SB[I302]⊕RK212)⊕a33∘SB(a30∘SB[I022]⊕a31∘SB[I132]⊕a32∘SB[I202]⊕a33∘SB[I312]⊕RK322)⊕RK333]⊕RK004.Note that this equation consists of five parts as follows:(3)I005=(a00∘SB[·])⊕(a01∘SB[·])⊕(a02∘SB[·])⊕(a03∘SB[·])⊕RK004.
If we find different (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) which satisfy that each subpart including (I102,I202,I302), that is, (2,3,4)th rows of the first part, (1,2,3)th rows of the second part, (1,2,4)th rows of the third part, and (1,3,4)th rows of the fourth part in (2), has the same value for a given I002, then I005′ is equal to I005′′. That is, for all I002∈{0,…,255}, these (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) result in the same 32-bit value of four subparts (the length of the value in each subpart is 8 bits). By the birthday paradox, we can obtain different (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) from 216(I102,I202,I302) with the probability of 0.5.We can expressI5 by using O5 as follows. Here, f-1 means the inverse of a function f(4)O5=ARKRK5∘MC∘SR∘SB[I5]=MC∘SR∘ARKSR-1∘MC-1[RK5]∘SB[I5]⟹SB[I5]=ARKSR-1∘MC-1[RK5]∘SR-1∘MC-1[O5].
If we obtain different (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) satisfying I005′=I005′′, then SB[I005′] is also equal to SB[I005′′]. Thus, from the above equation, we can construct the following equation. Here, bij means the entry of the coefficient matrix of MC-1(5)SB[I005′]=b00∘O005′⊕b01∘O105′⊕b02∘O205′⊕b03∘O305′=b00∘O005′′⊕b01∘O105′′⊕b02∘O205′′⊕b03∘O305′′=SB[I005′′].
For all I002∈{0,…,255}, we can check that I005′ is equal to I005′′ by using (5). That is, with the probability of 0.5, we can find different (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) satisfying (5) for all I002 (among 216 candidates).On the other hand, our attack on AES recovers a192-bit round key and the probability that (5) holds for one I002 is 2-8. So, if we use only 25I002, the probability that (5) holds is (2-8)25=2-200. Since 2-200·2192≪1, we consider only 25I002.


### 2.3. Collision Attack on a 7-Round Reduced AES

Now, we show how to exploit a4-round distinguisher constructed in the previous subsection in order to attack a 7-round reduced AES.Similarly to the previous subsection,O5 can be expressed by using O7 as follows:
(6)O7=ARKRK7∘SR∘SB∘ARKRK6∘MC∘SR∘SB[O5]=SR∘ARKSR-1[RK7]∘SB∘MC∘SR∘ARKSR-1∘MC-1[RK6]∘SB[O5]⟹O5=SB-1∘ARKSR-1∘MC-1[RK6]∘SR-1∘MC-1∘SB-1∘ARKSR-1[RK7]∘SR-1[O7].
For the simplicity of notations, SR-1∘MC-1[RK6] and SR-1[RK7] in (6) are denoted by RK6* and RK7*, respectively.Our attack procedure on AES is as follows (see Figure2). (1)
Construct232 plaintexts Pi, where all byte values except (P00i,P11i,P22i,P33i) are fixed constants, and obtain the corresponding ciphertexts Ci (i=0,…,232-1). Sort Ci's according to a 32-bit value P00i∥P11i∥P22i∥P33i.(2)
For eachj(=0,…,3), guess 40-bit round keys (RKj06*, RK0((4-j)mod4)7*, RK1((4-j)mod4)7*, RK2((4-j)mod4)7*, RK3((4-j)mod4)7*) and compute the corresponding Oj05 from the guessed round keys and Ci by using (6) (e.g., guess (RK006*,RK007*,RK107*,RK207*,RK307*) to compute O005). Sort Oj05 according to the guessed round keys, i and j, and keep them in a table.(3)
Select216 sets Sk including 25 output values X of MC in round 1(k=0,…,216-1). Note that Xmn are fixed constants in all Sk(0≤m≤3,1≤n≤3). In each Sk, 25X00 have different values but all Sk contain the same X00. In the case of (X10,X20,X30), they are different in each Sk but the same in all Sk.(4)
Guess32-bit round keys (RK000,RK110,RK220,RK330) and construct 216 sets Qk including the corresponding (P00′,P11′,P22′,P33′) from each X in Sk, and do the following:
(i)
choose different two setsQk1 and Qk2. By using the table constructed in Step 2, check that 25 pairs from Qk1 and Qk2 satisfy (5);(ii)
if all 25 pairs satisfy (5), then output the corresponding 192-bit guessed round keys as the right round keys of AES.Figure 2
The attack procedure on AES-192/256.The data complexity of this attack is232 chosen plaintexts and the memory complexity is 274(≈4·232·240) memory bytes. The computational complexity depends on Step 2 heavily. Thus, it is about 269.2(≈232·240·1/7·1/4·4) encryptions. Though this attack is not applicable to the full AES-192/256, this result is superior to the attack results of [1] (AES-192) and [3] (AES-256), respectively.


## 2.1. AES-192/256

AES-192/256 are 128-bit block ciphers with 192/256-bit secret keys. According to the length of the secret key, the number of rounds is 12 and 14, respectively. Each internal state is treated as a byte matrix of size 4×4, where each byte represents a value in GF(28) (see Figure 1).Figure 1
Internal state of AES-192/256 and Anubis.In roundr, input/output values and round key are denoted by Ir,Or, and RKr, respectively (r=1,…,12 (AES-192) or 14 (AES-256)). A whitening key is denoted by RK0. The round function of AES-192/256 applies the following four operations to the state matrix:(i)
SubBytes (SB): applying the same8×8 invertible S-box 16 times in parallel on each byte of the state;(ii)
ShiftRows (SR): cyclic shift of each row (theith row is shifted by i bytes to the left);(iii)
MixColumns (MC): multiplication of each column by a constant4×4 matrix over GF(28);(iv)
AddRoundKey (ARK): XORing the state with a128-bit round key.The SB, SR, MC, and ARK transformations are applied to each round except that MC is omitted in the last round. Besides, before the first round, an extra ARK is applied, which we call a whitening key step. For the more detailed descriptions of AES-192/256, we refer to [4]. We omit the key schedules of them, as they do not affect our attacks.


## 2.2. Finding a 4-Round Distinguisher of AES

In our attack on AES, we use a4-round distinguisher of round 2~5. We consider an input value I2 of round 2 in AES which is constructed as follows:(i)(I002,I102,I202,I302): four 8-bit variables;(ii)Iij2: a fixed 8-bit constant (0≤i≤3,1≤j≤3).By usingI2, we can construct the following equations on I3(i=0,…,3). Here, aij means the entry of the coefficient matrix of MC (j=0,…,3):
(1)Ii03=ai0∘SB[I002]⊕ai1∘SB[I112]⊕ai2∘SB[I222]⊕ai3∘SB[I332]⊕RKi02,Ii13=ai0∘SB[I012]⊕ai1∘SB[I122]⊕ai2∘SB[I232]⊕ai3∘SB[I302]⊕RKi12,Ii23=ai0∘SB[I022]⊕ai1∘SB[I132]⊕ai2∘SB[I202]⊕ai3∘SB[I312]⊕RKi22,Ii33=ai0∘SB[I032]⊕ai1∘SB[I102]⊕ai2∘SB[I212]⊕ai3∘SB[I322]⊕RKi32.Note that eachIi03, Ii13, Ii23, and Ii33 depends on only one 8-bit variable and one 8-bit round key: (I002,RKi02),(I302,RKi12),(I202,RKi22), and (I102,RKi32).Applying the above procedure repeatedly, as shown in (2), we can obtain an equation on an input value I005 of round 5 by using I2. Here, bold characters indicate (I102,I202,I302)(2)I005=a00∘SB[a00∘SB(a00∘SB[I002]⊕a01∘SB[I112]⊕a02∘SB[I222]⊕a03∘SB[I332]⊕RK002)⊕a01∘SB(a10∘SB[I012]⊕a11∘SB[I122]⊕a12∘SB[I232]⊕a13∘SB[I302]⊕RK112)⊕a02∘SB(a20∘SB[I022]⊕a21∘SB[I132]⊕a22∘SB[I202]⊕a23∘SB[I312]⊕RK222)⊕a03∘SB(a30∘SB[I032]⊕a31∘SB[I102]⊕a32∘SB[I212]⊕a33∘SB[I322]⊕RK332)⊕RK003]⊕a01∘SB[a10∘SB(a00∘SB[I012]⊕a01∘SB[I022]⊕ai2∘SB[I232]⊕a03∘SB[I302]⊕RK012)⊕a11∘SB(a10∘SB[I022]⊕a11∘SB[I132]⊕a12∘SB[I202]⊕a13∘SB[I312]⊕RK122)⊕a12∘SB(a20∘SB[I032]⊕a21∘SB[I102]⊕a22∘SB[I212]⊕a23∘SB[I322]⊕RK232)⊕a13∘SB(a30∘SB[I002]⊕a31∘SB[I112]⊕a32∘SB[I222]⊕a33∘SB[I332]⊕RK302)⊕RK113]⊕a02∘SB[a20∘SB(a00∘SB[I022]⊕a01∘SB[I132]⊕a02∘SB[I202]⊕a03∘SB[I312]⊕RK022)⊕a21∘SB(a10∘SB[I032]⊕a11∘SB[I102]⊕a12∘SB[I212]⊕a13∘SB[I322]⊕RK132)⊕a22∘SB(a20∘SB[I002]⊕a21∘SB[I112]⊕a22∘SB[I222]⊕a23∘SB[I332]⊕RK202)⊕a23∘SB(a30∘SB[I012]⊕a31∘SB[I122]⊕a32∘SB[I232]⊕a33∘SB[I302]⊕RK312)⊕RK223]⊕a03∘SB[a30∘SB(a00∘SB[I032]⊕a01∘SB[I102]⊕a02∘SB[I212]⊕a03∘SB[I322]⊕RK032)⊕a31∘SB(a10∘SB[I002]⊕a11∘SB[I112]⊕a12∘SB[I222]⊕a13∘SB[I332]⊕RK102)⊕a32∘SB(a20∘SB[I012]⊕a21∘SB[I122]⊕a22∘SB[I232]⊕a23∘SB[I302]⊕RK212)⊕a33∘SB(a30∘SB[I022]⊕a31∘SB[I132]⊕a32∘SB[I202]⊕a33∘SB[I312]⊕RK322)⊕RK333]⊕RK004.Note that this equation consists of five parts as follows:(3)I005=(a00∘SB[·])⊕(a01∘SB[·])⊕(a02∘SB[·])⊕(a03∘SB[·])⊕RK004.
If we find different (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) which satisfy that each subpart including (I102,I202,I302), that is, (2,3,4)th rows of the first part, (1,2,3)th rows of the second part, (1,2,4)th rows of the third part, and (1,3,4)th rows of the fourth part in (2), has the same value for a given I002, then I005′ is equal to I005′′. That is, for all I002∈{0,…,255}, these (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) result in the same 32-bit value of four subparts (the length of the value in each subpart is 8 bits). By the birthday paradox, we can obtain different (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) from 216(I102,I202,I302) with the probability of 0.5.We can expressI5 by using O5 as follows. Here, f-1 means the inverse of a function f(4)O5=ARKRK5∘MC∘SR∘SB[I5]=MC∘SR∘ARKSR-1∘MC-1[RK5]∘SB[I5]⟹SB[I5]=ARKSR-1∘MC-1[RK5]∘SR-1∘MC-1[O5].
If we obtain different (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) satisfying I005′=I005′′, then SB[I005′] is also equal to SB[I005′′]. Thus, from the above equation, we can construct the following equation. Here, bij means the entry of the coefficient matrix of MC-1(5)SB[I005′]=b00∘O005′⊕b01∘O105′⊕b02∘O205′⊕b03∘O305′=b00∘O005′′⊕b01∘O105′′⊕b02∘O205′′⊕b03∘O305′′=SB[I005′′].
For all I002∈{0,…,255}, we can check that I005′ is equal to I005′′ by using (5). That is, with the probability of 0.5, we can find different (I102′,I202′,I302′) and (I102′′,I202′′,I302′′) satisfying (5) for all I002 (among 216 candidates).On the other hand, our attack on AES recovers a192-bit round key and the probability that (5) holds for one I002 is 2-8. So, if we use only 25I002, the probability that (5) holds is (2-8)25=2-200. Since 2-200·2192≪1, we consider only 25I002.


## 2.3. Collision Attack on a 7-Round Reduced AES

Now, we show how to exploit a4-round distinguisher constructed in the previous subsection in order to attack a 7-round reduced AES.Similarly to the previous subsection,O5 can be expressed by using O7 as follows:
(6)O7=ARKRK7∘SR∘SB∘ARKRK6∘MC∘SR∘SB[O5]=SR∘ARKSR-1[RK7]∘SB∘MC∘SR∘ARKSR-1∘MC-1[RK6]∘SB[O5]⟹O5=SB-1∘ARKSR-1∘MC-1[RK6]∘SR-1∘MC-1∘SB-1∘ARKSR-1[RK7]∘SR-1[O7].
For the simplicity of notations, SR-1∘MC-1[RK6] and SR-1[RK7] in (6) are denoted by RK6* and RK7*, respectively.Our attack procedure on AES is as follows (see Figure2). (1)
Construct232 plaintexts Pi, where all byte values except (P00i,P11i,P22i,P33i) are fixed constants, and obtain the corresponding ciphertexts Ci (i=0,…,232-1). Sort Ci's according to a 32-bit value P00i∥P11i∥P22i∥P33i.(2)
For eachj(=0,…,3), guess 40-bit round keys (RKj06*, RK0((4-j)mod4)7*, RK1((4-j)mod4)7*, RK2((4-j)mod4)7*, RK3((4-j)mod4)7*) and compute the corresponding Oj05 from the guessed round keys and Ci by using (6) (e.g., guess (RK006*,RK007*,RK107*,RK207*,RK307*) to compute O005). Sort Oj05 according to the guessed round keys, i and j, and keep them in a table.(3)
Select216 sets Sk including 25 output values X of MC in round 1(k=0,…,216-1). Note that Xmn are fixed constants in all Sk(0≤m≤3,1≤n≤3). In each Sk, 25X00 have different values but all Sk contain the same X00. In the case of (X10,X20,X30), they are different in each Sk but the same in all Sk.(4)
Guess32-bit round keys (RK000,RK110,RK220,RK330) and construct 216 sets Qk including the corresponding (P00′,P11′,P22′,P33′) from each X in Sk, and do the following:
(i)
choose different two setsQk1 and Qk2. By using the table constructed in Step 2, check that 25 pairs from Qk1 and Qk2 satisfy (5);(ii)
if all 25 pairs satisfy (5), then output the corresponding 192-bit guessed round keys as the right round keys of AES.Figure 2
The attack procedure on AES-192/256.The data complexity of this attack is232 chosen plaintexts and the memory complexity is 274(≈4·232·240) memory bytes. The computational complexity depends on Step 2 heavily. Thus, it is about 269.2(≈232·240·1/7·1/4·4) encryptions. Though this attack is not applicable to the full AES-192/256, this result is superior to the attack results of [1] (AES-192) and [3] (AES-256), respectively.


## 3. Collision Attacks on 8-Round Reduced Crypton-192/256 and mCrypton-96/128

In this section, we present collision attacks on 8-round reduced Crypton-192/256 and mCrypton-96/128. Our attacks on 8-round reduced mCrypton-96/128 are similar to them on 8-round reduced Crypton-192/256. Thus, we mainly introduce the attacks on 8-round reduced Crypton-192/256. Furthermore, similarly to the attacks on AES-192/256, the attack procedure on Crypton-192 (mCrypton-96) is the same as that on Crypton-256 (mCrypton-128). Thus, for the simplicity of notations, we just call them Crypton-192/256 (mCrypton-96/128) and Crypton (mCrypton). First, we briefly present Crypton and mCrypton.


### 3.1. Crypton and mCrypton

As shown in Figure3(a), a 128-bit block cipher Crypton has a 12-round SPN structure with 128/192/2 56-bit secret keys and processes blocks of 128 bits in the form of 4 × 4 byte array (see Figure 4). Note that indices used in the internal state of Crypton are different from that of AES.(a) Crypton and (b) mCrypton.
(a)
(b)Figure 4
Internal state of Crypton and mCrypton.Similarly to AES-192/256, in roundr, we denote input/output values and round key Ir,Or, and RKr, respectively (r=1,…,12). The round function ρ of Crypton consists of the following four operations:  (i)
γ: applying four 4×4 S-boxes (S0,S1,S2,S3) 4 times in parallel on each byte of the state. Note that two versions (γo,γe) of γ are used according to rounds. In detail, γo is for odd rounds and γe is for even rounds;(ii)
π: mixing each byte column of 4 × 4 array by using four masking bytes (m0,m1,m2,m3). Similarly to γ, two versions (πo,πe) of π are applied according to rounds (πo is for odd rounds and πe is for even rounds);(iii)
τ: moving the byte at the (i,j)th position to the (j,i)th position;(iv)
σ: XORing the state with an 128-bit round key.The round functionρ consists of applying in sequence four operations, the S-box transformation γ, the bit permutation π, the byte transposition τ, and the key addition σ, to the 4×4 byte array. More specifically, the odd round function ρoRK and the even round function ρeRK are defined (for a round key RK) as follows:(i)
ρoRK=σRK∘τ∘πo∘γo for odd rounds;(ii)
ρeRK=σRK∘τ∘πe∘γefor even rounds.For the more detailed descriptions of Crypton, we refer to [5]. Similarly to our attacks on AES-192/256, our attacks on Crypton do not also consider the key schedule of this algorithm. Thus, we omit its key schedules.mCrypton is a 64-bit lightweight block cipher designed for use in low-cost and resource-constrained applications such as RFID tags and sensors in wireless sensor networks. As shown in Figure3(b), it has a 12-round SPN structure and supports the 64/96/128-bit secret keys. The overall structure of mCrypton is similar to Crypton except that mCrypton is based on nibble-oriented operations (note that Crypton is based on byte-oriented operations).


### 3.2. Collision Attacks on an 8-Round Reduced Crypton

First, we explain the way to find a distinguisher of Crypton. By using a similar method in the attack on AES-192/256, we can also construct a 4-round distinguisher of Crypton. Furthermore, because of the weak diffusion property of Crypton, we can extend this distinguisher to a 5-round distinguisher of it. In detail, our attacks on an 8-round reduced Crypton consider a 5-round distinguisher of round 2~6.Recall that, in the attack on AES-192/256, an equation onO005 can be constructed by using I2. We apply this method to Crypton. As a result, we obtain an equation on I306 by using I2. Similarly to AES-192/256, this equation consists of five parts as follows. Here, mi means a masking byte used in π and “∧” is a bitwise AND operation
(7)I306=(S0[·]∧m3)⊕(S1[·]∧m0)⊕(S2[·]∧m1)⊕(S3[·]∧m2)⊕RK305.On the other hand,I6 can be written by using O6 as follows:
(8)O6=σRK6∘τ∘πe∘γe[I6]=τ∘πe∘σπe-1∘τ-1(RK6)∘γe[I6]⟹γe[I6]=σπe-1∘τ-1(RK6)∘πe-1∘τ-1[O6].Thus, we use the following equation as a checking equation (note that, in the case of the attack on AES-192/256, a checking equation is (5))
(9)γe[I306′]=(O036′∧m0)⊕(O136′∧m3)⊕(O236′∧m2)⊕(O336′∧m1)=(O036′′∧m0)⊕(O136′′∧m3)⊕(O236′′∧m2)⊕(O336′′∧m1)=γe[I306′′].The overall attack procedure is similar to the case of AES. Figure5 presents our attack procedure on an 8-round reduced Crypton. The method to compute O6 from O8 is shown in
(10)O8=τ∘πe∘τ∘σRK8∘τ∘πe∘γe∘σRK7∘τ∘πo∘γo[O6]=τ∘πe∘τ∘τ∘πe∘σπe-1∘τ-1[RK8]∘γe∘τ∘πo∘σπo-1∘τ-1[RK7]∘γo[O6]=τ∘σπe-1∘τ-1[RK8]∘γe∘τ∘πo∘σπo-1∘τ-1[RK7]∘γo[O6]=στ∘πe-1∘τ-1[RK8]∘τ∘γe∘τ∘πo∘σπo-1∘τ-1[RK7]∘γo[O6]=στ∘πe-1∘τ-1[RK8]∘γe∘πo∘σπo-1∘τ-1[RK7]∘γo[O6].⟹O6=γo-1∘σπo-1∘τ-1[RK7]∘πo-1∘γe-1∘στ∘πe-1∘τ-1[RK8][O8].Figure 5
The attack procedure on Crypton-192/256 and mCrypton-96/128.The complexities of this attack are as follows:(i)
the data complexity:296 chosen plaintexts;(ii)
the memory complexity:2133 memory bytes;(iii)
the computational complexity:2161.6 encryptions.So far, the best attack result was the truncated differential cryptanalysis on8-round reduced Crypton-192/256 proposed in [8]. This attack requires the computational complexity of 2126.2 encryptions with 2126 chosen plaintexts, respectively. Compared to these results, our attack decreases the data complexity but increases the computational complexity.


### 3.3. Collision Attacks on an 8-Round Reduced mCrypton

As shown in Figure5, the attack procedure on mCrypton is the same as that on Crypton except that it is based on nibble-oriented operations (recall that Crypton is based on byte-oriented operations). In detail, our attack on mCrypton uses (9) as a checking equation and O6 is computed from O8 by using (10).Since the size of internal state of mCrypton is half of that in Crypton, the complexities of the attack on mCrypton are half of them on Crypton. The complexities of the attack on mCrypton are as follows:(i)
the data complexity:248 chosen plaintexts;(ii)
the memory complexity:281.6 memory bytes;(iii)
the computational complexity:265 encryptions.In [9], related-key impossible differential cryptanalysis on 9-round reduced mCrypton-96/128 was proposed. The attack on a 9-round reduced mCrypton-96 needs the computational complexity of 274.9 encryptions with 259.9 chosen plaintexts. In the case of a 9-round reduced mCrypton-128, we need the computational complexity of 266.7 encryptions with 259.7 chosen plaintexts. To our knowledge, these are the best results on mCrypton-96/128. However, considering the attack assumption of a related-key attack, our attacks are more practical than it.


## 3.1. Crypton and mCrypton

As shown in Figure3(a), a 128-bit block cipher Crypton has a 12-round SPN structure with 128/192/2 56-bit secret keys and processes blocks of 128 bits in the form of 4 × 4 byte array (see Figure 4). Note that indices used in the internal state of Crypton are different from that of AES.(a) Crypton and (b) mCrypton.
(a)
(b)Figure 4
Internal state of Crypton and mCrypton.Similarly to AES-192/256, in roundr, we denote input/output values and round key Ir,Or, and RKr, respectively (r=1,…,12). The round function ρ of Crypton consists of the following four operations:  (i)
γ: applying four 4×4 S-boxes (S0,S1,S2,S3) 4 times in parallel on each byte of the state. Note that two versions (γo,γe) of γ are used according to rounds. In detail, γo is for odd rounds and γe is for even rounds;(ii)
π: mixing each byte column of 4 × 4 array by using four masking bytes (m0,m1,m2,m3). Similarly to γ, two versions (πo,πe) of π are applied according to rounds (πo is for odd rounds and πe is for even rounds);(iii)
τ: moving the byte at the (i,j)th position to the (j,i)th position;(iv)
σ: XORing the state with an 128-bit round key.The round functionρ consists of applying in sequence four operations, the S-box transformation γ, the bit permutation π, the byte transposition τ, and the key addition σ, to the 4×4 byte array. More specifically, the odd round function ρoRK and the even round function ρeRK are defined (for a round key RK) as follows:(i)
ρoRK=σRK∘τ∘πo∘γo for odd rounds;(ii)
ρeRK=σRK∘τ∘πe∘γefor even rounds.For the more detailed descriptions of Crypton, we refer to [5]. Similarly to our attacks on AES-192/256, our attacks on Crypton do not also consider the key schedule of this algorithm. Thus, we omit its key schedules.mCrypton is a 64-bit lightweight block cipher designed for use in low-cost and resource-constrained applications such as RFID tags and sensors in wireless sensor networks. As shown in Figure3(b), it has a 12-round SPN structure and supports the 64/96/128-bit secret keys. The overall structure of mCrypton is similar to Crypton except that mCrypton is based on nibble-oriented operations (note that Crypton is based on byte-oriented operations).


## 3.2. Collision Attacks on an 8-Round Reduced Crypton

First, we explain the way to find a distinguisher of Crypton. By using a similar method in the attack on AES-192/256, we can also construct a 4-round distinguisher of Crypton. Furthermore, because of the weak diffusion property of Crypton, we can extend this distinguisher to a 5-round distinguisher of it. In detail, our attacks on an 8-round reduced Crypton consider a 5-round distinguisher of round 2~6.Recall that, in the attack on AES-192/256, an equation onO005 can be constructed by using I2. We apply this method to Crypton. As a result, we obtain an equation on I306 by using I2. Similarly to AES-192/256, this equation consists of five parts as follows. Here, mi means a masking byte used in π and “∧” is a bitwise AND operation
(7)I306=(S0[·]∧m3)⊕(S1[·]∧m0)⊕(S2[·]∧m1)⊕(S3[·]∧m2)⊕RK305.On the other hand,I6 can be written by using O6 as follows:
(8)O6=σRK6∘τ∘πe∘γe[I6]=τ∘πe∘σπe-1∘τ-1(RK6)∘γe[I6]⟹γe[I6]=σπe-1∘τ-1(RK6)∘πe-1∘τ-1[O6].Thus, we use the following equation as a checking equation (note that, in the case of the attack on AES-192/256, a checking equation is (5))
(9)γe[I306′]=(O036′∧m0)⊕(O136′∧m3)⊕(O236′∧m2)⊕(O336′∧m1)=(O036′′∧m0)⊕(O136′′∧m3)⊕(O236′′∧m2)⊕(O336′′∧m1)=γe[I306′′].The overall attack procedure is similar to the case of AES. Figure5 presents our attack procedure on an 8-round reduced Crypton. The method to compute O6 from O8 is shown in
(10)O8=τ∘πe∘τ∘σRK8∘τ∘πe∘γe∘σRK7∘τ∘πo∘γo[O6]=τ∘πe∘τ∘τ∘πe∘σπe-1∘τ-1[RK8]∘γe∘τ∘πo∘σπo-1∘τ-1[RK7]∘γo[O6]=τ∘σπe-1∘τ-1[RK8]∘γe∘τ∘πo∘σπo-1∘τ-1[RK7]∘γo[O6]=στ∘πe-1∘τ-1[RK8]∘τ∘γe∘τ∘πo∘σπo-1∘τ-1[RK7]∘γo[O6]=στ∘πe-1∘τ-1[RK8]∘γe∘πo∘σπo-1∘τ-1[RK7]∘γo[O6].⟹O6=γo-1∘σπo-1∘τ-1[RK7]∘πo-1∘γe-1∘στ∘πe-1∘τ-1[RK8][O8].Figure 5
The attack procedure on Crypton-192/256 and mCrypton-96/128.The complexities of this attack are as follows:(i)
the data complexity:296 chosen plaintexts;(ii)
the memory complexity:2133 memory bytes;(iii)
the computational complexity:2161.6 encryptions.So far, the best attack result was the truncated differential cryptanalysis on8-round reduced Crypton-192/256 proposed in [8]. This attack requires the computational complexity of 2126.2 encryptions with 2126 chosen plaintexts, respectively. Compared to these results, our attack decreases the data complexity but increases the computational complexity.


## 3.3. Collision Attacks on an 8-Round Reduced mCrypton

As shown in Figure5, the attack procedure on mCrypton is the same as that on Crypton except that it is based on nibble-oriented operations (recall that Crypton is based on byte-oriented operations). In detail, our attack on mCrypton uses (9) as a checking equation and O6 is computed from O8 by using (10).Since the size of internal state of mCrypton is half of that in Crypton, the complexities of the attack on mCrypton are half of them on Crypton. The complexities of the attack on mCrypton are as follows:(i)
the data complexity:248 chosen plaintexts;(ii)
the memory complexity:281.6 memory bytes;(iii)
the computational complexity:265 encryptions.In [9], related-key impossible differential cryptanalysis on 9-round reduced mCrypton-96/128 was proposed. The attack on a 9-round reduced mCrypton-96 needs the computational complexity of 274.9 encryptions with 259.9 chosen plaintexts. In the case of a 9-round reduced mCrypton-128, we need the computational complexity of 266.7 encryptions with 259.7 chosen plaintexts. To our knowledge, these are the best results on mCrypton-96/128. However, considering the attack assumption of a related-key attack, our attacks are more practical than it.


## 4. Collision Attack on an 8-Round Reduced Anubis

First, we present Anubis, and then a collision attack on an8-round reduced Anubis is introduced.


### 4.1. Anubis

As shown in Figure6, Anubis is a 128-bit block cipher with variable-length keys from 128 bits to 320 bits in steps of 32 bits. The number of rounds depends on the length of the secret key: at least 12 (for the 128-bit secret key), plus one extra round for each additional 32 bits. For example, when the length of the secret key is 192(=128+2·32) bits, the number of rounds is 14(=12+2).Figure 6
Anubis.Anubis processes blocks of128 bits in the form of 4×4 byte array and uses the same indices as AES (see Figure 1). Similarly to block ciphers concerned in the previous sections, in round r, we denote input/output values and round key Ir, Or, and RKr, respectively.The round function of Anubis consists of sixteen8×8 S-box parallel lookups, a linear transformation (matrix transposition followed by multiplication by a constant MDS diffusion matrix), and the round key addition. These transformations are defined as follows:(i)
γ: applying the same 8×8 S-box 16 times in parallel on each byte of the state;(ii)
τ: moving the byte at the (i,j)th position to the (j,i)th position;(iii)
θ: multiplication of each column by a constant 4×4 matrix over GF(28);(iv)
σ: XORing the state with a 128-bit round key.For the more detailed descriptions of Anubis, we refer to [7]. Similarly to the previous sections, we omit their key schedules, as they do not affect our attacks.


### 4.2. Collision Attacks on an 8-Round Reduced Anubis

Our attack on an8-round reduced Anubis is similar to the attacks on AES-192/256, Crypton-192/256, and mCrypton-96/128. In collision attack on an 8-round reduced Anubis, we use a 5-round distinguisher of round 2~6. By using a similar method of the attack introduced in the previous sections, we can obtain the following equation on I006 by using I2:
(11)I006=(S[·]∘01)⊕(S[·]∘02)⊕(S[·]∘04)⊕(S[·]∘06)⊕RK005.On the other hand,I6 can be written by using O6 as follows:
(12)O6=σRK6∘θ∘τ∘γ[I6]=θ∘τ∘στ-1∘θ-1[RK6]∘γ[I6]⟹γ[I6]=στ-1∘θ-1[RK6]∘τ-1∘θ-1[O6].
Thus, we use the following equation as a checking equation
(13)γ[I006′]=(O006′∘01)⊕(O106′∘02)⊕(O206′∘04)⊕(O306′∘06)=(O006′′∘01)⊕(O106′′∘02)⊕(O206′′∘04)⊕(O306′′∘06)=γe[I006′′].The attack procedure on an8-round reduced Anubis is similar to that on block ciphers proposed in the previous sections. Figure 7 presents our attack procedure on an 8-round reduced Anubis. In our attack, the method to compute O6 from O8 is
(14)O8=σRK8∘τ∘γ∘σRK7∘θ∘τ∘γ[O6]O8=τ∘στ-1[RK8]∘γ∘σRK7∘θ∘τ∘γ[O6]O8=τ∘στ-1[RK8]∘θ∘τ∘στ-1∘θ-1[RK7]∘γ[O6]⟹O6=γ-1∘στ-1∘θ-1[RK7]∘τ-1∘θ-1∘στ-1[RK8]∘τ-1[O8].
The complexities of this attack is as follows:(i)
the data complexity:296 chosen plaintexts;(ii)
the memory complexity:2133 memory bytes;(iii)
the computational complexity:2161.6 encryptions.Figure 7
The attack procedure on Anubis.So far, the best attack results on Anubis are a collision attack and a square attack on a7-round reduced version [11]. A collision attack on a 7-round reduced Anubis requires the computational complexity of 2140 encryptions with 232 chosen plaintexts. In the case of a square attack on this algorithm, we need the computational complexity of 2120 encryptions with 2128~2119 chosen plaintexts. Thus, our attack result is superior to these cryptanalytic results.


## 4.1. Anubis

As shown in Figure6, Anubis is a 128-bit block cipher with variable-length keys from 128 bits to 320 bits in steps of 32 bits. The number of rounds depends on the length of the secret key: at least 12 (for the 128-bit secret key), plus one extra round for each additional 32 bits. For example, when the length of the secret key is 192(=128+2·32) bits, the number of rounds is 14(=12+2).Figure 6
Anubis.Anubis processes blocks of128 bits in the form of 4×4 byte array and uses the same indices as AES (see Figure 1). Similarly to block ciphers concerned in the previous sections, in round r, we denote input/output values and round key Ir, Or, and RKr, respectively.The round function of Anubis consists of sixteen8×8 S-box parallel lookups, a linear transformation (matrix transposition followed by multiplication by a constant MDS diffusion matrix), and the round key addition. These transformations are defined as follows:(i)
γ: applying the same 8×8 S-box 16 times in parallel on each byte of the state;(ii)
τ: moving the byte at the (i,j)th position to the (j,i)th position;(iii)
θ: multiplication of each column by a constant 4×4 matrix over GF(28);(iv)
σ: XORing the state with a 128-bit round key.For the more detailed descriptions of Anubis, we refer to [7]. Similarly to the previous sections, we omit their key schedules, as they do not affect our attacks.


## 4.2. Collision Attacks on an 8-Round Reduced Anubis

Our attack on an8-round reduced Anubis is similar to the attacks on AES-192/256, Crypton-192/256, and mCrypton-96/128. In collision attack on an 8-round reduced Anubis, we use a 5-round distinguisher of round 2~6. By using a similar method of the attack introduced in the previous sections, we can obtain the following equation on I006 by using I2:
(11)I006=(S[·]∘01)⊕(S[·]∘02)⊕(S[·]∘04)⊕(S[·]∘06)⊕RK005.On the other hand,I6 can be written by using O6 as follows:
(12)O6=σRK6∘θ∘τ∘γ[I6]=θ∘τ∘στ-1∘θ-1[RK6]∘γ[I6]⟹γ[I6]=στ-1∘θ-1[RK6]∘τ-1∘θ-1[O6].
Thus, we use the following equation as a checking equation
(13)γ[I006′]=(O006′∘01)⊕(O106′∘02)⊕(O206′∘04)⊕(O306′∘06)=(O006′′∘01)⊕(O106′′∘02)⊕(O206′′∘04)⊕(O306′′∘06)=γe[I006′′].The attack procedure on an8-round reduced Anubis is similar to that on block ciphers proposed in the previous sections. Figure 7 presents our attack procedure on an 8-round reduced Anubis. In our attack, the method to compute O6 from O8 is
(14)O8=σRK8∘τ∘γ∘σRK7∘θ∘τ∘γ[O6]O8=τ∘στ-1[RK8]∘γ∘σRK7∘θ∘τ∘γ[O6]O8=τ∘στ-1[RK8]∘θ∘τ∘στ-1∘θ-1[RK7]∘γ[O6]⟹O6=γ-1∘στ-1∘θ-1[RK7]∘τ-1∘θ-1∘στ-1[RK8]∘τ-1[O8].
The complexities of this attack is as follows:(i)
the data complexity:296 chosen plaintexts;(ii)
the memory complexity:2133 memory bytes;(iii)
the computational complexity:2161.6 encryptions.Figure 7
The attack procedure on Anubis.So far, the best attack results on Anubis are a collision attack and a square attack on a7-round reduced version [11]. A collision attack on a 7-round reduced Anubis requires the computational complexity of 2140 encryptions with 232 chosen plaintexts. In the case of a square attack on this algorithm, we need the computational complexity of 2120 encryptions with 2128~2119 chosen plaintexts. Thus, our attack result is superior to these cryptanalytic results.


## 5. Conclusion

In this paper, we have introduced collision attacks on seven SPN block ciphers, 7-round reduced AES-192/256, 8-round reduced Crypton-192/256, 8-round reduced mCrypton-96/128, and an 8-round reduced Anubis. Our attacks are based on the idea of [3].Our attacks on7-round reduced AES-192/256 improve the attack results based on a type of meet-in-the-middle attack. Considering that the best attack results on Crypton-192/256 are those on 8-round reduced versions, our attacks on these algorithms are meaningful. Our attacks on 8-round reduced mCrypton-96/128 are not best results on mCrypton-96/128. However, considering that known best attack results on them are based on a related-key attack, our attacks are more practical than them. In the case of Anubis, our attack result is superior to known cryptanalytic result on this algorithm.



---

*Source: 713673-2013-11-10.xml*