Related-Key Differential Attacks on COSB-128

Abstract

COSB-128 (Moldovyan et al., 2002) is a block cipher with 128-bit and 256-bit secret keys, which use key and data-dependent operational substitutions in fast controllable permutation blocks (CPB) concept. It is designed with a simple key schedule to ensure a high speed of data transformation by fast block encryption algorithms and expected to be high stability to all known methods of cryptanalysis, especially differential and linear attacks. In this paper, we show that the COSB-128 block cipher still remains weaknesses to differential related-key cryptanalysis, by constructing two full 10-round related-key differential characteristics (DCs) of COSB-128 with high probabilities, and thence propose our two related-key differential attacks. The attacks require about 2²⁴ data and time complexities to recover 63-bit key information and 2²² data and time complexities to recover 6-bit key information. This study is the first known cryptanalytic result on COSB-128 until now. From this study, the new potential for the cryptanalysis on these types of block cipher will be further revealed.

1. Introduction

Recently, the use of network-based devices and services has increased gradually. Thence, the security becomes an essential interest, which is required not only to be strong with most known attacks but also to be optimized on software-hardware implementations [1, 2] or specialized applications. With these criteria, designing cipher using in which data-dependent controllable operations is a cryptographic primitive approach in modern applied cryptography.

When the best known algorithms using controllable permutations (RC5, RC6, etc. [3]) showed their limitations in protective transformation, the operational substitutions offer promise for fast block encryption algorithms with better performance.

Recently, there are some designs of block ciphers which are presented, such as CIKS-1 [4], CIKS-128 [5], Cobra-H64, Cobra-H128 [6], SCO-1, SCO-2, and SCO-3 [7] which aim to enhance the security of the DDP- (data-dependent permutation-) based ciphers structure. Although there are many well-known ciphers, with different specifications and characteristics, the security of them is still under consideration. All of them use a very simple key scheduling for high speed encryption algorithms, which enables the cryptanalysis exploit by applying related-key attacks concept.

COSB-128 [8] is a 128-bit block cipher with a 256-bit key; the number of round is 10. It uses controlled operational substitution (COS) with the concept of fast controllable permutation blocks (CPB) [9]. This cipher is expected to have high performance in hardware-software implementations and high stability to all known cryptanalysis, especially differential attacks and linear attacks.

Related-key differential cryptanalysis was introduced in 1994 by Biham [1, 2] and has become an effective and popular method for attacking many types of block ciphers. This attack researched on CIKS-cipher family [10], Cobra-cipher family [11], or SCO-cipher family [12]… has given a reasonable result with better performance.

In this paper, we show that this type of block cipher is still vulnerable to related-key differential attack, by constructing two full 10-round differential characteristics (DCs) of COSB-128 with high probabilities; thence, we present our two related-key differential attacks on it. The attack allows us to recover 63-bit key information with about 2²⁴ data related-key chosen plaintexts and 2²⁴ encryptions and 6-bit key information with about 2²² data related-key chosen plaintexts and 2²² encryptions. This study is the first known cryptanalytic result on COSB-128 so far.

This paper is organized as follows: in Section 2, we present the COSB-128 block cipher; in Section 3, the related-key differential characteristics and our related-key differential attack on COSB-128 are proposed. Finally, we give the conclusion of this paper in Section 4.

2. Description of COSB-128 Block Cipher

In this section, the structure of COSB-128 block cipher is reviewed. Firstly, we notice some notations using through the whole paper. The cipher $A=(a_1,a_2,\dots ,a_n)$ is assigned with $a_1$ and $a_n$ being the most significant bit and the least significant bit, respectively:

• (i)

$\Delta X_r$ : the input difference in round r;

(ii)

$\Delta K_r$ : the round-key difference in round r;

(iii)

$\Delta Y_r$ : the output difference in round r;

(iv)

$e_{i,j}$ : the ith bit and jth bit are ones; the others are zeros within a cipher (e.g., $e_{\mathrm{2,5}}=(0,1,0,0,1,0,\dots ,0)$ ).

COSB-128 [8] is a 128-bit block cipher using 256-bit secret key; the number of round is 10. The ciphers do the same iterative structure with the round function ${\text{Crypt}}^{\mathbf{\left(}e\mathbf{\right)}}$ ( $e=0$ : encryption, $e=1$ : decryption).

The round function ${\text{Crypt}}^{\mathbf{\left(}e\mathbf{\right)}}$ consists of basic arithmetical operations: ×, multiplication, ⊕, modulo 2 addition, a transformation of control vector H, a substitution transformation G, and two CPB-Boxes, ${\mathbf{F}}_{64/192}$ and ${\mathit{F}}_{\mathrm{64}/\mathrm{192}}^{-\mathrm{1}}$ .

The encryption procedure of COSB-128 is as follows.

• (1)

128-bit plaintext is divided into two 64-bit subblocks A and B:

$$\begin{array}{cc}& X=\left(A,B\right).\end{array}$$

(1)

 

Perform initial transformation as follows:

$$\begin{array}{cc}& \left(A_{\mathrm{0}},B_{\mathrm{0}}\right)=\left(A\oplus z_{\mathrm{1}},B\oplus z_{\mathrm{2}}\right).\end{array}$$

(2)

(2)

For $r=1$ to 9 do the following:

$$\begin{array}{cc}& \hspace{0.17em}\left(\text{a}\right)\hspace{0.17em}\hspace{0.17em}(A_r,B_r)={\text{Crypt}}^{\left(\mathrm{0}\right)}\left(A_{r-\mathrm{1}},B_{r-\mathrm{1}},K_r^{\left(\mathrm{0}\right)}\right)\\ \hspace{0.17em}\left(\text{b}\right)\hspace{0.17em}\hspace{0.17em}\left(A_r,B_r\right)=\left(B_r,A_r\right).\end{array}$$

(3)

(3)

Perform transformation $(A_{\mathrm{10}},B_{10})$ as follows:

$$\begin{array}{cc}& (A_{\mathrm{10}},B_{\mathrm{10}})={\text{Crypt}}^{\left(\mathrm{0}\right)}(A_{\mathrm{9}},B_{\mathrm{9}},K_{\mathrm{10}}^{\left(\mathrm{0}\right)}).\end{array}$$

(4)

(4)

Perform final transformation as follows:

$$\begin{array}{cc}& Y=(A^{\prime },B^{\prime })=(A_{\mathrm{10}}\oplus z_{\mathrm{3}},B_{\mathrm{10}}\oplus z_{\mathrm{4}}).\end{array}$$

(5)

The round function Crypt⁽⁰⁾ is given in Figures 1 and 2. For more detailed description of COSB-128, see [8].

Figure 1

Round function ${\text{Crypt}}^{(\mathrm{0})}$ of COSB-128.

Figure 2

(a) ${\mathbf{F}}_{64/192}$ and ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{-\mathrm{1}}$ , (b) ${\mathbf{F}}_{\mathrm{8}/\mathrm{12}}$ , (c) ${\mathbf{F}}_{\mathrm{8}/\mathrm{12}}^{-\mathrm{1}}$ , (d) ${\mathbf{F}}_{\mathrm{4}/\mathrm{4}}$ , (e) ${\mathbf{F}}_{4/4}^{-\mathrm{1}}$ , and (f) ${\mathbf{F}}_{\mathrm{2}/\mathrm{1}}$ .

The control ciphers $V_1,V_2\in {\mathbf{G}\mathbf{F}(2)}^{192}$ are performed through the transformation of control vector H, with the ciphers $V_i$ ,   $i=1,2$ . Consider the following:

$$\begin{array}{cc}& V_i=\left\{{W_{\mathrm{1}}}^{\left(i\right)}\hspace{0.17em}|\hspace{0.17em}{W_{\mathrm{2}}}^{\left(i\right)}\hspace{0.17em}|\hspace{0.17em}{W_{\mathrm{3}}}^{\left(i\right)}\hspace{0.17em}|\hspace{0.17em}{W_{\mathrm{4}}}^{\left(i\right)}\hspace{0.17em}|\hspace{0.17em}{W_{\mathrm{5}}}^{\left(i\right)}\hspace{0.17em}|\hspace{0.17em}{W_{\mathrm{6}}}^{\left(i\right)}\right\}.\end{array}$$

(6)

The output values of ${W_j}^{\left(i\right)}$ are defined as

$$\begin{array}{cc}& {W_{\mathrm{1}}}^{\left(\mathrm{1}\right)}=A_{\mathcal{l}},\hspace{1em}\hspace{1em}{W_{\mathrm{2}}}^{\left(\mathrm{1}\right)}={A_{\mathbf{h}}}^{⋘\mathrm{1}},\\ {W_{\mathrm{3}}}^{\left(\mathrm{1}\right)}={{\left(A\oplus K_{\mathrm{1}}\right)}_{\mathbf{h}}}^{⋘\mathrm{18}},\hspace{1em}\hspace{1em}{W_{\mathrm{4}}}^{\left(\mathrm{1}\right)}={{\left(A\oplus K_1\right)}_{\mathcal{l}}}^{⋘\mathrm{4}},\\ {W_{\mathrm{5}}}^{\left(\mathrm{1}\right)}={{\left(A\oplus K_2\right)}_{\mathcal{l}}}^{⋘\mathrm{8}},\hspace{1em}\hspace{1em}{W_{\mathrm{6}}}^{\left(\mathrm{1}\right)}={{\left(A\oplus K_2\right)}_{\mathit{h}}}^{⋘\mathrm{16}},\\ {W_{\mathrm{1}}}^{\left(\mathrm{2}\right)}=A_{\mathcal{l}},\hspace{1em}\hspace{1em}{W_{\mathrm{2}}}^{\left(\mathrm{2}\right)}={A_{\mathbf{h}}}^{⋘\mathrm{1}},\\ {W_{\mathrm{3}}}^{\left(\mathrm{2}\right)}={{\left(A\oplus K_{\mathrm{4}}\right)}_{\mathbf{h}}}^{⋘\mathrm{18}},\hspace{1em}\hspace{1em}{W_{\mathrm{4}}}^{\left(\mathrm{2}\right)}={{\left(A\oplus K_4\right)}_{\mathcal{l}}}^{⋘\mathrm{4}},\\ {W_{\mathrm{5}}}^{\left(\mathrm{2}\right)}={{\left(A\oplus K_3\right)}_{\mathcal{l}}}^{⋘\mathrm{8}},\hspace{1em}\hspace{1em}{W_{\mathrm{6}}}^{\left(\mathrm{1}\right)}={{\left(A\oplus K_3\right)}_{\mathit{h}}}^{⋘\mathrm{16}},\end{array}$$

(7)

where ${W_j}^{(i)}\in \mathbf{G}\mathbf{F}{\left(2\right)}^{32}$ , $\mathcal{l}$ is 32 lower-order digits, and h is 32 higher-order digits.

The substitution function G uses output vector $\Psi (A,Q)$ , in which Q depends on round cycles; $Q=K_1\oplus K_3$ for odd rounds and $Q=K_2\oplus K_4$ for even rounds; A, $Q\in \mathbf{G}\mathbf{F}{\left(2\right)}^{64}$ . Consider the following:

$$\begin{array}{l}\Psi \left(A,Q\right)=\left(A_1\times A_3\times Q_2\times A_5\times A_6\times A_8\right)\hfill \\ \oplus \left(A_1\times A_3\times A_6\times A_8\right)\hfill \\ \oplus \left(A_1\times Q_2\times A_5\times A_8\right)\oplus \left(A_3\times Q_2\times A_5\times A_6\right)\hfill \\ \oplus \left(A_1\times Q_2\times A_6\right)\oplus \left(A_3\times A_5\times A_8\right)\hfill \\ \oplus \left(A_1\times A_3\times Q_2\right)\oplus \left(A_5\times A_6\times A_8\right)\hfill \\ \oplus \left(A_1\times A_4\right)\oplus \left(Q_1\times A_6\right)\oplus \left(A_2\times A_8\right)\hfill \\ \oplus \left(A_3\times Q_3\right)\oplus \left(Q_2\times A_7\right)\hfill \\ \oplus \left(A_5\times Q_4\right)\oplus A_0\oplus Q_0,\hfill \end{array}$$

(8)

where

$$\begin{array}{cc}& A_{\mathrm{0}}=(a_{\mathrm{1}},a_{\mathrm{1}},\dots ,a_n),\\ A_{\mathrm{1}}=(a_n,a_{\mathrm{1}},\dots ,a_{n-\mathrm{1}}),\\ ⋮\hspace{0.17em}\\ A_j=(a_{n-j+\mathrm{1}},\dots ,a_n,a_{\mathrm{1}},\dots ,a_{n-j}),\\ Q_{\mathrm{0}}=(q_{\mathrm{1}},q_{\mathrm{1}},\dots ,q_n),\\ Q_{\mathrm{1}}=\left(q_n,q_{\mathrm{1}},\dots ,q_{n-\mathrm{1}}\right),\\ ⋮\hspace{0.17em}\\ Q_j=(q_{n-j+\mathrm{1}},\dots ,q_n,q_{\mathrm{1}},\dots ,q_{n-j}).\end{array}$$

(9)

The key schedule of COSB-128 is constructed in such a simple way, where 256-bit secret key Z is split into four 64-bit subkeys; $Z=(z_1,z_2,z_3,z_4)$ . The procedure of key scheduling is specified as in Table 1.

Table 1

Key schedule of COSB-128.

Key	$$O_1$$	$$O_2$$	$$O_3$$	$$O_4$$	$$O_5$$	$$O_6$$	$$O_7$$	$$O_8$$	$$O_9$$	$$O_{\mathrm{10}}$$
K 1	z 1	z 4	z 3	z 2	z 4	z 3	z 1	z 2	z 3	z 1
K 2	z 2	z 1	z 4	z 3	z 2	z 4	z 3	z 1	z 2	z 3
K 3	z 3	z 2	z 1	z 4	z 1	z 2	z 4	z 3	z 4	z 2
K 4	z 4	z 3	z 2	z 1	z 3	z 1	z 2	z 4	z 1	z 4

3. Key Recovery Attacks on COSB-128

In this section, we construct a full 10-round related-key differential characteristic (DC) of COSB-128 with high probabilities using some properties of ${\text{Crypt}}^{(e)}$ function and thence propose our related-key differential attack on COSB-128 block cipher.

3.1. Properties of COSB-128

We obtain some appropriate properties of ${\text{Crypt}}^{(e)}$ function of COSB-128 that enable us to construct related-key differential characteristics.

3.1.1. Properties with $F_{2/1}$

We assume $\mathrm{Pr}({\mathit{F}}_{2/1})(\Delta Y/\Delta X,\Delta V)$ is a probability to have the output difference $\Delta Y$ of ${\mathit{F}}_{2/1}$ , with $\Delta X$ and $\Delta V$ being the input difference and the controlling vector difference, respectively. Then we can calculate the probability as the following.

• (a)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{0},\mathrm{0})/(\mathrm{0},\mathrm{0}),\mathrm{0})=\mathrm{1}$ .

(b)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{0},\mathrm{1})/(\mathrm{0},\mathrm{1}),\mathrm{0})=\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{1},\mathrm{1})/(\mathrm{0},\mathrm{1}),\mathrm{0})={\mathrm{2}}^{-\mathrm{1}}$ .

(c)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{1},\mathrm{0})/(\mathrm{1},\mathrm{0}),\mathrm{0})=\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{1},\mathrm{1})/(\mathrm{1},\mathrm{0}),\mathrm{0})={\mathrm{2}}^{-\mathrm{1}}$ .

(d)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{1},\mathrm{0})/(\mathrm{1},\mathrm{1}),\mathrm{0})=\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{0},\mathrm{1})/(\mathrm{1},\mathrm{1}),\mathrm{0})={\mathrm{2}}^{-\mathrm{1}}$ .

(e)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{0},\mathrm{0})/(\mathrm{0},\mathrm{0}),\mathrm{1})=\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{1},\mathrm{1})/(\mathrm{0},\mathrm{0}),\mathrm{1})={\mathrm{2}}^{-\mathrm{2}}$ .

(f)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{0},\mathrm{0})/(\mathrm{1},\mathrm{1}),\mathrm{1})=\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})((\mathrm{1},\mathrm{1})/(\mathrm{1},\mathrm{1}),\mathrm{1})={\mathrm{2}}^{-\mathrm{2}}$ .

(g)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{2}/\mathrm{1}})(\Delta Y/\Delta X,\Delta V)={\mathrm{2}}^{-\mathrm{2}}$ ,

where ΔY = $\{(\mathrm{0},\mathrm{1}),(\mathrm{1},\mathrm{0})\}$ , $\Delta X=\{(\mathrm{0},\mathrm{1}),(\mathrm{1},\mathrm{0})\}$ , and $\Delta V=\mathrm{1}$ .

3.1.2. Properties with $F_{n\mathbf{/}m}$

Extensively, we let $\mathrm{Pr}({\mathbf{F}}_{n/m})(\Delta Y/\Delta X,\Delta V)$ be a probability to have the output difference $\Delta Y$ of ${\mathbf{F}}_{n/m}$ , with $\Delta X$ being the input difference and $\Delta V$ being the controlling vector difference. We have the following.

• (a)

$\mathrm{Pr}({\mathbf{F}}_{n/m})((\mathrm{0})/(\mathrm{0}),e_i)=\mathrm{Pr}({\mathbf{F}}_{n/m}^{-\mathrm{1}})((\mathrm{0})/(\mathrm{0}),e_i)={\mathrm{2}}^{-\mathrm{2}}$ .

(b)

$\mathrm{Pr}({\mathbf{F}}_{n/m(\mathbf{V})}(X))=\mathrm{Pr}({\mathbf{F}}_{n/m(\mathbf{V}\oplus e_i)}(X))={\mathrm{2}}^{-\mathrm{2}}$ , with $X\in {\left\{\mathrm{0},\mathrm{1}\right\}}^n$ .

(c)

$\mathrm{Pr}({{\mathbf{F}}_{n/m\left(\mathbf{V}\right)}^{-\mathrm{1}}}^{}(X))=\mathrm{Pr}({\mathbf{F}}_{n/m(\mathbf{V}\oplus e_i)}^{-\mathrm{1}}(X))={\mathrm{2}}^{-\mathrm{2}}$ , with $X\in {\left\{\mathrm{0},\mathrm{1}\right\}}^n.$   

3.1.3. Properties with $F_{64\mathbf{/}192}^{\mathbf{\left(}e\mathbf{\right)}}$

Similarly, we can get the probability $\mathrm{Pr}({\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{(e\mathbf{)}})(\Delta Y/\Delta X,\Delta V)$ of ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{(\mathrm{0}\mathbf{)}}$ , ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{(\mathrm{1}\mathbf{)}}$ , with $\Delta Y$ -output difference, $\Delta X$ -input difference, and $\Delta V$ -controlling vector difference. Consider the following.

• (a)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{64}/\mathrm{192}})(\mathrm{0}/\mathrm{0},\mathrm{0})=\mathrm{Pr}({\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{-\mathrm{1}})(\mathrm{0}/\mathrm{0},\mathrm{0})=\mathrm{1}$ .

(b)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{64}/\mathrm{192}})(\mathrm{0}/\mathrm{0},e_i)=\mathrm{Pr}({\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{-\mathrm{1}})(\mathrm{0}/\mathrm{0},e_i)={\mathrm{2}}^{-\mathrm{2}}$ .

(c)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{64}/\mathrm{192}})(e_j/e_i,\mathrm{0})=\mathrm{Pr}({\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{-\mathrm{1}})(e_j/e_i,\mathrm{0})={\mathrm{2}}^{-\mathrm{12}}$ , for any fixed i, j.

 

(both ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}$ and ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{-\mathrm{1}}$ have 6 active layers ${\mathbf{F}}_{\mathrm{2}/\mathrm{1}}$ within structure)

(d)

$\mathrm{Pr}({\mathbf{F}}_{\mathrm{64}/\mathrm{192}})(e_j/e_i,e_i)=\mathrm{Pr}({\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{-\mathrm{1}})(e_j/e_i,e_i)={\mathrm{2}}^{-\mathrm{12}}$ , for any fixed i, j.

 

(both ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}$ and ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}^{-\mathrm{1}}$ have 6 active layers ${\mathbf{F}}_{\mathrm{2}/\mathrm{1}}$ within structure).

3.1.4. Properties with Transformation H and G

• (a)

Let A, $A^{\prime }$ , and $A^{\prime \prime }$ be the inputs of transformation H, respectively:

$$\begin{array}{r}\hfill V_i=\left\{W_1\left|W_2\right|W_3\left|W_4\right|W_5|W_6\right\}=\text{H}\left(A,A^{\prime },A^{″}\right);\\ \hfill i=1,2.\end{array}$$

(10)

 

With the control vector $V_1$ of ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}$ , we have $\mathbf{H}(A,A^{\prime },A^{\prime \prime })\oplus (A,A^{\prime }\oplus e_{16},A^{\prime \prime })=e_{94}$ and $\mathit{H}(A,A^{\prime },A^{\prime \prime })\oplus (A,A^{\prime },A^{\prime \prime }\oplus e_{16})=e_{192}$ . Similarly, $\mathbf{H}(A,A^{\prime },A^{\prime \prime })\oplus (A,A^{\prime }\oplus e_{16},A^{\prime \prime })=e_{126}$ and $\mathbf{H}(A,A^{\prime },A^{\prime \prime })\oplus (A,A^{\prime },A^{\prime \prime }\oplus e_{16})=e_{32}$ of the control vector $V_2$ of ${\mathbf{F}}_{64/192}^{-\mathrm{1}}$ .

(b)

Let A be the input of G with key-dependent metric Q; then we can get the probability $\mathrm{Pr}(G_{\mathit{Q}}(A)\oplus G_{\mathit{Q}}(A)=0)=1$ and $\mathrm{Pr}(G_{\mathit{Q}}\oplus e_{64}(A)\oplus G_{\mathit{Q}}\oplus e_{64}(A)=0)=1$ .

3.2. Related-Key Differential Characteristics of COSB-128

With the properties defined in Section 3.1 combined with such a simple key schedule of COSB-128 structure, we are able to construct the related-key differential characteristics (DCs) for COSB-128 with high probability.

We assume that the plaintext pairs $(P,P^{*})$ are encrypted under the key pairs $(K,K^{*})$ , respectively, in which $\alpha =\Delta P=P\oplus P^{*}=(0,e_{16})$ and $\Delta K=K\oplus K^{*}=(0,e_{16},0,0)$ , to get the corresponding ciphertext pairs $(C,C^{*})$ .

Then, as Table 2 shows, we can construct a 10-round related-key differential characteristic $\alpha \to \beta$ , where $\beta =(e_{16},e_j)$ , $(1\le j\le 64)$ for rounds 1~10 of COSB-128 with probability $2^{-22}$ .

Table 2

Related-key differential characteristics (DCs) of a full 10-round COSB-128.

Round(r)	$$\mathrm{\Delta }{X}_r$$	( $$\Delta K_r$$ )	$$\mathit{E}\mathit{1}/\mathit{E}\mathit{2}/\mathit{E}\mathit{3}$$	Probability
IT	(0, $$e_{\mathrm{16}}$$ ) = α	(0, $$e_{\mathrm{16}}$$ )		1
1	(0, 0)	(0, $$e_{\mathrm{16}}$$ , 0, 0)	2−2/1/1	2−2	$${\mathit{Z}}_{\mathit{1}}$$
2	(0, 0)	(0, 0, $$e_{\mathrm{16}}$$ , 0)	1/1/2−2	2−2	$${\mathit{Z}}_{\mathit{2}}$$
3	(0, 0)	(0, 0, 0, $$e_{\mathrm{16}}$$ )	1/1/2−2	2−2	$${\mathit{Z}}_{\mathit{3}}$$
4	(0, 0)	( $$e_{\mathrm{16}}$$ , 0, 0, 0)	2−2/1/1	2−2	$${\mathit{Z}}_{\mathit{4}}$$
5	(0, 0)	(0, $$e_{\mathrm{16}}$$ , 0, 0)	2−2/1/1	2−2	$${\mathit{Z}}_{\mathit{1}}$$
6	(0, 0)	(0, 0, $$e_{\mathrm{16}}$$ , 0)	1/1/2−2	2−2	$${\mathit{Z}}_{\mathit{2}}$$
7	(0, 0)	(0, 0, 0, $$e_{\mathrm{16}}$$ )	1/1/2−2	2−2	$${\mathit{Z}}_{\mathit{3}}$$
8	(0, 0)	( $$e_{\mathrm{16}}$$ , 0, 0, 0)	2−2/1/1	2−2	$${\mathit{Z}}_{\mathit{4}}$$
9	(0, 0)	(0, $$e_{\mathrm{16}}$$ , 0, 0)	2−2/1/1	2−2	$${\mathit{Z}}_{\mathit{1}}$$
10	(0, 0)	(0, 0, $$e_{\mathrm{16}}$$ , 0)	1/1/2−4	2−4	$${\mathit{Z}}_{\mathit{2}}^{\prime }$$
FT	(0, $$e_j$$ )	( $$e_{\mathrm{16}}$$ , 0)		1
Output ( $$\Delta Y$$ )	( $$e_{\mathrm{16}}$$ , $$e_j$$ ) = β
Total				2−22

We describe the way to construct the DCs in detail as follows.

• ( ${\mathit{Z}}_1$ )

The first rounds with the input and round key differences are $(0,0)$ and $(0,e_{16},0,0)$ , respectively, so the output difference of the first H is $e_{192}$ with probability 1 (Section 3.1.4(a)). Thence, since the input difference and the control vector difference of ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}$ are 0 and $e_{192}$ , the output difference of ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}$ is 0 with probability $\mathbf{E}\mathbf{1}={\mathrm{2}}^{-\mathrm{2}}$ (Section 3.1.3(b)). The output difference of G is 0 with probability $\mathbf{E}\mathbf{2}=\mathrm{1}$ when the input and the round key differences are 0 and 0, respectively (odd round cycle, $\mathbf{Q}=K_1\oplus K_3$ ). Plus, the output difference of ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ is 0 with probability $\mathbf{E}\mathbf{3}=\mathrm{1}$ since output difference of the second H is 0 with probability 1 (Section 3.1.4(b)). Finally, we can get that the output difference of function ${\text{Crypt}}^{(e)}$ is 0 with probability $2^{-2}$ in case the input differences are $(0,0)$ under the round key differences which are $(0,e_{16},0,0)$ . Apply the method ( ${\mathbf{Z}}_{\mathrm{1}}$ ) for the fifth round and ninth round to find the DC of them.

( ${\mathit{Z}}_2$ )

The second round with the input and round key differences are $(0,0)$ and $(0,0,e_{16},0)$ , respectively; so the output difference of the first H is 0 with probability 1. Thence, since the input difference and the control vector difference of ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}$ are 0 and 0, the output difference of ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}$ is 0 with probability $\mathbf{E}\mathbf{1}=1$ (Section 3.1.3(a)). The output difference of G is 0 with probability $\mathbf{E}\mathbf{2}=\mathrm{1}$ when the input and the round key differences are 0 and 0, respectively (even round cycle, $\mathit{Q}=K_2\oplus K_4$ ). Plus, the output difference of ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ is 0 with probability $\mathbf{E}\mathbf{3}={\mathrm{2}}^{-\mathrm{2}}$ (Section 3.1.3(b)) since output difference of the second H is $e_{32}$ with probability 1 (Section 3.1.4(b)). Finally, we can get that the output difference of function ${\text{Crypt}}^{(e)}$ is 0 with probability $2^{-2}$ in case the input differences are $(0,0)$ under the round key differences which are $(0,0,e_{16},0)$ . Apply the method ( ${\mathbf{Z}}_{\mathrm{2}}$ ) for the sixth round to find the DC of it.

Similarly, we can get the methods ( ${\mathbf{Z}}_{\mathrm{3}}$ ) and ( ${\mathbf{Z}}_{\mathrm{4}}$ ) with probabilities $2^{-2}$ since the input is $(0,0)$ and round key differences are $(0,0,0,e_{16})$ , $(e_{16},0,0,0)$ , respectively.

With the last round, we change a little the difference characteristics for the output of ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ support to our related-key differential attacks. The input and round key differences of ${\text{Crypt}}^{(e)}$ are $(0,0)$ and $(0,0,e_{16},0)$ . The output difference of ${\mathbf{F}}_{\mathrm{64}/\mathrm{192}}$ is 0 with probability $\mathbf{E}\mathbf{1}=\mathrm{1}$ (the output difference of the first H is 0). Thus, the output difference of G with the input and the round key differences being 0 and 0 is 0 with probability $\mathbf{E}\mathbf{2}=\mathrm{1}$ (Section 3.1.4(b)). Plus the output difference of the second H is $e_{32}$ with probability 1 (Section 3.1.4(a)); in this case, the input difference and the control vector differences of ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ are 0 and $e_{32}$ ; we get that the output difference ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ is $e_j$ with probability $2^{-4}$ (Section 3.1.1). Finally, for the last round, the related-key differential characteristic holds the probability $2^{-4}$ .

See the Appendix for more description.

3.3. The First Related-Key Differential Attack on COSB-128

Based on the related-key DC we have constructed, we can recover a part of master key of COSB-128.

At first, we encrypt 2²³ plaintext pairs $(P,P^{*})$ and $\Delta P=P\oplus P^{*}=(0,e_{16})$ to get 2²³ corresponding ciphertext pairs $(C,C^{*})$ under an unknown key $K=(K_1,K_2,K_3,K_4)$ and an unknown related key $(K_1,K_2\oplus e_{16},K_3,K_4)$ . While the probability of related-key differential characteristics of COSB-128 is $2^{-22}$ , we expect there are at least 2 ciphertext pairs $(C,C^{*})$ with the difference $(e_{16},e_j)$ for each j, where $1\le j\le 64$ . So, with the DC described in Table 2, we can infer the jth one-bit difference where the ciphertext pairs $(C,C^{*})$ are given from the output differences of ${\mathbf{F}}_{\mathrm{1}/\mathrm{2}}^{{\mathbf{V}}_{\mathrm{6}}^{\mathbf{\prime }\mathrm{32}}}$ in ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ at the last round (refer to Figure 3). Thence, it can be expected that the differential route given is unique and we are able to retrieve 6 bits of controlling vectors for this route.

Figure 3

The possible routes of the ${\mathbf{F}}_{64/192}^{-1}$ on the last round.

The related-key differential attack on the full-round COSB-128 is as follows.

• (1)

Choose a pool of 2²³ plaintext pairs $(P_i,P_i^{*})$ with difference $\Delta P=\alpha =P\oplus P^{*}=(0,e_{16})$ . Then, with the chosen plaintext attack, we encrypt the plaintext pairs using $(K,K^{*})$ to get the ciphertext pairs $(C_i,C_i^{*})$ , in which $\Delta K=K\oplus K^{*}=(0,e_{16},0,0)$ .

(2)

For each i and j, check if $C_i\oplus C_i^{*}=(e_{16},e_j)$ , where $1\le i,j\le 64$ .

(3)

We assign j-BPO the bit-one positions of j. Then, with the number of ciphertext pairs satisfying the conditions at (2), we can extract some bits of the control vector through the difference route of the j-BPOs and the position of the 64th input bit of ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ (see Figure 3). From this point, because the control vector $V_{\mathrm{2}}$ of ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ in last round is in form of $C_L\oplus K_3$ , $C_L\oplus K_3\oplus K_4$ , and $C_L$ , we are able to find some corresponding bits of $K_3$ and $K_3\oplus K_4$ .

The data complexity of this attack is 2²⁴ related-key chosen plaintexts. The time complexity of (1) is about 2²⁴ full round COSB-128 encryptions and the time complexities of (2) and (3) are much less than that of (1). Also, each ciphertext pair passes (2) with probability of at least $2^{-22}$ ; thence, the ciphertext pairs with $(e_{16},e_j)$ difference are expected to be at least 2. It means, for each j ( $1\le j\le 64$ ), we have at least one ciphertext pair meets the $(e_{16},e_j)$ difference. So, we expect to retrieve 56-bit keys information of ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ and 7-bit keys information of ${\mathbf{F}}_{64/192}$ with the data and time complexities of 2²⁴.

3.4. The Second Related-Key Differential Attack on COSB-128

For increasing the differential probability, we propose the second attack by constructing another related-key differential characteristic on COSB-128 with probability $2^{-20}$ . In fact, we assume the probability of differential patterns of the 2nd, 3rd, 4th, 5th, and 6th layers in the box ${\mathbf{F}}_{64/192}^{\mathbf{-}\mathrm{1}}$ at the last round is 1. It means the bit-one input difference of the 32th ${\mathbf{F}}_{\mathrm{2}/\mathrm{1}}$ always gets the direction to the j-bit output difference of the 6th layer. Also, the probability is 1 because when the input difference is $(0,1)$ and controlling vector difference is 0 of ${\mathbf{F}}_{\mathrm{2}/\mathrm{1}}$ , the corresponding hamming weight of output difference is always 1. Then, we can recover a 6-bit key with data complexity being about 2²² related-key chosen plaintexts with time complexity of about 2²² full round COSB-128 encryptions.

The second related-key differential attack on COSB-128 is as follows.

• (1)

This step is same as the algorithm applied on the Step (1) of the first related-key differential attack on COSB-128 in Section 3.3.

(2)

For each i, check if $C_i\oplus C_i^{*}=(e_{16},e_j)$ , where $1\le j\le 64$ .

Thus, we can extent this attack to retrieve the whole of master key pair $(K,K^{\prime })$ by applying an exhaustive search for the remaining keys. The exhaustive search takes a running time of 2²⁵⁰ encryptions and recovers the full key with the same data complexity and time complexity of about 2²⁵⁰ full-round COSB-128 encryptions.

4. Conclusion

The network-environment devices and services have increased rapidly in recent years. It leads the cryptography to new way; it does not only offer protection for stability to all known attacks, but also needs to be optimized on software-hardware implementations and suitable for most constrained environment applications in communication networks nowadays. In order to construct fast block encryption algorithms for ensuring high speed encryption in data transformation, the data-dependent controllable operations have been highly used.

While the operational permutation blocks (RC5, RC6, etc. [3]) still remain limitations in protective data transformation, COSB-128 [8] is a 128-bit block and 256-bit key, which uses the controllable operational substitutions in the concept of CPB [9], is proposed to give a good performance and be stable to most known cryptanalyses.

In this paper, we constructed the two related-key differential characteristics of a full 10-round of COSB-128 cipher with high probabilities based on some differential properties combined with the simple key schedule within COSB-128 structure. Then, it enables us to propose the two related-key differential attacks on COSB-128. Our attacks require 2²⁴ and 2²² related-key chosen plaintexts, respectively, with the time complexities of 2²⁴ and 2²² full-round COSB-128 encryptions, to recover 63 bits and 6 bits key information, respectively. This research is the first known cryptanalytic result on COSB-128 so far. Furthermore, it is hoped it will extend a new potential with better performance for cryptanalysis on this algorithm with type of ciphers in further research.