Security research with Square attack to a variant Camellia cipher

Abstract

This paper investigates the relation between the choice of S-boxes and Square attack. A variant Camellia, which uses only a single S-box instead of four, is proposed. The security of the variant Camellia against Square attack is studied in detail. Result shows that it needs only 28 chosen plaintexts to recover a byte of the 6th round-key of variant Camellias, while the original Camellia needs either 28 chosen plaintexts to recover a byte of the 6th round-key and a byte of some constant or 216 chosen plaintexts to recover a byte of the 6th round-key. Furthermore, Square attacks on other round-reduced variant Camellia are proposed, and the time complexity of 11-round attack is reduced from 2²⁵⁰ to 2^225.5. The weaker variant Camellia indicates that the choice of S-box and the order of different S-boxes have influence on Square attack.

Keywords

block cipher / Camellia / Square attack

Introduction

Square attack, proposed by Ref. [1], considers the propagation of sums of (many) ciphertexts with special inputs. It was first applied to the Square cipher that is of substitution permutation network structured (SPN-structured). Reference [2] first applied Square attack, employing a different term “saturation attack” to Feistel cipher. The so-called multiset attack, proposed by Ref. [3], is another name of Square attack. In fact, all of these attacks belong to the integral cryptanalysis [4], proposed by Knudsen et al., at FSE 2002.

Integrals exploit the simultaneous relationship between many encryptions, in contrast to differential cryptanalysis where only pairs of encryptions are considered. This feature makes it especially well-suited in analyzing ciphers with primarily bijective components that are not vulnerable to differential and linear cryptanalysis. This feature also makes integral an increasingly popular tool in the recent cryptanalysis works. At FSE 2008, Ref. [5] proposed the bit-pattern-based integral attack that can be seen as a complement of the traditional integral attack proposed in Ref. [4], since the traditional ones can only be applied to byte (word)-oriented ciphers, while the bit-pattern based ones can only be applied to bit-oriented ciphers.

Camellia [6] is a 128-bit block cipher proposed by NTT and Mitsubishi in 2000 and supports 128/192/256-bit keys. The design of Camellia is based on the Feistel structure with an SPN-structured round function, and the number of rounds is 18 for 128-bit key version and 24 for 192/256-bit key version. An FL/FL^-1 function layer is inserted in every six rounds in order to thwart future unknown attacks. Before the first round and after the last round, there are pre- and post-whitening layers, respectively. Camellia had been submitted to the standardization and the evaluation projects, such as ISO/IEC JTC 1/SC 27, CRYPTREC, and NESSIE. It is one of the winners of the NESSIE project.

Since its publication, Camellia has been widely analyzed. In Ref. [7], the security against truncated differential cryptanalysis is studied, and it has been proved that 11 rounds are enough to make Camellia resilient to the byte-character-based truncated differential attacks. In Ref. [8], empowered by computer aids, security against higher order differential attack was studied. He and Qing found that 6-round Camellia is breakable by Square attack [9]. Reference [10] improved the known result about Square attack. Later, Ref. [11] adopted the equivalent structure of Feistel cipher that improved the known results of Square attack on Camellia. Reference [12] gave an efficient collision attack on Camellia, and later in Ref. [13], some nontrivial 8-round impossible differential was given; based on which, Ref. [14] gave an effective attack on Camellia with up to 14 rounds.

To date, there are many ciphers that adopt multi-S-boxes instead of single S-box, and Camellia is one of them. Another example that adopts multi-S-boxes is ARIA [15], which is a 128-bit block cipher designed by a group of Korean experts in 2003. ARIA is an SPN cipher. To make the encryption and decryption alike, the designers of ARIA adopted two S-boxes, which are denoted by S₁ and S₂, as well as their inversions S_{\mathrm{1}}^{-\mathrm{1}} and S_{\mathrm{2}}^{-\mathrm{1}} to make the cipher involutional.

Although many ciphers adopt multi-S-boxes, however, how the multi-S-boxes influence the security of ciphers remains undiscovered. Reference [7] investigated truncated differentials and found that for byte-character-based truncated differentials, the multi-S-boxes case can decrease the truncated differential probabilities, thus making the cipher stronger against truncated differential attack. Reference [16] investigated the security of ARIA against integral attack and suggested that if the cipher adopts only single S-box or different order of the multi-S-boxes, security margins are different. The basic technique of Ref. [16] is a counting method: if different values of a set appear even times, the sum of all element of the correspondence set is zero; in other words, the set is balanced.

This paper focuses on how multi-S-boxes and their order will influence the security of Camellia against Square attack. Our results show that if Camellia adopts single S-box, the security margin will be decreased to design a cipher using multi-S-boxes, the order of these S-boxes should be chosen carefully; otherwise, the security of the ciphers with different orders against Square attack might be compromised.

The rest of this paper is organized as follows: Section 2 briefly describes the Camellia cipher, its variant (Camellia*), and the basis of Square attack. Section 3 focuses on finding Square distinguisher of Camellia*. In Sect. 4, Square attacks on some round-reduced Camellia* are presented. Finally, Sect. 5 concludes the paper.

Preliminaries

Description of Camellia

Camellia is an iterative block cipher with Feistel structure. Let the ith round input and output be (L_i-1, R_i-1) and (L_i, R_i), then

\{\begin{array}{l}{L}_i=F(k_i\oplus L_{i-\mathrm{1}})\oplus R_{i-\mathrm{1}},\hfill \\ R_i=L_{i-\mathrm{1}},\hfill \end{array}

where F is the round function, and k_i is the round key, which is generated from a master key through the key schedule.

An FL/FL^-1 function is inserted every six rounds in order to thwart future unknown attack, and the FL function is defined as follows:

where \cap is the bit-wise and operation, while \cup is the bit-wise or operation.

The round function F function contains three transformations, namely, key-addition, S-function, and P-function. S-function contains four types of nonlinear S-boxes s₁, s₂, s₃, and s₄, where s₂, s₃, and s₄ are variations of s₁. S-function maps \left(x_1,x_2,\cdots ,x_8\right)\in {\mathfrak{F}}_{2^8}^8 to (y_{\mathrm{1}},y_{\mathrm{2}},\cdots ,y_{\mathrm{8}})\in {\mathfrak{F}}_{{{\mathrm{2}}^8}^{}}^{\mathrm{8}}, which is defined as

(y_{\mathrm{1}},y_{\mathrm{2}},y_{\mathrm{3}},y_{\mathrm{4}},y_{\mathrm{5}},y_{\mathrm{6}},y_{\mathrm{7}},y_{\mathrm{8}})=(s_{\mathrm{1}}(x_{\mathrm{1}}),s_{\mathrm{2}}(x_{\mathrm{2}}),s_{\mathrm{3}}(x_{\mathrm{3}}),s_{\mathrm{4}}(x_{\mathrm{4}}),s_{\mathrm{2}}(x_{\mathrm{5}}),s_{\mathrm{3}}(x_{\mathrm{6}}),s_{\mathrm{4}}(x_{\mathrm{7}}),s_{\mathrm{1}}(x_{\mathrm{8}})).

P-function maps \left(y_1,y_2,\cdots ,y_8\right)\in {\mathfrak{F}}_{2^8}^8 to \left(z_1,z_2,\cdots ,z_8\right)\in {\mathfrak{F}}_{2^8}^8:

\begin{array}{l}{z}_{\mathrm{1}}=y_{\mathrm{1}}\oplus y_{\mathrm{3}}\oplus y_{\mathrm{4}}\oplus y_{\mathrm{6}}\oplus y_{\mathrm{7}}\oplus y_{\mathrm{8}},\hfill \\ z_{\mathrm{2}}=y_{\mathrm{1}}\oplus y_{\mathrm{2}}\oplus y_{\mathrm{4}}\oplus y_{\mathrm{5}}\oplus y_{\mathrm{7}}\oplus y_{\mathrm{8}},\hfill \\ z_{\mathrm{3}}=y_{\mathrm{1}}\oplus y_{\mathrm{2}}\oplus y_{\mathrm{3}}\oplus y_{\mathrm{5}}\oplus y_{\mathrm{6}}\oplus y_{\mathrm{8}},\hfill \\ z_{\mathrm{4}}=y_{\mathrm{2}}\oplus y_{\mathrm{3}}\oplus y_{\mathrm{4}}\oplus y_{\mathrm{5}}\oplus y_{\mathrm{6}}\oplus y_{\mathrm{7}},\hfill \\ z_{\mathrm{5}}=y_{\mathrm{1}}\oplus y_{\mathrm{2}}\oplus y_{\mathrm{6}}\oplus y_{\mathrm{7}}\oplus y_{\mathrm{8}},\hfill \\ z_{\mathrm{6}}=y_{\mathrm{2}}\oplus y_{\mathrm{3}}\oplus y_{\mathrm{5}}\oplus y_{\mathrm{7}}\oplus y_{\mathrm{8}},\hfill \\ z_{\mathrm{7}}=y_{\mathrm{3}}\oplus y_{\mathrm{4}}\oplus y_{\mathrm{5}}\oplus y_{\mathrm{6}}\oplus y_{\mathrm{8}},\hfill \\ z_{\mathrm{8}}=y_{\mathrm{1}}\oplus y_{\mathrm{4}}\oplus y_{\mathrm{5}}\oplus y_{\mathrm{6}}\oplus y_{\mathrm{7}}.\hfill \end{array}

Obviously, P is a linear transformation, and it can be easily computed that P^-1, the inverse of the P-function, is defined as

\begin{array}{l}{y}_{\mathrm{1}}=z_{\mathrm{2}}\oplus z_{\mathrm{3}}\oplus z_{\mathrm{4}}\oplus z_{\mathrm{6}}\oplus z_{\mathrm{7}}\oplus z_{\mathrm{8}},\hfill \\ y_{\mathrm{2}}=z_{\mathrm{1}}\oplus z_{\mathrm{3}}\oplus z_{\mathrm{4}}\oplus z_{\mathrm{5}}\oplus z_{\mathrm{7}}\oplus z_{\mathrm{8}},\hfill \\ y_{\mathrm{3}}=z_{\mathrm{1}}\oplus z_{\mathrm{2}}\oplus z_{\mathrm{4}}\oplus z_{\mathrm{5}}\oplus z_{\mathrm{6}}\oplus z_{\mathrm{8}},\hfill \\ y_{\mathrm{4}}=z_{\mathrm{1}}\oplus z_{\mathrm{2}}\oplus z_{\mathrm{3}}\oplus z_{\mathrm{5}}\oplus z_{\mathrm{6}}\oplus z_{\mathrm{7}},\hfill \\ y_{\mathrm{5}}=z_{\mathrm{1}}\oplus z_{\mathrm{2}}\oplus z_{\mathrm{5}}\oplus z_{\mathrm{7}}\oplus z_{\mathrm{8}},\hfill \\ y_{\mathrm{6}}=z_{\mathrm{2}}\oplus z_{\mathrm{3}}\oplus z_{\mathrm{5}}\oplus z_{\mathrm{6}}\oplus z_{\mathrm{8}},\hfill \\ y_{\mathrm{7}}=z_{\mathrm{3}}\oplus z_{\mathrm{4}}\oplus z_{\mathrm{5}}\oplus z_{\mathrm{6}}\oplus z_{\mathrm{7}},\hfill \\ y_{\mathrm{8}}=z_{\mathrm{1}}\oplus z_{\mathrm{4}}\oplus z_{\mathrm{6}}\oplus z_{\mathrm{7}}\oplus z_{\mathrm{8}}.\hfill \end{array}

Since we assume that the round keys are independent with each other, the key schedule of Camellia is omitted, and we refer to Ref. [15] for more details.

To evaluate the influence of four S-boxes and different order of these S-boxes being used, we analyze the case where only single S-box is used, and this variant is all Camellia* whose S-function is replaced by

(y_{\mathrm{1}},y_{\mathrm{2}},y_{\mathrm{3}},y_{\mathrm{4}},y_{\mathrm{5}},y_{\mathrm{6}},y_{\mathrm{7}},y_{\mathrm{8}})=(s(x_{\mathrm{1}}),s(x_{\mathrm{2}}),s(x_{\mathrm{3}}),s(x_{\mathrm{4}}),s(x_{\mathrm{5}}),s(x_{\mathrm{6}}),s(x_{\mathrm{7}}),s(x_{\mathrm{8}})),

where s is one of s₁, s₂, s₃, and s₄, and the FL/FL^-1 is omitted. Other parts of Camellia and Camellia* are the same.

Basis of Square attack

The following definitions are essential when applying an integral attack.

Let a Λ-set be a set of 256 states that are all different in some of the state bytes (the active) and all equal in the other state bytes (the passive). We have

\forall x=(x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_n),y=(y_{\mathrm{1}},y_{\mathrm{2}},\cdots ,y_n)\in \mathrm{\Lambda }:\{\begin{array}{ll}{x}_i\ne y_i\hfill & \mathrm{i}\mathrm{f}{x}_i\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e},\hfill \\ x_i=y_i\hfill & \mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}.\hfill \end{array}

Let Γ-set (balanced set) be a set of 256 states that are all equal to zero in summation (the balanced). We have

{\displaystyle \sum _{x\in \mathrm{\Gamma }}x=\mathrm{0}}.

Applying the S-function or key-addition on a Λ-set results in a Λ-set with the positions of the active bytes unchanged. The result set of applying P-function to a Λ-set is not always a Λ-set but always a Γ-set.

In practice, if a balanced set comes with a nonlinear transformation, the finding process is stopped. Thus, the determination of the property of balanced set after it passed through a nonlinear transformation is very important in finding integral distinguishers. Reference [16] determined the property of balanced set after it passes through a nonlinear by determining that different values in the set appear even times; thus, the corresponding set is a balanced one.

4.5-round Square distinguisher of Camellia*

Let the input and output of the ith round be (L_i-1, R_i-1) and (L_i, R_i), respectively, and the output of S-function and P-function be Z_i and Y_i, respectively. Let X_i,j denote the jth byte of X_i, where X can represent L, R or Z, Y.

Assume that the input to Camellia* is

\{\begin{array}{l}{P}_{\mathrm{L}}=(c,c,c,c,c,c,c,c),\\ P_{\mathrm{R}}=(x,c,c,c,c,c,c,c),\end{array}

where c denotes some constant value in {\mathfrak{F}}_{{\mathrm{2}}^{\mathrm{8}}} (which are not necessarily equal to each other at different positions). Thus

Z_{\mathrm{2}}=(s(x\oplus t_{\mathrm{1}})\oplus t_{\mathrm{2}},c,c,c,c,c,c,c),

where t₁ and t₂ are some unknown constants in {\mathfrak{F}}_{{\mathrm{2}}^{\mathrm{8}}}. Let f\left(x\right)=s\left(x\oplus t_1\right)\oplus t_2. Since S(x) is a one-to-one map, so is f(x). After the P-function, we have

Y_{\mathrm{2}}=(f(x)\oplus {\alpha }_{\mathrm{1}},f(x)\oplus {\alpha }_{\mathrm{2}},f(x)\oplus {\alpha }_{\mathrm{3}},{\alpha }_{\mathrm{4}},f(x)\oplus {\alpha }_{\mathrm{5}},{\alpha }_{\mathrm{6}},{\alpha }_{\mathrm{7}},f(x)\oplus {\alpha }_{\mathrm{8}}),

where {\mathit{\alpha }}_{\mathrm{1}},{\mathit{\alpha }}_{\mathrm{2}},\cdots ,{\mathit{\alpha }}_{\mathrm{8}} are some unknown constants.

Similarly, we have

\begin{array}{c}{Z}_{\mathrm{3}}=(s(f(x)\oplus {\beta }_{\mathrm{1}}),s(f(x)\oplus {\beta }_{\mathrm{2}}),s(f(x)\oplus {\beta }_{\mathrm{3}}),{\beta }_{\mathrm{4}},\\ s(f(x)\oplus {\beta }_{\mathrm{5}}),{\beta }_{\mathrm{6}},{\beta }_{\mathrm{7}},s(f(x)\oplus {\beta }_{\mathrm{8}})),\end{array}

where {\mathit{\beta }}_{\mathrm{1}},{\mathit{\beta }}_{\mathrm{2}},\cdots ,{\mathit{\beta }}_{\mathrm{8}} are also some unknown constants.

Based on above, we can compute the expression of Y₃ and L₃ = R₄. Since each byte of L₃ is a sum of some active bytes and each byte of L₃ is balanced, this supports Ref. [7]’s claim as the 4-round Square distinguisher of Camellia.

After computing the expression of L₃, we can find that the 8th byte of L₃ satisfies

L_{\mathrm{3},\mathrm{8}}=s(f(x)\oplus {\beta }_{\mathrm{1}})\oplus s(f(x)\oplus {\beta }_{\mathrm{5}})\oplus \gamma ,

where γ is a constant.

Let f(x)\oplus {\beta }_{\mathrm{1}}=y, thus

L_{\mathrm{3},\mathrm{8}}=s(y)\oplus s(y\oplus {\beta }_{\mathrm{1}}\oplus {\beta }_{\mathrm{5}})\oplus \beta .

If {\mathit{\beta }}_{\mathrm{1}}\oplus {\mathit{\beta }}_{\mathrm{5}}=\mathrm{0}, L_{\mathrm{3},\mathrm{8}}=\mathit{\gamma } is a constant; if {\mathit{\beta }}_{\mathrm{1}}\oplus {\mathit{\beta }}_{\mathrm{5}}\ne \mathrm{0}, we have

s(y)\oplus s(y\oplus {\beta }_{\mathrm{1}}\oplus {\beta }_{\mathrm{5}})\oplus \gamma =s(y^{\ast })\oplus s(y^{\ast }\oplus {\beta }_{\mathrm{1}}\oplus {\beta }_{\mathrm{5}})\oplus \gamma ,

where y^{\ast }=y\oplus {\mathit{\beta }}_{\mathrm{1}}\oplus {\mathit{\beta }}_{\mathrm{5}}\ne y. Since L₃=R₄, the following theorem holds.

Theorem 1 Assuming Camellia* is defined as above, if all the bytes of the left half of the input to Camellia* are fixed, and in the right half, all the bytes are fixed except the first one is active, then all the bytes of the right half of the output of the 4th round are balanced, besides, the times that different values appear at the 8th byte, i.e., Z_4,8, are even integers.

According to Theorem 1, the times that different values of L_3,8 appear are even integers, Because the S-box is a bijective map, the times that different values of Z_4,8 appear are even integers. Thus, Z_4,8 is a balanced byte. Also, because Z_4,8 is the output of S-box, rather than a full round, the distinguisher shown in Theorem 1 is called a 4.5-round Square distinguisher of Camellia*.

In the original Camellia, we have

R_{\mathrm{4},\mathrm{8}}=s_{\mathrm{1}}(y)\oplus s_{\mathrm{2}}(y\oplus {\beta }_{\mathrm{1}}\oplus {\beta }_{\mathrm{5}})\oplus \gamma ,

by which we can only determine that R_4,8 is a balanced byte. If one wants to determine whether the times that different values of R_4,8 appear is even or odd, it is enough that the S-boxes at positions 1 and 5 are the same.

Reference [8] evaluated the security of Camellia against higher order differential attacks. According to the definition of higher order differences and by aid of computers, some higher order differences of round-reduced Camellia were found. In fact, the result of Theorem 1 will also be found by computers.

The results in this section show that, when a cipher adopts multi-S-boxes, in order to improve the immunity against Square attack, the designers must choose the order of the S-boxes carefully.

We can simply denote the Square distinguisher shown in Theorem 1 by (P_R,1, Z_4,8), which means that if only P_R,1 is active and other bytes are constants, Z_4,8 is a balanced byte. By the same techniques, we can find the following Square distinguishers of Camellia*: (P_R,2, Z_4,5), (P_R,3, Z_4,6), and (P_R,4, Z_4,7). Details of the proofs are omitted.

Square attacks on Camellia*

Square attack on 6-round Camellia*

To apply a 6-round Square attack, we adopt the method that has been used in Ref. [8] (See Fig. 1).

First, we have

P_{\mathrm{L}}\oplus Y_{\mathrm{2}}\oplus Y_{\mathrm{4}}\oplus Y_{\mathrm{6}}=C_{\mathrm{L}}.

Thus,

P_{\mathrm{L}}\oplus C_{\mathrm{L}}=Y_{\mathrm{2}}\oplus Y_{\mathrm{4}}\oplus Y_{\mathrm{6}}=P(Z_{\mathrm{2}}\oplus Z_{\mathrm{4}}{Z}_{\mathrm{6}}),

which means that

P^{-\mathrm{1}}(P_{\mathrm{L}}\oplus C_{\mathrm{L}})=Z_{\mathrm{2}}\oplus Z_{\mathrm{4}}\oplus Z_{\mathrm{6}}.

Thus, we have

$$\begin{gathered} {\displaystyle \sum _{P_{\mathrm{R},\mathrm{1}}}{P}^{-\mathrm{1}}{(P_{\mathrm{L}}\oplus C_{\mathrm{L}})}_{\mathrm{8}}}={\displaystyle \sum _{P_{\mathrm{R},\mathrm{1}}}{P}^{-\mathrm{1}}{(C_{\mathrm{L}})}_{\mathrm{8}}} \\ ={\displaystyle \sum _{P_{\mathrm{R},\mathrm{1}}}{(Z_{\mathrm{2}}\oplus Z_{\mathrm{4}}\oplus Z_{\mathrm{6}})}_{\mathrm{8}}} \\ ={\displaystyle \sum _{P_{\mathrm{R},\mathrm{1}}}{Z}_{\mathrm{2},\mathrm{8}}}\oplus {\displaystyle \sum _{P_{\mathrm{R},\mathrm{1}}}{Z}_{\mathrm{4},\mathrm{8}}}\oplus {\displaystyle \sum _{P_{\mathrm{R},\mathrm{1}}}{Z}_{\mathrm{6},\mathrm{8}}} \\ ={\displaystyle \sum _{P_{\mathrm{R},\mathrm{1}}}{Z}_{\mathrm{6},\mathrm{8}},} \end{gathered}$$

according to which we have the following attack on 6-round Camellia*.

Step 1 Choose plaintexts with the following form where c is some constant not necessarily equal to each other at different positions, and x takes all value of {\mathfrak{F}}_{{\mathrm{2}}^{\mathrm{8}}}:

\{\begin{array}{l}{P}_{\mathrm{L}}=(c,c,c,c,c,c,c,c),\\ P_{\mathrm{R}}=(x,c,c,c,c,c,c,c),\end{array}

the corresponding ciphertexts are denoted by (C_L(x), C_R(x)). Then, compute

\mathrm{s}\mathrm{u}\mathrm{m}={\displaystyle \sum _x{(P^{-\mathrm{1}}(C_{\mathrm{L}}(x)))}_{\mathrm{8}}}.

Step 2 Guess k_6,8 of the 6th round key and compute

\mathrm{s}\mathrm{u}{\mathrm{m}}^{\ast }={\displaystyle \sum _{x}s(C_{\mathrm{R},\mathrm{8}}\oplus k_{\mathrm{6},\mathrm{8}})}.

If \mathrm{s}\mathrm{u}{\mathrm{m}}^{\ast }=\mathrm{s}\mathrm{u}\mathrm{m}, keep k_6,8 as a candidate of the right subkey; otherwise, it is rejected.

Step 3 If necessary, repeat Steps 1 and 2 until the value of k_6,8 is uniquely determined.

For a wrong key, with probability 2^-8, \mathrm{s}\mathrm{u}{\mathrm{m}}^{\ast }=\mathrm{s}\mathrm{u}\mathrm{m} holds. Thus, after choosing a structure of plaintexts, there are (2⁸-1)×2^-8≈1 wrong keys that can pass the test. To uniquely determine the correct key, two structures are sufficient. Therefore, the data complexity of the above attack is 2×2⁸=2⁹ chosen plaintexts. Accordingly, the time complexity of the attack is about 2⁸×2⁸+2×2⁸ times lookup tables, and since there are 6×8 S-boxes in 6-round Camellia*, the time complexity is about (2⁸×2⁸+2×2⁸)/(6×8) ≈2^10.4 encryptions. Since the structure must be stored, the space complexity of the attack is 2⁸ plaintext/ciphertext pairs.

Square attack on 7-round Camellia*

The 7-round attack is based on the 6-round attack with additional one round at the beginning.

Step 1 Choose plaintexts with the left half being

P_{\mathrm{L}}=(x,c,c,c,c,c,c,c),

where c is some constant not necessarily equal to each other at different positions; guess a value for k_1,1, and compute

P_{\mathrm{R}}=P(S(x\oplus k_{\mathrm{1},1}),c,c,c,c,c,c,c)\mathrm{.}

Then, compute the corresponding ciphertext of (P_L, C_R), say, (C_L, C_R), and last, compute

\mathrm{s}\mathrm{u}\mathrm{m}={\displaystyle {\sum }_x{(P^{-\mathrm{1}}{C}_{\mathrm{L}})}_{\mathrm{8}}.}

.

Step 2 Guess a value for k_7,8, then compute

\mathrm{s}\mathrm{u}{\mathrm{m}}^{\ast }={\displaystyle {\sum }_{x}s(C_{\mathrm{R},\mathrm{8}}\oplus k_{\mathrm{7},\mathrm{8}})}.

If \mathrm{s}\mathrm{u}{\mathrm{m}}^{\ast }=\mathrm{s}\mathrm{u}\mathrm{m}, put (k_1,1, k_6,8) as a candidate of the right keys; otherwise, it is rejected.

Step 3 If necessary, repeat Steps 1 and 2 until the value of (k_1,1, k_6,8) is uniquely determined.

If k_1,1 is the correct value, the output of the first round is

\{\begin{array}{l}{L}_{\mathrm{1}}=(c,c,c,c,c,c,c,c),\\ R_{\mathrm{1}}=(y,c,c,c,c,c,c,c),\end{array}

thus the 6-round attack can be applied to the following 6-round cipher. Because a wrong value for k_7,8 can pass the test with probability 2^-8, three different structures of P_L will be needed to uniquely determine (k_1,1, k_6,8). Thus, the data complexity of the attack is 2^17.6 chosen plaintexts, time complexity is (2×2⁸×2⁸×2⁸+2⁸×2⁸+2×2⁸)/(8×7)≈2^19.2 encryptions, space complexity of the attack is 2⁸ plaintext/ciphertext pairs, and 2⁸ keys are candidates after analyzing the first structure.

This attack is valid even if an FL/FL^-1 is inserted.

In fact, if there is no FL/FL^-1 transformation, {(P^{-\mathrm{1}}{C}_{\mathrm{L}})}_{\mathrm{8}}, we only need to know five bytes of {(C_L)}_{\mathrm{8}}, thus when FL/FL^-1 is added, we need to guess another 5×8 bits of k_l and 8 bits of k_r, where k_l and k_r stand for the left and right halves of the correspondence subkey. Therefore, the number of structures must satisfy

which tells that N=\mathrm{9} is enough. Therefore, the data complexity is {\mathrm{2}}^{\mathrm{16}}\times \mathrm{9}\approx {\mathrm{2}}^{\mathrm{19.1}} chosen plaintexts, and the time complexity is {\mathrm{2}}^{\mathrm{18.2}}\times {\mathrm{2}}^{\mathrm{6}\times \mathrm{8}}={\mathrm{2}}^{\mathrm{66.2}} encryptions.

Square attack on 11-round Camellia*

The 11-round attack is based on the 6-round attack with additional two rounds at the beginning and three rounds at the end. In the two rounds at the beginning, it needs to guess six bytes subkeys; and in the three rounds at the end, it needs to guess 22 bytes subkeys.

Step 1 Guess a value for k_2,1, and

P_{\mathrm{L}}=(s(x\oplus k_{\mathrm{2},\mathrm{1}}),s(x\oplus k_{\mathrm{2},\mathrm{1}}),s(x\oplus k_{\mathrm{2},\mathrm{1}}),c,s(x\oplus k_{\mathrm{2},\mathrm{1}}),c,c,s(x\oplus k_{\mathrm{2},\mathrm{1}})),

then guess k_1,1, k_1,2, k_1,3, k_1,5, k_1,8 and compute

\begin{array}{c}{P}_{\mathrm{R}}=P(s(s(x\oplus k_{\mathrm{2},\mathrm{1}})\oplus k_{\mathrm{1},\mathrm{1}}),s(s(x\oplus k_{\mathrm{2},\mathrm{1}})\oplus k_{\mathrm{1},\mathrm{2}}),s(s(x\oplus k_{\mathrm{2},\mathrm{1}})\oplus k_{\mathrm{1},\mathrm{3}}),c,\\ s(s(x\oplus k_{\mathrm{2},\mathrm{1}})\oplus k_{\mathrm{1},\mathrm{5}}),c,c,s(s(x\oplus k_{\mathrm{2},\mathrm{1}})\oplus k_{\mathrm{1},\mathrm{8}})).\end{array}

Step 2 Guess all bytes of the 11th round-key (eight bytes) and compute (L₁₀, R₁₀), then guess all bytes of the 10th round-key (8 bytes) and compute (L_9,8, R₉); guess k_9,1, k_9,4, k_9,5, k_9,6, k_9,7 and compute (L_{8,(1,4,5,6,7)}, R_8,8); guess k_8,8 and check whether the following equation holds:

{\displaystyle \sum _{x}s(R_{\mathrm{8},\mathrm{8}}\oplus k_{\mathrm{8},\mathrm{8}})}={\displaystyle \sum _x(L_{\mathrm{8},\mathrm{1}}\oplus L_{\mathrm{8},\mathrm{4}}\oplus L_{\mathrm{8},\mathrm{5}}\oplus L_{\mathrm{8},\mathrm{6}}\oplus L_{\mathrm{8},\mathrm{7}}).}

If the equation does not hold, the combination of the correspondence subkeys is a wrong one.

Step 3 If necessary, repeat Steps 1 and 2 until the combination of the subkeys is uniquely determined.

To uniquely determine the candidates, it needs 29 different structures of P_L. Thus, the data complexity of the attack is 29×2⁸×2⁴⁰≈2^52.9 chosen plaintexts; the time complexity is (2⁸×2⁸×2⁴⁰×2²²×8+···)/(8×11)≈2^225.5 encryptions; and the space complexity is 2²¹⁶.

Conclusion

This paper primarily investigated the relationship between the order of S-boxes and immunity of ciphers against Square attack. Results in this paper show that, if Camellia adopts only a single S-box instead of four S-boxes, the security of Camellia against Square attack decreased dramatically. Also, if the order of the four S-boxed is changed, the security of Camellia against Square attack is also decreased. See Table 1 for the comparison of these results. In the design of a cipher, multi-S-boxes can improve the security of the cipher, given that one can carefully chooses the order of the S-boxes being used.

References

[1] Daemen J, Knudsen L R, Rijmen V. The block cipher Square. In: Proceedings of the 4th International Workshop on Fast Software Encryption. Lecture Notes in Computer Science, 1997, 1267: 149–165

[2] Lucks S. The saturation attack—a bait for Twofish. In: Proceedings of the 8th International Workshop on Fast Software Encryption. Lecture Notes in Computer Science, 2002, 2355: 1–15

[3] Biryukov A, Shamir A. Structural cryptanalysis of SASAS. In: Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology. Lecture Notes in Computer Science, 2001, 2045: 395–405

[4] Knudsen L R, Wagner D. Integral cryptanalysis. In: Proceedings of the 9th International Workshop on Fast Software Encryption. Lecture Notes in Computer Science, 2002, 2365: 112–127

[5] Reza Z’aba M, Raddum H, Henricksen M, Dawson E. Bit-pattern based integral attack. In: Proceedings of the 15th International Workshop on Fast Software Encryption. Lecture Notes in Computer Science, 2008, 5086: 363–381

[6] Aoki K, Ichikawa T, Kanda M, Matsui M, Moriai S, Nakajima J, Tokita T. Camellia: a 128-bit block cipher suitable for multiple platforms—design and analysis. In: Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science, 2001, 2012: 39–56

[7] Kanda M, Matsumoto T. Security of Camellia against truncated differential cryptanalysis. In: Proceedings of the 8th International Workshop on Fast Software Encryption. Lecture Notes in Computer Science, 2002, 2355: 286–299

[8] Hatano Y, Sekine H, Kaneko T. Higher order differential attack of Camellia (II). In: Proceedings of the 9th Annual International Workshop on Selected Areas in Cryptography, Lecture Notes in Computer Science, 2003, 2595: 129–146

[9] He Y P, Qing S H. Square attack on reduced Camellia cipher. In: Proceedings of the 3rd International Conference on Information and Communications Security. Lecture Notes in Computer Science, 2001, 2229: 238–245

[10] Yeom Y, Park S, Kim I. On the security of Camellia against the Square attack. In: Proceedings of the 9th International Workshop on Fast Software Encryption. Lecture Notes in Computer Science, 2002, 2365: 89–99

[11] Lei D, Chao L, Feng K Q. New observation on Camellia. In: Proceedings of the 12th International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science, 2006, 3897: 51–64

[12] Wu W L, Feng D G. Collision attack on reduced-round Camellia. Science in China, Series F: Information Sciences, 2005, 48(1): 78–90

[13] Wu W L, Zhang W T, Feng D G. Impossible differential cryptanalysis of reduced-round ARIA and Camellia. Journal of Compute Science and Technology, 2007, 22(3): 449–456

[14] Lu J Q, Kim J, Keller N, Dunkelman O. Improving the efficiency of impossible differential cryptanalysis of reduced Camellia and MISTY1. In: Proceedings of the Cryptopgraphers’ Track at the RSA conference on Topics in cryptology. Lecture Notes in Computer Science, 2008, 4964: 370–386

[15] Kwon D, Kim J, Park S, Sung S H, Sohn Y, Song J H, Yeom Y, Yoon E-J, Lee S, Lee J, Chee S, Han D, Hong J. New block cipher: ARIA. In: Proceedings of the 6th International Conference on Information Security and Cryptology. Lecture Notes in Computer Science, 2004, 2971: 432–445

[16] Li P, Sun B, Li C. Integral cryptanalysis of ARIA. In: Proceedings of Information Security and Cryptology—Inscrypt2009

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg