☝️ 🔥 🥦 Linear cryptanalysis on the example of the block encryption algorithm NUSH 💅🏾 🔦 🤜🏻

Introduction

In the modern world, there is an acute question about the confidentiality of data during their exchange and storage, which is achieved through all possible methods of encryption. However, with the advent of new encryption algorithms, work begins to study ways to violate the confidentiality of data, that is, they are looking for attacks on them.

Nowadays, block encryption algorithms such as AES, "Grasshopper", etc. are widely used. Linear cryptanalysis is one of the potentially effective methods of attacking them. The basic concept of this method was presented by Mitsuru Matsui in his work “Linear Cryptoanalysis Method for DES Cipher” [1] in the 90s. The essence of this method will be described in section 2 of this article.

As an example of effective use of this method, a linear cryptanalysis of the block encryption algorithm NUSH [2] is presented , a brief reference to which will be given below.

Fundamentals of Linear Cryptanalysis

As it was written above, the essence of linear cryptanalysis is described in the “Linear Cryptoanalysis Method for DES Cipher”. When using linear cryptanalysis, it is assumed that the structure of the cipher is known and that the cryptanalyst has a sufficient statistical sample “ciphertext-public key” obtained on a single key.

After meeting the above requirements, the structure of the algorithm is replaced with a simple linear function. As a rule, the analysis of linear functions is much simpler than of nonlinear functions of the cipher itself, which can reduce the problem of analyzing a cipher to the analysis of its linear modification. Further, from the obtained system of functions, the cryptanalyst guesses the key bits with a certain probability.

Let the <x,y> = x_1*y_1+x_2*y_2+...+x_n*y_n dot product of binary vectors modulo 2. And let the P,C,K plaintext, ciphertext and key, respectively.

Definition 1

$<P,\alpha>\oplus<C,\beta>=<K,\gamma>$

$1 \backslash 2 + \varepsilon$ $\varepsilon$ , $\ \alpha, \beta, \gamma$ - .

, .

(Pilling-up , “ ”)

X_i $1 \leq i \leq n$ - , $\mathbb {Z}_2$ .

$P \{X_i = 0\} = 1 \backslash 2 + \varepsilon_i$

$1 \leq \varepsilon_i \leq 1 \backslash 2$ . $X_1 \oplus X_2 \oplus ... \oplus X_n$ 0 $1 \backslash 2 + \varepsilon$ , $\varepsilon = 2^{n-1} \prod^{n}_{i=1} \varepsilon_i$

1: $\varepsilon_j = 0$ , $j \in \overline{1,n}$ .

NUSH

2000 NESSIE , , LAN Crypto – NUSH. , (64, 128, 192 256 ).

S- P-, (XOR, AND ..). . , , O(k) , k – .

N = 4n — P = P_0 P_1 P_2 P_3 . KS_i (start key) . : $a_0 b_0 c_0 d_0 = P_0 P_1 P_2 P_3 \oplus KS_0 KS_1 KS_2 KS_3$ . r-1 , KR_i (subKey) - , # — , , C_i,S_i , $\gg j$ — j :

${ for ( i=1...r-1 ) \\ a_i = b_{i-1} b_i=((c_i \oplus (KR_{i-1}+C_{i-1}))+b_{i-1}) \gg S_{i-1} \\ c_i = d_{i-1} \\ d_i = a_i \oplus (b_i \# d_i)}$

${a_r = a_{r-1} + (c_r \# d_{r-1}) \\ b_r = b_{r-1} \\ c_r = ((c_{r-1} \oplus (KR_r+C_{r-1})+b_{r-1})) \gg S_{r-1} \\ d_r = d_{r-1}}$

: $M_0 M_1 M_2 M_3 = a_r b_r c_r d_r \oplus KF_0 KF_1 KF_2 KF_3$

${d_{r-1} = d_r \\ b_{r-1} = b_r a_{r-1} = a_r - (c_r \# d_{r-1}) \\ a_{r-1} = a_r - (c_r \# d_r{r-1}) \\ c_{r-1} = c_r \gg (n- S_{r-1}) }$

r-1

${ for(i=r-1...1) \\ d_{i-1} = c_i \\ b_{i-1} = a_i \\ a_{i-1} = d_i - (b_i \# c_{i-1}) \\ c_{i-1} = (b_i \gg (n-S_{i-1}))-KR_{i-1}-a_{i-1}}$

NUSH

, , , 1

${ a_i[0] = b_{i-1}[0] \quad (1) }$

$f(x,y)=x \# y$ . , p=0.75 p=0.25 . p=0.75 p=0.25 d_i :

${d_i = a_{i-1}[0] \oplus b_i[0] \oplus d_{i-1}[0] \quad (2)}$

(1) (2) p=0.75

$a_i[0] \oplus b_i[0] \oplus d_i[0] = a_{i-1}[0] \oplus b_{i-1}[0] \oplus d_{i-1}[0] \oplus \theta \quad (3)$

$\theta = 0$ # “AND” $\theta = 1$ # “OR”.

, .

$a_1[0] \oplus b_1[0] \oplus d_1[0]$ . , S_0 = 4 , b_1[0] c_0[0-4] , b_0[0-4] , KR_0[0-4] .

5 c_0 . $a_1[0] \oplus b_1[0] \oplus d_1[0]$ a_0[0-4] , b_0[0] , c_0[0] , d_0[0-4] , KR_0[0-4] C_0[0-4] .

f_1 :

$a_1[0] \oplus b_1[0] \oplus d_1[0] = f_1 \begin{pmatrix} P_0[0], P_1[0-4], P_2[0-4], P_3[0], \\ KS_0[0], KS_1[0-4], KS_2[0-4], KS_3[0], KR_0[0-4] \end{pmatrix} \quad (4)$

$a_2[0] \oplus b_2[0] \oplus d_2[0]$ . , $a_2[0] \oplus b_2[0] \oplus d_2[0]$ $P_3[0] \oplus KS_0[0]$ , $P_2[0-11] \oplus KS_1[0-11]$ , $P_1[0-11] \oplus KS_2[0-11]$ , $P_0 [0-7] \oplus KS_2[0-7]$ , KR_0 [0-11] KR_1[0-7] . f_2 :

$a_2[0] \oplus b_2[0] \oplus d_2[0] = f_2 \begin{pmatrix} P_0[0-7], P_1[0-11], P_2[0-11], P_3[0], \\ KS_0[0], KS_1[0-11], KS_2[0-11], KS_3[0-7], KR_1[0-7] \end{pmatrix} \quad (5)$

$a_3[0] \oplus b_3[0] \oplus d_3[0]$ . , $a_3[0] \oplus b_3[0] \oplus d_3[0]$ , KS_0[0-11] , KS_1 , KS_2 , KS_3 , KR_0 , KR_1[0] KR_2[0-11] . f_3 :

$a_3[0] \oplus b_3[0] \oplus d_3[0] = f_3(P, KS_0[0-11], KS_1, KS_2, KS_3, KR_0, KR_1, KR_2[0-11]) \quad (6)$

$a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0]$ . ,

${ d_{32}[0] = c_{33}[0] \\ b_{32}[0] = a_{33}[0] \\ a_{32}[0] = d_{33}[0] \oplus (b_{33}[0] \& c_{32}[0])} \quad { \space \\ (7)}$

$a_{32}[0] b_{32}[0] c_{32}[0] d_{32}[0]$ $a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0]$ . $a_{34}[0], b_{34}[0], c_{34}[0], d_{34}[0]$ $KR_{33}[0]$ . , $a_{35}[0,1], b_{35}[0,1], c_{35}[0,1], d_{35}[0,1]$ $a_{36}[0,1], b_{36}[0,1], c_{36}[0,1], d_{36}[0,1]$ $KR_{35}[0]$ .

, $a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0]$ M_0[0,1] , M_1[0-2] , M_2[0,12] , M_3[0,1] , KF_0[0] , KF_1[0,12] , KF_2[0-2] , KF_3[0,1] , $KR_{33}[0]$ , $KR_{34}[0]$ , $KR_{35}[0]$ , , . f_4 :

$a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0] = f_4 \begin{pmatrix} {M_0[0,1], M_1[0-2], M_2[0-12], M_3[0,1], \\ KF_0[0,1], KF_1[0-12], KF_2[0-2], KF_3[0,1], \\ KR_{33}[0], KR_{34}[0], KR_{35}[0] } \end{pmatrix} \quad (8)$

$a_{31}[0] \oplus b_{31}[0] \oplus d_{31}[0]$ f_5 :

$a_ {31} [0] \ oplus b_ {31} [0] \ oplus d_ {31} [0] = f_5 \ begin {pmatrix} {M_0 [0-9], M_1 [0-11], M_2 [0 -12], M_3 [0,1], \\ KF_0 [0,1], KF_1 [0-12], KF_2 [0-11], KF_3 [0-9], \\ KR_ {32} [0] , KR_ {33} [0], KR_ {34} [0], KR_ {35} [0-9]} \ end {pmatrix} \ quad (9)$

. (3) , 29-

$a_2 [0] \ oplus b_2 [0] \ oplus d_2 [0] = a_ {31} [0] \ oplus b_ {31} [0] \ oplus d_ {31} [0] \ quad (10)$

$1/2 + 2 ^ {- 30}$ .

${f_2 (P, KS_0 [0], KS_1 [0-11], KS_2 [0-11], KS_3 [0-7], KR_1 [0-7]) = \\ = f_5 \ begin {pmatrix} {M , \\ KF_0 [0,1], KF_1 [0-12], KF_2 [0-11], KF_3 [0-9], \\ KR_ {32} [0], KR_ {33} [0], KR_ {34} [0], KR_ {35} [0-9]} \ end {pmatrix}} {\ space \\ \ space \\ \ quad (11)}$

NUSH , (11) m_0 - . , .

1. $K ^ i (i = 1, ..., 2 ^ {m_0})$ T_i - , (11).

2. T_j T_i , K ^ j .

3. , .

The article presents the basic concept of linear cryptanalysis and considers an example of its application in the analysis of the NUSH encryption algorithm.

Literature

1. Mitsuru Matsui, Linear cryptoanalysis method for DES cipher, Advances in Cryptogy-Eurocrypt'93, Berlin: Springer-Verlag, 1993, 386-397.

2. Wu Wenling & Feng Dengguo, Linear cryptoanalysis of NUSH block cipher, Science in China (Seria F), February 2002, Vol. 45, no. 1.

3. M. Heys, A Tutorial on Linear and Differential Cryptoanalysis, Cryptologia, June 2001, Vol. 26 No. 3.

4.https://www.youtube.com/watch?v=nEHVfeaPjNw

Linear cryptanalysis on the example of the block encryption algorithm NUSH

Introduction

Fundamentals of Linear Cryptanalysis

NUSH

NUSH

Literature

More articles: