On mathematical models of key mixing for iterative block encryption algorithms

For a binary symmetric iterative block encryption algorithm A with r rounds, the following notation is used: k is a key of A, k E V = [GF(2)]^Z; x - x1x2... x_n is an information block, x E V^; q is a round key, q E УЛ; ф^, q) is the round function; q» is an i-th round key, i E {1, 2,..., r}; фqi : K, ^ Vn is the i-th round substitution, ф_щ(x) = ф^^); Ф_р = ф_9р · ... · ф₉₁ is the p-round substitution, p E {1,..., r}; p is the minimal p (if exists) such that every bit in k is an essential argument for the function Ф_р; p(qj), the exponent of q^ and p(k), the exponent of k, are the least p (if exist) such that every coordinate function of Ф_р essentially depends on each bit in q» and k respectively; A is a Boolean matrix (aj)_nxn, where aj = 1 iff j-th coordinate function of ф^^) essentially depends on xj, i E {1,...,n}; matrix A⁴(/*) is obtained from A* by removing rows with the numbers which aren't in a set I, 0 = I С {1,..., n}; I*-exp A is the (local) I*-exponent of A, that is, the least integer 7 (if exists) such that, for any t ^ 7, the matrix A⁴(/*) consists of positive integers; B_q. is the set of numbers of coordinates in k which q» essentially depends on. Let B_qi П B_qj = 0 for all i, j E {1,... ,p}, i = j. Then the following statements are true: 1) if Ф_г(x, k) depends on each bit of k, then p(k) = p(1) + (p - 1) and p(q») = p(1) + (i - 1), i = 1,... ,p; 2) if {1,...,/} = B_qi U ... U B_qp, n = A, and h and h' are any substitutions on V\, then p(k) ^ I*-exp A + (p - 1) for I = {1,..., n} in case ф^^) = h(x ф q) and for I = {1} in case ф^, q) = h'((x + q)mod 2^Л). As a consequence, if A is the Feistel algorithm, where x = x'x'', |x'| = |x''| = n/2, and ф^, q) = (x'', x' ф - (x'', q)), then p(k) ^ I*-exp A + (p - 1) for I = {n/2 + 1,..., n} in case ^(x", q) = h(x" ф q) and for I = {n/2 + 1} in case ^(x",q) = fc'((x" + q) mod 2^Л). Particularly, p(k) ^ 10 for GOST 28147-89.

Keywords

Authors

References