# Improved Biclique Cryptanalysis of the Lightweight Block Cipher Piccolo

Authors: Guoyong Han; Wenying Zhang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Biclique cryptanalysis is a typical attack through finding a biclique which is a type of bipartite diagram to reduce the computational complexity. By investigating the subkey distribution and the encryption structure, we find out a weakness in the key schedule of Piccolo-80. A 6-round biclique is constructed for Piccolo-80 and a 7-round biclique for Piccolo-128. Then a full round biclique cryptanalysis of Piccolo is presented. The results of the attacks are with data complexity of 240 and 224 chosen ciphertexts and with computational complexity of 279.22 and 2127.14, respectively. They are superior to other known results of biclique cryptanalytic on Piccolo.


---

## Body

## 1. Introduction

In ASIACRYPT 2011, Bogdanov et al. proposed a biclique on recovering the keys of the full AES-128/192/256 [1], which is a type of meet-in-the-middle attack and the recent cryptanalysis technique of block ciphers. In [1], they gave two techniques by constructing bicliques for AES. One is the independent related-key differentials biclique and the other is the long biclique. Soon after the paper was published, a great deal of cryptanalytical results on the other block ciphers were suggested.The crucial issue of the technology is to construct a superior biclique structure at the ciphertext (or plaintext). In a biclique, one top set comprises2d1 ciphertexts (or plaintexts) while the other set is composed of  2d2 intermediate states. If d1=d2=d, the biclique structure is called a d-dimension (d=d1=d2=8 in this paper). In some constrained environments, for example, RFID tags or sensor nodes, the size of the secret key is typically 64, 80, or 128 bits. A lot of attacks on lightweight block cipher by using biclique have been published, such as Piccolo [2], IDEA [3], HIGHT [4, 5], LED [6], PRESENT [7, 8], TWINE [9, 10], and KLEIN [11].The meet-in-the-middle (MITM) attack is a representative method which is used in the security evaluation of block cipher, and its exceptional property is only a minimal data complexity. In recent years, many varieties emerged, for example, 3-subset MITM [12]. Many methods carry out the preimage attack to the hash function [13] and they consist of spice-and-cut frame and partial matching and so forth. Using the key expansion algorithm, opponent can construct a structure and pick out wrong keys through partial matching, which is the important idea of the method.Piccolo is a 64-bit block cipher. In accordance with the different length of the key, we signify the ciphers by Piccolo-80/128, respectively [14]. In ISPEC 2012, Wang et al. presented a biclique attack on reduced round Piccolo [2]. They attacked a 25-round Piccolo-80 with 248 chosen plaintexts and 278.95 computations. In the case of a 28-round Piccolo-128, this attack required 224 chosen plaintexts and 2126.79 computations. However, the authors considered Piccolo-80 without the postwhitening key and Piccolo-128 without the prewhitening key. In [5], Song et al. proposed a full round biclique cryptanalysis on Piccolo-80 demanding 248 chosen plaintexts and 279.34 computations and on Piccolo-128 requiring 224 chosen plaintexts and 2127.36 computations. In [15], we find two faults which are detailed in Section 4.1 in this paper. Compared to these results, ours are superior to theirs.In this paper, we detect a weakness in the key schedule on Piccolo-80; that is, the round keyrk47 can offset the postwhitening key partially. Based on this, the data complexity can be decreased greatly. We apply some observations on Piccolo in [16] and construct an independent related-key differentials biclique for the last several rounds. Then an 8-dimensional biclique structure of 6 rounds is constructed for Piccolo-80 and an 8-dimensional biclique structure of 7 rounds for Piccolo-128. The attacks are, respectively, with data complexity of 240 and 224, and with computational complexity of 279.22 and 2127.14, which are the best results currently. The attack results on Piccolo are summarized in Tables 1 and 2.Table 1
Summary of previous results of different method on Piccolo.
Piccolo-80 rounds
Piccolo-128 rounds
Method
Reference
7
7
Differential
Reference [14]
8
8
Linear
Reference [14]
9
9
Boomerang
Reference [14]
9
9
Impossible differential
Reference [14]
14
21
MITM
Reference [17]
19
23
MITM expectation
Reference [14]
25
28
Biclique cryptanalysis
Reference [2]
25
31
Biclique cryptanalysis
This paperTable 2
Summary of biclique cryptanalytic results on Piccolo.
Target algorithm
Round
Data
Computations
Attack type
Reference
Piccolo-80
25 (without the postwhitening key)
248
278.95
Biclique
Reference [2]
Piccolo-80
25 (full)
248
279.34
Biclique
Reference [5]
Piccolo-80
25 (full)
240
279.22
Biclique
Section4.2
Piccolo-128
28 (without the prewhitening key)
224
2126.79
Biclique
Reference [2]
Piccolo-128
31 (full)
248
2127.36
Biclique
Reference [5]
Piccolo-128
31 (full)
224
2127.14
Biclique
Section4.3
Piccolo-128
31 (full)
28
2127.30
Biclique
Section4.4The structure of the paper is as follows. Section2 describes the structures of Piccolo-80 and Piccolo-128. Section 3 introduces briefly biclique cryptanalysis. Then, Section 4 presents the cryptanalysis with an 8-dimensional biclique of 6 rounds on full round Piccolo-80 and with a biclique structure of 7 rounds on full round Piccolo-128. The data complexity and computational complexity on Piccolo-80 and Piccolo-128 are given, respectively. Finally, we draw our conclusion in Section 5.


## 2. Piccolo Specifications

### 2.1. Notations

⊕: bit-wise exclusive or (XOR).
r: iterative rounds.
∥: concatenation.
K
i: the ith 16-bit group of the key K(0≤i≤4 for Piccolo-80, 0≤i≤7 for Piccolo-128).
W
K
i: the 16-bit whitening key (0≤i≤3).
r
k
i: the 16-bit round key (0≤i≤49 for Piccolo-80, 0≤i≤61 for Piccolo-128).
c
o
n
i
80: a 16-bit round constant.
a
(
b
): b denoting the bit length of a.
P: 64-bit plaintext, P including four 16-bit words P[i](0≤i≤3).
C: 64-bit ciphertext, C including four 16-bit words C[i](0≤i≤3).
F
i
,
j
r(64): the ith and jth byte of the state afterF-Function in rth round.


### 2.2. Description of Piccolo

The structure of Piccolo is a variation of generalized Feistel, as shown in Figure1. Piccolo-80/128 supports 80-bit and 128-bit key sizes along with 25 and 31 rounds, respectively.Figure 1
The structure of Piccolo.The detailed descriptions of Piccolo are in [14], and each round of Piccolo consists of the following 3 steps:(1)
F-Function (FF), {0,1}16→{0,1}16 being composed of two S-box layers and a diffusion matrixM.(2)
AddRoundKey (AK), the 64-bit intermediate state XORs a round key.(3)
RoundPermutation (RP), which splits a 64-bit input into eight bytes and then maps them.


### 2.3. Key Schedule

The key schedule of Piccolo is straightforward and simple. Firstly, the 80-bit master key of Piccolo-80 is represented by concatenation of five 2 bytes; that is,K=K0∥K1∥K2∥K3∥K4, where Kj = (K[j]L, K[j]R). The whitening keys (WK0,WK1,WK2,WK3) and the subkey (rk2i,rk2i+1) of 25 rounds are engendered as follows:WK0 = K[0]L∥K[1]R, WK1 = K[1]L∥K[0]R, WK2 = K[4]L∥K[3]R, WK3 = K[3]L∥K[4]R.Fori = 0 to r-1(1)rk2i,rk2i+1=con2i80,con2i+180⊕K2,K3,imod5≡0or  2,K0,K1,imod5≡1or4,K4,K4,imod5≡3.For Piccolo-128, the distribution of subkey is similar to that of Piccolo-80. The 128-bit master key is denoted byK=K[0]∥K[1]∥K[2]∥K[3]∥K[4]∥K[5]∥K[6]∥K[7], where K[j]= (K[j]L,K[j]R). The whitening keys and 31-round subkey are computed as follows:WK0 = K[0]L∥K[1]R, WK1 = K[1]L∥K[0]R, WK2 = K[4]L∥K[7]R, WK3 = K[7]L∥K[4]R.Fori = 0 to 2r-1
if ((i + 2) mod 8 ≡ 0), then
(K[0]∥K[1]∥K[2]∥K[3]∥K[4]∥K[5]∥K[6]∥K[7]) = (K[2]∥K[1]∥K[6]∥K[7]∥K[0]∥K[3]∥K[4]∥K[5]);rki=K[i+2mod⁡8]⊕coni128.The specific subkeys of Piccolo-80/128 are illustrated in Table3.Table 3
Key schedule of Piccolo.
Piccolo-80
Piccolo-128
Roundi
Round key
Master key
Roundi
Round key
Master key
Initial
(
W
K
0
,
W
K
1
)
(
K
[
0
]
L
∥
K
[
1
]
R
,
K
[
1
]
L
∥
K
[
0
]
R
)
Initial
(
W
K
0
,
W
K
1
)
(
K
[
0
]
L
∥
K
[
1
]
R
,
K
[
1
]
L
∥
K
[
0
]
R
)
0
(rk0,rk1)
(K[2],K[3])
0
(rk0,rk1)
(K[2],K[3])
1
(rk2,rk3)
(K[0],K[1])
1
(rk2,rk3)
(K[4],K[5])
2
(rk4,rk5)
(K[2],K[3])
2
(rk4,rk5)
(K[6],K[7])
3
(rk6,rk7)
(K[4],K[4])
3
(rk6,rk7)
(K[2],K[1])
4
(rk8,rk9)
(K[0],K[1])
4
(rk8,rk9)
(K[6],K[7])
5
(rk10,rk11)
(K[2],K[3])
5
(rk10,rk11)
(K[0],K[3])
6
(rk12,rk13)
(K[0],K[1])
6
(rk12,rk13)
(K[4],K[5])
⋮
⋮
⋮
⋮
⋮
⋮
18
(rk36,rk37)
(K[4],K[4])
24
(rk48,rk49)
(K[4],K[3])
19
(rk38,rk39)
(K[0],K[1])
25
(rk50,rk51)
(K[2],K[5])
20
(rk40,rk41)
(K[2],K[3])
26
(rk52,rk53)
(K[0],K[7])
21
(rk42,rk43)
(K[0],K[1])
27
(rk54,rk55)
(K[4],K[1])
22
(rk44,rk45)
(K[2],K[3])
28
(rk56,rk57)
(K[0],K[7])
23
(rk46,rk47)
(K[4],K[4])
29
(rk58,rk59)
(K[6],K[3])
24
(rk48,rk49)
(K[0],K[1])
30
(rk60,rk61)
(K[2],K[5])
Final
(
W
K
2
,
W
K
3
)
(
K
[
4
]
L
∥
K
[
3
]
R
,
K
[
3
]
L
∥
K
[
4
]
R
)
Final
(
W
K
2
,
W
K
3
)
(
K
[
4
]
L
∥
K
[
7
]
R
,
K
[
7
]
L
∥
K
[
4
]
R
)


## 2.1. Notations

⊕: bit-wise exclusive or (XOR).
r: iterative rounds.
∥: concatenation.
K
i: the ith 16-bit group of the key K(0≤i≤4 for Piccolo-80, 0≤i≤7 for Piccolo-128).
W
K
i: the 16-bit whitening key (0≤i≤3).
r
k
i: the 16-bit round key (0≤i≤49 for Piccolo-80, 0≤i≤61 for Piccolo-128).
c
o
n
i
80: a 16-bit round constant.
a
(
b
): b denoting the bit length of a.
P: 64-bit plaintext, P including four 16-bit words P[i](0≤i≤3).
C: 64-bit ciphertext, C including four 16-bit words C[i](0≤i≤3).
F
i
,
j
r(64): the ith and jth byte of the state afterF-Function in rth round.


## 2.2. Description of Piccolo

The structure of Piccolo is a variation of generalized Feistel, as shown in Figure1. Piccolo-80/128 supports 80-bit and 128-bit key sizes along with 25 and 31 rounds, respectively.Figure 1
The structure of Piccolo.The detailed descriptions of Piccolo are in [14], and each round of Piccolo consists of the following 3 steps:(1)
F-Function (FF), {0,1}16→{0,1}16 being composed of two S-box layers and a diffusion matrixM.(2)
AddRoundKey (AK), the 64-bit intermediate state XORs a round key.(3)
RoundPermutation (RP), which splits a 64-bit input into eight bytes and then maps them.


## 2.3. Key Schedule

The key schedule of Piccolo is straightforward and simple. Firstly, the 80-bit master key of Piccolo-80 is represented by concatenation of five 2 bytes; that is,K=K0∥K1∥K2∥K3∥K4, where Kj = (K[j]L, K[j]R). The whitening keys (WK0,WK1,WK2,WK3) and the subkey (rk2i,rk2i+1) of 25 rounds are engendered as follows:WK0 = K[0]L∥K[1]R, WK1 = K[1]L∥K[0]R, WK2 = K[4]L∥K[3]R, WK3 = K[3]L∥K[4]R.Fori = 0 to r-1(1)rk2i,rk2i+1=con2i80,con2i+180⊕K2,K3,imod5≡0or  2,K0,K1,imod5≡1or4,K4,K4,imod5≡3.For Piccolo-128, the distribution of subkey is similar to that of Piccolo-80. The 128-bit master key is denoted byK=K[0]∥K[1]∥K[2]∥K[3]∥K[4]∥K[5]∥K[6]∥K[7], where K[j]= (K[j]L,K[j]R). The whitening keys and 31-round subkey are computed as follows:WK0 = K[0]L∥K[1]R, WK1 = K[1]L∥K[0]R, WK2 = K[4]L∥K[7]R, WK3 = K[7]L∥K[4]R.Fori = 0 to 2r-1
if ((i + 2) mod 8 ≡ 0), then
(K[0]∥K[1]∥K[2]∥K[3]∥K[4]∥K[5]∥K[6]∥K[7]) = (K[2]∥K[1]∥K[6]∥K[7]∥K[0]∥K[3]∥K[4]∥K[5]);rki=K[i+2mod⁡8]⊕coni128.The specific subkeys of Piccolo-80/128 are illustrated in Table3.Table 3
Key schedule of Piccolo.
Piccolo-80
Piccolo-128
Roundi
Round key
Master key
Roundi
Round key
Master key
Initial
(
W
K
0
,
W
K
1
)
(
K
[
0
]
L
∥
K
[
1
]
R
,
K
[
1
]
L
∥
K
[
0
]
R
)
Initial
(
W
K
0
,
W
K
1
)
(
K
[
0
]
L
∥
K
[
1
]
R
,
K
[
1
]
L
∥
K
[
0
]
R
)
0
(rk0,rk1)
(K[2],K[3])
0
(rk0,rk1)
(K[2],K[3])
1
(rk2,rk3)
(K[0],K[1])
1
(rk2,rk3)
(K[4],K[5])
2
(rk4,rk5)
(K[2],K[3])
2
(rk4,rk5)
(K[6],K[7])
3
(rk6,rk7)
(K[4],K[4])
3
(rk6,rk7)
(K[2],K[1])
4
(rk8,rk9)
(K[0],K[1])
4
(rk8,rk9)
(K[6],K[7])
5
(rk10,rk11)
(K[2],K[3])
5
(rk10,rk11)
(K[0],K[3])
6
(rk12,rk13)
(K[0],K[1])
6
(rk12,rk13)
(K[4],K[5])
⋮
⋮
⋮
⋮
⋮
⋮
18
(rk36,rk37)
(K[4],K[4])
24
(rk48,rk49)
(K[4],K[3])
19
(rk38,rk39)
(K[0],K[1])
25
(rk50,rk51)
(K[2],K[5])
20
(rk40,rk41)
(K[2],K[3])
26
(rk52,rk53)
(K[0],K[7])
21
(rk42,rk43)
(K[0],K[1])
27
(rk54,rk55)
(K[4],K[1])
22
(rk44,rk45)
(K[2],K[3])
28
(rk56,rk57)
(K[0],K[7])
23
(rk46,rk47)
(K[4],K[4])
29
(rk58,rk59)
(K[6],K[3])
24
(rk48,rk49)
(K[0],K[1])
30
(rk60,rk61)
(K[2],K[5])
Final
(
W
K
2
,
W
K
3
)
(
K
[
4
]
L
∥
K
[
3
]
R
,
K
[
3
]
L
∥
K
[
4
]
R
)
Final
(
W
K
2
,
W
K
3
)
(
K
[
4
]
L
∥
K
[
7
]
R
,
K
[
7
]
L
∥
K
[
4
]
R
)


## 3. Biclique Attack on Piccolo

### 3.1. Definition of Biclique

Biclique cryptanalysis is an attack based on MITM. The major idea is to build bicliques on the target subcipher and promote the computational efficiency. The basic principles of the biclique attack are explained in [1]. Let f be a several-round subcipher and f-1 is the inverse of f. The f maps 2d intermediate states {Sj} to 2d ciphertexts {Ci} with 22d keys {K[i,j]}:(2)Ki,j=K0,0K0,1⋯K0,2d-1⋮⋮⋱⋮K2d-1,0K2d-1,1⋯K2d-1,2d-1.The 3-tuple [{Ci},{Sj},{K[i,j]}] is named a biclique withd-dimension, if(3)Ci=fKi,jsj∀i,j∈0,1d.To avoid duplication, we do not explicate the detailed attack basis but three stages of the attack are described in more detail.


### 3.2. Biclique Cryptanalysis of Piccolo-80

#### 3.2.1. Phase 1: Key Partitioning

For greater clarity, we divide the key into 264 groups which have 216 keys. The K[0,0] enumerates 64-bit keys and fixes 16-bit keys with 016. As depicted in Section 2.3, each round has 32-bit subkey which is generated by master keysK[i] andK[j]. By investigating the subkey distribution (Table 3), an 8-dimensional biclique structure of 6 rounds is constructed by each right half of K[4] and K[2], that is, K[4]R and K[2]R. We find K[4]R of the round key rk47 can offset K[4]R of the postwhitening key, so it can decrease the data complexity greatly. By calculation, the computational complexity is optimal so far.The keysK[0,0],K[0,j],K[i,0], and K[i,j] of each group are depicted, as shown below:(4)K0,0=XX,XX,XA,XX,XA,whereX∈0,18,A=0x00,K0,j=K0,0⊕00,00,0j,00,00,wherej∈0,18,Ki,0=K0,0⊕00,00,00,00,0i,wherei∈0,18.Finally,(5)Ki,j=K0,0⊕K0,j⊕Ki,0=K0,0⊕00,00,0j,00,0i.Thus, the space ofK is divided into 264 groups of 216 keys each.


#### 3.2.2. Phase 2: 8-Dimensional Biclique Structure of 6 Rounds

We construct an 8-dimensional biclique structure of 6 rounds for Piccolo-80 with whitening keys for each group (Figure2). The biclique structure connects 28 ciphertexts to 28 intermediate states in each group of keys. The process of calculating the ciphertexts and intermediate states consists of the following 3 steps.Figure 2
6-round biclique construction of dimension 8 in Piccolo-80.
(a)
(b)
(c)Step 1.
LetC0=0(64) and decrypt C0 for 6 rounds to obtain S0 (Figure 2(a)); that is, S0 = f-1K[0,0](C0). The procedure is named basic calculation.Step 2.
In order to get the corresponding ciphertextCi, encrypt S0 using different keys K[i,0] for i∈{0,1}8 (Figure 2(c)). The differences between K[i,0] and K[0,0] can lead to the gray intermediate states’ differences and cause the computational complexity. The gray intermediate states need to be computed 28-1 times, whereas the remaining states are calculated just once because they have been already computed in Step 1. This step derives f(S0)→K[i,0]Ci.Step 3.
To get the corresponding statesSj, decrypt C0 using different keys K[0,j] for j∈{0,1}8 (Figure 2(b)). The differences between K[0,j] and K[0,0] can bring about the gray intermediate states’ differences. The gray intermediate states need to be computed 28-1 times, whereas the remaining states have been already computed. As a result, f-1(C0)→K[0,j](Sj) has been constructed.Thanks to the simplicity of the distribution of the subkey of Piccolo, the two differential paths do not share any active state. Fortunately, it is so easy to verify thatf(Sj)→K[i,j]Ci is always true for all i,j∈{0,1}8. Up to now, for each key group, we get a corresponding 8-dimensional biclique structure as discussed above.From Figure2, we find a weakness in the key schedule of Piccolo-80; that is, K[4]R of the round key rk47 can offset K[4]R of the postwhitening key. So it can reduce the data complexity greatly. The calculations of complexities are presented in Section 4.2.


#### 3.2.3. Phase 3: Meeting in the Middle over 19 Rounds

Choose a 16-bit internal state (V=F1,49) afterF-Function in round 9, as the intermediate matching variable (see Figure 3). The choice is made according to the total number ofF-Function and an effective filtering of the wrong keys. Next, we calculate these matching variates in both directions in order to obtain the accurate key.Figure 3
Recomputations in MITM for Piccolo-80.
(a)
(b)Backward Direction. Each value of the state Sj is decrypted under the key K[0,j] to derive V0,j⟵←K[0,j]Sj. After that, Sj is decrypted using all the possible 2d-1 keys K[i,j] to get  Vi,j⟵←K[i,j]Sj. Because of the same beginning, the key differences between K[0,j] and K[i,j] can cause the computational complexity. On Figure 3(b), the gray bytes are active and the white bytes need not be computed.Forward Direction. The procedure of forward direction is a bit more complex than the backward direction in calculation. Firstly, we decrypt the ciphertexts Ci for i∈{0,1}8 to obtain 28 plaintexts Pi. Secondly, each Pi is encrypted under the key K[i,0] to derive Pi→K[i,0]Vi,0→. After that, Pi is encrypted using all the possible 2d-1 keys K[i,j] to obtain Pi→K[i,j]Vi,j→. The differences between K[i,0] and K[i,j] can influence the computational complexity. On Figure 3(a), the gray bytes are active and the white bytes need not be computed.Search Candidates. In the last session of the attack, the adversary verifies the rest candidate key by the equality of Vi,j→ and Vi,j⟵ for all i,j∈{0,1}8 in each group exhaustively, until the right key is discovered.


### 3.3. Biclique Cryptanalysis of Piccolo-128

#### 3.3.1. Phase 1: Key Partitioning

We divide the 128-bit key into 2112 groups. K[0,0] enumerates 112-bit keys and fixes 16-bit keys with 016. By investigating the subkey distribution (Table 3), an 8-dimensional biclique structure of 7 rounds is constructed by each left half of K[6] and K[7], that is, K[6]L and K[7]L. The computational complexity of this structure is less than others’.Similar to Piccolo-80, the keysK[0,0],K[0,j],K[i,0], and K[i,j] of each group are depicted, as shown below:(6)K0,0=XX,XX,XX,XX,XX,XX,AX,AX,whereX∈0,18,A=0x00,K0,j=K0,0⊕00,00,00,00,00,00,00,j0,wherej∈0,18,Ki,0=K0,0⊕00,00,00,00,00,00,i0,00,wherei∈0,18.Finally,(7)Ki,j=K0,0⊕K0,j⊕Ki,0=K0,0⊕00,00,00,00,00,00,i0,j0.Thus, the key space ofK is divided into 2112 groups of 216 keys each.


#### 3.3.2. Phase 2: 8-Dimensional Biclique Structure of 7 Rounds

We construct an 8-dimensional biclique structure of 7 rounds for Piccolo-128 for each group (Figure4). Here, g is subciphers for round 24~30 and g-1 is the inverse of g. The process of calculating the ciphertexts and intermediate states consists of the following 3 steps.Figure 4
7-round biclique construction of dimension 8 in Piccolo-128.
(a)
(b)
(c)Step 1.
LetC0=0(64) and decrypt C0 for 7 rounds to obtain S0 (Figure 4(a)); that is, S0 = g-1K[0,0](C0).Step 2.
EncryptS0 using different keys K[i,0] for i∈{0,1}8 (Figure 4(c)). The differences between K[i,0] and K[0,0] can influence the gray intermediate states’ differences. This step derives g(S0)→K[i,0]Ci.Step 3.
DecryptC0 using different keys K[0,j] for j∈{0,1}8 (Figure 4(b)). The differences between K[0,j] and K[0,0] can bring about the gray intermediate states’ differences. As a result, g-1(C0)→K[0,j](Sj) has been constructed.Thanks to the simplicity of the distribution of the subkey of Piccolo-128, it is also very easy to verify thatg(Sj)→K[i,j]Ci is always true for all i,j∈{0,1}8. Up to now, for each key group, we get a corresponding 8-dimensional biclique structure.


#### 3.3.3. Phase 3: Meeting in the Middle over 24 Rounds

Select a 16-bit internal state (U=F1,412) afterF-Function in round 12, as the intermediate matching variable (see Figure 5). Next, we calculate these matching variates in both directions in order to obtain the right key.Figure 5
Recomputations in MITM for Piccolo-128.
(a)
(b)Backward Direction. Each value of the state Sj is decrypted under the key K[0,j] to obtain U0,j⟵←K[0,j]Sj. After that, Sj is decrypted using all the possible 2d-1 keys K[i,j] to get Ui,j⟵←K[i,j]Sj. On Figure 5(b), the gray bytes are active and the white bytes do not need to be computed.Forward Direction. Firstly, we decrypt the ciphertexts Ci for i∈{0,1}8 to obtain 28 plaintexts Pi. Secondly, each Pi is encrypted under the key K[i,0] to obtain Pi→K[i,0]Ui,0→. Then, Pi is encrypted using all the possible 2d-1 keys K[i,j] to get Pi→K[i,j]Ui,j→. On Figure 5(a), the gray bytes are active and the white bytes do not need to be computed.Search Candidates. In the last session of the attack, the adversary verifies the equality of Ui,j→ and Ui,j⟵ for all i,j∈{0,1}8 to discover the correct key.


### 3.4. Another Biclique Cryptanalysis of Piccolo-128

Similar to Section3.3, we construct an 8-dimensional biclique structure of 5 rounds (26~30) for Piccolo-128 by each left half of K[6] and K[2], that is, K[6]L and K[2]L (Figure 6).Figure 6
5-round biclique construction of dimension 8 in Piccolo-128.In the phase of meeting in the middle over 26 rounds, we select a 16-bit internal state (U=F1,413) afterF-Function in round 13, as the intermediate matching variable.


## 3.1. Definition of Biclique

Biclique cryptanalysis is an attack based on MITM. The major idea is to build bicliques on the target subcipher and promote the computational efficiency. The basic principles of the biclique attack are explained in [1]. Let f be a several-round subcipher and f-1 is the inverse of f. The f maps 2d intermediate states {Sj} to 2d ciphertexts {Ci} with 22d keys {K[i,j]}:(2)Ki,j=K0,0K0,1⋯K0,2d-1⋮⋮⋱⋮K2d-1,0K2d-1,1⋯K2d-1,2d-1.The 3-tuple [{Ci},{Sj},{K[i,j]}] is named a biclique withd-dimension, if(3)Ci=fKi,jsj∀i,j∈0,1d.To avoid duplication, we do not explicate the detailed attack basis but three stages of the attack are described in more detail.


## 3.2. Biclique Cryptanalysis of Piccolo-80

### 3.2.1. Phase 1: Key Partitioning

For greater clarity, we divide the key into 264 groups which have 216 keys. The K[0,0] enumerates 64-bit keys and fixes 16-bit keys with 016. As depicted in Section 2.3, each round has 32-bit subkey which is generated by master keysK[i] andK[j]. By investigating the subkey distribution (Table 3), an 8-dimensional biclique structure of 6 rounds is constructed by each right half of K[4] and K[2], that is, K[4]R and K[2]R. We find K[4]R of the round key rk47 can offset K[4]R of the postwhitening key, so it can decrease the data complexity greatly. By calculation, the computational complexity is optimal so far.The keysK[0,0],K[0,j],K[i,0], and K[i,j] of each group are depicted, as shown below:(4)K0,0=XX,XX,XA,XX,XA,whereX∈0,18,A=0x00,K0,j=K0,0⊕00,00,0j,00,00,wherej∈0,18,Ki,0=K0,0⊕00,00,00,00,0i,wherei∈0,18.Finally,(5)Ki,j=K0,0⊕K0,j⊕Ki,0=K0,0⊕00,00,0j,00,0i.Thus, the space ofK is divided into 264 groups of 216 keys each.


### 3.2.2. Phase 2: 8-Dimensional Biclique Structure of 6 Rounds

We construct an 8-dimensional biclique structure of 6 rounds for Piccolo-80 with whitening keys for each group (Figure2). The biclique structure connects 28 ciphertexts to 28 intermediate states in each group of keys. The process of calculating the ciphertexts and intermediate states consists of the following 3 steps.Figure 2
6-round biclique construction of dimension 8 in Piccolo-80.
(a)
(b)
(c)Step 1.
LetC0=0(64) and decrypt C0 for 6 rounds to obtain S0 (Figure 2(a)); that is, S0 = f-1K[0,0](C0). The procedure is named basic calculation.Step 2.
In order to get the corresponding ciphertextCi, encrypt S0 using different keys K[i,0] for i∈{0,1}8 (Figure 2(c)). The differences between K[i,0] and K[0,0] can lead to the gray intermediate states’ differences and cause the computational complexity. The gray intermediate states need to be computed 28-1 times, whereas the remaining states are calculated just once because they have been already computed in Step 1. This step derives f(S0)→K[i,0]Ci.Step 3.
To get the corresponding statesSj, decrypt C0 using different keys K[0,j] for j∈{0,1}8 (Figure 2(b)). The differences between K[0,j] and K[0,0] can bring about the gray intermediate states’ differences. The gray intermediate states need to be computed 28-1 times, whereas the remaining states have been already computed. As a result, f-1(C0)→K[0,j](Sj) has been constructed.Thanks to the simplicity of the distribution of the subkey of Piccolo, the two differential paths do not share any active state. Fortunately, it is so easy to verify thatf(Sj)→K[i,j]Ci is always true for all i,j∈{0,1}8. Up to now, for each key group, we get a corresponding 8-dimensional biclique structure as discussed above.From Figure2, we find a weakness in the key schedule of Piccolo-80; that is, K[4]R of the round key rk47 can offset K[4]R of the postwhitening key. So it can reduce the data complexity greatly. The calculations of complexities are presented in Section 4.2.


### 3.2.3. Phase 3: Meeting in the Middle over 19 Rounds

Choose a 16-bit internal state (V=F1,49) afterF-Function in round 9, as the intermediate matching variable (see Figure 3). The choice is made according to the total number ofF-Function and an effective filtering of the wrong keys. Next, we calculate these matching variates in both directions in order to obtain the accurate key.Figure 3
Recomputations in MITM for Piccolo-80.
(a)
(b)Backward Direction. Each value of the state Sj is decrypted under the key K[0,j] to derive V0,j⟵←K[0,j]Sj. After that, Sj is decrypted using all the possible 2d-1 keys K[i,j] to get  Vi,j⟵←K[i,j]Sj. Because of the same beginning, the key differences between K[0,j] and K[i,j] can cause the computational complexity. On Figure 3(b), the gray bytes are active and the white bytes need not be computed.Forward Direction. The procedure of forward direction is a bit more complex than the backward direction in calculation. Firstly, we decrypt the ciphertexts Ci for i∈{0,1}8 to obtain 28 plaintexts Pi. Secondly, each Pi is encrypted under the key K[i,0] to derive Pi→K[i,0]Vi,0→. After that, Pi is encrypted using all the possible 2d-1 keys K[i,j] to obtain Pi→K[i,j]Vi,j→. The differences between K[i,0] and K[i,j] can influence the computational complexity. On Figure 3(a), the gray bytes are active and the white bytes need not be computed.Search Candidates. In the last session of the attack, the adversary verifies the rest candidate key by the equality of Vi,j→ and Vi,j⟵ for all i,j∈{0,1}8 in each group exhaustively, until the right key is discovered.


## 3.2.1. Phase 1: Key Partitioning

For greater clarity, we divide the key into 264 groups which have 216 keys. The K[0,0] enumerates 64-bit keys and fixes 16-bit keys with 016. As depicted in Section 2.3, each round has 32-bit subkey which is generated by master keysK[i] andK[j]. By investigating the subkey distribution (Table 3), an 8-dimensional biclique structure of 6 rounds is constructed by each right half of K[4] and K[2], that is, K[4]R and K[2]R. We find K[4]R of the round key rk47 can offset K[4]R of the postwhitening key, so it can decrease the data complexity greatly. By calculation, the computational complexity is optimal so far.The keysK[0,0],K[0,j],K[i,0], and K[i,j] of each group are depicted, as shown below:(4)K0,0=XX,XX,XA,XX,XA,whereX∈0,18,A=0x00,K0,j=K0,0⊕00,00,0j,00,00,wherej∈0,18,Ki,0=K0,0⊕00,00,00,00,0i,wherei∈0,18.Finally,(5)Ki,j=K0,0⊕K0,j⊕Ki,0=K0,0⊕00,00,0j,00,0i.Thus, the space ofK is divided into 264 groups of 216 keys each.


## 3.2.2. Phase 2: 8-Dimensional Biclique Structure of 6 Rounds

We construct an 8-dimensional biclique structure of 6 rounds for Piccolo-80 with whitening keys for each group (Figure2). The biclique structure connects 28 ciphertexts to 28 intermediate states in each group of keys. The process of calculating the ciphertexts and intermediate states consists of the following 3 steps.Figure 2
6-round biclique construction of dimension 8 in Piccolo-80.
(a)
(b)
(c)Step 1.
LetC0=0(64) and decrypt C0 for 6 rounds to obtain S0 (Figure 2(a)); that is, S0 = f-1K[0,0](C0). The procedure is named basic calculation.Step 2.
In order to get the corresponding ciphertextCi, encrypt S0 using different keys K[i,0] for i∈{0,1}8 (Figure 2(c)). The differences between K[i,0] and K[0,0] can lead to the gray intermediate states’ differences and cause the computational complexity. The gray intermediate states need to be computed 28-1 times, whereas the remaining states are calculated just once because they have been already computed in Step 1. This step derives f(S0)→K[i,0]Ci.Step 3.
To get the corresponding statesSj, decrypt C0 using different keys K[0,j] for j∈{0,1}8 (Figure 2(b)). The differences between K[0,j] and K[0,0] can bring about the gray intermediate states’ differences. The gray intermediate states need to be computed 28-1 times, whereas the remaining states have been already computed. As a result, f-1(C0)→K[0,j](Sj) has been constructed.Thanks to the simplicity of the distribution of the subkey of Piccolo, the two differential paths do not share any active state. Fortunately, it is so easy to verify thatf(Sj)→K[i,j]Ci is always true for all i,j∈{0,1}8. Up to now, for each key group, we get a corresponding 8-dimensional biclique structure as discussed above.From Figure2, we find a weakness in the key schedule of Piccolo-80; that is, K[4]R of the round key rk47 can offset K[4]R of the postwhitening key. So it can reduce the data complexity greatly. The calculations of complexities are presented in Section 4.2.


## 3.2.3. Phase 3: Meeting in the Middle over 19 Rounds

Choose a 16-bit internal state (V=F1,49) afterF-Function in round 9, as the intermediate matching variable (see Figure 3). The choice is made according to the total number ofF-Function and an effective filtering of the wrong keys. Next, we calculate these matching variates in both directions in order to obtain the accurate key.Figure 3
Recomputations in MITM for Piccolo-80.
(a)
(b)Backward Direction. Each value of the state Sj is decrypted under the key K[0,j] to derive V0,j⟵←K[0,j]Sj. After that, Sj is decrypted using all the possible 2d-1 keys K[i,j] to get  Vi,j⟵←K[i,j]Sj. Because of the same beginning, the key differences between K[0,j] and K[i,j] can cause the computational complexity. On Figure 3(b), the gray bytes are active and the white bytes need not be computed.Forward Direction. The procedure of forward direction is a bit more complex than the backward direction in calculation. Firstly, we decrypt the ciphertexts Ci for i∈{0,1}8 to obtain 28 plaintexts Pi. Secondly, each Pi is encrypted under the key K[i,0] to derive Pi→K[i,0]Vi,0→. After that, Pi is encrypted using all the possible 2d-1 keys K[i,j] to obtain Pi→K[i,j]Vi,j→. The differences between K[i,0] and K[i,j] can influence the computational complexity. On Figure 3(a), the gray bytes are active and the white bytes need not be computed.Search Candidates. In the last session of the attack, the adversary verifies the rest candidate key by the equality of Vi,j→ and Vi,j⟵ for all i,j∈{0,1}8 in each group exhaustively, until the right key is discovered.


## 3.3. Biclique Cryptanalysis of Piccolo-128

### 3.3.1. Phase 1: Key Partitioning

We divide the 128-bit key into 2112 groups. K[0,0] enumerates 112-bit keys and fixes 16-bit keys with 016. By investigating the subkey distribution (Table 3), an 8-dimensional biclique structure of 7 rounds is constructed by each left half of K[6] and K[7], that is, K[6]L and K[7]L. The computational complexity of this structure is less than others’.Similar to Piccolo-80, the keysK[0,0],K[0,j],K[i,0], and K[i,j] of each group are depicted, as shown below:(6)K0,0=XX,XX,XX,XX,XX,XX,AX,AX,whereX∈0,18,A=0x00,K0,j=K0,0⊕00,00,00,00,00,00,00,j0,wherej∈0,18,Ki,0=K0,0⊕00,00,00,00,00,00,i0,00,wherei∈0,18.Finally,(7)Ki,j=K0,0⊕K0,j⊕Ki,0=K0,0⊕00,00,00,00,00,00,i0,j0.Thus, the key space ofK is divided into 2112 groups of 216 keys each.


### 3.3.2. Phase 2: 8-Dimensional Biclique Structure of 7 Rounds

We construct an 8-dimensional biclique structure of 7 rounds for Piccolo-128 for each group (Figure4). Here, g is subciphers for round 24~30 and g-1 is the inverse of g. The process of calculating the ciphertexts and intermediate states consists of the following 3 steps.Figure 4
7-round biclique construction of dimension 8 in Piccolo-128.
(a)
(b)
(c)Step 1.
LetC0=0(64) and decrypt C0 for 7 rounds to obtain S0 (Figure 4(a)); that is, S0 = g-1K[0,0](C0).Step 2.
EncryptS0 using different keys K[i,0] for i∈{0,1}8 (Figure 4(c)). The differences between K[i,0] and K[0,0] can influence the gray intermediate states’ differences. This step derives g(S0)→K[i,0]Ci.Step 3.
DecryptC0 using different keys K[0,j] for j∈{0,1}8 (Figure 4(b)). The differences between K[0,j] and K[0,0] can bring about the gray intermediate states’ differences. As a result, g-1(C0)→K[0,j](Sj) has been constructed.Thanks to the simplicity of the distribution of the subkey of Piccolo-128, it is also very easy to verify thatg(Sj)→K[i,j]Ci is always true for all i,j∈{0,1}8. Up to now, for each key group, we get a corresponding 8-dimensional biclique structure.


### 3.3.3. Phase 3: Meeting in the Middle over 24 Rounds

Select a 16-bit internal state (U=F1,412) afterF-Function in round 12, as the intermediate matching variable (see Figure 5). Next, we calculate these matching variates in both directions in order to obtain the right key.Figure 5
Recomputations in MITM for Piccolo-128.
(a)
(b)Backward Direction. Each value of the state Sj is decrypted under the key K[0,j] to obtain U0,j⟵←K[0,j]Sj. After that, Sj is decrypted using all the possible 2d-1 keys K[i,j] to get Ui,j⟵←K[i,j]Sj. On Figure 5(b), the gray bytes are active and the white bytes do not need to be computed.Forward Direction. Firstly, we decrypt the ciphertexts Ci for i∈{0,1}8 to obtain 28 plaintexts Pi. Secondly, each Pi is encrypted under the key K[i,0] to obtain Pi→K[i,0]Ui,0→. Then, Pi is encrypted using all the possible 2d-1 keys K[i,j] to get Pi→K[i,j]Ui,j→. On Figure 5(a), the gray bytes are active and the white bytes do not need to be computed.Search Candidates. In the last session of the attack, the adversary verifies the equality of Ui,j→ and Ui,j⟵ for all i,j∈{0,1}8 to discover the correct key.


## 3.3.1. Phase 1: Key Partitioning

We divide the 128-bit key into 2112 groups. K[0,0] enumerates 112-bit keys and fixes 16-bit keys with 016. By investigating the subkey distribution (Table 3), an 8-dimensional biclique structure of 7 rounds is constructed by each left half of K[6] and K[7], that is, K[6]L and K[7]L. The computational complexity of this structure is less than others’.Similar to Piccolo-80, the keysK[0,0],K[0,j],K[i,0], and K[i,j] of each group are depicted, as shown below:(6)K0,0=XX,XX,XX,XX,XX,XX,AX,AX,whereX∈0,18,A=0x00,K0,j=K0,0⊕00,00,00,00,00,00,00,j0,wherej∈0,18,Ki,0=K0,0⊕00,00,00,00,00,00,i0,00,wherei∈0,18.Finally,(7)Ki,j=K0,0⊕K0,j⊕Ki,0=K0,0⊕00,00,00,00,00,00,i0,j0.Thus, the key space ofK is divided into 2112 groups of 216 keys each.


## 3.3.2. Phase 2: 8-Dimensional Biclique Structure of 7 Rounds

We construct an 8-dimensional biclique structure of 7 rounds for Piccolo-128 for each group (Figure4). Here, g is subciphers for round 24~30 and g-1 is the inverse of g. The process of calculating the ciphertexts and intermediate states consists of the following 3 steps.Figure 4
7-round biclique construction of dimension 8 in Piccolo-128.
(a)
(b)
(c)Step 1.
LetC0=0(64) and decrypt C0 for 7 rounds to obtain S0 (Figure 4(a)); that is, S0 = g-1K[0,0](C0).Step 2.
EncryptS0 using different keys K[i,0] for i∈{0,1}8 (Figure 4(c)). The differences between K[i,0] and K[0,0] can influence the gray intermediate states’ differences. This step derives g(S0)→K[i,0]Ci.Step 3.
DecryptC0 using different keys K[0,j] for j∈{0,1}8 (Figure 4(b)). The differences between K[0,j] and K[0,0] can bring about the gray intermediate states’ differences. As a result, g-1(C0)→K[0,j](Sj) has been constructed.Thanks to the simplicity of the distribution of the subkey of Piccolo-128, it is also very easy to verify thatg(Sj)→K[i,j]Ci is always true for all i,j∈{0,1}8. Up to now, for each key group, we get a corresponding 8-dimensional biclique structure.


## 3.3.3. Phase 3: Meeting in the Middle over 24 Rounds

Select a 16-bit internal state (U=F1,412) afterF-Function in round 12, as the intermediate matching variable (see Figure 5). Next, we calculate these matching variates in both directions in order to obtain the right key.Figure 5
Recomputations in MITM for Piccolo-128.
(a)
(b)Backward Direction. Each value of the state Sj is decrypted under the key K[0,j] to obtain U0,j⟵←K[0,j]Sj. After that, Sj is decrypted using all the possible 2d-1 keys K[i,j] to get Ui,j⟵←K[i,j]Sj. On Figure 5(b), the gray bytes are active and the white bytes do not need to be computed.Forward Direction. Firstly, we decrypt the ciphertexts Ci for i∈{0,1}8 to obtain 28 plaintexts Pi. Secondly, each Pi is encrypted under the key K[i,0] to obtain Pi→K[i,0]Ui,0→. Then, Pi is encrypted using all the possible 2d-1 keys K[i,j] to get Pi→K[i,j]Ui,j→. On Figure 5(a), the gray bytes are active and the white bytes do not need to be computed.Search Candidates. In the last session of the attack, the adversary verifies the equality of Ui,j→ and Ui,j⟵ for all i,j∈{0,1}8 to discover the correct key.


## 3.4. Another Biclique Cryptanalysis of Piccolo-128

Similar to Section3.3, we construct an 8-dimensional biclique structure of 5 rounds (26~30) for Piccolo-128 by each left half of K[6] and K[2], that is, K[6]L and K[2]L (Figure 6).Figure 6
5-round biclique construction of dimension 8 in Piccolo-128.In the phase of meeting in the middle over 26 rounds, we select a 16-bit internal state (U=F1,413) afterF-Function in round 13, as the intermediate matching variable.


## 4. Complexities

### 4.1. Comments on the Result of [15]

Jeong et al. applied biclique cryptanalysis to the lightweight block ciphers LED, Piccolo, and PRESENT in [15]. They used the concept of independent-biclique which included constructing biclique structure by independent related-key differentials and matching with precomputations. They found a limited and slow diffusion of the subkey distribution and encryption process. As a result, their attacks can discover the master key with computational complexities superior to an exhaustive search. However, we find two faults of their biclique cryptanalysis of Piccolo as follows:(
1
) Jeong et al. found that K[4]L and K[2]L gave the construction of an 8-dimensional biclique which was shown in Figure 10 of [15]. The Δi-differential affected only 6 bytes (C[0]L, C[1]L, C[1]R, C[2]L, C[3]L, and C[3]R) which is drawn on Figure 7(a) (including the grid line byte) in this paper. As a result, the data complexity does not go beyond 248.Figure 7
Revision of the other solutions.
(a)
(b)In the attack shown in Figure7, it is clear that the left half of the round key rk46 can offset the left half of WK2 (the postwhitening key); that is, there is no difference in the grid line byte (C[0]L). Based on this, the biclique cryptanalysis of Jeong et al. goes wrong.So, theΔi-differential affects only 5 bytes (C[1]L, C[1]R, C[2]L, C[3]L, and C[3]R) of the ciphertext and the data complexity does not go beyond 240. The correct difference path does not include the grid line byte (C[0]L).(
2
) Jeong et al. thought that only 2 bytes were active in the decryption of 17th round in backward direction for Piccolo-80 of recomputation, shown in Figure 11 of [15]. 13F-Functions (without the grid line) were computed 28 times and 4F-Functions were computed once. They are drawn on Figure 7(b) in this paper. Then the total complexity of this step is 28×(28×13+4)F-Functions.It is clear that 6 bytes of intermediate are active in the decryption of 17th round in backward direction for Piccolo-80 of recomputation and all bytes are active of 16th round. Based on these, their computational complexity of this step goes wrong.So, 15F-Functions (including the grid line) are computed 28 times and 2F-Functions are computed once. Then the total complexity of this step is 28×(28×15+2)F-Functions. The correct difference path includes the grid line bytes.Similarly, 3 bytes but not one byte are active in the decryption of 22nd round in backward direction for Piccolo-128 of recomputation and they are shown in Figure13 of [15]. 20 rather than 18F-Functions are computed 28 times and 3 instead of 5F-Functions are computed once.


### 4.2. Complexities of Biclique Cryptanalysis on Piccolo-80

#### 4.2.1. Data Complexity

By analyzing the key schedule, we find a weakness in the key schedule on Piccolo-80; that is, the round keyrk47 can offset the postwhitening key partially (see Figure 2). Based on this, the data complexity can be reduced greatly.The amount of ciphertexts to be decrypted dominates the data complexity (Figure2). For each biclique structure, let C0=0(64). All the ciphertexts share the equal values in 3 bytes (Ci[0], Ci[4], and Ci[5], i.e., white bytes), so the data complexity does not go beyond 240.


#### 4.2.2. Computational Complexity

The amount of theF-Functions to be computed determines the attack complexity. Each round of Piccolo-80 takes 2F-Functions computations. So, the single encryption equals computed25×2=50F-Functions. For each of 264 groups of keys, the following calculation should be completed.Biclique Complexity. 5F-Functions (Figure 2(b), noted with gray) need to be computed 28 times and 2F-Functions (Figure 2(c), noted with gray) need to be computed 28 times. The remaining 5F-Functions are computed only once. Thus, this stage requires 28×7+5F-Functions computations in total. Then, the computational complexity of a biclique structure is about 25.17 full round Piccolo-80 encryptions.Matching Complexity. In forward direction, the differences between K[i,0] and K[i,j] dominate the computational complexity. On Figure 3(a), for a single Pi, 14F-Functions (noted with gray) are computed 28 times, 3F-Functions (noted with grid line) are computed only once, and 3F-Functions (noted with white) do not need to be computed. So, the complexity of this process is 28×(28×14+3)F-Functions, which is about 214.16 full round Piccolo-80 encryptions.In backward direction, on Figure3(b), for a single Sj, 15F-Functions (noted with gray) are computed 28 times, 2F-Functions (noted with grid line) are computed only once, and 1F-Function (noted with white) need not be computed. So, the complexity of this process is 28× (28×15+2)F-Functions, which is about 214.26 full round Piccolo-80 encryptions.Finally,216 key candidates are verified by a matching variable (16 bits) in each group, and the average of 216-16=1 candidate key needs to be rechecked.Thus, the total computational complexity of this attack on Piccolo-80 is(8)C=264×25.17+214.16+214.26+1≈279.22.


### 4.3. Complexities of Biclique Cryptanalysis on Piccolo-128

#### 4.3.1. Data Complexity

For each biclique structure, letC0=0(64). All the ciphertexts share the equal values in 5 bytes (Ci[1], Ci[4], Ci[5], Ci[6], and Ci[7], i.e., white bytes), so the data complexity does not go beyond 224 (See Figure 4).


#### 4.3.2. Computational Complexity

Each round of Piccolo-128 takes 2F-Functions computations. So, the single encryption equals computed 31×2=62F-Functions. For each of 2112 groups of keys, the following calculation should be completed.Biclique Complexity. 13F-Functions (Figure 4(b), noted with gray) need to be computed 28 times and 1F-Function (Figure 4(c), noted with gray) needs to be computed 28 times. Thus, this stage requires 28×14F-Functions computations in total. Then, the computational complexity of a biclique structure is about 25.85 full round Piccolo-128 encryptions.Matching Complexity. In forward direction, for a single Pi, 16F-Functions (noted with gray) are computed 28 times, 7F-Functions (noted with grid line) are computed only once, and 3F-Functions (noted with white) do not need to be computed on Figure 5(a). So, the complexity of this process is 28×(28×16+7)F-Functions, which is about 214.05 full round Piccolo-128 encryptions.In backward direction, for a singleSj, 18F-functions (noted with gray) are computed 28 times, 3F-functions (noted with grid line) are computed only once, and 1F-Function (noted with white) need not be computed on Figure 5(b). So, the complexity of this process is 28×(28×18+3)F-Functions, which is about 214.22 full round Piccolo-128 encryptions.Finally,216 key candidates are verified by a matching variate (16 bits) in each group, and the average of 216-16=1 candidate key needs to be rechecked.Thus, the total computational complexity of this attack on Piccolo-128 is(9)C=2112×25.85+214.08+214.22+1≈2127.14.


### 4.4. Complexities of Another Biclique Cryptanalysis on Piccolo-128

#### 4.4.1. Data Complexity

For each biclique structure, letC0=0(64). All the ciphertexts share the equal values in 7 bytes (Ci[0], Ci[1], Ci[3], Ci[4], Ci[5], Ci[6], and Ci[7], i.e., white bytes), so the data complexity does not go beyond 28 (See Figure 6).


#### 4.4.2. Computational Complexity

Biclique Complexity. This stage requires 28×5+5F-Functions computations in total. Then, the computational complexity of a biclique structure is about 24.38 full round Piccolo-128 encryptions.Matching Complexity. In forward direction, the complexity is 28×(28×18+7)F-Functions, which is about 214.22 full round Piccolo-128 encryptions. In backward direction, the complexity is 28×(28×20+3)F-Functions, which is about 214.37 full round Piccolo-128 encryptions.Thus, the total computational complexity of this attack on Piccolo-128 is(10)C=2112×24.38+214.22+214.37+1≈2127.30.


## 4.1. Comments on the Result of [15]

Jeong et al. applied biclique cryptanalysis to the lightweight block ciphers LED, Piccolo, and PRESENT in [15]. They used the concept of independent-biclique which included constructing biclique structure by independent related-key differentials and matching with precomputations. They found a limited and slow diffusion of the subkey distribution and encryption process. As a result, their attacks can discover the master key with computational complexities superior to an exhaustive search. However, we find two faults of their biclique cryptanalysis of Piccolo as follows:(
1
) Jeong et al. found that K[4]L and K[2]L gave the construction of an 8-dimensional biclique which was shown in Figure 10 of [15]. The Δi-differential affected only 6 bytes (C[0]L, C[1]L, C[1]R, C[2]L, C[3]L, and C[3]R) which is drawn on Figure 7(a) (including the grid line byte) in this paper. As a result, the data complexity does not go beyond 248.Figure 7
Revision of the other solutions.
(a)
(b)In the attack shown in Figure7, it is clear that the left half of the round key rk46 can offset the left half of WK2 (the postwhitening key); that is, there is no difference in the grid line byte (C[0]L). Based on this, the biclique cryptanalysis of Jeong et al. goes wrong.So, theΔi-differential affects only 5 bytes (C[1]L, C[1]R, C[2]L, C[3]L, and C[3]R) of the ciphertext and the data complexity does not go beyond 240. The correct difference path does not include the grid line byte (C[0]L).(
2
) Jeong et al. thought that only 2 bytes were active in the decryption of 17th round in backward direction for Piccolo-80 of recomputation, shown in Figure 11 of [15]. 13F-Functions (without the grid line) were computed 28 times and 4F-Functions were computed once. They are drawn on Figure 7(b) in this paper. Then the total complexity of this step is 28×(28×13+4)F-Functions.It is clear that 6 bytes of intermediate are active in the decryption of 17th round in backward direction for Piccolo-80 of recomputation and all bytes are active of 16th round. Based on these, their computational complexity of this step goes wrong.So, 15F-Functions (including the grid line) are computed 28 times and 2F-Functions are computed once. Then the total complexity of this step is 28×(28×15+2)F-Functions. The correct difference path includes the grid line bytes.Similarly, 3 bytes but not one byte are active in the decryption of 22nd round in backward direction for Piccolo-128 of recomputation and they are shown in Figure13 of [15]. 20 rather than 18F-Functions are computed 28 times and 3 instead of 5F-Functions are computed once.


## 4.2. Complexities of Biclique Cryptanalysis on Piccolo-80

### 4.2.1. Data Complexity

By analyzing the key schedule, we find a weakness in the key schedule on Piccolo-80; that is, the round keyrk47 can offset the postwhitening key partially (see Figure 2). Based on this, the data complexity can be reduced greatly.The amount of ciphertexts to be decrypted dominates the data complexity (Figure2). For each biclique structure, let C0=0(64). All the ciphertexts share the equal values in 3 bytes (Ci[0], Ci[4], and Ci[5], i.e., white bytes), so the data complexity does not go beyond 240.


### 4.2.2. Computational Complexity

The amount of theF-Functions to be computed determines the attack complexity. Each round of Piccolo-80 takes 2F-Functions computations. So, the single encryption equals computed25×2=50F-Functions. For each of 264 groups of keys, the following calculation should be completed.Biclique Complexity. 5F-Functions (Figure 2(b), noted with gray) need to be computed 28 times and 2F-Functions (Figure 2(c), noted with gray) need to be computed 28 times. The remaining 5F-Functions are computed only once. Thus, this stage requires 28×7+5F-Functions computations in total. Then, the computational complexity of a biclique structure is about 25.17 full round Piccolo-80 encryptions.Matching Complexity. In forward direction, the differences between K[i,0] and K[i,j] dominate the computational complexity. On Figure 3(a), for a single Pi, 14F-Functions (noted with gray) are computed 28 times, 3F-Functions (noted with grid line) are computed only once, and 3F-Functions (noted with white) do not need to be computed. So, the complexity of this process is 28×(28×14+3)F-Functions, which is about 214.16 full round Piccolo-80 encryptions.In backward direction, on Figure3(b), for a single Sj, 15F-Functions (noted with gray) are computed 28 times, 2F-Functions (noted with grid line) are computed only once, and 1F-Function (noted with white) need not be computed. So, the complexity of this process is 28× (28×15+2)F-Functions, which is about 214.26 full round Piccolo-80 encryptions.Finally,216 key candidates are verified by a matching variable (16 bits) in each group, and the average of 216-16=1 candidate key needs to be rechecked.Thus, the total computational complexity of this attack on Piccolo-80 is(8)C=264×25.17+214.16+214.26+1≈279.22.


## 4.2.1. Data Complexity

By analyzing the key schedule, we find a weakness in the key schedule on Piccolo-80; that is, the round keyrk47 can offset the postwhitening key partially (see Figure 2). Based on this, the data complexity can be reduced greatly.The amount of ciphertexts to be decrypted dominates the data complexity (Figure2). For each biclique structure, let C0=0(64). All the ciphertexts share the equal values in 3 bytes (Ci[0], Ci[4], and Ci[5], i.e., white bytes), so the data complexity does not go beyond 240.


## 4.2.2. Computational Complexity

The amount of theF-Functions to be computed determines the attack complexity. Each round of Piccolo-80 takes 2F-Functions computations. So, the single encryption equals computed25×2=50F-Functions. For each of 264 groups of keys, the following calculation should be completed.Biclique Complexity. 5F-Functions (Figure 2(b), noted with gray) need to be computed 28 times and 2F-Functions (Figure 2(c), noted with gray) need to be computed 28 times. The remaining 5F-Functions are computed only once. Thus, this stage requires 28×7+5F-Functions computations in total. Then, the computational complexity of a biclique structure is about 25.17 full round Piccolo-80 encryptions.Matching Complexity. In forward direction, the differences between K[i,0] and K[i,j] dominate the computational complexity. On Figure 3(a), for a single Pi, 14F-Functions (noted with gray) are computed 28 times, 3F-Functions (noted with grid line) are computed only once, and 3F-Functions (noted with white) do not need to be computed. So, the complexity of this process is 28×(28×14+3)F-Functions, which is about 214.16 full round Piccolo-80 encryptions.In backward direction, on Figure3(b), for a single Sj, 15F-Functions (noted with gray) are computed 28 times, 2F-Functions (noted with grid line) are computed only once, and 1F-Function (noted with white) need not be computed. So, the complexity of this process is 28× (28×15+2)F-Functions, which is about 214.26 full round Piccolo-80 encryptions.Finally,216 key candidates are verified by a matching variable (16 bits) in each group, and the average of 216-16=1 candidate key needs to be rechecked.Thus, the total computational complexity of this attack on Piccolo-80 is(8)C=264×25.17+214.16+214.26+1≈279.22.


## 4.3. Complexities of Biclique Cryptanalysis on Piccolo-128

### 4.3.1. Data Complexity

For each biclique structure, letC0=0(64). All the ciphertexts share the equal values in 5 bytes (Ci[1], Ci[4], Ci[5], Ci[6], and Ci[7], i.e., white bytes), so the data complexity does not go beyond 224 (See Figure 4).


### 4.3.2. Computational Complexity

Each round of Piccolo-128 takes 2F-Functions computations. So, the single encryption equals computed 31×2=62F-Functions. For each of 2112 groups of keys, the following calculation should be completed.Biclique Complexity. 13F-Functions (Figure 4(b), noted with gray) need to be computed 28 times and 1F-Function (Figure 4(c), noted with gray) needs to be computed 28 times. Thus, this stage requires 28×14F-Functions computations in total. Then, the computational complexity of a biclique structure is about 25.85 full round Piccolo-128 encryptions.Matching Complexity. In forward direction, for a single Pi, 16F-Functions (noted with gray) are computed 28 times, 7F-Functions (noted with grid line) are computed only once, and 3F-Functions (noted with white) do not need to be computed on Figure 5(a). So, the complexity of this process is 28×(28×16+7)F-Functions, which is about 214.05 full round Piccolo-128 encryptions.In backward direction, for a singleSj, 18F-functions (noted with gray) are computed 28 times, 3F-functions (noted with grid line) are computed only once, and 1F-Function (noted with white) need not be computed on Figure 5(b). So, the complexity of this process is 28×(28×18+3)F-Functions, which is about 214.22 full round Piccolo-128 encryptions.Finally,216 key candidates are verified by a matching variate (16 bits) in each group, and the average of 216-16=1 candidate key needs to be rechecked.Thus, the total computational complexity of this attack on Piccolo-128 is(9)C=2112×25.85+214.08+214.22+1≈2127.14.


## 4.3.1. Data Complexity

For each biclique structure, letC0=0(64). All the ciphertexts share the equal values in 5 bytes (Ci[1], Ci[4], Ci[5], Ci[6], and Ci[7], i.e., white bytes), so the data complexity does not go beyond 224 (See Figure 4).


## 4.3.2. Computational Complexity

Each round of Piccolo-128 takes 2F-Functions computations. So, the single encryption equals computed 31×2=62F-Functions. For each of 2112 groups of keys, the following calculation should be completed.Biclique Complexity. 13F-Functions (Figure 4(b), noted with gray) need to be computed 28 times and 1F-Function (Figure 4(c), noted with gray) needs to be computed 28 times. Thus, this stage requires 28×14F-Functions computations in total. Then, the computational complexity of a biclique structure is about 25.85 full round Piccolo-128 encryptions.Matching Complexity. In forward direction, for a single Pi, 16F-Functions (noted with gray) are computed 28 times, 7F-Functions (noted with grid line) are computed only once, and 3F-Functions (noted with white) do not need to be computed on Figure 5(a). So, the complexity of this process is 28×(28×16+7)F-Functions, which is about 214.05 full round Piccolo-128 encryptions.In backward direction, for a singleSj, 18F-functions (noted with gray) are computed 28 times, 3F-functions (noted with grid line) are computed only once, and 1F-Function (noted with white) need not be computed on Figure 5(b). So, the complexity of this process is 28×(28×18+3)F-Functions, which is about 214.22 full round Piccolo-128 encryptions.Finally,216 key candidates are verified by a matching variate (16 bits) in each group, and the average of 216-16=1 candidate key needs to be rechecked.Thus, the total computational complexity of this attack on Piccolo-128 is(9)C=2112×25.85+214.08+214.22+1≈2127.14.


## 4.4. Complexities of Another Biclique Cryptanalysis on Piccolo-128

### 4.4.1. Data Complexity

For each biclique structure, letC0=0(64). All the ciphertexts share the equal values in 7 bytes (Ci[0], Ci[1], Ci[3], Ci[4], Ci[5], Ci[6], and Ci[7], i.e., white bytes), so the data complexity does not go beyond 28 (See Figure 6).


### 4.4.2. Computational Complexity

Biclique Complexity. This stage requires 28×5+5F-Functions computations in total. Then, the computational complexity of a biclique structure is about 24.38 full round Piccolo-128 encryptions.Matching Complexity. In forward direction, the complexity is 28×(28×18+7)F-Functions, which is about 214.22 full round Piccolo-128 encryptions. In backward direction, the complexity is 28×(28×20+3)F-Functions, which is about 214.37 full round Piccolo-128 encryptions.Thus, the total computational complexity of this attack on Piccolo-128 is(10)C=2112×24.38+214.22+214.37+1≈2127.30.


## 4.4.1. Data Complexity

For each biclique structure, letC0=0(64). All the ciphertexts share the equal values in 7 bytes (Ci[0], Ci[1], Ci[3], Ci[4], Ci[5], Ci[6], and Ci[7], i.e., white bytes), so the data complexity does not go beyond 28 (See Figure 6).


## 4.4.2. Computational Complexity

Biclique Complexity. This stage requires 28×5+5F-Functions computations in total. Then, the computational complexity of a biclique structure is about 24.38 full round Piccolo-128 encryptions.Matching Complexity. In forward direction, the complexity is 28×(28×18+7)F-Functions, which is about 214.22 full round Piccolo-128 encryptions. In backward direction, the complexity is 28×(28×20+3)F-Functions, which is about 214.37 full round Piccolo-128 encryptions.Thus, the total computational complexity of this attack on Piccolo-128 is(10)C=2112×24.38+214.22+214.37+1≈2127.30.


## 5. Conclusion

Designers have given several attacks including linear cryptanalysis, impossible differential cryptanalysis, and MITM attack on security analysis for Piccolo. The best result was 3-subset MITM attacks on 14/21-round Piccolo-80/128 without the whitening key. The previous results and our results are summarized on Piccolo in Tables1 and 2. Some results did not include whitening key; some attacks were reduced-round. However, our results are full round Piccolo-80/128.By analyzing the distribution of the subkey and the structure of encryption, we find two faults of the results in [15] and a weakness in the key schedule on Piccolo-80. The two faults are depicted in Section 4.1. The weakness on Piccolo-80 is that the right half of the round key rk47 can offset the right half of the postwhitening key WK3 (Figure 2(c)). Based on this, the data complexity can be decreased greatly.We use biclique cryptanalysis to recover the master key for the full round Piccolo-80 with a 6-round biclique and the full round Piccolo-128 with a 7-round biclique, respectively. The attacks require data complexity of240 and 224 chosen ciphertexts and computational complexity of 279.22 and 2127.14, respectively. These results are superior to other biclique cryptanalytic results on Piccolo.This result is that the biclique technology can attack some ciphers with simple key schedule and slow diffusion. So, the designers of lightweight ciphers need to consider not only the implementation efficiency, but also key schedule complexity and diffusion speed.



---

*Source: 7589306-2017-03-02.xml*