Sage Journals: Discover world-class research

Abstract

PRINTcipher-48/96 are 48/96-bit block ciphers proposed in CHES 2010 which support the 80/160-bit secret keys, respectively. In this paper, we propose related-key cryptanalysis of PRINTcipher. To recover the 80-bit secret key of PRINTcipher-48, our attack requires 2⁴⁷ related-key chosen plaintexts with a computational complexity of $2^{60 \cdot 62}$ . In the case of PRINTcipher-96, we require 2⁹⁵ related-key chosen plaintexts with a computational complexity of 2¹⁰⁷. These results are the first known related-key cryptanalytic results on them.

1. Introduction

Recently, the security of constrained hardware environments such as RFID tags and sensor nodes is major topic in cryptography [1, 2]. The research on lightweight block ciphers suitable for the efficient implementation in constrained hardware environments such as RFID tags and sensor nodes has been studied. As a result, PRESENT [3], LED [4], HIGHT [5], PRINTcipher [6], and Piccolo [7] were proposed.

PRINTcipher is a $48 / 96$ -bit block cipher proposed in CHES 2010 thst supports the $80 / 160$ -bit secret keys. According to the block size, they are denoted by PRINTcipher-48 and PRINTcipher-96, respectively. The attractive properties of PRINTcipher are that all rounds use the same round key and differ only by a round counter and that the linear layer is partially key-dependent. Because of these properties, most known cryptanalytic results on PRINTcipher are based on weak keys (see Table 1). The best attack results on PRINTcipher are invariance subspace attacks on the full PRINTcipher-48/96 [8]. In detail, the attack on the full PRINTcipher-48 is applicable to $2^{52}$ weak keys and requires $5$ chosen plaintexts with a negligible computational complexity. In the case of the full PRINTcipher-96, it is applicable to $2^{102}$ weak keys and requires $5$ chosen plaintexts with a negligible computational complexity.

Table 1

Summary of cryptanalytic results on PRINTcipher.

Target algorithm	Attack method	Attack rounds	Number of weak keys	Complexity		Reference
Target algorithm	Attack method	Attack rounds	Number of weak keys	Data	Computation	Reference
PRINTcipher-48	DC	$22$	·	$2^{48}$	$2^{48}$	[9]
	LC $^{*}$	29	$2^{75}$	$2^{48}$	$2^{73}$	[10]
	CDLC $^{*}$	31	$2^{68.56}$	$2^{46.92}$	$2^{25.92}$	[11]
	ISA $^{*}$	Full ( $48$ )	$2^{52}$	$5$	Negligible	[8]
	RKDC	Full ( $48$ )	·	$2^{47}$	$2^{60.62}$	This paper

PRINTcipher-96	ISA $^{*}$	Full ( $96$ )	$2^{102}$	$5$	Negligible	[8]
PRINTcipher-96	RKDC	Full ( $96$ )	·	$2^{95}$	$2^{107}$	This paper

$^{*}$ Attack results based on weak keys.

CDLC: combined differential and linear cryptanalysis.

ISA: invariant subspace attack.

RKDC: related-key differential cryptanalysis.

In this paper, we find weakness of PRINTcipher-48/96 on related-key attacks. To construct related-key differential characteristics, we focus on related keys that have different values in the part related to a key-dependent permutation. Thus, we can construct t-round related-key differential characteristics with a probability of $2^{- t}$ . By using these characteristics, we can recover the secret keys of PRINTcipher-48/96. Our results are summarized in Table 1. In detail, to recover the $80$ -bit secret key of PRINTcipher-48, our attack requires $4$ related keys, $2^{47}$ related-key chosen plaintexts, and a computational complexity of $2^{60.62}$ . In the case of PRINTcipher-96, we require $4$ related keys, $2^{95}$ related-key chosen plaintexts, and a computational complexity of $2^{107}$ . These results are the first known related-key cryptanalytic results on them.

This paper is organized as follows. In Section 2, we describe briefly the structure of PRINTcipher. In Section 3, we explain how to construct related-key differential characteristics on PRINTcipher. Related-key attacks on PRINTcipher-48 and PRINTcipher-96 are proposed in Sections 4 and 5, respectively. Finally, we give our conclusion in Section 6.

2. Description of PRINTcipher

PRINTcipher-48/96 are $48 / 96$ -bit block ciphers supporting the $80 / 160$ -bit secret keys. Note that PRINTcipher uses the same round key $(S K^{1}, S K^{2})$ for all rounds. In detail, the secret key K is divided into $(S K^{1}, S K^{2})$ . $S K^{1}$ is used to XORing with an intermediate value, and $S K^{2}$ controls a key-dependent permutation.

Figure 1 presents a single round of PRINTcipher-b, where $b \in {48,96}$ . The encryption process of PRINTcipher-b is as follows. Here, the number of rounds is b. A b-bit round key $S K^{1} = (s k_{0}^{1}, \dots, s k_{b - 1}^{1})$ and a $(2 b / 3)$ -bit round key $S K^{2} = (S K_{0}^{2}, \dots, S K_{b / 3 - 1}^{2})$ ; here, $s k_{0}^{1}$ is the most significant bit of $S K^{1}$ .

(1)

A b-bit plaintext $P = (p_{0}, p_{1}, \dots, p_{b - 1})$ is loaded to a b-bit intermediate value $X = (x_{0}, x_{1}, \dots, x_{b - 1})$ .

(2)

For $i = 1, \dots, b$ , do the following steps.

(a)

X is XORed with a b-bit round key $S K^{1}$ . Consider

\begin{matrix} x_{j} ⟵ x_{j} ⨁ s k_{j}^{1} (j = 0,1, \dots, b - 1) . \end{matrix}

(1)

(b)

Consider $X \leftarrow B P (X)$ , where $B P$ is a bit permutation.

(c)

Consider $X \leftarrow X \oplus R C_{i}$ , where $R C_{i}$ is a round constant.

(d)

For $l = 0, \dots, b / 3 - 1$ , $(x_{3 l}, x_{3 l + 1}, x_{3 l + 2}) \leftarrow K P_{l} ((x_{3 l}, x_{3 l + 1}, x_{3 l + 2}))$ , where $K P_{l}$ is the lth key-dependent permutation based on a $2$ -bit $S K_{l}^{2} = (s k_{l, 0}^{2}, s k_{l, 1}^{2})$ (see Figure 1).

(e)

Consider that X is mixed by using $b / 3$ identical $3 \times 3 S$ -boxes.

(3)

$C = (c_{0}, \dots, c_{b - 1}) \leftarrow X$ .

Figure 1

A single round of PRINTcipher-b.

With a bit permutation $B P$ , a value of the bit position i is moved to the bit position j, where

\begin{matrix} j = {\begin{cases} 3 i \mod (b - 1), & for 0 \leq i \leq b - 2, \\ b - 1, & for i = b - 1 . \end{cases} \end{matrix}

(2)

In a key-dependent permutation $K P$ , an intermediate value X is arranged in $b / 3$ blocks of $3$ bits each, which are permuted individually according to a $2$ -bit $S K_{l}^{2}$ . Out of $6$ possible permutations on $3$ bits, only four permutations are valid for PRINTcipher. In detail, as shown in Table 2, a $3$ -bit input value $(y_{0}, y_{1}, y_{2})$ is permuted to the corresponding output value according to a $2$ -bit $(s k_{l, 0}^{2}, s k_{l, 1}^{2})$ . Here, $K P_{l}^{m n}$ means $K P_{l}$ in the case that $(s k_{l, 0}^{2}, s k_{l, 1}^{2}) = (m, n)$ .

Table 2

Key-dependent permutation $K P_{l}$ .

(a)

Notation			$(s k_{l, 0}^{2}, s k_{l, 1}^{2})$			$K P_{l} (y_{0}, y_{1}, y_{2})$

$K P_{l}^{00}$			$(0,0)$			$(y_{0}, y_{1}, y_{2})$
$K P_{l}^{01}$			$(0,1)$			$(y_{1}, y_{0}, y_{2})$
$K P_{l}^{10}$			$(1,0)$			$(y_{0}, y_{2}, y_{1})$
$K P_{l}^{11}$			$(1,1)$			$(y_{2}, y_{1}, y_{0})$

(b)

x	0	1	2	3	4	5	6	7

$S (x)$	0	1	3	6	7	4	5	2

3. Construction of Related-Key Differential Characteristics on PRINTcipher

In this section, we present how to construct t-round related-key differential characteristics on PRINTcipher-48/96 by using properties of a key-dependent permutation $K P$ and S-box.

3.1. Related-Key Properties on Key-Dependent Permutation and S-Box

We consider a $3$ -bit input value $(y_{0}, y_{1}, y_{2})$ of a key-dependent permutation $K P_{l} (l = 0, \dots, 15)$ . If a $2$ -bit round key $(s k_{l, 0}^{2}, s k_{l, 1}^{2})$ is equal to $(0,0)$ or $(0,1)$ , from Table 2, the corresponding output value is computed as follows:

(i)

$(0,0) : (y_{0}, y_{1}, y_{2}) \overset{K P_{l}^{00}}{\to} (y_{0}, y_{1}, y_{2})$ ;

(ii)

$(0,1) : (y_{0}, y_{1}, y_{2}) \overset{K P_{l}^{01}}{\to} (y_{1}, y_{0}, y_{2})$ .

In the above relations, if $y_{0}$ is equal to $y_{1}$ , each permutation outputs the same value and vice versa. That is, the following equation holds:

\begin{matrix} y_{0} = y_{1} \Leftrightarrow K P_{l}^{00} ((y_{0}, y_{1}, y_{2})) = K P_{l}^{01} ((y_{0}, y_{1}, y_{2})) . \end{matrix}

(3)

In total, we can obtain the following six properties of $K P$ .

Property 1.

Consider $y_{0} = y_{1} \Leftrightarrow K P_{l}^{00} ((y_{0}, y_{1}, y_{2})) = K P_{l}^{01} ((y_{0}, y_{1}, y_{2}))$ .

Property 2.

Consider $y_{1} = y_{2} \Leftrightarrow K P_{l}^{00} ((y_{0}, y_{1}, y_{2})) = K P_{l}^{10} ((y_{0}, y_{1}, y_{2}))$ .

Property 3.

Consider $y_{0} = y_{2} \Leftrightarrow K P_{l}^{00} ((y_{0}, y_{1}, y_{2})) = K P_{l}^{11} ((y_{0}, y_{1}, y_{2}))$ .

Property 4.

Consider $y_{0} = y_{1} = y_{2} \Leftrightarrow K P_{l}^{01} ((y_{0}, y_{1}, y_{2})) = K P_{l}^{10} ((y_{0}, y_{1}, y_{2}))$ .

Property 5.

Consider $y_{0} = y_{1} = y_{2} \Leftrightarrow K P_{l}^{01} ((y_{0}, y_{1}, y_{2})) = K P_{l}^{11} ((y_{0}, y_{1}, y_{2}))$ .

Property 6.

Consider $y_{0} = y_{1} = y_{2} \Leftrightarrow K P_{l}^{10} ((y_{0}, y_{1}, y_{2})) = K P_{l}^{11} ((y_{0}, y_{1}, y_{2}))$ .

Furthermore, from the definition of S-box S, we can obtain the following property.

Property 7.

If $K P_{l}^{00}$ and $K P_{l}^{01}$ have the same input value Y, the output difference of S-box, $S ((K P_{l}^{00} (Y))) \oplus S (K P_{l}^{01} (Y))$ , should be included in a set ${0,2, 4}$ .

3.2. Related-Key Differential Characteristics on PRINTcipher-48

Among the above seven properties, we focus on Properties 1, 2 and 3. To apply these properties on the proposed attack, we first consider the following related-key pairs $(K = (S K^{1}, S K^{2}), K^{*} = (S K^{1 *}, S K^{2 *}))$ . Here, $l = 0, \dots, 15$ .

Case 1 (l).

Consider the following:

(i)

$S K^{1} = S K^{1 *}$ ;

(ii)

$S K_{l}^{2} = (0,0), S K_{l}^{2 *} = (0,1)$ ;

(iii)

$S K_{i}^{2} = S K_{i}^{2 *}$ where $i \neq l$ ,

Case 2 (l).

Consider the following:

(i)

$S K^{1} = S K^{1 *}$ ;

(ii)

$S K_{l}^{2} = (0,0), S K_{l}^{2 *} = (1,0)$ ;

(iii)

$S K_{i}^{2} = S K_{i}^{2 *}$ , where $i \neq l$ .

Case 3 (l).

Consider the following:

(i)

$S K^{1} = S K^{1 *}$ ;

(ii)

$S K_{l}^{2} = (0,0), S K_{l}^{2 *} = (1,1)$ ;

(iii)

$S K_{i}^{2} = S K_{i}^{2 *}$ , where $i \neq l$ .

We assume that the input difference of the target round is zero. If a related-key pair $(K, K^{*})$ satisfies Case 1 (0), $K P_{0}$ has a nonzero related-key difference. Here, from Property 1, it can be easily shown that the output difference of $K P_{0}$ is zero with a probability of $2^{- 1}$ (i.e., the probability that $y_{0}$ is equal to $y_{1}$ ). Since the output differences of other $K P_{l}$ 's except $K P_{0}$ are zero, as shown in Figure 2, we can construct a $1$ -round related-key differential characteristic $0 \overset{Case 1 (0)}{\to} 0$ with a probability of $2^{- 1}$ under Case 1 (0). Since PRINTcipher-48 uses the same round key for all rounds, we can easily extend this result to a t-round related-key differential characteristic. That is, we can construct a t-round related-key differential characteristic $0 \overset{Case 1 (0)}{\to} 0$ with a probability of $2^{- t}$ . The other cases of Case 1 $(l)$ are explained in a similar fashion. Moreover, in Case 2 $(l)$ and Case 3 $(l)$ , we can construct t-round related-key differential characteristics $0 \overset{Case 2 (l)}{\to} 0$ and $0 \overset{Case 3 (l)}{\to} 0$ with a probability of $2^{- t}$ , respectively.

Figure 2

$1$ -round related-key differential characteristic under Case 1 $(0)$ .

Note that we cannot control the exact values of the related-key pair $(K, K^{*})$ under a related-key attack scenario. In other words, we cannot apply the above related-key differential characteristics to our attack directly. To solve this problem, for each $K P_{l}$ , we consider the following four related keys simultaneously. Here, K means the right secret key of PRINTcipher-48.

(i)

Consider $K_{l}^{(0,0)} = [S K^{1}, (S K_{0}^{2}, S K_{1}^{2}, \dots, S K_{l}^{2} \oplus (0,0), \dots, S K_{15}^{2})] = K$ .

(ii)

Consider $K_{l}^{(0,1)} = [S K^{1}, (S K_{0}^{2}, S K_{1}^{2}, \dots, S K_{l}^{2} \oplus (0,1), \dots, S K_{15}^{2})]$ .

(iii)

Consider $K_{l}^{(1,0)} = [S K^{1}, (S K_{0}^{2}, S K_{1}^{2}, \dots, S K_{l}^{2} \oplus (1,0), \dots, S K_{15}^{2})]$ .

(iv)

Consider $K_{l}^{(1,1)} = [S K^{1}, (S K_{0}^{2}, S K_{1}^{2}, \dots, S K_{l}^{2} \oplus (1,1), \dots, S K_{15}^{2})]$ .

From these four related keys, we can combine six related-key pairs. For each value of $S K_{l}^{2}$ , a related-key pair is satisfied one among three cases, Case 1 $(l)$ , Case 2 $(l)$ , and Case 3 $(l)$ (see Table 3). For example, we assume that $S K_{l}^{2}$ is equal to $(1,0)$ . Then, four related keys are computed as follows.

(i)

Consider $K_{l}^{(0,0)} = [S K^{1}, (S K_{0}^{2}, S K_{1}^{2}, \dots, ((1,0) \oplus (0,0) = (1,0)), \dots, S K_{15}^{2})]$ .

(ii)

Consider $K_{l}^{(0,1)} = [S K^{1}, (S K_{0}^{2}, S K_{1}^{2}, \dots, ((1,0) \oplus (0,1) = (1,1)), \dots, S K_{15}^{2})]$ .

(iii)

Consider $K_{l}^{(1,0)} = [S K^{1}, (S K_{0}^{2}, S K_{1}^{2}, \dots, ((1,0) \oplus (1,0) = (0,0)), \dots, S K_{15}^{2})]$ .

(iv)

Consider $K_{l}^{(1,1)} = [S K^{1}, (S K_{0}^{2}, S K_{1}^{2}, \dots, ((1,0) \oplus (1,1) = (0,1)), \dots, S K_{15}^{2})]$ .

Recall that the condition of Case 1 $(l)$ is that $S K_{l}^{2} = (0,0)$ and $S K_{l}^{2 *} = (0,1)$ . Thus, $(K_{l}^{(1,0)}, K_{l}^{(1,1)})$ satisfies this condition. Similarly, the condition of Case 2 $(l)$ is that $S K_{l}^{2} = (0,0)$ and $S K_{l}^{2 *} = (1,0)$ . Thus, $(K_{l}^{(1,0)}, K_{l}^{(0,0)})$ satisfies this condition.

Table 3

The corresponding related-key pair according to the value of $S K_{l}^{2}$ .

$S K_{l}^{2}$	Case 1 (l)	Case 2 (l)	Case 3 (l)
$(0,0)$	$(K_{l}^{(0,0)}, K_{l}^{(0,1)})$	$(K_{l}^{(0,0)}, K_{l}^{(1,0)})$	$(K_{l}^{(0,0)}, K_{l}^{(1,1)})$
$(0,1)$	$(K_{l}^{(0,1)}, K_{l}^{(0,0)})$	$(K_{l}^{(0,1)}, K_{l}^{(1,1)})$	$(K_{l}^{(0,1)}, K_{l}^{(1,0)})$
$(1,0)$	$(K_{l}^{(1,0)}, K_{l}^{(1,1)})$	$(K_{l}^{(1,0)}, K_{l}^{(0,0)})$	$(K_{l}^{(1,0)}, K_{l}^{(0,1)})$
$(1,1)$	$(K_{l}^{(1,1)}, K_{l}^{(1,0)})$	$(K_{l}^{(1,1)}, K_{l}^{(0,1)})$	$(K_{l}^{(1,1)}, K_{l}^{(0,0)})$

If $S K_{l}^{2}$ is equal to $(0,0)$ , three related-key pairs $(K_{l}^{(0,0)}, K_{l}^{(0,1)})$ , $(K_{l}^{(0,0)}, K_{l}^{(1,0)})$ , and $(K_{l}^{(0,0)}, K_{l}^{(1,1)})$ satisfy Case 1 $(l)$ , Case 2 $(l)$ , and Case 3 $(l)$ , respectively (see Table 3). It means that t-round related-key differential characteristics $0 \overset{Case 1 (l)}{\to} 0$ , $0 \overset{Case 2 (l)}{\to} 0$ , and $0 \overset{Case 3 (l)}{\to} 0$ are satisfied with a probability of $2^{- t}$ , respectively. However, if $S K_{l}^{2}$ is not equal to $(0,0)$ , only one of related-key pairs satisfies the corresponding condition. For example, it is assumed that the right $S K_{l}^{2}$ is $(1,0)$ . Only one key pair, $(K_{l}^{(0,0)}, K_{l}^{(1,0)})$ , among three related-key pairs is satisfied Case 2 $(l)$ from Table 3. It means that the corresponding differential characteristic $0 \overset{Case 2 (l)}{\to} 0$ is satisfied with a probability of $2^{- t}$ and that the other differential characteristics $0 \overset{Case 1 (l)}{\to} 0$ and $0 \overset{Case 3 (l)}{\to} 0$ are satisfied with a random probability $(= 2^{- 2 t})$ , respectively.

3.3. Related-Key Differential Characteristics on PRINTcipher-96

In the case of PRINTcipher-96, we can construct $96 (= 3 \cdot 32) t$ -round related-key differential characteristics with a probability $2^{- t}$ by using the similar method on PRINTcipher-48. In detail, for each $K P_{l}$ , we can obtain the same six properties and three cases, Case 1 $(l)$ , Case 2 $(l)$ , and Case 3 $(l)$ . Thus, we get three t-round related-key differential characteristics for each $K P_{l} (l = 0, \dots, 31)$ .

4. Related-Key Cryptanalysis on PRINTcipher-48

We are ready to propose related-key cryptanalysis on PRINTcipher-48. Recall that we can construct t-round related-key differential characteristics on PRINTcipher- $48$ with a probability of $2^{- t}$ . These related-key differential characteristics depend on the concrete key value. However, the attacker did not control the exact key value under a related-key attack scenario.

To solve this, we use 4 related keys $K_{0}^{(0,0)}$ , $K_{0}^{(0,1)}$ , $K_{0}^{(1,0)}$ , and $K_{0}^{(1,1)}$ . In detail, two key pairs $(K_{0}^{(0,0)}, K_{0}^{(0,1)})$ and $(K_{0}^{(1,0)}, K_{0}^{(1,1)})$ are considered. Then, among two key pairs, only one should satisfy Case 1 $(0)$ . Thus we first apply the related-key pair $(K_{0}^{(0,0)}, K_{0}^{(0,1)})$ to our attack. After that, we repeat the same procedure using the other related-key pair $(K_{0}^{(1,0)}, K_{0}^{(1,1)})$ . For the convenience of description, we assume that the key pair $(K_{0}^{(0,0)}, K_{0}^{(0,1)})$ satisfies Case 1 $(0)$ .

4.1. Basic Related-Key Attack on PRINTcipher-48

To attack the full PRINTcipher- $48$ , we consider $44$ -round related-key differential characteristic $0 \overset{Case 1 (0)}{\to} 0$ (from round $2$ to round $45$ ) with a probability of $2^{- 44}$ .

Our attack procedure mainly consists of the following steps. First, we consider plaintext structures which are composed of $4$ plaintexts each. Second, we discard the wrong ciphertext pairs from the difference between ciphertexts. Finally, we guess the partial secret key and determine related-key pairs satisfying Case 1 $(0)$ .

4.1.1. Collection of Ciphertexts

First, we consider the following plaintext structures $𝒮^{x_{0}, x_{1}}$ which are composed of $4$ plaintexts each (see Figure 3).

(i)

Consider $𝒮^{x_{0}, x_{1}} = {s_{i, j}^{x_{0}, x_{1}}}$ , where

(a)

$s_{i, j}^{x_{0}, x_{1}} = (i ∥ x_{0} ∥ j ∥ x_{1})$ ;

(b)

$i, j \in {0,1}$ ;

(c)

$x_{0}$ : arbitrary $15$ -bit value;

(d)

$x_{1}$ : arbitrary 31-bit value.

Figure 3

Basic related-key differential attack on PRINTcipher- $48$ .

Among all possible sixteen plaintext pairs for each plaintext structure, we consider only the following $8$ plaintext pairs:

\begin{matrix} (s_{0,0}^{x_{0}, x_{1}}, s_{0,0}^{x_{0}, x_{1}}), (s_{0,1}^{x_{0}, x_{1}}, s_{0,1}^{x_{0}, x_{1}}), \\ (s_{1,0}^{x_{0}, x_{1}}, s_{1,0}^{x_{0}, x_{1}}), (s_{1,1}^{x_{0}, x_{1}}, s_{1,1}^{x_{0}, x_{1}}), \\ (s_{0,0}^{x_{0}, x_{1}}, s_{1,1}^{x_{0}, x_{1}}), (s_{0,1}^{x_{0}, x_{1}}, s_{1,0}^{x_{0}, x_{1}}), \\ (s_{1,0}^{x_{0}, x_{1}}, s_{0,1}^{x_{0}, x_{1}}), (s_{1,1}^{x_{0}, x_{1}}, s_{0,0}^{x_{0}, x_{1}}) . \end{matrix}

(4)

Recall that $(K_{0}^{(0,0)}, K_{0}^{(0,1)})$ is assumed to satisfy Case 1 $(0)$ . Thus, for only four plaintext pairs in each plaintext structure, the input difference of round $2$ is zero. Here, when we use $2^{44}$ plaintext structures, the expected number of right pairs is $4 (= 4 \cdot 2^{44} \cdot 2^{- 44})$ . Note that our related-key differential characteristics hold with a probability of $2^{- 44}$ .

4.1.2. Filtering the Wrong Pairs

We discard the wrong ciphertext pairs by checking the difference between ciphertexts. For the right ciphertext pair, the output difference of round $45$ should be zero as shown in Figure 3.

In round $46$ , from Property 7, the possible output difference of the first S-box is $0$ or $2$ or $4$ . The differential propagation in round 47~48 is shown in Figure 3. Then, we discard the wrong ciphertext pairs by checking the following three checkPoints.

(i)

${C h e c k P o i n t}_{1}$ . The difference between the rightmost $30$ bits of ciphertext is zero.

(ii)

${C h e c k P o i n t}_{2}$ . The output difference of $K P_{1}, K P_{2}, \dots, K P_{5}$ in round $48$ should be included in a set ${0,1, 2,4}$ .

(iii)

${C h e c k P o i n t}_{3}$ . The input difference of $K P_{0}$ should be included in a set ${0,4}$ .

Since the filtering probability of this step is $2^{- 37} (= 2^{- 30} \cdot 2^{- 1 \cdot 5} \cdot 2^{- 2})$ , $2^{10} (= 8 \cdot 2^{44} \cdot 2^{- 37})$ ciphertext pairs are survived.

4.1.3. Recovery of the Secret Key of PRINTcipher-48

For each ciphertext pair passing the above steps, we guess the following $16$ -bit key:

\begin{matrix} (S K_{1}^{2}, S K_{2}^{2}, S K_{3}^{2}, S K_{4}^{2}, S K_{5}^{2}, s k_{0}^{1}, s k_{1}^{1}, s k_{2}^{1}, s k_{3}^{1}, s k_{4}^{1}, s k_{5}^{1}) . \end{matrix}

(5)

Then we recover $16$ -bit key by checking the following checkPoints (see Figure 3).

(i)

${C h e c k P o i n t}_{4}$ . Input differences of $K P_{1}, K P_{2}, K P_{3}, K P_{4}$ , and $K P_{5}$ in round 48 should be $0$ or $4$ .

(ii)

${C h e c k P o i n t}_{5}$ . Input differences of $K P_{0}$ and $K P_{1}$ in round 47 should be $0$ or $4$ .

(iii)

${C h e c k P o i n t}_{6}$ . Output difference of the first S-box in round 46 should be $0$ or $2$ or $4$ .

First, we check ${C h e c k P o i n t}_{4}$ . In this step, we guess a $10$ -bit key $(S K_{1}^{2}, S K_{2}^{2}$ , $S K_{3}^{2}, S K_{4}^{2}, S K_{5}^{2})$ . Since the filtering probability of this step is $2^{- 5}$ , $2^{5} (= 2^{10} \cdot 2^{- 5})$ ciphertext pairs remained for each guessed key. Then, we guess an additional $6$ -bit key $(s k_{0}^{1}, s k_{1}^{1}, s k_{2}^{1}, s k_{3}^{1}, s k_{4}^{1}, s k_{5}^{1})$ and check ${C h e c k P o i n t}_{5}$ and ${C h e c k P o i n t}_{6}$ . Since the filtering probabilities of this step are $2^{- 4} {(C h e c k P o i n t}_{5})$ and $0.75 ({C h e c k P o i n t}_{6})$ , the expected number of the remaining ciphertext pairs is $1.5$ for each guessed key. Finally, we determine the guessed key with the maximal number of remaining ciphertext pairs as the right key.

Until now, we introduced the attack procedure with a related-key pair $(K_{0}^{(0,0)}$ , $K_{0}^{(0,1)})$ . In case of the related-key pair $(K_{0}^{(1,0)}, K_{0}^{(1,1)})$ , the attack procedure can be explained in a similar fashion. Our attack procedure on the full PRINTcipher-48 is summarized as follows.

(1)

Select $2^{44}$ plaintext structures which are composed of $4$ plaintexts each and obtain the corresponding ciphertexts under four related keys $K_{0}^{(0,0)}$ , $K_{0}^{(0,1)}$ , $K_{0}^{(1,0)}$ , and $K_{0}^{(1,1)}$ , respectively.

(2)

Considering the related-key pair $(K_{0}^{(0,0)}, K_{0}^{(0,1)})$ , we have the following.

(a)

Discard wrong pairs which do not satisfy ${C h e c k P o i n t}_{1}$ , ${C h e c k P o i n t}_{2}$ , and ${C h e c k P o i n t}_{3}$ .

(b)

Guess 16-bit key $(S K_{1}^{2}, S K_{2}^{2}, S K_{3}^{2}, S K_{4}^{2}, S K_{5}^{2}, s k_{0}^{1}, s k_{1}^{1}, s k_{2}^{1}, s k_{3}^{1}, s k_{4}^{1}, s k_{5}^{1})$ and count the ciphertext pairs satisfying ${C h e c k P o i n t}_{4}$ , ${C h e c k P o i n t}_{5}$ , and ${C h e c k P o i n t}_{6}$ .

(3)

Considering the related-key pair $(K_{0}^{(1,0)}, K_{0}^{(1,1)})$ , we have the following.

(a)

Discard wrong pairs which do not satisfy ${C h e c k P o i n t}_{1}$ , ${C h e c k P o i n t}_{2}$ , and ${C h e c k P o i n t}_{3}$ .

(b)

(4)

Output the guessed key with the maximal count as the right key.

(5)

Do an exhaustive search for the remaining secret key by using trial encryption.

4.2. Complexities of Basic Related-Key Attack on PRINTcipher-48

This attack considers 4 related keys $(K_{0}^{(0,0)}, K_{0}^{(0,1)}, K_{0}^{(1,0)}, and K_{0}^{(0,0)})$ . And $2^{46}$ plaintexts are used for each related-key. Hence, a data complexity of our attack is $2^{48}$ related-key chosen plaintexts.

A computational complexity of Step 1 is $2^{48}$ PRINTcipher- $48$ encryptions. In Step 2(a) and Step 3(a), $2^{10} (= 8 \cdot 2^{44} \cdot 2^{- 37})$ ciphertext pairs are survived. Thus computational complexities of Step 2(b) and Step 3(b) do not exceed $2^{26}$ PRINTcipher- $48$ encryptions, respectively. From Step 2 and Step 3, we can recover the $17$ -bit information on the $80$ -bit secret key of PRINTcipher- $48$ . Thus, a computational complexity of Step 5 is $2^{63}$ PRINTcipher- $48$ encryptions. Hence, a total computational complexity of our attack is $2^{63}$ .

4.3. Improved Related-Key Attack on PRINTcipher-48

In this subsection, we improve the basic related-key attack on the full PRINTcipher-48. To improve the basic attack, we consider $43$ -round related-key differential characteristic $0 \overset{Case 1 (0)}{\to} 0$ (from round $2$ to round $44$ ) with a probability of $2^{- 43}$ . The overall attack procedure is similar to the basic attack procedure.

(1)

Select $2^{43}$ plaintext structures which are composed of $4$ plaintexts each and obtain the corresponding ciphertexts under four related keys $K_{0}^{(0,0)}$ , $K_{0}^{(0,1)}$ , $K_{0}^{(1,0)}$ , and $K_{0}^{(1,1)}$ , respectively.

(2)

Considering the related-key pair $(K_{0}^{(0,0)}, K_{0}^{(0,1)})$ , we have the following.

(a)

Discard wrong pairs which do not satisfy ${C h e c k P o i n t}_{7}$ , ${C h e c k P o i n t}_{8}$ , and ${C h e c k P o i n t}_{9}$ .

(b)

Guess $30$ -bit key $(S K_{1}^{2}, \dots, S K_{15}^{2})$ and remain the ciphertext pairs satisfying ${C h e c k P o i n t}_{10}$ and ${C h e c k P o i n t}_{11}$ .

(c)

Guess $18$ -bit key $(s k_{0}^{1}, \dots, s k_{17}^{1})$ and count the ciphertext pairs satisfying ${C h e c k P o i n t}_{12}$ , ${C h e c k P o i n t}_{13}$ , and ${C h e c k P o i n t}_{14}$ .

(3)

Considering the related-key pair $(K_{0}^{(1,0)}, K_{0}^{(1,1)})$ , we have the following.

(a)

Discard wrong pairs which do not satisfy ${C h e c k P o i n t}_{7}, {C h e c k P o i n t}_{8}$ and ${C h e c k P o i n t}_{9}$ .

(b)

Guess $30$ -bit key $(S K_{1}^{2}, \dots, S K_{15}^{2})$ and remain the ciphertext pairs satisfying ${C h e c k P o i n t}_{10}$ and ${C h e c k P o i n t}_{11}$ .

(c)

Guess $18$ -bit key $(s k_{0}^{1}, \dots, s k_{17}^{1})$ and count the ciphertext pairs satisfying ${C h e c k P o i n t}_{12}$ , ${C h e c k P o i n t}_{13}$ and ${C h e c k P o i n t}_{14}$ .

(4)

Output the guessed key with the maximal count as the right key.

(5)

Do an exhaustive search for the remaining secret key using trial encryption.

4.4. Complexities of Improved Related-Key Attack on PRINTcipher-48

The improved attack uses 4 related keys $(K_{l}^{(0,0)}, K_{l}^{(0,1)}, K_{l}^{(1,0)}, and K_{l}^{(0,0)})$ and $2^{47}$ related-key chosen plaintexts. Hence, a data complexity of our attack is $2^{47}$ related-key chosen plaintexts.

A computational complexity of Step 1 is $2^{47}$ PRINTcipher- $48$ encryptions.

In Step 2(a) and Step 3(a), similar to the basic attack, we discard wrong ciphertext pairs by checking the following three checkPoints (see Figure 4).

(i)

${C h e c k P o i n t}_{7}$ . The output difference of $K P_{2}, K P_{3}, \dots, K P_{15}$ in round $48$ should be included in a set ${0,1, 2,4}$ .

(ii)

${C h e c k P o i n t}_{8}$ . The input difference of $K P_{0}$ in round $48$ should be included in a set ${0,2, 4,6}$ .

(iii)

${C h e c k P o i n t}_{9}$ . The output difference of $K P_{1}$ in round $48$ should be included in a set ${0,1, 2,3, 4,5, 6}$ .

Figure 4

Improved related-key differential attack on PRINTcipher- $48$ .

The filtering probability of this step is computed as follows:

\begin{matrix} \frac{7}{2^{18}} (= 2^{- 1 \cdot 14} \cdot 2^{- 1} \cdot \frac{7}{8}) . \end{matrix}

(6)

Thus, $7 \cdot 2^{28} (= 8 \cdot 2^{43} \cdot 7 / 2^{18})$ ciphertext pairs remained on average. So, computational complexities of Step 2(b) and 3(b) are computed as follows:

\begin{matrix} 2^{55.22} (\approx 7 \cdot 2^{28} \cdot 2^{30} \cdot \frac{1}{48}) . \end{matrix}

(7)

For each remaining ciphertext pair, we guess total $48$ -bit key $(S K_{1}^{2}, \dots, S K_{15}^{2}, s k_{0}^{1}, \dots, s k_{17}^{1})$ . Then we recover $16$ -bit key by checking the following checkPoints.

(i)

${C h e c k P o i n t}_{10}$ . Input difference of $K P_{2}, K P_{3}, \dots, K P_{15}$ in round 48 should be included in a set ${0,4}$ .

(ii)

${C h e c k P o i n t}_{11}$ . Input difference of $K P_{1}$ in round 48 should be included in a set ${0,2, 4,6}$ .

(iii)

${C h e c k P o i n t}_{12}$ . Input difference of $K P_{0}, \dots, K P_{5}$ in round 47 should be included in a set ${0,4}$ .

(iv)

${C h e c k P o i n t}_{13}$ . Input difference of $K P_{0}$ and $K P_{1}$ in round 46 should be included in a set ${0,4}$ .

(v)

${C h e c k P o i n t}_{14}$ . Output difference of the first S-box in round 45 should be included in a set ${0,2, 4}$ .

In Step 2(b) and Step 3(b), we guess $30$ -bit key $(S K_{1}^{2}, \dots, S K_{15}^{2}$ and check ${C h e c k P o i n t}_{10}$ and ${C h e c k P o i n t}_{11}$ . The filtering probability of this step is computed as follows:

\begin{matrix} \frac{6}{7 \cdot 2^{14}} (= 2^{- 1 \cdot 14} \cdot \frac{6}{7}) . \end{matrix}

(8)

Thus, $3 \cdot 2^{15} (= 7 \cdot 2^{28} \cdot 6 / (7 \cdot 2^{14}))$ ciphertext pairs remained for each guessed key. Since $3 \cdot 2^{15}$ ciphertext pairs remained in Step 2(b) and Step 3(b) for each guessed key, computational complexities of Step 2(c) and Step 3(c) are $3 \cdot 2^{59} (= 3^{15} \cdot 2^{48} \cdot 3 / 48)$ PRINTcipher- $48$ encryptions.

In Step 2(c) and Step 3(c), we guess $15$ -bit key $(s k_{0}^{1}, \dots, s k_{14}^{1})$ in order to check ${C h e c k P o i n t}_{12}$ , ${C h e c k P o i n t}_{13}$ , and ${C h e c k P o i n t}_{14}$ . Similar to the basic attack, the expected number of the remaining ciphertext pairs is $1.5$ for each guessed key. Note that the expected number of right pairs is $4$ similar to the basic attack.

Since we can recover the $49$ -bit information on the $80$ -bit secret key of PRINTcipher- $48$ , a computational complexity of Step 5 is $2^{31}$ PRINTcipher- $48$ encryptions. Hence, a total computational complexity of our attack is computed as follows:

\begin{matrix} 2^{60.62} (\approx 2^{47} + 2^{55.22} + (3 \cdot 2^{59}) + 2^{31}) . \end{matrix}

(9)

5. Related-Key Cryptanalysis on PRINTcipher-96

The overall attack procedure on the full PRINTcipher-96 is similar to that on the full PRINTcipher-48. Thus, we explain the attack procedure on the full PRINTcipher-96 briefly. In this attack, we consider $91$ -round related-key differential characteristics $0 \overset{Case 1 (0)}{\to} 0$ (from round $2$ to round $92$ ) with a probability of $2^{- 91}$ . The checkPoints used in this attack are as follows (see Figure 5).

(i)

${C h e c k P o i n t}_{15}$ . The rightmost $40$ -bit of ciphertext does not have difference.

(ii)

${C h e c k P o i n t}_{16}$ . The output difference of $K P_{1}, K P_{2}, \dots, K P_{17}$ in round $48$ is included in a set ${0,1, 2,4}$ .

(iii)

${C h e c k P o i n t}_{17}$ . The input difference of $K P_{0}$ is included in a set ${0,4}$ .

(iv)

${C h e c k P o i n t}_{18}$ . Input difference of $K P_{1}, K P_{2}, \dots, K P_{17}$ in round 96 should be included in a set ${0,4}$ .

(v)

${C h e c k P o i n t}_{19}$ . Input difference of $K P_{0}, \dots, K P_{5}$ in round 95 should be included in a set ${0,4}$ .

(vi)

${C h e c k P o i n t}_{20}$ . Input difference of $K P_{0}$ and $K P_{1}$ in round 94 should be included in a set ${0,4}$ .

(vii)

${C h e c k P o i n t}_{21}$ . Output difference of the first S-box in round 93 should be included in a set ${0,2, 4}$ .

Figure 5

Related-key differential attack on PRINTcipher- $96$ .

The attack procedure on the PRINTcipher- $96$ is summarized as follows.

(1)

Select $2^{91}$ plaintext structures which are composed of $4$ plaintexts each and obtain the corresponding ciphertexts under four related keys $K_{0}^{(0,0)}$ , $K_{0}^{(0,1)}$ , $K_{0}^{(1,0)}$ , and $K_{0}^{(1,1)}$ , respectively.

(2)

Considering the related-key pair $(K_{0}^{(0,0)}, K_{0}^{(0,1)})$ , we have the following.

(a)

Discard wrong pairs which do not satisfy ${C h e c k P o i n t}_{15}, {C h e c k P o i n t}_{16}$ , and ${C h e c k P o i n t}_{17}$ .

(b)

Guess $34$ -bit key $(S K_{1}^{2}, \dots, S K_{17}^{2})$ and remain the ciphertext pairs satisfying ${C h e c k P o i n t}_{18}$ .

(c)

Guess $18$ -bit key $(s k_{0}^{1}, \dots, s k_{17}^{1})$ and count the ciphertext pairs satisfying ${C h e c k P o i n t}_{19}, {C h e c k P o i n t}_{20}$ and ${C h e c k P o i n t}_{21}$ .

(3)

Considering the related-key pair $(K_{0}^{(1,0)}, K_{0}^{(1,1)})$ , we have the following.

(a)

Discard wrong pairs which do not satisfy ${C h e c k P o i n t}_{15}$ , ${C h e c k P o i n t}_{16}$ , and ${C h e c k P o i n t}_{17}$ .

(b)

Guess $34$ -bit key $(S K_{1}^{2}, \dots, S K_{17}^{2})$ and remain the ciphertext pairs satisfying ${C h e c k P o i n t}_{18}$ .

(c)

Guess $18$ -bit key $(s k_{0}^{1}, \dots, s k_{17}^{1})$ and count the ciphertext pairs satisfying ${C h e c k P o i n t}_{19}, {C h e c k P o i n t}_{20}$ , and ${C h e c k P o i n t}_{21}$ .

(4)

Output the guessed key with the maximal count as the right key.

(5)

Do an exhaustive search for the remaining secret key using trial encryption.

Since 4 related keys $(K_{0}^{(0,0)}, K_{0}^{(0,1)}, K_{0}^{(1,0)}, and K_{0}^{(0,0)})$ are used in our attack, the data complexity of our attack is $2^{95}$ related-key chosen plaintexts. And a total computational complexity of our attack is about $2^{107}$ PRINTcipher- $96$ encryptions.

6. Conclusion

In this paper, we proposed related-key cryptanalysis of PRINTcipher. Our attack results are summarized in Table 1. To recover the $80$ -bit secret key of PRINTcipher-48, our attack required $2^{47}$ related-key chosen plaintexts with a computational complexity of $2^{60.62}$ . In the case of PRINTcipher-96, $2^{95}$ related-key chosen plaintexts with a computational complexity of $2^{107}$ are required. These results are the first known related-key cryptanalytic results on them.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This research was supported by the MSIP (Ministry of Science, ICT & Future Planning), Korea, under the C-ITRC (Convergence Information Technology Research Center) Support Program (NIPA-2013-H0301-13-3007).

References

Grover

Berghel

A survey of RFID deployment and security issues

Journal of Information Processing Systems 2011 7 4 561 580

Seo

Lee

A study on RFID system with secure service availability for ubiquitous computing

Journal of Information Processing Systems 2005 1 1 96 101

10.3745/JIPS.2005.1.1.096

Bogdanov

Knudsen

L. R.

Leander

Paar

Poschmann

Robshaw

M. J. B.

Seurin

Vikkelsoe

PRESENT: an ultra-lightweight block cipher

Cryptographic Hardware and Embedded Systems—CHES 2007 2007 4727

Berlin, Germany

Springer

450 466 Lecture Notes in Computer Science

2-s2.0-37149045263

Guo

Peyrin

Poschmann

Robshaw

The LED block cipher

Cryptographic Hardware and Embedded Systems—CHES 2011 2011 6917

Berlin, Germany

Springer

326 341 Lecture Notes in Computer Science

2-s2.0-80053476418

10.1007/978-3-642-23951-9_22

Hong

Sung

Hong

Lim

Lee

Koo

B.-S.

Lee

Chang

Lee

Jeong

Kim

Chee

HIGHT: a new block cipher suitable for low-resource device

Cryptographic Hardware and Embedded Systems—CHES 2006 2006 4249

Berlin, Germany

Springer

46 59 Lecture Notes in Computer Science

2-s2.0-33750699594

Knudsen

Leander

Poschmann

Robshaw

M. J. B.

PRINTcipher: a block cipher for IC-printing

Cryptographic Hardware and Embedded Systems, CHES 2010 2010 6225

Berlin, Germany

Springer

16 32 Lecture Notes in Computer Science

2-s2.0-78049340840

10.1007/978-3-642-15031-9_2

Shibutani

Isobe

Hiwatari

Mitsuda

Akishita

Shirai

Piccolo: an ultra-lightweight blockcipher

Cryptographic Hardware and Embedded Systems—CHES 2011 2011 6917

Berlin, Germany

Springer

342 357 Lecture Notes in Computer Science

2-s2.0-80053524244

10.1007/978-3-642-23951-9_23

Leander

Abdelraheem

M. A.

Alkhzaimi

Zenner

A cryptanalysis of PRINTcipher: the invariant subspace attack

Advances in Cryptology—CRYPTO 2011 2011 6841

Berlin, Germany

Springer

206 221 Lecture Notes in Computer Science

2-s2.0-80052002674

10.1007/978-3-642-22792-9_12

Abdelraheem

M. A.

Leander

Zenner

Differential cryptanalysis of round-reduced PRINTcipher: computing roots of permutations

Fast Software Encryption 2011 6733

Berlin, Germany

Springer

1 17 Lecture Notes in Computer Science

2-s2.0-79959960154

10.1007/978-3-642-21702-9_1

10.

Ågren

Johansson

Linear cryptanalysis of PRINTcipher—trails and samples everywhere

Progress in Cryptology—INDOCRYPT 2011 2011 7107

Berlin, Germany

Springer

114 133 Lecture Notes in Computer Science

2-s2.0-83755161555

10.1007/978-3-642-25578-6_10

11.

Karakoç

Demirci

Harmancı

A. E.

Combined differential and linear cryptanalysis of reduced-round PRINTcipher

Selected Areas in Cryptography 2012 7118

Berlin, Germany

Springer

169 184 Lecture Notes in Computer Science

2-s2.0-84857738219

10.1007/978-3-642-28496-0_10

Related-Key Cryptanalysis on the Full PRINTcipher Suitable for IC-Printing

Abstract

1. Introduction

2. Description of PRINTcipher

3. Construction of Related-Key Differential Characteristics on PRINTcipher

3.1. Related-Key Properties on Key-Dependent Permutation and S-Box

Property 1.

Property 2.

Property 3.

Property 4.

Property 5.

Property 6.

Property 7.

3.2. Related-Key Differential Characteristics on PRINTcipher-48

Case 1 (l).

Case 2 (l).

Case 3 (l).

3.3. Related-Key Differential Characteristics on PRINTcipher-96

4. Related-Key Cryptanalysis on PRINTcipher-48

4.1. Basic Related-Key Attack on PRINTcipher-48

4.1.1. Collection of Ciphertexts

4.1.2. Filtering the Wrong Pairs

4.1.3. Recovery of the Secret Key of PRINTcipher-48

4.2. Complexities of Basic Related-Key Attack on PRINTcipher-48

4.3. Improved Related-Key Attack on PRINTcipher-48

4.4. Complexities of Improved Related-Key Attack on PRINTcipher-48

5. Related-Key Cryptanalysis on PRINTcipher-96

6. Conclusion

Footnotes

Conflict of Interests

Acknowledgment

References