The Security Weakness of Block Cipher Piccolo against Fault Analysis

Abstract

Piccolo is a 64-bit lightweight block cipher which is able to be implemented in constrained hardware environments such as a wireless sensor network. Fault analysis is a type of side channel attack and cube attack is an algebraic attack finding sufficiently low-degree polynomials in a cipher. In this paper, we show a fault analysis on the Piccolo by using cube attack. We find 16 linear equations corresponding to a round function F by cube attack, which are used to fault analysis. Our attack has the complexity of 2^8.49 and 2^9.21 encryptions with fault injections of target bit positions into Piccolo-80 and Piccolo-128, respectively. And our attack needs 2^20.86 and 2^21.60 encryptions with random 4-bit fault injections for Piccolo-80 and Piccolo-128, respectively.

1. Introduction

Fault analysis is a type of side channel attack. This analysis was introduced by Boneh et al. in [1]. Differential fault analysis (DFA), which is an improved method of fault analysis, was introduced by Biham and Shamir in [2]. DFA is applied to various block ciphers such as AES [3, 4], ARIA [5], SEED [6], CLEFIA [7], LED [8], Piccolo [9–12], PRESENT [13], and KATAN32 [14]. Cube attack was introduced by Dinur and Shamir in [15]. This attack is an algebraic attack by finding sufficiently low-degree polynomials in a cipher. Cube attack is applied to various cryptosystems such as block cipher [16] and stream cipher [15, 17].

In CHES 2011, Piccolo was introduced by Shibutani et al. in [18]. Piccolo is a block cipher which supports 80-bit and 128-bit secret key size. In this paper, we analyze two versions of Piccolo [18] with fault analysis by using cube attack. In ISPEC 2012, fault analysis using cube attack was introduced by Abdul-Latip et al. in [16]. In this paper, we apply this method on Piccolo-80 and Piccolo-128. As a result, we find 16 linear equations corresponding to a round function F by cube attack, which are used to fault analysis.

Piccolo is analyzed by various techniques. In ISPEC 2012, Wang et al. suggest biclique cryptanalysis of reduced round Piccolo in [19]. They analyze reduced version of Piccolo-80 without postwhitening keys XOR and reduced 28-round Piccolo-128 without prewhitening keys XOR. In 2013, Song et al. suggest biclique cryptanalysis of full rounds of Piccolo [20]. And also Jeong suggests a differential fault analysis of full rounds of Piccolo [9].

In this paper, we show a fault analysis on the Piccolo by using cube attack. We find 16 linear equations corresponding to a round function F of Piccolo by using cube attack. These equations are used to our attack. In this paper, we describe the case that an adversary injects random 4-bit faults. Our attack has the complexity of $2^{20.86}$ and $2^{21.60}$ encryptions for Piccolo-80 and Piccolo-128, respectively, while the assumption of [9] is an adversary that injects random byte faults. Reference [9] has the complexity of 2²⁴ and 2⁴⁰ encryptions for Piccolo-80 and Piccolo-128, respectively. Our attack has a lower computational complexity than [9], even though the assumption of fault injection in our attack differs from [9].

In Section 2, we briefly describe the procedures of cube attack and cube tester. And then we describe the brief specifications of Piccolo in Section 3. In Section 4, a method of fault analysis of Piccolo by using cube attack is presented. Finally, our conclusions are in Section 5.

2. Cube Attack and Cube Tester

Algebraic attack is to find a solution, which is the key, of a system of equations that represent target cipher with given plaintext and the corresponding ciphertext, that is representing cipher as a system of equations with multiple variables defined over finite field where each key bit is represented as a variable in the system. Solving the system is equivalent to finding the secret key of the target cipher. Cube attack is an algebraic attack finding sufficiently low-degree polynomials in cipher.

2.1. Cube Attack

Cube attack was introduced by Dinur and Shamir in [15]. Cube attack is a chosen plaintext attack. The main idea of cube attack is to find linear equations consisting of secret variables by using cube sum. Let $p(v_{\mathrm{1}},\dots ,v_n,k_{\mathrm{1}},\dots ,k_m)$ be a polynomial derived from a cipher, where $v_{\mathrm{1}},\dots ,v_n$ are public variables and $k_{\mathrm{1}},\dots ,k_m$ are secret variables. In other words, each secret variable is considered a bit in secret key and each public variable is considered a bit in plaintext or internal state. Let $I=\{I_{\mathrm{1}},\dots ,I_s\}\subseteq \{\mathrm{1},\dots ,n\}$ be a set and let $t_I$ be the monomial $x_{I_1}{x}_{I_2}\dots x_{I_s}$ . Note that the set in terms of I is called cube index. Then the polynomial p is represented by three polynomials $t_I$ , $p_{S(I)}$ , and q as the following form:

$$\begin{array}{l}p\left(v_{\mathrm{1}},\dots ,v_n,k_{\mathrm{1}},\dots ,k_m\right)\\ \hspace{1em}=t_I·p_{S\left(I\right)}+q\left(v_{\mathrm{1}},\dots ,v_n,k_{\mathrm{1}},\dots ,k_m\right),\end{array}$$

(1) where q is not consisting of a monomial which has a factor $t_I$ .

Cube attack is required to check the linearity of $p_{S(I)}$ which is called superpoly. A superpoly $p_{S(I)}$ is called a maxterm if $p_{S(I)}$ is linear. We use the following cube sum to find a $p_{S(I)}$ :

$$\begin{array}{cc}& p_{S\left(I\right)}=\sum _{(v_{I_{\mathrm{1}}},\dots ,v_{I_s})\in \text{GF}(\mathrm{2}{)}^s}p\left(v_{\mathrm{1}},\dots ,v_n,k_{\mathrm{1}},\dots ,k_m\right),\end{array}$$

(2) where plaintext bits except cube index ( $v_i,i\in \{\mathrm{1},\dots ,n\}-I$ ) are fixed as constants.

As the above representation, cube is completed with the sum total $2^S$ pairs of plaintext and ciphertext for a cube index $I=\{I_1,\dots ,I_s\}$ . To check whether $p_{S(I)}$ is a maxterm, linearity test is required. Let $p_{S(I)}(k_1,\dots ,k_m)$ be a polynomial of m variables over GF(2). Let t be the number of tests. The following is a procedure of linearity test.

Step 1.

Choose 2 random vectors $x,y\in \text{GF}(\mathrm{2}{)}^m$ .

Step 2.

If $p_{S(I)}(x)\oplus p_{S(I)}(y)\oplus p_{S(I)}(\mathrm{0})\ne p_{S(I)}(x\oplus y)$ ,

then $p_{S(I)}$ is not linear. Stop the test.

Step 3.

Repeat Steps 1 and 2, t times.

Step 4.

$p_{S(I)}$ is linear. Stop the test,

where    $\mathrm{0}=(\mathrm{0},\dots ,\mathrm{0})\in \text{GF}(\mathrm{2}{)}^m$ .

If $p_{S(I)}(k_{\mathrm{1}},\dots ,k_m)$ is linear, the above equation in Step 2 is always correct for all inputs $x,y\in \text{GF}(\mathrm{2}{)}^m$ . Because checking all inputs is impossible, an upper bound of number of linearity tests has to be set. If there are at most $d_1$ elements in a cube index for testing linearity, at most ${\mathrm{2}}^{d_{\mathrm{1}}}\times (\mathrm{3}\times t+\mathrm{1})$ pairs of plaintext and ciphertext are needed. Cube attack consists of preprocessing phase and online phase. Preprocessing phase is to find a system of linear equations by using cube sum and linearity test. Online phase is recovering the master key stored by using an encryption oracle. The following are details for the two phases.

Preprocessing Phase. After finding a polynomial from a cipher, find a cube, that is, a maxterm, by using linearity test. Since we know output after all plaintext bits are entered in encryption oracle, fix plaintext except cube index as a constant. Fixed constants of every cube do not have to be equal. Let $f_i$ be a maxterm which consists of only secret variables $k_{\mathrm{1}},\dots ,k_m$ and let $b_i$ be the value of the maxterm $f_i$ which is found from online phase. We consider the following system of equations:

$$\begin{array}{l}{f}_{\mathrm{1}}(k_{\mathrm{1}},\dots ,k_m)=b_{\mathrm{1}}\\ \phantom{\text{hhhhhhhl}}⋮\\ f_l(k_{\mathrm{1}},\dots ,k_m)=b_l.\end{array}$$

(3) In the preprocessing phase, find enough maxterms to recover the master key and precalculate this system of equations by using Gaussian elimination. If we find m linear independent maxterms, then recover all the master keys with $m^3$ operations for recovery by using Gaussian elimination. In general, it is lower than complexity $l\hspace{0.17em}\times \hspace{0.17em}{\mathrm{2}}^{d_{\mathrm{1}}}\hspace{0.17em}\times \hspace{0.17em}(\mathrm{3}\times \hspace{0.17em}t+\mathrm{1})$ for finding l maxterms. Let $f_{\mathrm{1}},\dots ,f_m$ be linearly independent. Then the master keys are represented as the following system:

$$\begin{array}{l}{k}_{\mathrm{1}}=\sum _{i=\mathrm{1}}^m{a}_{\mathrm{1},i}·b_i\\ \phantom{hhhhh}⋮\\ k_m=\sum _{i=\mathrm{1}}^m{a}_{m,i}·b_i,\end{array}$$

(4) where $a_{i,j}\in \text{GF}(\mathrm{2})$ .

Online Phase. In online phase, calculate the value of cube sum from an encryption oracle by using the cube that has been found in the preprocessing phase. Let each plaintext bit not in the cube be constant. The calculated value is $b_i$ , that is, the value of the maxterm. By substituting the value $b_i$ into (4), we recover the master key. Let cube index found at preprocessing phase have at most $d_2$ elements. Then the complexity of online phase is $m\times {\mathrm{2}}^{d_{\mathrm{2}}}$ .

2.2. Cube Tester

Cube attack finds a maxterm by testing linearity of $p_{S(I)}$ of a given polynomial p and cube index I. Cube tester distinguishes a polynomial from a random polynomial by many tests including linearity test. There are some other tests using cube sum in [21]. In cube attack, a plaintext bit not in the cube is fixed as a constant. However all bits not in the cube have to be considered variables in the cube tester. Since the purpose of using the cube tester is getting information, which are properties of polynomial, we use the low-degree test that is in [21]. The degree N is determined by low-degree test. Let I be a cube index, let J be the number of bits not in the cube index (i.e., $J=n+m-S$ ; $p_{S(I)}$ consists of J variables), and t is the number of tests. Since low-degree test is valid only when $p(\mathrm{0})=\mathrm{0}$ for the given polynomial p, we define $p_{S(I)}^{*}(x)=p_{S(I)}(x)+p_{S(I)}(\mathrm{0})$ . Then low-degree test for the polynomial $p_{S(I)}^{*}(x)$ is as follows.

Step 1.

Choose $N+1$ random vectors $y_{\mathrm{1}},\dots ,y_{N+\mathrm{1}}\in \text{GF}(\mathrm{2}{)}^J$ .

Step 2.

If ${\sum }_{\varphi \ne S\subset \{y_{\mathrm{1}},\dots ,y_{N+\mathrm{1}}\}}^{}{p}_{S(I)}^{*}({\sum }_{y_i\in S}^{}{y}_i)\ne \mathrm{0}$ , then

degree of $p_{S(I)}>N$ . Stop the test.

Step 3.

Repeat Steps 1 and 2, t times.

Step 4.

Degree of $p_{S(I)}\le N$ . Stop the test.

If $N=1$ , then the low-degree test is similar to the linearity test. We use the idea of the cube tester which uses every bit not in the cube index (consisting of plaintext and the master key) as a variable.

3. Description of Piccolo

Piccolo is a 64-bit block cipher with 80- and 128-bit key size. The structure of Piccolo is a Feistel network. Piccolo-80 consists of 25 rounds and Piccolo-128 consists of 31 rounds. Figure 1 illustrates the working processing of Piccolo. Each round consists of two functions, round function F and round permutation $\text{RP}$ . The round functions F and $\text{RP}$ are as follows.

Figure 1

Encryption process of Piccolo.

Round Function F. The round function F is defined by

$$\begin{array}{ll}F\left(x_{\mathrm{0}},x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}}\right)& =\left(S\left(x_{\mathrm{0}}\right),S\left(x_{\mathrm{1}}\right),S\left(x_{\mathrm{2}}\right),S\left(x_{\mathrm{3}}\right)\right)\\ & \hspace{1em}·M·{\left(S\left(x_{\mathrm{0}}\right),S\left(x_{\mathrm{1}}\right),S\left(x_{\mathrm{2}}\right),S\left(x_{\mathrm{3}}\right)\right)}^t,\end{array}$$

(5) where $X^t$ is the transposition of X.

$S(x)$ is the 4-bit S-box and M is the diffusion matrix as follows (see Table 1):

$$\begin{array}{cc}& M=\left(\begin{array}{cccc}\mathrm{2}& \mathrm{3}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{2}& \mathrm{3}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{2}& \mathrm{3}\\ \mathrm{3}& \mathrm{1}& \mathrm{1}& \mathrm{2}\end{array}\right).\end{array}$$

(6) The multiplications between M and vectors are defined by an irreducible polynomial $x^4+x+1$ over $\text{GF}(2^4)$ .

Table 1

S-box of Piccolo.

x	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
$S(x)$	e	4	b	2	3	8	0	9	1	a	7	f	6	c	5	d

Round Permutation RP. The round permutation $\text{RP}$ is defined by

$$\begin{array}{cc}& \text{RP}\left(x_{\mathrm{0}},x_{\mathrm{1}},\dots ,x_{\mathrm{7}}\right)=\left(x_{\mathrm{2}},x_{\mathrm{7}},x_{\mathrm{4}},x_{\mathrm{1}},x_{\mathrm{6}},x_{\mathrm{3}},x_{\mathrm{0}},x_{\mathrm{5}}\right),\end{array}$$

(7) where $x_i$ is byte.

For description of Piccolo and our attack, we denote intermediate variables before r-round as $X^r=X_{\mathrm{0}}^r\mid X_{\mathrm{1}}^r\mid X_{\mathrm{2}}^r\mid X_{\mathrm{3}}^r=(x_{\mathrm{0}}^r,\dots ,x_{\mathrm{63}}^r)$ and intermediate variables before r-round's $\text{RP}$ function as $Y^r=Y_{\mathrm{0}}^r\mid Y_{\mathrm{1}}^r\mid Y_{\mathrm{2}}^r\mid Y_{\mathrm{3}}^r$ (i.e., $\text{RP}(Y^r)=X^{r+\mathrm{1}}$ ). Let the round function F in r-round be $F(X_i^r)=(F_{\mathrm{0}}(X_i^r),\dots ,F_{\mathrm{15}}(X_i^r))$ and let the round key be $r{k}_r=(k_{\mathrm{0}}^r,\dots ,k_{\mathrm{15}}^r)$ . The other notations are as follows:

• $\hspace{0.17em}(X_i^r{)}^L$

: left 8 bits of $X_i^r$ and $(X_i^r{)}^R$ : right 8 bits of $X_i^r$ ;

 

$K_i^L$ : left 8 bits of $K_i$ and $K_i^R$ : right 8 bits of $K_i$ ;

 

$A\mid B$ : concatenation of A and B.

Let the 64-bit plaintext and ciphertext be P and C, respectively. Encryption of Piccolo is defined as follows:

• (1)

$P_{\mathrm{0}}\mid P_{\mathrm{1}}\mid P_{\mathrm{2}}\mid P_{\mathrm{3}}\leftarrow P$ ( $P_i$ is the 16-bit plaintext);

(2)

$X_{\mathrm{0}}^{\mathrm{1}}\leftarrow P_{\mathrm{0}}\oplus w{k}_{\mathrm{0}},\hspace{0.17em}{X}_{\mathrm{1}}^{\mathrm{1}}=P_{\mathrm{1}}$

•  

$X_{\mathrm{2}}^{\mathrm{1}}\leftarrow P_{\mathrm{2}}\oplus w{k}_{\mathrm{1}},X_{\mathrm{3}}^{\mathrm{1}}=P_{\mathrm{3}}$ ;

(3)

for $i=1$ to $r-1$

•  

$Y_{\mathrm{0}}^i\leftarrow X_{\mathrm{0}}^i,Y_{\mathrm{1}}^i\leftarrow X_{\mathrm{1}}^i\oplus F(X_{\mathrm{0}}^i)\oplus r{k}_{\mathrm{2}i-\mathrm{2}}$

 

$Y_{\mathrm{2}}^i\leftarrow X_{\mathrm{2}}^i,Y_{\mathrm{3}}^i\leftarrow X_{\mathrm{3}}^i\oplus F(X_{\mathrm{2}}^i)\oplus r{k}_{\mathrm{2}i-\mathrm{1}}$

 

$X^{i+\mathrm{1}}\leftarrow \text{RP}(Y^i)$ ;

(4)

$Y_{\mathrm{0}}^r\leftarrow X_{\mathrm{0}}^r\oplus w{k}_{\mathrm{2}},Y_{\mathrm{1}}^r\leftarrow X_{\mathrm{1}}^r\oplus F(X_{\mathrm{0}}^r)\oplus r{k}_{\mathrm{2}r-\mathrm{2}}$

•  

$Y_{\mathrm{2}}^r\leftarrow X_{\mathrm{2}}^r\oplus w{k}_{\mathrm{3}},Y_{\mathrm{3}}^r\leftarrow X_{\mathrm{3}}^r\oplus F(X_{\mathrm{2}}^r)\oplus r{k}_{\mathrm{2}r-\mathrm{1}}$ ;

(5)

$C\leftarrow Y_{\mathrm{0}}^r\mid Y_{\mathrm{1}}^r\mid Y_{\mathrm{2}}^r\mid Y_{\mathrm{3}}^r$ ( $Y_i^r$ is the 16-bit ciphertext).

Key schedule of Piccolo consists of the following.

•  

Piccolo-80:

$$\begin{array}{l}w{k}_{\mathrm{0}}⟵K_{\mathrm{0}}^L\mid K_{\mathrm{1}}^R,w{k}_{\mathrm{1}}⟵K_{\mathrm{1}}^L\mid K_{\mathrm{0}}^R,\\ w{k}_{\mathrm{2}}⟵K_{\mathrm{4}}^L\mid K_{\mathrm{3}}^R,w{k}_{\mathrm{3}}⟵K_{\mathrm{3}}^L\mid K_{\mathrm{4}}^R,\end{array}$$

(8)for $i\leftarrow \mathrm{0}$ to $\mathrm{24}$ do

•  

if $i\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\mathrm{5}=\mathrm{0}\hspace{0.17em}\hspace{0.17em}\text{or}\hspace{0.17em}\hspace{0.17em}\mathrm{2}$ , then

$$\begin{array}{cc}& \left(r{k}_{\mathrm{2}i},r{k}_{\mathrm{2}i+\mathrm{1}}\right)⟵\left({\text{con}}_{\mathrm{2}i}^{\mathrm{80}},{\text{con}}_{\mathrm{2}i+\mathrm{1}}^{\mathrm{80}}\right)\oplus \left(K_{\mathrm{2}},K_{\mathrm{3}}\right)\end{array}$$

(9)

 

if $i\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\mathrm{5}=\mathrm{1}\hspace{0.17em}\hspace{0.17em}\text{or}\hspace{0.17em}\hspace{0.17em}\mathrm{4}$ , then

$$\begin{array}{cc}& \left(r{k}_{\mathrm{2}i},r{k}_{\mathrm{2}i+\mathrm{1}}\right)⟵\left({\text{con}}_{\mathrm{2}i}^{\mathrm{80}},{\text{con}}_{\mathrm{2}i+\mathrm{1}}^{\mathrm{80}}\right)\oplus \left(K_{\mathrm{0}},K_{\mathrm{1}}\right)\end{array}$$

(10)

 

if $i\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\mathrm{5}=\mathrm{3}$ , then

$$\begin{array}{cc}& \left(r{k}_{\mathrm{2}i},r{k}_{\mathrm{2}i+\mathrm{1}}\right)⟵\left({\text{con}}_{\mathrm{2}i}^{\mathrm{80}},{\text{con}}_{\mathrm{2}i+\mathrm{1}}^{\mathrm{80}}\right)\oplus \left(K_{\mathrm{4}},K_{\mathrm{4}}\right),\end{array}$$

(11)where ${\text{con}}_i^{\mathrm{80}}$ is the round constant.

 

Piccolo-128:

$$\begin{array}{cc}& w{k}_{\mathrm{0}}⟵K_{\mathrm{0}}^L\mid K_{\mathrm{1}}^R,w{k}_{\mathrm{1}}⟵K_{\mathrm{1}}^L\mid K_{\mathrm{0}}^R,\\ w{k}_{\mathrm{2}}⟵K_{\mathrm{4}}^L\mid K_{\mathrm{7}}^R,w{k}_{\mathrm{3}}⟵K_{\mathrm{7}}^L\mid K_{\mathrm{4}}^R,\end{array}$$

(12)for $i\leftarrow \mathrm{0}$ to $\mathrm{61}$ do

•  

if $(i+\mathrm{2})\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\mathrm{8}=\mathrm{0}$ , then

$$\begin{array}{l}\left(K_{\mathrm{0}},K_{\mathrm{2}},K_{\mathrm{6}},K_{\mathrm{4}}\right)⟵\left(K_{\mathrm{2}},K_{\mathrm{6}},K_{\mathrm{4}},K_{\mathrm{0}}\right)\\ \left(K_{\mathrm{3}},K_{\mathrm{7}},K_{\mathrm{5}}\right)⟵\left(K_{\mathrm{7}},K_{\mathrm{5}},K_{\mathrm{3}}\right)\\ r{k}_i⟵r{k}_{\left(i+\mathrm{2}\right)\mathrm{mod}\mathrm{8}}\oplus {\text{con}}_i^{\mathrm{128}},\end{array}$$

(13)where ${\text{con}}_i^{\mathrm{128}}$ is the round constant.

Since key schedule of Piccolo is just performing XOR determined constants to the master key, recovering the round key and recovering the master key are the same. Table 2 is showing the master key used for the round key of Piccolo. Detailed descriptions of Piccolo are in [18].

Table 2

Round key of Piccolo.

Piccolo-80			Piccolo-128
Round	Round key	Master key	Round	Round key	Master key
First	wk 0, wk1	$K_0^L\left|K_1^R,K_1^L\right|K_0^R$	First	wk 0, wk1	$K_0^L\left|K_1^R,K_1^L\right|K_0^R$
1	rk0, rk1	K2, K3	1	rk0, rk1	K2, K3
2	rk2, rk3	K0, K1	2	rk2, rk3	K4, K5
3	rk4, rk5	K2, K3	3	rk4, rk5	K6, K7
4	rk6, rk7	K4, K4	4	rk6, rk7	K2, K1
5	rk8, rk9	K0, K1	5	rk8, rk9	K6, K7
6	rk10, rk11	K2, K3	6	rk10, rk11	K0, K3
7	rk12, rk13	K0, K1	7	rk12, rk13	K4, K5
8	rk14, rk15	K2, K3	8	rk14, rk15	K6, K1
9	rk16, rk17	K4, K4	9	rk16, rk17	K4, K5
10	rk18, rk19	K0, K1	10	rk18, rk19	K2, K7
11	rk20, rk21	K2, K3	11	rk20, rk21	K0, K3
12	rk22, rk23	K0, K1	12	rk22, rk23	K4, K1
13	rk24, rk25	K2, K3	13	rk24, rk25	K0, K3
14	rk26, rk27	K4, K4	14	rk26, rk27	K6, K5
15	rk28, rk29	K0, K1	15	rk28, rk29	K2, K7
16	rk30, rk31	K2, K3	16	rk30, rk31	K0, K1
17	rk32, rk33	K0, K1	17	rk32, rk33	K2, K7
18	rk34, rk35	K2, K3	18	rk34, rk35	K4, K3
19	rk36, rk37	K4, K4	19	rk36, rk37	K6, K5
20	rk38, rk39	K0, K1	20	rk38, rk39	K2, K1
21	rk40, rk41	K2, K3	21	rk40, rk41	K6, K5
22	rk42, rk43	K0, K1	22	rk42, rk43	K0, K7
23	rk44, rk45	K2, K3	23	rk44, rk45	K4, K3
24	rk46, rk47	K4, K4	24	rk46, rk47	K6, K1
25	rk48, rk49	K0, K1	25	rk48, rk49	K4, K3
Final	wk2, wk3	$K_4^L\left|K_3^R,K_3^L\right|K_4^R$	26	rk50, rk51	K2, K5
			27	rk52, rk53	K0, K7
			28	rk54, rk55	K4, K1
			29	rk56, rk57	K0, K7
			30	rk58, rk59	K6, K3
			31	rk60, rk61	K2, K5
			Final	wk2, wk3	$K_4^L\left|K_7^R,K_7^L\right|K_4^R$

4. Fault Analysis on the Piccolo

In this section, we show the fault analysis for Piccolo-80 and Piccolo-128. We assume that an adversary is able to make 4-bit errors in a maximum at a time on a round during an encryption process. By using cube sum, find system of linear equations in the common F of Piccolo-80 and Piccolo-128. And use the system to represent the phase recovering the master key of Piccolo-80 and Piccolo-128. Analysis of a round function F in Section 4.1 is corresponding to the preprocessing phase of cube attack. The attack in Sections 4.2 and 4.3 is the case of an encryption oracle that is given and is corresponding to online phase.

4.1. Equations of Round Function F

Since round function F is the same for Piccolo-80 and Piccolo-128, the results of fault injection attack on F are the same in the both algorithms. Let $F(X)=(F_{\mathrm{0}}(X),\dots ,F_{\mathrm{15}}(X))$ , where $X=(x_{\mathrm{0}},x_{\mathrm{1}},\dots ,x_{\mathrm{15}})$ is an 16-bit intermediate value and each $F_j(x)$ is a bit $(F:\text{GF}(\mathrm{2}{)}^{\mathrm{16}}\to \text{GF}(\mathrm{2}{)}^{\mathrm{16}})$ . We test all possible cubes of degree 1 to degree 4 and all possible inputs for each cube. We get many linear polynomials and choose 16 appropriate polynomials for recovering the master key. Table 3 shows our selected 16 polynomials, cube index, and output bit $(F_i)$ .

Table 3

Cube sum result of $F(x_{\mathrm{0}},\dots ,x_{\mathrm{15}})$ .

Cube index	Outbit ( $F_i$ )	Polyequation
1, 5, 6	8	$x_0+1$
0, 8, 9, 11	10	$x_1+1$
1, 5, 6	12	$x_0+x_2$
0, 8, 9, 11	7	$x_3$
0, 1, 5, 6	4	$x_4+1$
4, 8	12	$x_5+x_9$
4, 5, 8, 9	4	$x_6+1$
4, 8, 9, 11	7	$x_5+x_7+1$
5, 6, 9	12	$x_8+1$
4, 5, 7, 8	6	$x_9$
5, 6, 9	8	$x_{\mathrm{10}}+1$
4, 5, 7, 8	3	$x_{\mathrm{11}}$
5, 6, 13	8	$x_{\mathrm{12}}+x_{\mathrm{14}}$
0, 12	4	$x_1+x_{\mathrm{13}}$
5, 6, 13	12	$x_{\mathrm{14}}+1$
0, 8, 11, 12	7	$x_3+x_{\mathrm{15}}$

4.2. Analysis on the Piccolo-80

We explain how to recover all the master keys of Piccolo-80. By key schedule of Piccolo-80, recovering ${wk}_2$ , ${wk}_3$ , ${rk}_{44}$ , ${rk}_{48}$ , and ${rk}_{49}$ is equal to recovering all the master keys of Piccolo-80. Let plaintext P be given and let $X_i^j,Y_i^j$ be intermediate values for plaintext P. In this paper, we recover the master key of Piccolo-80 by recovering some $X_i^j$ s. Figure 2 is for the last 4 rounds of Piccolo-80. The following is the attack on Piccolo-80.

Figure 2

Fault analysis of Piccolo-80.

Step 1.

First, we analyze the last round (i.e., round 25). Perform cube sum by using the cube in Table 3 for F which takes $X_{\mathrm{0}}^{\mathrm{25}}$ . For example, consider 6th equation of Table 3. Suppose that inject fault into $x_{\mathrm{4}}^{\mathrm{25}}$ to $x_{\mathrm{8}}^{\mathrm{25}}$ . Then, since fault is injected into only $X_{\mathrm{0}}^{\mathrm{25}}$ , value of $X_{\mathrm{1}}^{\mathrm{25}}$ or $r{k}_{\mathrm{48}}$ is not changed. We notate the following to explain our attack:

•  

$X_{\mathrm{0}}^{\mathrm{25}}=(x_{\mathrm{0}}^{\mathrm{25}},\dots ,x_{\mathrm{15}}^{\mathrm{25}}),X_{\mathrm{1}}^{\mathrm{25}}=(x_{\mathrm{16}}^{\mathrm{25}},\dots ,x_{\mathrm{31}}^{\mathrm{25}})$ ;

 

$Y_{\mathrm{0}}^{\mathrm{25}}=(y_{\mathrm{0}}^{\mathrm{25}},\dots ,y_{\mathrm{15}}^{\mathrm{25}})$ ;

 

$y_{\mathrm{12}}^{\mathrm{25}}[x_{\mathrm{4}}^{\mathrm{25}}]$ : $y_{\mathrm{12}}^{\mathrm{25}}$ when fault is injected into $x_{\mathrm{4}}^{\mathrm{25}}$ ;

 

$y_{\mathrm{12}}^{\mathrm{25}}[x_{\mathrm{8}}^{\mathrm{25}}]$ : $y_{\mathrm{12}}^{\mathrm{25}}$ when fault is injected into $x_{\mathrm{8}}^{\mathrm{25}}$ ;

 

$y_{\mathrm{12}}^{\mathrm{25}}[x_{\mathrm{4}}^{\mathrm{25}},x_{\mathrm{8}}^{\mathrm{25}}]$ : $y_{\mathrm{12}}^{\mathrm{25}}$ when fault is injected into both $x_{\mathrm{4}}^{\mathrm{25}}$ , $x_{\mathrm{8}}^{\mathrm{25}}$ .

We calculate cube sum for cube index $\{\mathrm{4,8}\}$ like the following:

$$\begin{array}{l}\text{Cube}\hspace{0.17em}\hspace{0.17em}\text{sum}=\sum _{x_{\mathrm{4}},x_{\mathrm{8}}\in \left\{\mathrm{0,1}\right\}}{F}_{\mathrm{12}}\left(x_{\mathrm{0}}^{\mathrm{25}},\dots ,x_{\mathrm{15}}^{\mathrm{25}}\right)\\ =\sum _{x_{\mathrm{4}},x_{\mathrm{8}}\in \left\{\mathrm{0,1}\right\}}\left[F_{\mathrm{12}}\left(x_{\mathrm{0}}^{\mathrm{25}},\dots ,x_{\mathrm{15}}^{\mathrm{25}}\right)\oplus x_{\mathrm{28}}^{\mathrm{25}}\oplus k_{\mathrm{12}}^{\mathrm{48}}\right]\\ =y_{\mathrm{12}}^{\mathrm{25}}\oplus y_{\mathrm{12}}^{\mathrm{25}}\left[x_{\mathrm{4}}^{\mathrm{25}}\right]\oplus y_{\mathrm{12}}^{\mathrm{25}}\left[x_{\mathrm{8}}^{\mathrm{25}}\right]\oplus y_{\mathrm{12}}^{\mathrm{25}}\left[x_{\mathrm{4}}^{\mathrm{25}},x_{\mathrm{8}}^{\mathrm{25}}\right].\end{array}$$

(14) $y_{\mathrm{12}}^{\mathrm{25}}$ is not the output of F. But since cube sum does XOR even times, $x_{\mathrm{28}}^{\mathrm{25}}$ and $r{k}_{\mathrm{12}}^{\mathrm{48}}$ are offset. That is, we know value of cube sum cause of $Y_{\mathrm{0}}^{\mathrm{25}}\mid Y_{\mathrm{1}}^{\mathrm{25}}\mid Y_{\mathrm{2}}^{\mathrm{25}}\mid Y_{\mathrm{3}}^{\mathrm{25}}=C$ . In the same way, cube sum using fault injection in this paper is performed. By performing cube sum for every cube in Table 3, we get 16 systems of equations. Recover input $X_{\mathrm{0}}^{\mathrm{25}}$ . Similarly, we recover input $X_{\mathrm{2}}^{\mathrm{25}}$ using F which takes $X_{\mathrm{2}}^{\mathrm{25}}$ . Since $X_{\mathrm{0}}^{\mathrm{25}}\oplus w{k}_{\mathrm{2}}=Y_{\mathrm{0}}^{\mathrm{25}},X_{\mathrm{2}}^{\mathrm{25}}\oplus w{k}_{\mathrm{3}}=Y_{\mathrm{2}}^{\mathrm{25}}$ , we recover $w{k}_{\mathrm{2}},w{k}_{\mathrm{3}}\hspace{0.17em}$ (i.e., $K_{\mathrm{3}}$ , $K_{\mathrm{4}}$ ).

Step 2.

Since we know ${wk}_2$ and ${wk}_3$ , calculate intermediate value $X_{\mathrm{0}}^{\mathrm{25}}$ , $X_{\mathrm{2}}^{\mathrm{25}}$ for given ciphertext. Round permutation $\text{RP}$ in round 24 is as follows:

$$\begin{array}{cc}& Y_{\mathrm{1}}^{\mathrm{24}}={\left(X_{\mathrm{0}}^{\mathrm{25}}\right)}^L\mid {\left(X_{\mathrm{2}}^{\mathrm{25}}\right)}^R,\hspace{1em}\hspace{1em}{Y}_{\mathrm{3}}^{\mathrm{24}}={\left(X_{\mathrm{2}}^{\mathrm{25}}\right)}^L\mid {\left(X_{\mathrm{0}}^{\mathrm{25}}\right)}^R\\ Y_{\mathrm{0}}^{\mathrm{24}}={\left(X_{\mathrm{3}}^{\mathrm{25}}\right)}^L\mid {\left(X_{\mathrm{1}}^{\mathrm{25}}\right)}^R,\hspace{1em}\hspace{1em}{Y}_{\mathrm{2}}^{\mathrm{24}}={\left(X_{\mathrm{1}}^{\mathrm{25}}\right)}^L\mid {\left(X_{\mathrm{3}}^{\mathrm{25}}\right)}^R.\end{array}$$

(15) Therefore, we calculate $Y_{\mathrm{1}}^{\mathrm{24}}$ , $Y_{\mathrm{3}}^{\mathrm{24}}$ for given ciphertext. By using this, analyze round 24. In a similar way with Step 1, recover $X_{\mathrm{0}}^{\mathrm{24}}$ , $X_{\mathrm{2}}^{\mathrm{24}}$ by using the cube in Table 3 for F which takes $X_{\mathrm{0}}^{\mathrm{24}}$ , $X_{\mathrm{2}}^{\mathrm{24}}$ . Since $X_{\mathrm{0}}^{\mathrm{24}}=Y_{\mathrm{0}}^{\mathrm{24}}$ , $X_{\mathrm{2}}^{\mathrm{24}}=Y_{\mathrm{2}}^{\mathrm{24}}$ , $Y_{\mathrm{0}}^{\mathrm{24}}=(X_{\mathrm{3}}^{\mathrm{25}}{)}^L\mid (X_{\mathrm{1}}^{\mathrm{25}}{)}^R$ , and $Y_{\mathrm{2}}^{\mathrm{24}}=(X_{\mathrm{1}}^{\mathrm{25}}{)}^L\mid (X_{\mathrm{3}}^{\mathrm{25}}{)}^R$ , we recover $X_{\mathrm{1}}^{\mathrm{25}}$ , $X_{\mathrm{3}}^{\mathrm{25}}$ . Then we recover $r{k}_{\mathrm{48}},r{k}_{\mathrm{49}}$ (i.e., $K_{\mathrm{0}}$ , $K_{\mathrm{1}}$ ) since $X_{\mathrm{1}}^{\mathrm{25}}\oplus F(X_{\mathrm{0}}^{\mathrm{25}})\oplus r{k}_{\mathrm{48}}=Y_{\mathrm{1}}^{\mathrm{25}},X_{\mathrm{3}}^{\mathrm{25}}\oplus F(X_{\mathrm{2}}^{\mathrm{25}})\oplus r{k}_{\mathrm{49}}=Y_{\mathrm{3}}^{\mathrm{25}}$ .

Step 3.

We recover $K_0$ , $K_1$ , $K_3$ , and $K_4$ so far. Given ciphertext C, we calculate $X_{\mathrm{0}}^{\mathrm{24}}$ , $X_{\mathrm{1}}^{\mathrm{24}}$ , $X_{\mathrm{2}}^{\mathrm{24}}$ , and $X_{\mathrm{3}}^{\mathrm{24}}$ . That is, we recover $X_{\mathrm{0}}^{\mathrm{23}}$ , $X_{\mathrm{2}}^{\mathrm{23}}$ , $Y_{\mathrm{1}}^{\mathrm{23}}$ , and $Y_{\mathrm{3}}^{\mathrm{23}}$ . We want to recover $X_{\mathrm{1}}^{\mathrm{23}}$ . Since $X_{\mathrm{0}}^{\mathrm{22}}=Y_{\mathrm{0}}^{\mathrm{22}}=(X_{\mathrm{3}}^{\mathrm{23}}{)}^L\mid (X_{\mathrm{1}}^{\mathrm{23}}{)}^R$ , $X_{\mathrm{2}}^{\mathrm{22}}=Y_{\mathrm{2}}^{\mathrm{22}}=(X_{\mathrm{1}}^{\mathrm{23}}{)}^L\mid (X_{\mathrm{3}}^{\mathrm{23}}{)}^R$ , if we recover right 8 bits of $X_{\mathrm{0}}^{\mathrm{22}}$ and left 8 bits of $X_{\mathrm{2}}^{\mathrm{22}}$ , then we recover $X_{\mathrm{1}}^{\mathrm{23}}$ . To recover right 8 bits of $X_{\mathrm{0}}^{\mathrm{22}}$ , inject fault into bits corresponding to cube index of last 8 equations in Table 3. For recovering left 8 bits of $X_{\mathrm{2}}^{\mathrm{22}}$ , inject fault into bits corresponding to cube index of first 8 equations in Table 3. Then we recover $X_{\mathrm{1}}^{\mathrm{23}}$ . Since $X_{\mathrm{1}}^{\mathrm{23}}\oplus F(X_{\mathrm{0}}^{\mathrm{23}})\oplus r{k}_{\mathrm{44}}=Y_{\mathrm{1}}^{\mathrm{23}}$ ,we recover $r{k}_{\mathrm{44}}$ (i.e., $K_{\mathrm{2}}$ ).

Use the above 3 steps to recover all the master keys used for Piccolo-80. This needs the assumption that we inject fault into at most 4 bits in the same time. Thus in this paper we consider the following as an analyzing way.

Assumption 1.

We inject fault into at most 4 bits in the same time. But, apply this to only last round.

Assumption 2.

We inject fault into at most 4 bits in the same time. But, apply this to only rounds 24 and 25.

Assumption 3.

We inject fault into at most 4 bits in the same time.

That is, suppose that we analyze only Step 1 or Steps 1 and 2. Even though we analyze only Steps 1 and 2, since at least 32 bits of 80-bit master key are recovered, we recover all the master keys with less operations than brute-force attack. To recover $X_i^r$ , inject fault into 11 bits among 16 bits of internal state $X_i^r$ by using injections 66 times. To recover left 8 bits and right 8 bits of $X_i^r$ (i.e., $(X_i^r{)}^L,(X_i^r{)}^R$ ), we inject fault into 8 bits and 10 bits among 16 bits of $X_i^r$ , respectively. Then $(X_i^r{)}^L,(X_i^r{)}^R$ are recovered by using injections 44 and 39 times, respectively.

Under Assumption 1, we need 133 encryptions for recovering 32-bit master key $({wk}_2,{wk}_3)$ . We exclusively search to recover remaining 48-bit master key. Therefore, we need total $\mathrm{133}+{\mathrm{2}}^{\mathrm{48}}\approx {\mathrm{2}}^{\mathrm{48}}$ encryptions for recovering the master key under Assumption 1.

Under Assumption 2, we need 133 encryptions for recovering 32-bit master key $({wk}_2,{wk}_3)$ . For recovering 32-bit round keys ${rk}_{48}$ and ${rk}_{49}$ , we have to calculate $Y_{\mathrm{1}}^{\mathrm{24}},Y_{\mathrm{3}}^{\mathrm{24}}$ . Given ciphertext, calculating $Y_{\mathrm{1}}^{\mathrm{24}}$ is equivalent to 0.5 round encryption. So is $Y_{\mathrm{3}}^{\mathrm{24}}$ . Hence, we need $\mathrm{132}+(\mathrm{132}\mathrm{\hspace{0.17em}\hspace{0.17em}}\times \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{0.5}+\mathrm{1})/\mathrm{25}$ encryptions for recovering 32-bit round keys ${rk}_{48}$ and ${rk}_{49}$ . We exclusively search to recover remaining 16-bit master key. Therefore, we need total $\mathrm{133}+(\mathrm{132}+\mathrm{67}/\mathrm{25})+{\mathrm{2}}^{\mathrm{16}}\approx {\mathrm{2}}^{\mathrm{16.01}}$ encryptions for recovering the master key under Assumption 2.

Under Assumption 3, we need $\mathrm{133}+(\mathrm{132}+\mathrm{67}/\mathrm{25})$ encryptions for recovering ${wk}_2$ , ${wk}_3$ , ${rk}_{48}$ , and ${rk}_{49}$ . Given ciphertext, calculating $Y_{\mathrm{1}}^{\mathrm{22}}$ is equivalent to 2.5 round encryption. We need $\mathrm{44}\hspace{0.17em}+\hspace{0.17em}\mathrm{39}\hspace{0.17em}+\hspace{0.17em}\{(\mathrm{44}\hspace{0.17em}+\hspace{0.17em}\mathrm{39})\hspace{0.17em}\times \hspace{0.17em}\mathrm{2.5}\hspace{0.17em}+\hspace{0.17em}\mathrm{1}\mathrm{\hspace{0.17em}\hspace{0.17em}}\times \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{3}\}/\mathrm{25}$ encryptions for recovering 32-bit round keys ${rk}_{44}$ , ${rk}_{45}$ . Therefore, we need total $\mathrm{133}+(\mathrm{132}+\mathrm{67}/\mathrm{25})+(\mathrm{83}+\mathrm{210.5}/\mathrm{25})\approx {\mathrm{2}}^{\mathrm{8.49}}$ encryptions for recovering the master key under Assumption 3. Table 4 is showing encryption complexity needed for recovering the master key of each assumption.

Table 4

Attack complexity of Piccolo-80.

Assumption	Required fault	Complexity
Assumption 1	$\mathrm{132}\approx {\mathrm{2}}^{\mathrm{7.04}}$	${\mathrm{2}}^{\mathrm{48}}$
Assumption 2	$\mathrm{264}\approx {\mathrm{2}}^{\mathrm{8.04}}$	${\mathrm{2}}^{\mathrm{16.01}}$
Assumption 3	$\mathrm{347}\approx {\mathrm{2}}^{\mathrm{8.44}}$	$\mathrm{359.1}\approx {\mathrm{2}}^{\mathrm{8.49}}$

4.3. Analysis on the Piccolo-128

Piccolo-128 recovers the master key in a similar way to Piccolo-80. Figure 3 is for the last 5 rounds of Piccolo-128. The following is how Piccolo-128 recovers the master key.

Figure 3

Fault analysis of Piccolo-128.

Step 1.

First, we analyze the last round (i.e., round 25). In a similar way with Step 1 in analysis of Piccolo-80, recover $X_{\mathrm{0}}^{\mathrm{31}}$ , $X_{\mathrm{2}}^{\mathrm{31}}$ by using the cube in Table 3 for F which takes $X_{\mathrm{0}}^{\mathrm{31}}$ , $X_{\mathrm{2}}^{\mathrm{31}}$ . Since $X_{\mathrm{0}}^{\mathrm{31}}\oplus w{k}_{\mathrm{2}}=Y_{\mathrm{0}}^{\mathrm{31}},\hspace{0.17em}{X}_{\mathrm{2}}^{\mathrm{31}}\oplus w{k}_{\mathrm{3}}=Y_{\mathrm{2}}^{\mathrm{31}}$ , we recover $w{k}_{\mathrm{2}}$ , $w{k}_{\mathrm{3}}\hspace{0.17em}\hspace{0.17em}(K_{\mathrm{4}},K_{\mathrm{7}})$ .

Step 2.

Since we know $w{k}_{\mathrm{2}}$ and $w{k}_{\mathrm{3}}$ , calculate intermediate values $X_{\mathrm{0}}^{\mathrm{31}},\hspace{0.17em}{X}_{\mathrm{2}}^{\mathrm{31}}$ for given ciphertext. Since $Y_{\mathrm{1}}^{\mathrm{30}}=(X_{\mathrm{0}}^{\mathrm{31}}{)}^L\mid (X_{\mathrm{2}}^{\mathrm{31}}{)}^R,\hspace{0.17em}{Y}_{\mathrm{3}}^{\mathrm{30}}=(X_{\mathrm{2}}^{\mathrm{31}}{)}^L\mid (X_{\mathrm{0}}^{\mathrm{31}}{)}^R$ , we calculate $Y_{\mathrm{1}}^{\mathrm{30}},\hspace{0.17em}{Y}_{\mathrm{3}}^{\mathrm{30}}$ for given ciphertext. In a similar way with Step 1 in analysis of Piccolo-80, recover $X_{\mathrm{0}}^{\mathrm{30}}$ , $X_{\mathrm{2}}^{\mathrm{30}}$ by using the cube in Table 3 for F which takes $X_{\mathrm{0}}^{\mathrm{30}}$ , $X_{\mathrm{2}}^{\mathrm{30}}$ . We recover $X_{\mathrm{1}}^{\mathrm{31}}$ , $X_{\mathrm{3}}^{\mathrm{31}}$ , since $X_{\mathrm{0}}^{\mathrm{30}}=Y_{\mathrm{0}}^{\mathrm{30}},\hspace{0.17em}{X}_{\mathrm{2}}^{\mathrm{30}}=Y_{\mathrm{2}}^{\mathrm{30}}$ , and $Y_{\mathrm{0}}^{\mathrm{30}}=(X_{\mathrm{3}}^{\mathrm{31}}{)}^L\mid (X_{\mathrm{1}}^{\mathrm{31}}{)}^R,\hspace{0.17em}{Y}_{\mathrm{2}}^{\mathrm{30}}=(X_{\mathrm{1}}^{\mathrm{31}}{)}^L\mid (X_{\mathrm{3}}^{\mathrm{31}}{)}^R$ . Since $X_{\mathrm{1}}^{\mathrm{31}}\oplus F(X_{\mathrm{0}}^{\mathrm{31}})\oplus r{k}_{\mathrm{60}}=Y_{\mathrm{1}}^{\mathrm{31}}$ , $\mathrm{\hspace{0.17em}\hspace{0.17em}}{X}_{\mathrm{3}}^{\mathrm{31}}\oplus F(X_{\mathrm{2}}^{\mathrm{31}})\oplus r{k}_{\mathrm{61}}=Y_{\mathrm{3}}^{\mathrm{31}}$ , we recover $r{k}_{\mathrm{60}}$ , $r{k}_{\mathrm{61}}\hspace{0.17em}\hspace{0.17em}(K_{\mathrm{2}},K_{\mathrm{5}})$ .

Step 3.

Since we know $w{k}_{\mathrm{2}}$ , $w{k}_{\mathrm{3}}$ , ${rk}_{60}$ , and ${rk}_{61}$ , calculate intermediate values $X_{\mathrm{0}}^{\mathrm{30}}$ , $X_{\mathrm{2}}^{\mathrm{30}}$ , $Y_{\mathrm{1}}^{\mathrm{30}}$ , and $Y_{\mathrm{3}}^{\mathrm{30}}$ for given ciphertext. Since $Y_{\mathrm{1}}^{\mathrm{29}}=(X_{\mathrm{0}}^{\mathrm{30}}{)}^L\mid (X_{\mathrm{2}}^{\mathrm{30}}{)}^R$ , $Y_{\mathrm{3}}^{\mathrm{29}}=(X_{\mathrm{2}}^{\mathrm{30}}{)}^L\mid (X_{\mathrm{0}}^{\mathrm{30}}{)}^R$ , we calculate $Y_{\mathrm{1}}^{\mathrm{29}}$ , $Y_{\mathrm{3}}^{\mathrm{29}}$ for given ciphertext. In a similar way with Step 1 in analysis of Piccolo-80, recover $X_{\mathrm{0}}^{\mathrm{29}}$ , $X_{\mathrm{2}}^{\mathrm{29}}$ by using the cube in Table 3 for F which takes $X_{\mathrm{0}}^{\mathrm{29}}$ , $X_{\mathrm{2}}^{\mathrm{29}}$ . We recover $X_{\mathrm{1}}^{\mathrm{30}}$ , $X_{\mathrm{3}}^{\mathrm{30}}$ since $X_{\mathrm{0}}^{\mathrm{29}}=Y_{\mathrm{0}}^{\mathrm{29}}$ , $X_{\mathrm{2}}^{\mathrm{29}}=Y_{\mathrm{2}}^{\mathrm{29}}$ , and $Y_{\mathrm{0}}^{\mathrm{29}}=(X_{\mathrm{3}}^{\mathrm{30}}{)}^L\mid (X_{\mathrm{1}}^{\mathrm{30}}{)}^R$ , $Y_{\mathrm{2}}^{\mathrm{29}}=(X_{\mathrm{1}}^{\mathrm{30}}{)}^L\mid (X_{\mathrm{3}}^{\mathrm{30}}{)}^R$ . Since $X_{\mathrm{1}}^{\mathrm{30}}\oplus F(X_{\mathrm{0}}^{\mathrm{30}})\oplus r{k}_{\mathrm{58}}=Y_{\mathrm{1}}^{\mathrm{30}}$ and $X_{\mathrm{3}}^{\mathrm{30}}\oplus F(X_{\mathrm{2}}^{\mathrm{30}})\oplus r{k}_{\mathrm{59}}=Y_{\mathrm{3}}^{\mathrm{30}}$ , we recover $r{k}_{\mathrm{58}}$ , $r{k}_{\mathrm{59}}$ ( $K_{\mathrm{6}}$ , $K_{\mathrm{3}}$ ).

Step 4.

This step is similar to Step 3 in analysis of Piccolo-80. Given ciphertext C, we calculate $X_{\mathrm{0}}^{\mathrm{29}}$ , $X_{\mathrm{2}}^{\mathrm{29}}$ , $Y_{\mathrm{1}}^{\mathrm{29}}$ , and $Y_{\mathrm{3}}^{\mathrm{29}}$ . We want to recover $X_{\mathrm{1}}^{\mathrm{29}}$ . Since $X_{\mathrm{0}}^{\mathrm{28}}=Y_{\mathrm{0}}^{\mathrm{28}}=(X_{\mathrm{3}}^{\mathrm{29}}{)}^L\mid (X_{\mathrm{1}}^{\mathrm{29}}{)}^R$ , $X_{\mathrm{2}}^{\mathrm{28}}=Y_{\mathrm{2}}^{\mathrm{28}}=(X_{\mathrm{1}}^{\mathrm{29}}{)}^L\mid (X_{\mathrm{3}}^{\mathrm{29}}{)}^R$ , if we recover right 8 bits of $X_{\mathrm{0}}^{\mathrm{28}}$ and left 8 bits of $X_{\mathrm{2}}^{\mathrm{28}}$ , then we recover $X_{\mathrm{1}}^{\mathrm{29}}$ . To recover right 8 bits of $X_{\mathrm{0}}^{\mathrm{28}}$ , inject fault into bits corresponding to cube index of last 8 equations in Table 3. For recovering left 8 bits of $X_{\mathrm{2}}^{\mathrm{28}}$ , inject fault into bits corresponding to cube index of first 8 equations in Table 3. Then $X_{\mathrm{1}}^{\mathrm{29}}$ is recovered. And then we recover $r{k}_{\mathrm{56}}$  ( $K_{\mathrm{0}}$ ), because $X_{\mathrm{1}}^{\mathrm{29}}\oplus F(X_{\mathrm{0}}^{\mathrm{29}})\oplus r{k}_{\mathrm{56}}=Y_{\mathrm{1}}^{\mathrm{29}}$ .

Step 5.

This step is similar to Step 3 in analysis of Piccolo-80. We want to recover $X_{\mathrm{3}}^{\mathrm{28}}$ . Given ciphertext C, we calculate $X_{\mathrm{0}}^{\mathrm{28}}$ , $X_{\mathrm{2}}^{\mathrm{28}}$ , $Y_{\mathrm{1}}^{\mathrm{28}}$ , and $Y_{\mathrm{3}}^{\mathrm{28}}$ . Since $X_{\mathrm{0}}^{\mathrm{27}}=Y_{\mathrm{0}}^{\mathrm{27}}=(X_{\mathrm{3}}^{\mathrm{28}}{)}^L\mid (X_{\mathrm{1}}^{\mathrm{28}}{)}^R$ , $X_{\mathrm{2}}^{\mathrm{27}}=Y_{\mathrm{2}}^{\mathrm{27}}=(X_{\mathrm{1}}^{\mathrm{28}}{)}^L\mid (X_{\mathrm{3}}^{\mathrm{28}}{)}^R$ , we recover left 8 bits of $X_{\mathrm{0}}^{\mathrm{27}}$ and right 8 bits of $X_{\mathrm{2}}^{\mathrm{27}}$ . To recover left 8 bits of $X_{\mathrm{0}}^{\mathrm{27}}$ , inject fault into bits corresponding to cube index of first 8 equations in Table 3. For recovering right 8 bits of $X_{\mathrm{2}}^{\mathrm{27}}$ , inject fault into bits corresponding to cube index of last 8 equations in Table 3. Then we recover $X_{\mathrm{3}}^{\mathrm{28}}$ . And we recover $r{k}_{\mathrm{55}}\hspace{0.17em}(K_{\mathrm{1}})$ since $X_{\mathrm{3}}^{\mathrm{28}}\oplus F(X_{\mathrm{2}}^{\mathrm{28}})\oplus r{k}_{\mathrm{55}}=Y_{\mathrm{3}}^{\mathrm{28}}$ .

Use the above 5 steps to recover all the master keys used for Piccolo-128. This needs the assumption that we inject fault into at most 4 bits in the same time. Assume that we analyze only Steps 1, 2, 3, and 4 such as Piccolo-80. Even though we analyze only Steps 1, 2, 3, and 4, since at least 32 bits of 128-bit master key are recovered, we recover all the master keys with less operations than brute-force attack. Table 5 is showing encryption complexity needed for recovering the master key of each assumption.

Table 5

Attack complexity of Piccolo-128.

Assumption	Required fault	complexity
Step 1	$\mathrm{132}\approx {\mathrm{2}}^{\mathrm{7.04}}$	${\mathrm{2}}^{\mathrm{96}}$
Step 2	$\mathrm{264}\approx {\mathrm{2}}^{\mathrm{8.04}}$	${\mathrm{2}}^{\mathrm{64}}$
Step 3	$\mathrm{396}\approx {\mathrm{2}}^{\mathrm{8.63}}$	${\mathrm{2}}^{\mathrm{32}}$
Step 4	$\mathrm{479}\approx {\mathrm{2}}^{\mathrm{8.90}}$	${\mathrm{2}}^{\mathrm{16.01}}$
Step 5	$\mathrm{562}\approx {\mathrm{2}}^{\mathrm{9.13}}$	$\mathrm{593.64}\approx {\mathrm{2}}^{\mathrm{9.21}}$

4.4. Improved Attack

The attacks described in Sections 4.2 and 4.3 are valid under the assumption that an adversary is able to control the injecting time and bit positions to inject fault and the number of bits of fault injection. However it is difficult to control bit positions where faults are injected. Therefore, in this section, we explain the way of attack under the assumption that an adversary is not able to control bit positions to inject faults. That is, an adversary is able to inject i bits of random faults into Piccolo-80 and Piccolo-128. The attack of Section 4.4 is similar to the attack of Sections 4.2 and 4.3. But this attack adds the process that determines fault position before each Step of Sections 4.2 and 4.3.

Assume that we inject i bits of random fault into last round. In some cases, we determine fault position. Then, the following is how to determine position of fault injection for 3 cases. (Each case with 4 fault bits is described in Figures 4, 5, and 6).

Figure 4

Determine position of fault injection for Case 1 (i = 4).

Figure 5

Determine position of fault injection for Case 2 ( $i=4$ , $j=1$ ).

Figure 6

Determine position of fault injection for Case 3 ( $i=4$ , $j=1$ ).

Case 1.

There are i bits error in $Y_{\mathrm{0}}^r(Y_{\mathrm{2}}^r)$ after fault injection. Since $X_{\mathrm{0}}^r⨁w{k}_{\mathrm{2}}=Y_{\mathrm{0}}^r\hspace{0.17em}(X_{\mathrm{2}}^r⨁w{k}_{\mathrm{3}}=Y_{\mathrm{2}}^r)$ and i fault bits, if $Y_{\mathrm{0}}^r\hspace{0.17em}(Y_{\mathrm{2}}^r)$ is different i bits from original ciphertext, then fault injection position in $X_{\mathrm{0}}^r(X_{\mathrm{2}}^r)$ must be same with changed i bits after fault injection in $Y_{\mathrm{0}}^r\hspace{0.17em}(Y_{\mathrm{2}}^r)$ .

Case 2.

There are j bits error in $Y_{\mathrm{0}}^r$ and $i-j$ bits error in $Y_{\mathrm{2}}^r$ after fault injection. In a similar way to Case 1, fault injection position in $X_{\mathrm{0}}^r$ must be same with changed j bits after fault injection in $Y_{\mathrm{0}}^r$ . And fault injection position in $X_{\mathrm{2}}^r$ must be same with changed i-j bits after fault injection in $Y_{\mathrm{2}}^r$ .

Case 3.

There are $i-j$ bits error in $Y_{\mathrm{0}}^r\hspace{0.17em}(Y_{\mathrm{2}}^r)$ and j bits error in $Y_3^r(Y_1^r)$ . And there is no error in $Y_2^r(Y_0^r)$ . If there are j bits error in $Y_3^r(Y_1^r)$ , then $X_{\mathrm{2}}^r(X_{\mathrm{0}}^r)$ or $X_{\mathrm{3}}^r(X_{\mathrm{1}}^r)$ is fault injected. Since there is no error in $Y_2^r(Y_0^r)$ , fault injection position in $X_{\mathrm{3}}^r(X_{\mathrm{1}}^r)$ must be same with changed j bits after fault injection in $Y_3^r(Y_1^r)$ . Furthermore, $X_{\mathrm{0}}^r(X_{\mathrm{2}}^r)$ must be same with changed $i-j$ bits after fault injection in $Y_{\mathrm{0}}^r\hspace{0.17em}(Y_{\mathrm{2}}^r)$ since there are $i-j$ bits error in $Y_{\mathrm{0}}^r\hspace{0.17em}(Y_{\mathrm{2}}^r)$ .

Therefore, we determine the position of fault injection for these 3 cases. Table 3 is the table of optimal cubes that are used for the attack in Sections 4.2 and 4.3. Therefore, there are many cubes except cubes in Table 3. Because there are too many cubes, we do not describe all cubes in this paper. For example, suppose that we get 16 ciphertexts for cube sum of $\{\mathrm{0,1},\mathrm{3,4}\}$ . Then we calculate all of subcubes of $\{\mathrm{0,1},\mathrm{3,4}\}$ . So, we use cubes in Table 6 and recover 1st, 2nd, 5th, and 7th bit of whitening key.

Table 6

Subcube of {0, 1, 3, 4}.

Cube index	Outbit ( $F_i$ )	Polyequation
0, 3	0	$x_2+1$
0, 4	8	$x_1+x_5+1$
0, 1, 3, 4	2	$x_5$
0, 1, 3, 4	15	$x_7$

By the same method, we use sufficient cubes for recovering ${wk}_2$ and ${wk}_3$ of Piccolo-80 and Piccolo-128 and recover ${wk}_2$ and ${wk}_3$ . Since we know ${wk}_2$ and ${wk}_3$ , calculate intermediate values $X_{\mathrm{0}}^r,\hspace{0.17em}{X}_{\mathrm{2}}^r$ for given ciphertext. Therefore, we inject faults into $(r-1)$ th round, determining position of fault injection by 3 cases that described this section. And we recover $(r-1)$ th round key. This process is the same with Step 2 in Section 4.2 and Step 2 in Section 4.3 except determining position of fault injection. By the same way, we recover all the master keys of Piccolo-80 and Piccolo-128 using Steps in Sections 4.2 and 4.3 with determining position of fault injection, respectively.

The complexity of this attack depends on the complexity for finding ciphertext to recover round key. For Table 3, we need 66 ciphertexts. Table 7 is showing necessary positions of fault injection for cubes of Table 3.

Table 7

Necessary positions of fault injections for Table 3.

Number of fault bits (Number of faults)	Necessary positions of fault injection
1 (11)	(0), (1), (4), (5), (6), (7), (8), (9), (11), (12), (13)
2 (27)	(0, 1), (0, 5), (0, 6), (0, 8), (0, 9), (0, 11), (0, 12), (1, 5), (1, 6), (4, 5), (4, 7), (4, 8), (4, 9), (4, 11), (5, 6), (5, 7), (5, 8), (5, 9), (5, 13), (6, 9), (6, 13), (7, 8), (8, 9), (8, 11), (8, 12), (9, 11), (11, 12)
3 (22)	(0, 1, 5), (0, 1, 6), (0, 5, 6), (0, 8, 9), (0, 8, 11), (0, 8, 12), (0, 9, 11), (0, 11, 12), (1, 5, 6), (4, 5, 7), (4, 5, 8), (4, 5, 9), (4, 7, 8), (4, 8, 9), (4, 8, 11), (4, 9, 11), (5, 6, 9), (5, 6, 13), (5, 7, 8), (5, 8, 9), (8, 9, 11), (8, 11, 12)
4 (6)	(0, 1, 5, 6), (0, 8, 9, 11), (0, 8, 11, 12), (4, 5, 7, 8), (4, 5, 8, 9), (4, 8, 9, 11)

For calculating complexity, we assume that an adversary always injects 4-bit random fault into the last three and five rounds for Piccolo-80 and Piccolo-128, respectively. Since an adversary injects exactly 4-bit fault, position of all fault bits has to match position that we want. This probability is $1/\left(\begin{array}{c}\mathrm{64}\\ \mathrm{4}\end{array}\right)\approx {\mathrm{2}}^{-\mathrm{19.277}}$ . That is, an adversary injects ${\mathrm{2}}^{-\mathrm{19.277}}$ times for each round and gets all ciphertexts that correspond to Table 3 for each round. Therefore, this attack on Piccolo-80 needs $\mathrm{3}·{\mathrm{2}}^{\mathrm{19.277}}\approx {\mathrm{2}}^{\mathrm{20.862}}$ fault injections. Similarly, this attack on Piccolo-128 needs $\mathrm{5}·{\mathrm{2}}^{\mathrm{19.277}}\approx {\mathrm{2}}^{\mathrm{21.599}}$ fault injections. The number of additional encryptions to recover the master key is negligible. Hence, our attack has the complexity of $2^{20.86}$ and $2^{21.60}$ encryptions with four bits of random fault injections for Piccolo-80 and Piccolo-128, respectively.

5. Conclusions

In this paper, we present the security weakness of Piccolo against fault analysis. Our attack fully exploits the structure of Piccolo, which is a Feistel network. We describe an attack for fault injection of target bit positions on Piccolo-80 and Piccolo-128. The master key of Piccolo-80 and Piccolo-128 is recovered by fault analysis by using cube attack with injecting faults 2^8.44 and 2^9.14, respectively. Our attack has the complexity of $2^{8.49}$ and $2^{9.21}$ encryptions for Piccolo-80 and Piccolo-128, respectively, which are practical complexities. And finally, an attack for random four bits fault injection for Piccolo-80 and Piccolo-128 is presented. This attack needs $2^{20.86}$ and $2^{21.60}$ encryptions with four bits of random fault injections for Piccolo-80 and Piccolo-128, respectively.