Substitution block ciphers with functional keys | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 38. DOI: 10.17223/20710410/38/4

We define a substitution block cipher C with the plaintext and ciphertext blocks in Fn and with the keyspace K_s0,_n(g) that is the set {/(x) : f (x) = ))); ai,a₂ e Fn;n₁,n₂ G S_n}, where so is an integer, 1 ^ so ^ n; g : Fn ^ Fn is a bijec-tive vector function g(x) = g₁(x)g₂(x) ...g_n(x) such that every its coordinate function gi(x) essentially depends on some Si ^ s₀ variables in the string x = x₁x₂ .. .x_n; S_n is the set of all permutations of the row (12... n); n_i and a_i are the permutation and negation operations, that is, (n = (i₁i₂ ... i_n)) ^ (n(a₁a₂ ... a_n) = a_il a_i2 .. . . . ^ain ⁾, (a = b₁b₂ .. .bn) ^ ((a₁a₂ ... a_n)^ = a^₁¹ a2²... a^) and, for a and b in F₂, a^b = a if b = 1 and a^b = -a if b = 0. Like g, any key / in K_s0,_n(g) is a bijection on Fn, / (x) = f₁(x)/₂(x) ...f_n(x), and every its coordinate function f_i(x) essentially depends on not more than so variables in x. The encryption of a plaintext block x and the decryption of a ciphertext block y on the key f are defined in C as follows: y = f (x) and x = f^-1(y). Here, we suggest a known plaintext attack on C with the threat of discovering the key f that was used. Let P₁ ,P₂,..., P_m be some blocks of a plaintext, C₁, C₂,..., Cm be the corresponding blocks of a ciphertext, i.e., Ci = f (Pi) for l = 1,2,... ,m, and Pi = Pi1Pi2 ... Pin, Ci = СцС12 ... Cin. The object is to determine the coordinate function f_i(x) of f for each i G {1,2,...,n}. The suggested attack consists of two steps, namely we first determine the essential variables x_il,...,x_is of f_i(x) and then compute a Boolean function h(x_il,...,x_is) such that h(a_il,... ,a_is) = f_i(a₁,..., a_n) for all n-tuples (a₁a₂ ... a_n) G Fn. For determining the essential variables of f_i, we construct a Boolean matrix || inf D(f_i)|| with the set of rows inf D(fi), where D(fi) = {Pi 0 Pj : Cii = Cji; l,j = 1, 2,..., m}, Cii = fi(Pi), l = 1,...,m, i = 1,...,n, and infD(f_i) is the subset of all the minimal vectors in D(f_i). Then the numbers of essential variables for f_i are the numbers of columns in the intersection of all covers of || inf D(f_i)|| with the cardinalities not more than s₀, where a cover of a Boolean matrix M is defined as a subset C of its columns such that each row in M has ’1’ in a column in C. For computing h(x_il,... ,x_is), we first set h(P_iil,..., P_iis) = C_ii for l = 1,..., m and then, if h_i is not yet completely determined on F2, we increase the number m of known blocks (P_i,C_i) of plain- and ciphertexts or extend h_i on F2 in such a way that the vector function h = h₁h₂ ... h_n with the completely defined coordinate functions is a bijection on Fn. We also describe some special known plaintext attacks on substitution block ciphers with keyspaces being subsets of K_s0,_n(g).