Security Analysis of Scalable Block Cipher PP-1 Applicable to Distributed Sensor Networks

Abstract

PP-1 is a scalable block cipher which can be implemented on a platform with limited resource. In this paper, we analyze the security of PP-1 by using truncated differential cryptanalysis. As concrete examples, we consider four versions of PP-1, PP-1/64, PP-1/128, PP-1/192, and PP-1/256. Our attack is applicable to full-round versions of them, respectively. The proposed attacks can recover a secret key of PP-1 with the computational complexity which is faster than the exhaustive search. These are the first known cryptanalytic results on PP-1.

1. Introduction

Recently, the research on lightweight block ciphers has received considerable attention. Since these can be efficiently implemented under restricted resources such as low-cost, low-power, and lightweight platforms, they are applicable to low-end devices such as RFID tags, sensor nodes, and smart devices [1–6]. So far, many lightweight block ciphers (e.g., HIGHT [7], CLEFIA [8], KATAN/KTANTAN [9], PRINTCIPHER [5], and PP-1 [10]) have been proposed.

PP-1 is an involutional SPN block cipher which can be implemented on a platform with limited resources. It supports the scalability, which allows using different data block sizes and secret key sizes. In detail, PP-1 is an n-bit scalable block cipher and supports $n/\mathrm{2}n$ -bit secret keys. $(n=\mathrm{64},\mathrm{128},\mathrm{192},\dots )$ . It uses an $\mathrm{8}\times \mathrm{8}$ S-box which is an involution and a bit-oriented permutation which is also an involution. As a result, it is a totally involutional cipher. To our knowledge, there is no cryptanalytic result on PP-1.

In this paper, we analyze the security of PP-1 on truncated differential cryptanalysis. As concrete examples, we consider four versions of PP-1, PP-1/64, PP-1/128, PP-1/192, and PP-1/256. Here, $\mathrm{64}$ , $\mathrm{128}$ , $\mathrm{192}$ , and $\mathrm{256}$ indicate the length of data blocks. Our attack is applicable to full-round versions of them, respectively. Our attack results are summarized in Table 1. Here, PP-1/n_k means an n-bit PP-1 which supports a k-bit secret key. Note that since our attacks do not use the property of the key schedule of PP-1, the data complexity and the memory complexity of the attacks on PP-1/n_k and PP-1/n_ $\mathrm{2}k$ have the same value. From this table, our attacks can recover a secret key of PP-1 with the computational complexity which is faster than the exhaustive search. These results are the first known cryptanalytic results on PP-1.

Table 1

Our attack results on PP-1.

Target algorithm	Data complexity	Memory complexity	Computational complexity
PP-1/64_64	${\mathit{2}}^{\mathrm{45.29}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$   CP	${\mathit{2}}^{\mathrm{41.29}}$   bytes	${\mathrm{2}}^{\mathrm{45.29}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$   encryptions
PP-1/64_128			${\mathrm{2}}^{\mathrm{48.21}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$   encryptions
PP-1/128_128	${\mathrm{2}}^{\mathrm{103.45}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$   CP	${\mathit{2}}^{\mathrm{44.45}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$   bytes	${\mathit{2}}^{\mathrm{103.45}}$   encryptions
PP-1/128_256			${\mathit{2}}^{\mathrm{168}}$   encryptions
PP-1/192_192	${\mathrm{2}}^{\mathrm{157.85}}$   CP	${\mathit{2}}^{\mathrm{35.44}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$   bytes	${\mathit{2}}^{\mathrm{157.85}}$   encryptions
PP-1/192_384			${\mathit{2}}^{\mathrm{296}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$   encryptions
PP-1/256_256	${\mathit{2}}^{\mathrm{210.84}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$   CP	${\mathit{2}}^{\mathrm{24.84}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$   bytes	${\mathit{2}}^{\mathrm{210.84}}$   encryptions
PP-1/256_512			${\mathit{2}}^{\mathrm{432}}$   encryptions

PP-1/n_k: an n-bit PP-1 with a k-bit secret key.

CP: chosen plaintexts.

The rest of this paper is organized as follows. In Section 2, we briefly present PP-1. In Section 3, differentials on PP-1 are derived, and their probabilities are computed. Truncated differential cryptanalysis on each version of PP-1 is proposed in Sections 4, 5, and 6, respectively. Finally, we give our conclusion in Section 7.

2. Description of PP-1

PP-1 is an n-bit scalable block cipher and has r-round SPN structure $(n=\mathrm{64,128,192},\dots )$ . The length of a secret key is n or $\mathrm{2}n$ bits. In [10], the designers of PP-1 proposed the following four versions of PP-1 as concrete examples.

• (i)

  PP-1/64: $n=\mathrm{64}$ , $r=\mathrm{11}$ , that is, a $\mathrm{64}$ -round block cipher with $\mathrm{64}/\mathrm{128}$  bit secret keys and $\mathrm{11}$ rounds.

• (ii)

  PP-1/128: $n=\mathrm{128}$ , $r=\mathrm{22}$ , PP-1/192: $n=\mathrm{192}$ , $r=\mathrm{32}$ , PP-1/256: $n=\mathrm{256}$ , $r=\mathrm{43}$ .

For the simplicity of notations, we denote an n-bit PP-1 with a k-bit secret key PP-1/n_k. And input/output values and a round key in round i are denoted by $I^i$ , $O^i$ , and ${\text{RK}}^i$ , respectively $(i=\mathrm{1},\dots ,r)$ .

We omit the key schedule of PP-1, as it is not effectively used in our attack.

2.1. The Round Function

As shown in Figure 1(a), the round function of PP-1 consists of $(n/\mathrm{64})$ nonlinear $\text{NL}$ functions $({\text{NL}}_{\mathrm{0}},\dots ,{\text{NL}}_{(n/\mathrm{64}-\mathrm{1})})$ and an n-bit involutional permutation P. For example, when $n=\mathrm{64}$ , the round function uses only ${\text{NL}}_{\mathrm{0}}$ . Note that P is not conducted in the last round. $({\text{NL}}_{\mathrm{0}},\dots ,{\text{NL}}_{(n/\mathrm{64}-\mathrm{1})})$ have the same structure but different round keys are used.

Figure 1

(a) The round function of PP-1 and (b) the nonlinear function ${\text{NL}}_j$ .

In round i, two n-bit round keys ${\text{RK}}^i=({\text{RK}}_{\mathrm{0}}^i,{\text{RK}}_{\mathrm{1}}^i)$ are used as follows:

$$\begin{array}{cc}& {\text{RK}}_{\mathrm{0}}^i={\text{RK}}_{\mathrm{00}}^i\parallel \cdots \parallel {\text{RK}}_{\mathrm{0}(n/\mathrm{64}-\mathrm{1})}^i,\\ {\text{RK}}_{\mathrm{1}}^i={\text{RK}}_{\mathrm{10}}^i\parallel \cdots \parallel {\text{RK}}_{\mathrm{1}(n/\mathrm{64}-\mathrm{1})}^i.\end{array}$$

(1)

Here, ${\text{NL}}_j$ takes $\mathrm{128}$  bit sub-round key $({\text{RK}}_{\mathrm{0}j}^i,{\text{RK}}_{\mathrm{1}j}^i)$   $(j=\mathrm{0},\dots ,(n/\mathrm{64}-\mathrm{1}))$ .

2.2. The Nonlinear Function $\text{NL}$

In round i, ${\text{NL}}_j$ outputs a $\mathrm{64}$  bit value from a $\mathrm{64}$  bit input value and a $\mathrm{128}$  bit subround key $({\text{RK}}_{\mathrm{0}j}^i,{\text{RK}}_{\mathrm{1}j}^i)$ $(j=\mathrm{0},\dots ,(n/\mathrm{64}-\mathrm{1}))$ . It consists of one $\mathrm{8}\times \mathrm{8}$ S-box S, $\text{XOR}(\oplus )$ , $\text{addition}(⊞)$ , and $\text{substraction}(\boxminus )$ modulo ${\mathrm{2}}^{\mathrm{8}}$ (see Figure 1(b)).

A $\mathrm{128}$  bit sub-round key $({\text{RK}}_{\mathrm{0}j}^i,{\text{RK}}_{\mathrm{1}j}^i)$ is divided into eight $\mathrm{8}$  bit elementary keys as follows, respectively:

$$\begin{array}{cc}& {\text{RK}}_{\mathrm{0}j}^i={\text{RK}}_{\mathrm{0}j\mathrm{0}}^i\parallel \cdots \parallel {\text{RK}}_{\mathrm{0}j\mathrm{7}}^i,\\ {\text{RK}}_{\mathrm{1}j}^i={\text{RK}}_{\mathrm{1}j\mathrm{0}}^i\parallel \cdots \parallel {\text{RK}}_{\mathrm{1}j\mathrm{7}}^i.\end{array}$$

(2)

Thus, each elementary key is XORed or added or subtracted with an $\mathrm{8}$  bit intermediate value. For example, ${\text{RK}}_{\mathrm{1}j\mathrm{0}}^i$ is XORed with the $\mathrm{8}$  bit output value of the first S-box.

2.3. The Permutation Function P

P is an n-bit involutional bit-oriented permutation. It is constructed by using two algorithms, the auxiliary algorithm (Algorithm 1) to compute auxiliary permutation Prm and the main algorithm (Algorithm 2) to compute permutation P.

Algorithm 1: Prm(x, nBb, nSb).

(1)  nS ← nBb div nSb.

(2)   Sno ← (x mod nS) + 1.

(3)  Sb ← ((x − 1) div nS) + 1.

(4)  y← (Sno − 1) · nSb + Sb.

(5)  Return y.

Algorithm 2: P(pno, nBb, nSb).

(1)  y← Prm(pno, nBb div 2, nSb div 2).

(2)  px ← 2 ·  pno − 1.

(3)  py ← 2 ·  y.

(4)  Return (px, py).

For example, the $\mathrm{128}$  bit permutation P is obtained as a result of $\mathrm{64}$ calls of Algorithm 2 for a pair numbered as $pno$ from $\mathrm{1}$ to $\mathrm{64}$ , the number of block bits $nBb=\mathrm{128}$ and the number of S-box bits $nSb=\mathrm{8}$ . When $pno=\mathrm{2}$ , the value y of Prm is equal to $\mathrm{9}$ and the resultant pair $(px,py)=(\mathrm{3,18})$ . It means that the third bit of the input value is mapping to the eighteenth bit of the output value.

3. Construction of Differentials on PP-1

In this section, we introduce the methodology of constructing differentials on PP-1 used in our attacks. For the simplicity of notations, we define the following notations.

• (i)

  $(\alpha \to \beta {)}_t$ : a t-round differential characteristic where input/output differences are α and β, respectively.

• (ii)

  $[\alpha \to \beta {]}_t$ : a t-round differential where input/output differences are α and β, respectively.

• (iii)

  $(a,x)$ : a byte string where the ath byte value is x and the other bytes are zero (the index of the left most byte is $\mathrm{0}$ ).

3.1. Differential Characteristic on PP-1

In general, a differential characteristic with the higher probability passes less nonlinear operations, such as S-box, than it with the lower probability. Recall that a $NF$ -function consists of S-box, addition, substraction, and XOR. Among these operations, nonlinear operations are S-box, addition, and subtraction. Thus, in order to construct a differential characteristic with a high probability, we should avoid them.

We examined such differential characteristics on PP-1. As a result, we found several t-round differential characteristics with a probability of ${\mathrm{2}}^{-\mathrm{7}·t}$ . For example, in the case of PP-1/64, we can construct $((\mathrm{7},\mathtt{0}\mathtt{x}\mathtt{01})\to (\mathrm{7},\mathtt{0}\mathtt{x}\mathtt{01}){)}_t$ with a probability of ${\mathrm{2}}^{-\mathrm{7}·t}$ . This characteristic passes only one S-box in each round and the probability that S-box outputs an output difference $\mathtt{0}\mathtt{x}\mathtt{01}$ from an input difference $\mathtt{0}\mathtt{x}\mathtt{01}$ is ${\mathrm{2}}^{-\mathrm{7}}$ .

We expect that this type of difference characteristics have the highest probability. That is, they pass least S-boxes, addition operations, and subtraction operations. We extend it to differentials in the next subsection.

3.2. Finding of Differentials with a High Probability

The probability of a differential is computed by adding the probabilities of all differential characteristics which are included in it. The more differential characteristics with a high probability a differential includes, the higher its probability is. Thus, in order to find a differential on PP-1 with a high probability, we consider the following criteria.

• (i)

  In each round, a differential characteristic has only one active S-box.

• (ii)

  In each round, a differential characteristic does not pass addition/subtraction operations.

The probabilities that all t-round differential characteristics satisfying the above criteria are at least ${\mathrm{2}}^{-\mathrm{7}·t}$ , since the minimum probability from the difference distribution table on S-box is ${\mathrm{2}}^{-\mathrm{7}}$ . Thus, we measure the probability of a differential by counting only the number of differential characteristics which satisfy the above criteria and are included in it. That is, if there are w such differential characteristics, the probability of a differential including them is at least $w·{\mathrm{2}}^{-\mathrm{7}·t}$ . On the other hand, in the case of differential characteristics which do not satisfy the above criteria, they pass the additional nonlinear operations in each round. In this case, the probabilities of them are much smaller than ${\mathrm{2}}^{-\mathrm{7}·t}$ . Thus, we expect that differential characteristics which do not satisfy the above criteria depend on the probability of a differential less.

In order to count efficiently differential characteristics satisfying the above criteria, we consider differences δ's satisfying the following conditions.

• (i)

  $\delta =(a,x)$ where $(a\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{8})\in \{\mathrm{0,2},\mathrm{5,7}\}$ and x is a nonzero byte value.

• (ii)

  $P(\delta )=(b,y)$ where $(b\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{8})\in \{\mathrm{0,2},\mathrm{5,7}\}$ and y is a nonzero byte value.

Let 𝒟 be a set containing such δ's. We can easily prove that all t-round differential characteristics satisfying the above criteria include $({\delta }_i\to {\delta }_j{)}_{\mathrm{1}}$ in each round $({\delta }_i,{\delta }_j\in 𝒟)$ . It means that we only need to consider 𝒟 in order to find all differential characteristics holding the above criteria.

Let $N({\delta }_i,{\delta }_j,t)$ be the number of $({\delta }_i\to {\delta }_j{)}_t$ . For each ${\delta }_i$ and ${\delta }_j$ included in 𝒟, we compute w using the following recurrence relation:

$$\begin{array}{cc}& N\left({\delta }_i,{\delta }_j,t+\mathrm{1}\right)=\sum _{{\delta }_k\in 𝒟}‍N\left({\delta }_i,{\delta }_k,\mathrm{1}\right)·N\left({\delta }_k,{\delta }_j,t\right).\end{array}$$

(3)

Since $N({\delta }_i,{\delta }_k,\mathrm{1})$ is compute by using the difference distribution table for an S-box of PP-1, we can easily compute $N({\delta }_i,{\delta }_j,t)$ for given t.

For example, we found twenty one δ's for PP-1/64 (see Table 2). As a simulation result, $N((\mathrm{7},\mathtt{0}\mathtt{x}\mathtt{01}),(\mathrm{7},\mathtt{0}\mathtt{x}\mathtt{09}),\mathrm{8})$ is $\mathrm{8429}$ . It means that the probability of $[(\mathrm{7},\mathtt{0}\mathtt{x}\mathtt{01})\to (\mathrm{7},\mathtt{0}\mathtt{x}\mathtt{09}){]}_{\mathrm{8}}$ is ${\mathrm{2}}^{-\mathrm{42.96}}(=\mathrm{8429}·{\mathrm{2}}^{-\mathrm{7}·\mathrm{8}})$ .

Table 2

A difference set 𝒟 for PP-1/64.

(0, 0x20)	(0, 0x04)	(0, 0x01)	(2, 0x40)	(2, 0x10)	(2, 0x20)	(2, 0x30)
(5, 0x02)	(5, 0x04)	(5, 0x80)	(5, 0x84)	(5, 0x01)	(5, 0x08)	(5, 0x09)
(7, 0x02)	(7, 0x04)	(7, 0x80)	(7, 0x84)	(7, 0x01)	(7, 0x08)	(7, 0x09)

4. Truncated Differential Analysis on PP-1/64

In this section, we propose truncated differential analysis on full-round PP-1/64_64 and full-round PP-1/64_128. Since PP-1/64_64 and PP-1/64_128 have the same structure except the key schedule, the attack procedures on them are similar. Thus, we mainly introduce the attack procedure on PP-1/64_64.

By using the method in the previous section, we construct forty nine $\mathrm{8}$ -round differentials $[P((\mathrm{7},\alpha ))\to (\mathrm{7},\beta ){]}_{\mathrm{8}}\hspace{0.17em}\hspace{0.17em}(\alpha ,\beta \in \{\mathtt{0}\mathtt{x}\mathtt{01,0}\mathtt{x}\mathtt{02,0}\mathtt{x}\mathtt{04,0}\mathtt{x}\mathtt{08,0}\mathtt{x}\mathtt{09,0}\mathtt{x}\mathtt{80},\mathtt{0}\mathtt{x}\mathtt{84}\})$ . And we extend these $\mathrm{8}$ -round differentials to total $\mathrm{1785}(=\mathrm{7}·\mathrm{255})$ $\mathrm{9}$ -round differentials $[P((\mathrm{7},\alpha ))\to P((\mathrm{7},x_j^i)){]}_{\mathrm{9}}$   $(x_j^i\in X^i)$ . Here, $X^i$ 's are defined as follows $(i=\mathrm{1},\dots ,\mathrm{6})$ :

$$\begin{array}{c}{X}^{\mathrm{0}}=\left\{\mathrm{0000000}{\mathrm{0}}_{\mathrm{2}}\right\},\\ X^{\mathrm{1}}=\left\{\mathrm{0000}?\mathrm{00}{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-X^{\mathrm{0}},\\ X^{\mathrm{2}}=\left\{\mathrm{0}?\mathrm{00}?\mathrm{00}{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{1}}{X}^i,\\ X^{\mathrm{3}}=\left\{??\mathrm{00}??\mathrm{0}{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{2}}{X}^i,\\ X^{\mathrm{4}}=\left\{??\mathrm{00}???{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{3}}{X}^i,\\ X^{\mathrm{5}}=\left\{???\mathrm{0}???{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{4}}{X}^i,\\ X^{\mathrm{6}}=\left\{???????{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{5}}{X}^i.\end{array}$$

(4)

4.1. Construction of Structures

We consider a structure $S_i$ consisting of $\mathrm{256}$ plaintext; that is, $S_i=\{(i\parallel j)\mid j=\mathrm{0,1},\mathrm{2},\dots ,\mathrm{255}\}$ where i is a $\mathrm{56}$  bit fixed value. Then we can compose ${\mathrm{2}}^{\mathrm{15}}$ plaintext pairs for each structure. Among these plaintext pairs, there are ${\mathrm{2}}^{\mathrm{7}}$ plaintext pairs where an input difference of round $\mathrm{2}$ is one of $P((\mathrm{7},\alpha ))$ for each α. Table 3 presents the expected number of right plaintext pairs where an output difference of round $\mathrm{10}$ is included in $P((\mathrm{7},X^i))$ . These values are computed as follows:

$$\begin{array}{cc}& \sum _{\alpha }‍\sum _{x_j^i\in X^i}‍{\mathrm{2}}^{\mathrm{7}}·\text{Pr}\left[{\left[\alpha ⟶x_j^i\right]}_{\mathrm{9}}\right].\end{array}$$

(5)

Table 3

The expected number of right pairs for PP-1/64.

Set of output differences of round 10	The expected number of right pairs
P((7, ${\mathrm{X}}^{\mathrm{1}}$ ))	${\mathrm{2}}^{-\mathrm{35.29}}$
P((7, ${\mathrm{X}}^{\mathrm{2}}$ ))	${\mathit{2}}^{-\mathrm{35.27}}$
P((7, ${\mathrm{X}}^{\mathrm{3}}$ ))	${\mathit{2}}^{-\mathrm{33.19}}$
P((7, ${\mathrm{X}}^{\mathrm{4}}$ ))	${\mathrm{2}}^{-\mathrm{32.65}}$
P((7, X5))	${\mathrm{2}}^{-\mathrm{31.53}}$
P((7, ${\mathrm{X}}^{\mathrm{6}}$ ))	${\mathrm{2}}^{-\mathrm{30.66}}$

4.2. Truncated Differential Analysis on PP-1/64

The main idea of our attack is to exploit the fact that the expected number of plaintext pairs where an output difference of round $\mathrm{10}$ is included in $P(X^i)$ is ${\mathrm{2}}^{-\mathrm{30.66}}\hspace{0.17em}~\hspace{0.17em}{\mathrm{2}}^{-\mathrm{35.29}}$ for each structure (see Table 3).

In our attack on PP-1/64_64, we first obtain a $\mathrm{72}$  bit partial information on ${\text{RK}}^{\mathrm{11}}=({\text{RK}}_{\mathrm{0}}^{\mathrm{11}},{\text{RK}}_{\mathrm{1}}^{\mathrm{11}})$ and an $\mathrm{8}$  bit ${\text{RK}}_{\mathrm{007}}^{\mathrm{1}}$ . The attack procedure is as follows (see Figure 2).

• (1)

  Choose ${\mathrm{2}}^{\mathrm{37.29}}$ structures which are composed of $\mathrm{256}$ plaintexts and obtain the corresponding ciphertexts. From these ciphertexts, compute ${\mathrm{2}}^{\mathrm{52.29}}(={\mathrm{2}}^{\mathrm{15}}·{\mathrm{2}}^{\mathrm{37.29}})$ ciphertext pairs $(C^i,C^{i*})$ (note that we can compute total ${\mathrm{2}}^{\mathrm{15}}$ ciphertext pairs for each structure).

• (2)

  Check that the difference $\mathrm{\Delta }{C}^i$ between ciphertext pair $(C^i,C^{i*})$ is $\mathtt{0}\mathtt{x}????\mathtt{00}??\mathtt{00}??????$ ; that is, $\mathrm{\Delta }{C}_{\mathrm{02}}^i=\mathrm{\Delta }{C}_{\mathrm{04}}^i=\mathtt{0}\mathtt{x}\mathtt{00}$ for each i $(?\in \{\mathrm{0,1}{\}}^{\mathrm{4}})$ . We keep all ciphertext pairs passing Step (2) and the corresponding plaintext pairs in a table and call a set containing them 𝒜.

• (3)

  Filter out the ciphertext pairs where $\mathrm{\Delta }{C}_{\mathrm{00}}^i,\mathrm{\Delta }{C}_{\mathrm{01}}^i,\mathrm{\Delta }{C}_{\mathrm{03}}^i$ , $\mathrm{\Delta }{C}_{\mathrm{05}}^i$ and $\mathrm{\Delta }{C}_{\mathrm{06}}^i$ are not zero in 𝒜. Do the following for the remaining ciphertext pairs:

• (b)

  Partially encrypt all remaining ciphertext pairs with the guessed round key ${\text{RK}}_{\mathrm{107}}^{\mathrm{11}}$ to get $\mathrm{\Delta }{I}_{\mathrm{07}}^{\mathrm{11}}$ . Check that $\mathrm{\Delta }{I}_{\mathrm{07}}^{\mathrm{11}}$ is included in $P(X^{\mathrm{1}})$ from (4). If it is included in $P(X^{\mathrm{1}})$ , add the counter, corresponding to the guessed key, to one.

• (c)

  Output a guessed key which has the maximal counter as a right ${\text{RK}}_{\mathrm{107}}^{\mathrm{11}}$ .

(4)

From 𝒜, filter out the ciphertext pairs where $\mathrm{\Delta }{C}_{\mathrm{00}}^i,\mathrm{\Delta }{C}_{\mathrm{03}}^i$ , $\mathrm{\Delta }{C}_{\mathrm{05}}^i$ , and $\mathrm{\Delta }{C}_{\mathrm{06}}^i$ are not zero and the ciphertext pairs considered in Step (3). Do the following for the remaining ciphertext pairs:

• (a)

Check that $\mathrm{\Delta }{C}_{\mathrm{07}}$ is a nonzero value for each remaining ciphertext pair. Partially encrypt the ciphertext pairs passing this test with the recovered round key ${\text{RK}}_{\mathrm{107}}^{\mathrm{11}}$ to obtain $\mathrm{\Delta }{I}_{\mathrm{07}}^{\mathrm{11}}$ . If this value is not included in $P(X^{\mathrm{1}})$ , filter out the corresponding ciphertext pairs.

(b)

Guess $\mathrm{16}$  bit round keys $({\text{RK}}_{\mathrm{001}}^{\mathrm{11}},{\text{RK}}_{\mathrm{101}}^{\mathrm{11}})$ . (“Guess 2” in Figure 2).

(c)

Similarly to Step $(\mathrm{3})(\text{b})$ , partially encrypt the remaining ciphertext pairs with the guessed round keys to get $\mathrm{\Delta }{I}_{\mathrm{01}}^{\mathrm{11}}$ . Check that $\mathrm{\Delta }{I}_{\mathrm{01}}^{\mathrm{11}}$ is included in $P(X^{\mathrm{2}})$ from (4). If it is included in $P(X^{\mathrm{2}})$ , add the counter, corresponding to the guessed key, to one.

(d)

Output a guessed key which has the maximal counter as right ${\text{RK}}_{\mathrm{001}}^{\mathrm{11}}$ and ${\text{RK}}_{\mathrm{101}}^{\mathrm{11}}$ .

(5)

From 𝒜, discard the ciphertext pairs where $\mathrm{\Delta }{C}_{\mathrm{00}}^i,\mathrm{\Delta }{C}_{\mathrm{03}}^i$ , and $\mathrm{\Delta }{C}_{\mathrm{06}}^i$ are not zero and the ciphertext pairs considered in Step (3) and (4). Do the following for the remaining ciphertext pairs:

• (a)

Similarly to Step $(\mathrm{4})(\text{a})$ , filter out the ciphertext pairs where $\mathrm{\Delta }{I}_{\mathrm{07}}^{\mathrm{11}}$ and $\mathrm{\Delta }{I}_{\mathrm{01}}^{\mathrm{11}}$ are not included in $P(X^{\mathrm{1}})$ and $P(X^{\mathrm{2}})$ , respectively.

(b)

Guess an $\mathrm{8}$  bit round keys ${\text{RK}}_{\mathrm{105}}^{\mathrm{11}}$ . (“Guess 3” in Figure 2).

(c)

Similarly to Step $(\mathrm{4})(\text{c})$ , check that $\mathrm{\Delta }{I}_{\mathrm{05}}^{\mathrm{11}}$ is included in $P(X^{\mathrm{3}})$ . Output a guessed key which has the maximal counter as a right ${\text{RK}}_{\mathrm{105}}^{\mathrm{11}}$ .

(6)

From 𝒜, discard the ciphertext pairs where $\mathrm{\Delta }{C}_{\mathrm{03}}^i$ and $\mathrm{\Delta }{C}_{\mathrm{06}}^i$ are not zero and the ciphertext pairs considered in Step (3), (4) and (5). Do the following for the remaining ciphertext pairs:

• (a)

Similarly to Step $(\mathrm{5})(\text{a})$ , filter out the ciphertext pairs where $\mathrm{\Delta }{I}_{\mathrm{07}}^{\mathrm{11}}$ , $\mathrm{\Delta }{I}_{\mathrm{01}}^{\mathrm{11}}$ and $\mathrm{\Delta }{I}_{\mathrm{05}}^{\mathrm{11}}$ are not included in $P(X^{\mathrm{1}})$ , $P(X^{\mathrm{2}})$ and $P(X^{\mathrm{3}})$ , respectively.

(b)

Guess an $\mathrm{8}$  bit round keys ${\text{RK}}_{\mathrm{100}}^{\mathrm{11}}$ . (“Guess 4” in Figure 2).

(c)

Similarly to Step $(\mathrm{5})(\text{c})$ , check that $\mathrm{\Delta }{I}_{\mathrm{00}}^{\mathrm{11}}$ is included in $P(X^{\mathrm{4}})$ . Output a guessed key which has the maximal counter as a right ${\text{RK}}_{\mathrm{100}}^{\mathrm{11}}$ .

(7)

From 𝒜, filter out the ciphertext pairs where $\mathrm{\Delta }{C}_{\mathrm{03}}^i$ is not zero and the ciphertext pairs considered in Step (3), (4), (5) and (6). Do the following for the remaining ciphertext pairs:

• (a)

Similarly to Step $(\mathrm{6})(\text{a})$ , filter out the ciphertext pairs where $\mathrm{\Delta }{I}_{\mathrm{07}}^{\mathrm{11}}$ , $\mathrm{\Delta }{I}_{\mathrm{01}}^{\mathrm{11}}$ , $\mathrm{\Delta }{I}_{\mathrm{05}}^{\mathrm{11}}$ and $\mathrm{\Delta }{I}_{\mathrm{00}}^{\mathrm{11}}$ are not included in $P(X^{\mathrm{1}})$ , $P(X^{\mathrm{2}})$ , $P(X^{\mathrm{3}})$ and $P(X^{\mathrm{4}})$ , respectively.

(b)

Guess $\mathrm{16}$  bit round keys $({\text{RK}}_{\mathrm{006}}^{\mathrm{11}},{\text{RK}}_{\mathrm{106}}^{\mathrm{11}})$ . (“Guess 5” in Figure 2).

(c)

Similarly to Step $(\mathrm{6})(\text{c})$ , check that $\mathrm{\Delta }{I}_{\mathrm{06}}^{\mathrm{11}}$ is included in $P(X^{\mathrm{5}})$ . Output a guessed key which has the maximal counter as right ${\text{RK}}_{\mathrm{006}}^{\mathrm{11}}$ and ${\text{RK}}_{\mathrm{106}}^{\mathrm{11}}$ .

(8)

From 𝒜, filter out the ciphertext pairs considered in Step (3), (4), (5), (6) and (7). Do the following for the remaining ciphertext pairs:

• (a)

Similarly to Step $(\mathrm{7})(\text{a})$ , filter out the ciphertext pairs where $\mathrm{\Delta }{I}_{\mathrm{07}}^{\mathrm{11}}$ , $\mathrm{\Delta }{I}_{\mathrm{01}}^{\mathrm{11}}$ , $\mathrm{\Delta }{I}_{\mathrm{05}}^{\mathrm{11}}$ , $\mathrm{\Delta }{I}_{\mathrm{00}}^{\mathrm{11}}$ and $\mathrm{\Delta }{I}_{\mathrm{06}}^{\mathrm{11}}$ are not included in $P(X^{\mathrm{1}})$ , $P(X^{\mathrm{2}})$ , $P(X^{\mathrm{3}})$ , $P(X^{\mathrm{4}})$ and $P(X^{\mathrm{5}})$ , respectively.

(b)

Guess $\mathrm{16}$  bit round keys $({\text{RK}}_{\mathrm{003}}^{\mathrm{11}},{\text{RK}}_{\mathrm{103}}^{\mathrm{11}})$ . (“Guess 6” in Figure 2).

(c)

Similarly to Step $(\mathrm{7})(\text{c})$ , check that $\mathrm{\Delta }{I}_{\mathrm{03}}^{\mathrm{11}}$ is included in $P(X^{\mathrm{6}})$ . Output a guessed key which has the maximal counter as right ${\text{RK}}_{\mathrm{003}}^{\mathrm{11}}$ and ${\text{RK}}_{\mathrm{103}}^{\mathrm{11}}$ .

(9)

Get the the corresponding plaintext pairs to all ciphertext pairs considered in Step $(\mathrm{3})(\text{b})$ , $(\mathrm{4})(\text{c})$ , $(\mathrm{5})(\text{c})$ , $(\mathrm{6})(\text{c})$ , $(\mathrm{7})(\text{c})$ and $(\mathrm{8})(\text{c})$ , respectively. With them, do the following:

• (a)

Guess an $\mathrm{8}$  bit ${\text{RK}}_{\mathrm{007}}^{\mathrm{1}}$ (“Guess 7” in Figure 2).

(b)

Partially encrypt the plaintext pairs in Step (9) with the guessed round key to obtain the output difference of the $\mathrm{8}$ th S-box in round $\mathrm{1}$ , that is, $(P^{-\mathrm{1}}(I^{\mathrm{2}}){)}_{\mathrm{07}}$ .

(c)

If the computed difference is included in $\{\mathtt{0}\mathtt{x}\mathtt{01},\mathtt{0}\mathtt{x}\mathtt{02},\mathtt{0}\mathtt{x}\mathtt{04},\mathtt{0}\mathtt{x}\mathtt{08},\mathtt{0}\mathtt{x}\mathtt{09},\mathtt{0}\mathtt{x}\mathtt{80},\mathtt{0}\mathtt{x}\mathtt{84}\}$ , add the counter, corresponding to the guessed key, to one.

(d)

Output a guessed key which has the maximal counter as a right ${\text{RK}}_{\mathrm{007}}^{\mathrm{1}}$ .

(10)

With an $\mathrm{80}$  bit suggested round key, compute a secret key by operating the key schedule of PP-1_64. Output the computed secret key as a right secret key of PP-1_64.

Figure 2

The attack procedure on full-round PP-1/64_64.

In our attack on PP-1/64_64, we construct ${\mathrm{2}}^{\mathrm{37.29}}$ structures which are composed of $\mathrm{256}$ plaintexts. Thus, the data complexity of our attack is about ${\mathrm{2}}^{\mathrm{45.29}}(\approx {\mathrm{2}}^{\mathrm{37.29}}·{\mathrm{2}}^{\mathrm{8}})$ chosen plaintexts. We store all ciphertext pairs passing Step (2) and the corresponding plaintext pairs in a table. The probability that a ciphertext pair passes Step (2) is ${\mathrm{2}}^{-\mathrm{16}}$ . Thus, ${\mathrm{2}}^{\mathrm{36.29}}(\approx {\mathrm{2}}^{\mathrm{52.29}}·{\mathrm{2}}^{-\mathrm{16}})$ ciphertext pairs pass this step. Hence, the memory complexity of this attack is about ${\mathrm{2}}^{\mathrm{41.29}}(\approx {\mathrm{2}}^{\mathrm{52.29}}·{\mathrm{2}}^{-\mathrm{16}}·\mathrm{4}·\mathrm{8})$ memory bytes.

The computational complexity of our attack is dominated by Step (1). The computational complexity of Step (1) is about ${\mathrm{2}}^{\mathrm{45.29}}(\approx {\mathrm{2}}^{\mathrm{37.29}}·{\mathrm{2}}^{\mathrm{8}})$ encryptions. The probability that a wrong ciphertext pair passes Step (3) is ${\mathrm{2}}^{-\mathrm{40}}$ . Since the expected number of the remaining wrong ciphertext pairs is ${\mathrm{2}}^{-\mathrm{3.71}}(\approx {\mathrm{2}}^{\mathrm{36.29}}·{\mathrm{2}}^{-\mathrm{40}})$ , we expect that only right ciphertext pairs are survived. From (4), we can check easily that all ciphertext pairs where the corresponding $\mathrm{\Delta }{O}^{\mathrm{10}}$ 's are included in $P(X^{\mathrm{1}})$ pass Step (3). Thus, the expected number of right ciphertext pairs is $\mathrm{4}(\approx {\mathrm{2}}^{\mathrm{37.29}}·{\mathrm{2}}^{-\mathrm{35.29}})$ from Table 3. The computational complexity of Step $(\mathrm{3})(\text{b})$ is about ${\mathrm{2}}^{\mathrm{3.54}}(\approx {\mathrm{2}}^{\mathrm{8}}·\mathrm{4}·\mathrm{1}/\mathrm{11}·\mathrm{1}/\mathrm{8})$ encryptions. Similarly to Step $(\mathrm{3})(\text{b})$ , the computational complexities of other steps are also small. Hence, the computational complexity of our attack on PP-1/64_64 is about ${\mathrm{2}}^{\mathrm{45.29}}$ encryptions.

In the case of the attack on PP-1/64_128, the data and memory complexities are the same as them of the attack on PP-1/64_64. However, the computational complexity of this attack is dominated by Step (1) and (10), since we should do an exhaustive search for the remaining $\mathrm{48}$  bit key information. The computational complexity of Step (1) is about ${\mathrm{2}}^{\mathrm{45.29}}(\approx {\mathrm{2}}^{\mathrm{37.29}}·{\mathrm{2}}^{\mathrm{8}})$ encryptions. In Step (10), the probability that a wrong key passes this step is ${\mathrm{2}}^{-\mathrm{64}}$ . Thus, it is sufficient to use just one plaintext/ciphertext pair. The computational complexity of Step (10) is about ${\mathrm{2}}^{\mathrm{48}}$ . Hence, the computational complexity of PP-1/64_128 is about ${\mathrm{2}}^{\mathrm{48.21}}(\approx {\mathrm{2}}^{\mathrm{45.29}}+{\mathrm{2}}^{\mathrm{48}})$ encryptions.

5. Truncated Differential Analysis on Full-Round PP-1/128

Our attacks on full-round PP-1/128_128 and full-round PP-1/128_256 use $\mathrm{20}$ -round differentials which are constructed by using the method introduced in Section 3. In detail, in order to construct them, we consider twenty five $\mathrm{19}$ -round differentials $[P((\mathrm{15},\alpha ))\to (\mathrm{15},\beta ){]}_{\mathrm{19}}\hspace{0.17em}\hspace{0.17em}(\alpha ,\beta \in \{\mathtt{0}\mathtt{x}\mathtt{01,0}\mathtt{x}\mathtt{08,0}\mathtt{x}\mathtt{09,0}\mathtt{x}\mathtt{10,0}\mathtt{x}\mathtt{80}\})$ . Then we extend these $\mathrm{19}$ -round differentials to total $\mathrm{1275}(=\mathrm{5}·\mathrm{255})$   $\mathrm{20}$ -round differentials $[P((\mathrm{15},\alpha ))\to P((\mathrm{15},y_j^i)){]}_{\mathrm{20}}$   $(y_j^i\in Y^i)$ . Here, $Y^i$ 's are defined as follows $(i=\mathrm{1},\dots ,\mathrm{7})$ :

$$\begin{array}{cc}& Y^{\mathrm{0}}=\left\{\mathrm{0000000}{\mathrm{0}}_{\mathrm{2}}\right\},\\ Y^{\mathrm{1}}=\left\{\mathrm{0000}?\mathrm{00}{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-Y^{\mathrm{0}},\\ Y^{\mathrm{2}}=\left\{\mathrm{0}?\mathrm{00}?\mathrm{00}{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{1}}{Y}^i,\\ Y^{\mathrm{3}}=\left\{??\mathrm{00}?\mathrm{00}{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{2}}{Y}^i,\\ Y^{\mathrm{4}}=\left\{??\mathrm{00}??\mathrm{0}{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{3}}{Y}^i,\\ Y^{\mathrm{5}}=\left\{??\mathrm{00}???{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{4}}{Y}^i,\\ Y^{\mathrm{6}}=\left\{???\mathrm{0}???{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{5}}{Y}^i,\\ Y^{\mathrm{7}}=\left\{???????{?}_{\mathrm{2}}\mid ?\in \left\{\mathrm{0,1}\right\}\right\}-\bigcup _{i=\mathrm{0}}^{\mathrm{6}}{Y}^i.\end{array}$$

(6)

In the similar manner to the previous section, we choose a structure $S_i$ which consist of $\mathrm{256}$ plaintext; that is, $S_i=\{(i\parallel j)\mid j=\mathrm{0,1},\mathrm{2},\dots ,\mathrm{255}\}$ , where i is a $\mathrm{120}$  bit fixed value. Then, as shown in Table 4, we can calculate the expected number of right plaintext pairs where $\mathrm{\Delta }{O}^{\mathrm{21}}$ is included in $P(\mathrm{15},(Y^i))$ for each structure.

Table 4

The expected number of right pairs for PP-1/128.

Set of output differences of round 21	The expected number of right pairs
P((15, $Y^{\mathrm{1}}$ ))	${\mathit{2}}^{-\mathrm{93.33}}$
P((15, $Y^{\mathrm{2}}$ ))	${\mathit{2}}^{-\mathrm{93.45}}$
P((15, $Y^{\mathrm{3}}$ ))	${\mathit{2}}^{-\mathrm{92.64}}$
P((15, $Y^{\mathrm{4}}$ ))	${\mathit{2}}^{-\mathrm{92.01}}$
P((15, $Y^{\mathrm{5}}$ ))	${\mathit{2}}^{-\mathrm{96.86}}$
P((15, $Y^{\mathrm{6}}$ ))	${\mathit{2}}^{-\mathrm{89.78}}$
P((15, $Y^{\mathrm{7}}$ ))	${\mathit{2}}^{-\mathrm{88.92}}$

5.1. Truncated Differential Analysis on PP-1/128

Our attack on full-round PP-1/128_128 is similar to that on full-round PP-1/128_256. Thus, we mainly present the attack procedure on PP-1/128_128. Since it is similar to the attack procedure on full-round PP-1/64_64, we briefly introduce it. The attack procedure on full-round PP-1/128_128 is as follows (see Figure 3).

• (1)

  Select ${\mathrm{2}}^{\mathrm{95.45}}$ structures which are composed of $\mathrm{256}$ plaintexts and get the corresponding ciphertexts. From these ciphertexts, compute ${\mathrm{2}}^{\mathrm{110.45}}$ ciphertext pairs ( $C^i,C^{i*}$ ).

• (2)

  Check that $\mathrm{\Delta }{C}_{\mathrm{01}}^i=\mathrm{\Delta }{C}_{\mathrm{02}}^i=\mathrm{\Delta }{C}_{\mathrm{04}}^i=\mathrm{\Delta }{C}_{\mathrm{05}}^i=\mathrm{\Delta }{C}_{\mathrm{06}}^i=\mathrm{\Delta }{C}_{\mathrm{10}}^i=\mathrm{\Delta }{C}_{\mathrm{11}}^i=\mathrm{\Delta }{C}_{\mathrm{12}}^i=\mathrm{\Delta }{C}_{\mathrm{14}}^i=\mathrm{0}$ for each ciphertext pair. We keep all ciphertext pairs passing Step (2) and the corresponding plaintext pairs in a table and call a set containing them 𝒜.

• (3)

  From 𝒜, filter out the ciphertext pairs where $\mathrm{\Delta }{C}_{\mathrm{00}}^i$ , $\mathrm{\Delta }{C}_{\mathrm{03}}^i$ , $\mathrm{\Delta }{C}_{\mathrm{07}}^i$ , $\mathrm{\Delta }{C}_{\mathrm{13}}^i$ , $\mathrm{\Delta }{C}_{\mathrm{15}}^i$ , and $\mathrm{\Delta }{C}_{\mathrm{16}}^i$ are not zero. Do the following for the remaining ciphertext pairs:

• (b)

  Check that $\mathrm{\Delta }{I}_{\mathrm{17}}^{\mathrm{22}}$ is included in $P(Y^{\mathrm{1}})$ . Output a guessed key which has the maximal counter as right ${\text{RK}}_{\mathrm{117}}^{\mathrm{22}}$ .

(4)

Similarly to Step (3), determine sequentially the following right round keys.

• (a)

$({\text{RK}}_{\mathrm{003}}^{\mathrm{22}},{\text{RK}}_{\mathrm{103}}^{\mathrm{22}})$ (“Guess 2”),

(b)

${\text{RK}}_{\mathrm{115}}^{\mathrm{22}}$ (“Guess 3”).

(c)

$({\text{RK}}_{\mathrm{013}}^{\mathrm{22}},{\text{RK}}_{\mathrm{115}}^{\mathrm{22}})$ (“Guess 4”).

(d)

${\text{RK}}_{\mathrm{101}}^{\mathrm{22}}$ (“Guess 5”).

(e)

$({\text{RK}}_{\mathrm{016}}^{\mathrm{22}},{\text{RK}}_{\mathrm{116}}^{\mathrm{22}})$ (“Guess 6”).

(f)

${\text{RK}}_{\mathrm{117}}^{\mathrm{22}}$ (“Guess 7”).

(5)

Get the the corresponding plaintext pairs to all ciphertext pairs considered in Steps (3) and (4). With them, do the following:

• (a)

Guess an $\mathrm{8}$  bit ${\text{RK}}_{\mathrm{017}}^{\mathrm{1}}$ (“Guess 8”).

(b)

Partially encrypt the plaintext pairs in Step (5) with the guessed round key to obtain the output difference of the $\mathrm{8}$ th S-box in second $NF$ -function of round $\mathrm{1}$ , that is, $(P^{-\mathrm{1}}(I^{\mathrm{2}}){)}_{\mathrm{17}}$ .

(c)

If the computed difference is included in $\{\mathtt{0}\mathtt{x}\mathtt{01},\mathtt{0}\mathtt{x}\mathtt{08},\mathtt{0}\mathtt{x}\mathtt{09},\mathtt{0}\mathtt{x}\mathtt{10},\mathtt{0}\mathtt{x}\mathtt{80}\}$ , add the counter, corresponding to the guessed key, to one.

(d)

Output a guessed key which has the maximal counter as a right ${\text{RK}}_{\mathrm{017}}^{\mathrm{1}}$ .

(6)

With an $\mathrm{88}$  bit suggested round key, do an exhaustive search for the remaining $\mathrm{40}$  bit key information by using one trial encryption. During this procedure, if a $\mathrm{128}$  bit secret key satisfies one known plaintext/ciphertext pair, output this $\mathrm{128}$  bit secret key as a right $\mathrm{128}$  bit secret key of full-round PP-1/128_128.

Figure 3

The attack procedure on full-round PP-1/128_128.

In this attack, we construct ${\mathrm{2}}^{\mathrm{95.45}}$ structures. Thus, the data complexity of our attack on full-round PP-1/128_128 is about ${\mathrm{2}}^{\mathrm{103.45}}(\approx {\mathrm{2}}^{\mathrm{95.45}}·{\mathrm{2}}^{\mathrm{8}})$ chosen plaintexts. In Step (2), since the probability that a ciphertext pair passes Step (2) is ${\mathrm{2}}^{-\mathrm{72}}$ , we store ${\mathrm{2}}^{\mathrm{38.45}}(\approx {\mathrm{2}}^{\mathrm{110.45}}·{\mathrm{2}}^{-\mathrm{72}})$ ciphertext pairs pass this step and the corresponding plaintext pairs in a table. Thus, the memory complexity of this attack is about ${\mathrm{2}}^{\mathrm{44.45}}(\approx {\mathrm{2}}^{\mathrm{38.45}}·\mathrm{4}·\mathrm{16})$ memory bytes. The computational complexity of this attack is dominated by Step (1), that is, about ${\mathrm{2}}^{\mathrm{103.45}}(\approx {\mathrm{2}}^{\mathrm{95.45}}·{\mathrm{2}}^{\mathrm{8}})$ encryptions.

In the case of the attack on full-round PP-1/128_256, the data and memory complexities are the same as them of the attack on full-round PP-1/128_128. However, the computational complexity of this attack is dominated by Step (6), since we should do an exhaustive search for the remaining $\mathrm{168}$  bit key information. In Step (6), the probability that a wrong key that passes this step is ${\mathrm{2}}^{-\mathrm{128}}$ . Thus, this step needs two plaintext/ciphertext pairs. The computational complexity of Step (6) is about ${\mathrm{2}}^{\mathrm{168}}(\approx {\mathrm{2}}^{\mathrm{168}}+{\mathrm{2}}^{\mathrm{168}}·{\mathrm{2}}^{-\mathrm{128}})$ encryptions. Hence, the computational complexity of our attack on full-round PP-1/128_256 is about ${\mathrm{2}}^{\mathrm{168}}$ encryptions.

6. Truncated Differential Analysis on Full-Round PP-1/192 and PP-1/256

This section introduces our attack results on full-round PP-1/192 and full-round PP-1/256. Overall, the attack procedures on them are similar to the attack procedures on PP-1/64.

Our attacks on full-round PP-1/192 uses ${\mathrm{2}}^{\mathrm{149.85}}$ structures $S_i=\{(i\parallel j)\mid j=\mathrm{0,1},\mathrm{2},\dots ,\mathrm{255}\}$ , where i is a $\mathrm{184}$  bit fixed value. First, we construct thirty six $\mathrm{29}$ -round differentials $[P((\mathrm{23},\alpha ))\to (\mathrm{23},\beta ){]}_{\mathrm{29}}$   $(\alpha ,\beta \in \{\mathtt{0}\mathtt{x}\mathtt{01,0}\mathtt{x}\mathtt{02,0}\mathtt{x}\mathtt{08,0}\mathtt{x}\mathtt{09,0}\mathtt{x}\mathtt{40},\mathtt{0}\mathtt{x}\mathtt{80}\})$ . Then we extend these $\mathrm{29}$ -round differentials to total $\mathrm{1530}(=\mathrm{6}·\mathrm{255})$   $\mathrm{30}$ -round truncated differentials $[P((\mathrm{23},\alpha ))\to P((\mathrm{23},y_j^i)){]}_{\mathrm{30}}$    $(y_j^i\in Y^i)$ . Note that $Y^i$ 's used in this attack are the same as them in the attack on full-round PP-1/128. Table 5 presents the expected number of right plaintext pairs where $\mathrm{\Delta }{O}^{\mathrm{31}}$ is included in $P(\mathrm{23},(Y^i))$ in each structure. The complexities of our attacks are as follows.

Table 5

The expected number of right pairs for PP-1/192.

Set of output differences of round 31	The expected number of right pairs
P((23, $Y^{\mathit{1}}$ ))	${\mathrm{2}}^{-\mathrm{147.85}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$
P((23, $Y^{\mathit{2}}$ ))	${\mathit{2}}^{-\mathrm{147.01}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$
P((23, $Y^{\mathit{3}}$ ))	${\mathit{2}}^{-\mathrm{145.93}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$
P((23, $Y^{\mathit{4}}$ ))	${\mathrm{2}}^{-\mathrm{145.48}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$
P((23, $Y^{\mathit{5}}$ ))	${\mathrm{2}}^{-\mathrm{144.38}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$
P((23, $Y^{\mathit{6}}$ ))	${\mathit{2}}^{-\mathrm{143.26}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$
P((23, $Y^{\mathit{7}}$ ))	${\mathit{2}}^{-\mathrm{142.38}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$

PP-1/192_192(PP-1/192_384)

• (a)

  The data complexity: about ${\mathrm{2}}^{\mathrm{157.85}}$ chosen plaintexts.

• (b)

  The memory complexity: about ${\mathrm{2}}^{\mathrm{35.44}}$ memory bytes.

• (c)

  The computational complexity: about ${\mathrm{2}}^{\mathrm{157.85}}({\mathrm{2}}^{\mathrm{296}})$ encryptions.

In the case of PP-1/256, we consider ${\mathrm{2}}^{\mathrm{202.84}}$ structure $S_i=\{(i\parallel j)\mid j=\mathrm{0,1},\mathrm{2},\dots ,\mathrm{255}\}$ , where i is a $\mathrm{248}$  bit fixed value. And we construct $\mathrm{2040}$ $\mathrm{41}$ -round differentials $[P((\mathrm{31},\alpha ))\to P((\mathrm{31},y_j^i)){]}_{\mathrm{41}}\hspace{0.17em}(\alpha \in \{\mathtt{0}\mathtt{x}\mathtt{01,0}\mathtt{x}\mathtt{02,0}\mathtt{x}\mathtt{04,0}\mathtt{x}\mathtt{08,0}\mathtt{x}\mathtt{09},\mathtt{0}\mathtt{x}\mathtt{10,0}\mathtt{x}\mathtt{40,0}\mathtt{x}\mathtt{80}\})\hspace{0.17em}(y_j^i\in Y^i)$ . Note that $Y^i$ 's used in this attack are also the same as them in the attack on full-round PP-1/128. Table 6 presents the expected number of right plaintext pairs where $\mathrm{\Delta }{O}^{\mathrm{42}}$ is included in $P(\mathrm{31},(Y^i))$ in each structure. The complexities of our attacks are as follows.

Table 6

The expected number of right pairs for PP-1/256.

Set of output differences of round 42	The expected number of right pairs
P((31, Y1))	${\mathrm{2}}^{-\mathrm{200.73}}$
P((31, Y2))	${\mathrm{2}}^{-\mathrm{200.84}}$
P((31, Y3))	${\mathit{2}}^{-\mathrm{199.89}}$
P((31, Y4))	${\mathrm{2}}^{-\mathrm{199.23}}$
P((31, Y5))	${\mathrm{2}}^{-\mathrm{198.10}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$
P((31, Y6))	${\mathit{2}}^{-\mathrm{197.09}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$
P((31, Y7))	${\mathit{2}}^{-\mathrm{196.18}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$

PP-1/256_256(PP-1/256_512)

• (a)

  The data complexity: about ${\mathrm{2}}^{\mathrm{210.84}}$ chosen plaintexts.

• (b)

  The memory complexity: about ${\mathrm{2}}^{\mathrm{24.84}}$ memory bytes.

• (c)

  The computational complexity: about ${\mathrm{2}}^{\mathrm{210.84}}({\mathrm{2}}^{\mathrm{432}})$ encryptions.

7. Conclusion

In this paper, we have presented the first known cryptanalytic results of four concrete versions of a scalable block cipher PP-1, full-round PP-1/64, full-round PP-1/128, full-round PP-1/192, and full-round PP-1/256, by using truncated differential cryptanalysis. As summarized in Table 1, our attacks on these algorithms require computational complexities smaller than the exhaustive search. These results indicate that PP-1 is vulnerable to truncated differential cryptanalysis and that it is insecure.