Key schedule based on a modified additive generator.pdf 1. Introduction The key schedule is an important component of any iterated block cipher. The first versions of key schedules (DES, GOST 28147-89) involved bit sampling from the cipher key which gives the cryptanalyst grounds for attacks such as differential analysis. In AES, the generation of round keys is more complex and requires a non-stationary recurrence relation over a set of binary vectors. The Kuznechik algorithm provides a complex key dependency using the Feistel network. The goal of key schedule algorithms is to combine a complex functional relationship between the bits of the cipher key and the round keys with a relatively low computational complexity of key generation. This paper proposes a round key generator (RKG) based on a modified additive generator and, in addition, on MAG and a linear congruent generator (LCG) in a series circuit. 2. Additive generator The additive generator (AG) is a shift register of length n with feedback f(zo, . . . , zn-1) over the space of binary r-dimensional vectors, i.e., a register transformation of the set Vnr = {(zo, . . . , zn-1) : zo, . . . , zn-1 G Vr}: ^(zo ,...,Zn-1) = (zi,...,z„_i,f (zo,.. zn- 1 )) , (1) where the function f: Vnr Vr is the shift register feedback function. The AG feedback has the following form: f (z0,..., zn-1) = z0 И z2 И z4 И z6, where И is addition modulo 2r, that is, f is bijective on the variable z0, hence the transformation is also bijective [1]. It has insufficient mixing: the leading bits of all vectors depend only on the least significant ones. Therefore, a transformation of the modified AG is proposed, in which the vector value of the feedback is transformed by permutation g of the set Vr. The feedback of the MAG is denoted by fg. It is proved that the transformation (z0,...,zn_1) is bijective if and only if the function is bijective and g is a permutation [2]. The MAG is studied given r = 32, where the transformation g(k) is a cyclic shift permutation of binary vectors by k bits towards the leading bits. Hence ^g(k) is a bijection of the set Vnr, and the feedback function has the form fg(k)(zo,... ,zn_1) = Int32(g(k)(Vec32(zo И Z2 И Z4 И z6))), (2) where Vec32: Z232 V32 is a bijection that maps a number X G Z232 to its binary representation, Int32 = Vec3_21 is the inverse function. Given t = 0, 1, 2, . . ., we denote: • g(k) - left cyclic shift by 1 bit (k = 1); • Xj^ - the state of the j-th MAG cell at t, j = 0,1,..., 6; • X(t) = (X((t), X(t),..., x6^) - the state of the MAG at t; • X(0) - the initial state of MAG. The key of MAG is its initial state. From (1) and (2) we get: X(t+1) = (X(t),...,X6t),g(k)(X0t) И X^ И X^ И X^)). (3) A round key sequence is formed as an irregular sample from the sequence {X0(t)}, t = = 0, 1, 2, . . . 3. Cyclic structure of the MAG state digraph To avoid repetitions in the sequence of round keys, short cycles of length less than 300 are undesirable in the cyclic transformation structure (this limit is determined by the required number of round keys in a number of block ciphers). The structure of the MAG state digraph was studied. We denote by r(^g(k)) the ^g(k) transformation digraph, i.e., r(^g(k)) = (V224,E), where E is the set of arcs. The arc (zi,zj) exists if ^g(k)(zi) = zj. The digraph r(^g(k)) has one self-loop generated by the zero fill of MAG. The cyclic structure of the digraph r(^g(k)) was studied given k =1, r = 4,5,6 (as r increases, the computational complexity increases rapidly). Using an algorithm that generates a sequence of MAG states, 11 cycles at r = 4, more than 18 cycles at r = 5, and more than two cycles at r = 6 are found in the corresponding digraphs. In Table 1, the lengths of the found cycles are provided. At r = 32, the lengths of the cycles are also experimentally evaluated. We assume 108 generated pseudorandom numbers as initial values. For each of the numbers assumed 1000 clock cycles of the generator are implemented (which is enough to generate all the round keys). It is obtained that the length of all cycles exceeds 1000, which excludes repetitions in the sequence of round keys. The results of the experiment given r = 32 suggest that a randomly chosen state of MAG with a probability close to 1 belongs to a cycle of the length greater than 1000. Ta b l e 1 Cycles lengths Cycle number Length, r = 4 Length, r = 5 Length, r = 6 1 234 711 845 16 871 058 994 837 124 439 025 2 17 076 802 13 808 636 426 117 617 876 965 3 15 925 876 1 965 696 526 4 305 050 1 122 723 601 5 208 004 233 097 005 6 91 195 151 954 479 7 67 889 65 351 609 8 28 603 43 458 018 9 11 552 41 627 677 10 7 497 29 128 117 11 1 142 14 671 598 12 10 296 293 13 1 134 118 14 460 091 15 212 519 16 120 918 17 62 980 18 22 785 4. Round keys generator using LCG In a RKG based on the MAG and LCG series circuit, the key is the initial state of LCG and MAG. The recurrence of the LCG can be represented as Xn+1 = (aXn + c) mod m, n > 0, where a is a multiplier, m is a modulus, c is a shift and X0 is an initial value. Recommended LCG parameters: a = 1, m = 232, c is an odd number, guaranteeing the full-cycle permutation of LCG [3]. The MAG+LCG automaton model's transition function is injective regarding the input variable, hence the period length of the sequence of GRK states is a multiple of the period length of LCG, that is a multiple of 232 [4]. From (3) we get X(t+1) = (X1t),..., X6t),g(k)(X0t) ffl x24) ffl x4 ffl X^) ffi (Ko ffl c(t + 1))), where K0 is the lowest 32 bits of the initial key, c G Z232 is an odd number, t = 1, 2, 3, . . . is the sequence number of iteration of the RKG. Consequently, the period length of the sequence {Xo(t)} is guaranteed to be at least 232. 5. Mixing properties and nonlinearity The RKG parameter k influences the key schedule properties of nonlinearity and mixing. These properties are evaluated using the local exponent of the mixing digraph for RKG state permutations (according to the matrix-graph approach [5]). After evaluation, the properties are determined experimentally. The experiment results are presented here given different k. The least number of the RKG clock cycles is found after which each vector {Xo(t)} coordinate depends essentially and nonlinearly on each initial state bit. In Table 2, the results for k = 1, 3, 5 are provided. Ta b l e 2 Experimental evaluation of total mixing and nonlinearity characteristics k Round t of total mixing Round t of nonlinearity 1 30 33 3 18 20 5 16 18 6. Conclusion Advanced characteristics of RKG based on MAG are shown both with and without the use of LCG. In the first case, the structural properties of the permutation states of RKG are guaranteed by the LCG parameters. In the second case, they are justified experimentally. The computational complexity of the round key generation method is low, which can be explained by uncomplicated implementation of MAG and LCG. The presented method of key schedule generation can be used in many iterated block ciphers, in particular, the method is recommended for wide-block algorithm KB-256.

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