The difference relations and impossible differentials construction for the KB-256 algorithm.pdf 1. Introduction The existence of a difference relation for a block cipher algorithm may indicate the possibility of developing efficient key recovering methods. We show that difference relations discovered for a block cipher algorithm can be efficiently used for key recovery computation (as compared to exhaustive key search) for the nine-round KB 256-3 algorithm. The existence of an impossible differential for a block cipher algorithm enables cryptanalysts to recover information about encrypted blocks. 2. Description of the KB 256-3 encryption algorithm The KB 256-3 encryption algorithm, based on the generalized Feistel network, was proposed in [1, 2]. Next, the algorithm description is provided. We introduce notations as follows: - ffl - the addition modulo 232; - ф - the XOR of two binary strings of the same length; - Vn - a set of binary strings of length п G N, where V = {0,1}; - K = (K0, K1,..., K7), where Kj G V32, j = 0,..., 7, - an encryption key; - Qi = (qo.i,q1.i,q2.i), where qo.», q1.», q2.» G V32, i = 1,..., 16, -round keys, derived from the encryption key. Encryption of a 256-bit block X = (X0, X1, X2, . . . , X7), where Xj0 G V32, j = 0, . . . , 7, with an encryption key K can be performed by applying 16-round functions R, in sequence. Each of these functions depends on three 32-bit round keys (q0i, q1i, q2i), i = 1, . . . , 16 (i.e., each round of encryption uses three round keys). We denote the round transformation of the KB 256-3 encryption algorithm by R : V256 x V96 V256. As a result, after the round i G {1, . . . , 16}, the block X G V256 encrypted with the key K can be written as R(. . . R(R(X0, Q1), Q2)), . . . , Qi) = Xi = (X0i, X1i, . . . , X7i). We introduce the additional notation: F(X, K) = R(. . . R(R(X, Q1), Q2)), . . . , Q16). 3. Round transformation We define a round transformation. We use notations as follows: 1) E(A0, A1,..., A7) = A1 ffl A3 ffl A4 ffl A6 ffl A7, where Ai G V32, i = 0,..., 7; 2) f(a0, a1, . . . , a7)=T(s0(a0), s1(a1), . . . , s7(a7)), where 4-bit permutations s0, s1, . . . , s7 are taken from [3], T is the left cyclic shift of a 32-bit string by 19 positions, ai G V4, i = 0, . . . , 7. Hence, the round transformation can be written as R (A, (b0, b1, b2)) = = (A1, A2 ф f (^(A) ffl b0^ A3, A4 A5 ф f (^(A) ffl b1), A6, A7, Ao ф f (^(A) ffl b2)). 4. Round key sequence To construct a sequence qj based on the key K = (K0, K1, . . . , K7), Kj G V32, j = = 0, . . . , 7, we use the non-linear shift register with а G V32 as a parameter. The initial state of the register is: q1 = K0, q2 = K1, q3 = K2, q4 = K3, q5 = K4, q6 = K5, q7 = K6; q» = T [q»_1 ffl q»_3 И q»_5 И qi-7] И K7 ffl (i - 7)a, where i G {8, . . . , 123} and T1 is a left cyclic shift of a string from V32. 5. Difference relation We define the difference relation for the algorithm under study. Let X0. X ? be plaintexts: 0 0 0 0 0 0 0 0 0 Л = (^X? ,Xi , X2 , X3 ,X4 ,X5 ,X6 ,X7) . X? = (Xj,x? ® 231, X0, X;?. X4, X0, X6 ф 231, X?). It is evident that X? ф X? = (0. 231.0. 0. 0. 0. 231.0). For plaintexts X? и X? and any round keys Q1. Q2.... . Q6 G V96 the following equations hold: R(... R(X?. Qi)..... Qi) ф R(... R(X?. Qi).....Qi) = Ci. where i = 1..... 6 and constant C1. C2..... C6 are C1 = (2;1.0.0.0.0.2;1.0.0); C2 = (0.0.0.0.2;1.0.0.2;1); C; = (0.0.0.2;1.0.0.2;1.0); C4 = (0.0.2;1.0.0.2;1.0.0); C5 = (0.2;1.0.0.2;1.0.0.0); C6 = (2;1.0.0.2;1.0.0.0.0). Thus, the difference relation with probability 1 for the six-round algorithm is provided. 6. Difference relation attack on 9 rounds We consider the truncated KB-256 algorithm which comprises 9 encryption rounds. The algorithm structure besides the number of rounds is similar to that of the original algorithm. Let X? and X? be plaintexts such that X? фX? = C?. The encrypted plaintexts X9. X9 are known to the cryptanalyst. It is also known that X6 фХ6 = (231.0. 0. 231.0. 0. 0.0). Due to the algorithm functioning principles, the following equations hold: 68 X4 = X2 ; X76 = X58. The equations are easy to verify. Next, we demonstrate how round keys q19. q29 can be recovered. For ease, we denote a = q19, b = q29. The cryptanalyst derives: Yi = Xi9 ф f (X?9 ffi X29 ffi X39 ffi X59 ffi X69 ffi a); Y2 = x9 ф f (x9 и x9 и x; и x9 и x6 и a). () The Y1. Y2 values potentially coincide X8 and X8 respectively. It is known that X8 = X2. So for the key a the following equation holds: Y1 = Y2. The b key can be recovered in the same way. Generally, it is possible that for several a values equations 1 hold. In this section, we study the KB-256 algorithm properties without delving into the key recovery algorithm. Therefore, for ease, we assume that having a single a, the equations 1 hold. Obviously, recovering a round key allows recovering the key within approximately 2224 operations. By operation we assume encryption of a block using KB-256. 7. Finding an impossible differential for the KB-256-3 algorithm In this section, we prove that an impossible differential exists for the KB-256 algorithm. We assume that an impossible differential for the encryption algorithm E : Vn x Vk Vn is the pair D1. D2 G such that for any key K G Vk and for any X. X G Vn such that X ф X = D1 the inequality holds: Ek (X) ф Ek (X) = D2 If an impossible differential exists, in some cases, it is possible to design an effective attack on block algorithms [4]. In general, this property enables a cryptanalyst to gain some information about the plaintext from the ciphertext. We demonstrate that there exists an impossible differential D1 , D2 for the KB-256 algorithm, where D1 = (0, 231, 0, 0, 0, 0, 231, 0), D2 = (231, 0, 0, 231, 0, 0, 0, 0). By verification, a cryptanalyst can make sure that the text pair X, X such that X ф X = (0, 231,0, 0, 0,0, 231, 0), after 8 rounds, becomes the pair X8,X8 such that X8 фX8 = (t1, t2, 0, t3,t4, 0, t5, t6) for some non-zero vectors t1, t2, t3, t4, t5,t6 G V32. We note that t1,t2,t3,t4, t5,t6 depend on each pair X,X. In Table 1, the differences between texts after each of 8 rounds are presented. Ta b l e 1 Round no. Difference 1 (231, 0, 0, 0, 0, 231,0, 0) 2 (0, 0, 0, 0, 231, 0, 0, 231) 3 (0, 0, 0, 231,0, 0, 231,0) 4 (0, 0, 231,0, 0, 231,0, 0) 5 (0, 231,0, 0, 231, 0, 0, 0) 6 (231, 0, 0, 0, 0, 231,0, 0) 7 (0, ◦, 231, 0, ◦, 0, 0, ◦) 8 (tl,t2,0,

Скачать электронную версию публикации