2001-05-02

Security proof

The insecurity level of a keyed function is by convention defined as the probability that you might distinguish it from a random function after a certain number of queries to it using any distinguisher. (cf Goldwasser & Bellare 1999) The task at hand is to (1) find an appropriate way to model Steak as a structure of keyed functions, (2) model the way these functions are promoted, and (3) find the most effective distinguisher for each of these functions.

Firstly, let F_k: {0,1}⁸ => {0,1}⁸ be the function such that k is the key data of Steak, and F_k(x) is the key stream output of Steak given the key data k and the preceding cipher text byte x. If the vector size is large enough, this function has a very low insecurity level. In order to prove so, the following observations should be made:

Proposition 1: Let h be a selector of any combination of 256 distinct elements out of a set of at least 65536 of the least natural numbers. Let the injective function G_h: {0,1}⁸ => {0,1}³² be such a combination. Then, for any random function g: {0,1}⁸ => {0,1}⁸, there is an h such that for all x we have that g(x) = G_h(x) mod 256.

Now, let’s structure the function F_k in the following manner: Let Gⁱ_k: {0,1}⁸ => {0,1}³² be the dynamic key data generator of F_k at round i. Then for all x we have that F_k(x) = L_k(Gⁿ_k(x)) mod 256, where n is the vector size, and the function L_k simply undoes the key data feedback of the last round. Furthermore, due to the PV-pipe of the feedback process, we have that the 256-element combination corresponding to the function Gⁱ_k has a selector corresponding to the preceding round function G^i-1_k. In other words, since the main function of Steak is bijective, the probability increases with the vector size of Steak that for any random function g there is an equivalent function F_k. The bijectivity of the main function also ensures that the number of collisions for each F_k in the set {F_k} converges to a constant function of k as the vector size increases. This means that for all practical purposes the function F_k might be modeled as a random function.

Secondly, we ought to prove that the process of selecting the next function F_x°k also might be modeled as a random function.

However, one ought to notice that there would be a potential weakness to any such proof. For each of the 2²⁰⁴⁸ possible g there is only a limited number of keys k such that F_k is equivalent to g. If this set is known, then for each cipher text x it would be trivial to compute the set of possible functions F_x°k. For all we know it would be an immensely complex task to find the set {k} corresponding to a random function g since the set of all keys is larger than 2⁶⁰⁰⁰, but we can’t prove that it can’t be done. 

One should also note that there are more than 2⁴⁰⁰⁰  full sized keys corresponding to each function g. Since all S-boxes are single cycle permutations, the ratio of keys actually inconsistent with the extension of the promotion from F_k to F_x°k  cannot be larger than 3 divided by 256 (given that full sized random keys are used), because that's the trivial upper bound of the probability that, for a vector size of one, you will not find two keys k, k', that differs in at most three of the S-boxes and are such that both F_k and F_k' are equivalent to g₀ and for all possible values of x both F_x°k and F_x°k' are equivalent to g₁. (Note that this is an approximate model. The MTT is not MDS, so the relation between the sboxes would have to be more complex, but since the MTT is bijective the probability of finding them is roughly bounded by the same number, in particular if the vector size is larger than one.) If one does not take the static and dynamic vectors into account, this entails that the unicity distance of Steak cannot be less than 3 bytes and key retreival requires an effort of at least O(2²⁴), where O is bounded downwards by the effort of finding the set {k} corresponding to the value pair (x,g(x)) for a random function g. These bounds are fully independant of the security of the promotion function.

This said, the proof is more or less trivial.

To begin with, it is important that the dynamic key data V_m significantly contributes to the promotion of  F_k to F_x°k. If it doesn't, then it might be possible to extract the s-boxes and the vectors separately from the sequence (or rather 256-branched tree) of (F^m_k), and it would make less difference whether the dynamic vector is pseudo random or not. More specifically, we would prefer that for any random function g and fixed A_k and D_k, there is a constant epistemic probability that one might find a vector V_m such that F^m_k = g. This seems to be the case: Each G^i°m_k depends (close to) linearly on the value of V_m[n-i+1], but a linear change to G^i°m_k will, after it has passed through A_k[n-i] and D_k, result in a non-linear change to G^i+1°m_k. This is largely due to the fact that the s-boxes are single cycle, and hence never can be fully linear. Consequently, the probability is extremely low that there are non-zero values x and y such that (V_m[n-i+1]+x,V_m[n-i]) and (V_m[n-i+1],V_m[n-i]+y) will result in the same function G^i+1°m_k. The degree to which this property holds for large chunks of V_m ought to be high. The s-boxes will always be non-linear to some degree, and this non-linearity will show in the way G^i°m_k selects G^i+1°m_k.

The pseudo randomness of V_m might be established as follows: Let H^i°m°j_k be such that for any i, j, m, k, we have that H^i°m°j_k(PV_n-i+j+1) = PV_n-i+1, where PV_i = V[i] according to the notation of the algorithm. Define the value PV_n-i+j+1 such that if n-i+j+1 is greater than n, then this is the corresponding internal state of F^m-1_k at round i-j-n, etc. Note that the four most and least significant bits of H^1°m°j_k will always depend (close to linearly) on the cipher text byte C_m-1. This byte will be pseudo random if the least significant byte of H^n°m-1°j_k is pseudo random. It isn't material in this context that this byte is public. Now, according to the assements about the impact of V_m on the selection of each G^i°m_k, it is correspondingly reasonable to assess that there is a value e such that if j > e, then H^i°m°j_k is a pseudo random permutation. (Our statistical tests indicate that e = 3 is sufficient.) This entails that if e.g. n = 8 and j = 4, then the string of V₁[5], V₁[1], V₂[5], V₂[1], ... will be pseudo random up to a length corresponding to at least the strength of each H^4°m°4_k, H^8°m°4_k. The entropy of the promotion from F^m_k to F^m+1_k cannot be less than the entropy of this string, because the strings V₁[8], V₁[4],.. , V₁[7], V₁[3], ... etc will all have the same security bound, and if the conjunction of them would decrease the strength of the promotion from F^m_k to F^m+1_k, then this must be due to the way some H^i°m°j_k selects the next H^i+1°m°j_k, and that would be contrary to our assumptions that this step cause a high probability security increment.

It is important to note that there is a close relationship between the function F^m_k and the promotion of F^m_k to F^m+1_k, since each G^i°m_k is constituted by the same steps in the algorithm as H^i°m°j_k. There is however a "but": Although the set {...,(G^i-1°m_k(x),G^i°m_k(x)),...} is a subset of H^i°m°j_k, knowing G^i°m_k extensively, but nothing about G^i-1°m_k, will not leak any information at all about H^i°m°j_k given that i > 1. In the informal sense, a cipher like Steak will never be cracked by an adversary who first learns the value of one vector element, solves an equation to learn another value, etc, but rather as the result of an statistical attack of some kind. Primarily because the only thing known to attacker in the first place is the cipher text and possibly the plain text - secondarily because unequivocal knowledge of isolated elements of key data will still leave too many unknown variables for the equations to be solved. The point of this exercise is foremost to prove that it is impossible that knowledge of one function F^m_k could enable the adversary to make more than a lucky guess about any internal key data, but also to justify the assessment that knowledge of several functions in the tree (F^m_k) could not enable the adversary to do significantly better, because the relationship between these functions is too complex.

For example: Knowing both G^i-1°m_k and G^i°m_k extensively will reveal no more than a 2^-24 fraction of the extension of H^i°m°j_k. Furthermore, knowing G^i-1°m_k and G^i°m_k extensively would make it theoretically possible to compute the set {B} of all possible values of the sum B = A[n-i+1]+V[n-i] through exhaustive key search, but only Bwould be revealed. If the set {B} is sufficiently large, extensive knowledge of G^i-1°m+1_k and G^i°m+1_k  would not add a significant amount of information about either V_m[n-i] or V_m+1[n-i]. A conservative estimation is that |{B}| > 2^31.9 (based on the number of ways to modify the s-boxes, and obtain the same functions G^i-1°m_k and G^i°m_k, that would not be possible because the s-boxes are single cycle and the MTT is not MDS), implying that one would need at least 10 value pairs (G^i-1°m_k(x), G^i°m_k(x)) for different m before the intersection of the sets {B} was less than 2³¹. Given that the adversary's knowledge of G^i-1°m_k and G^i°m_k was likely to actually only be probabilistic to begin with, the increment of knowledge obtained by making more queries is more or less negligleble.

Thirdly, we prove that the advantage of any distinguisher for Steak has a polynomial bound, and base this on few assumptions:

1. The relation between the key stream output and the least byte V[1][0] of the internal state vector has no distinguisher with an advantage greater than any other distinguisher for Steak. This is a justified assumption: V[1][0] is a bijective function of V_m[1][0] with the key stream output x as the key parameter, and V_m[1] will have an impact on x only after being distorted by nearly all other key data. This assumption is clearly similar to the assessment that F^m_k might be modeled as a random function.
2. The probability is negligleble that, for any pair of key data k and k', there is a more efficient way to tell if F_k = F_k' other than computation of at least one element in the each respective code book. 

The second assumption is justified by the properties of G^i°m_k and implies that it would be infeasible to find an advantageous trade-off between time, memory and probability, for any method that would narrow the set {k} corresponding to F^m_k down to the subset corresponding to F^m+1_k. Suppose that we have found a way of representing a subset M_m of the set {k} corresponding to F^m_k. (For the sake of simplicitly, I will assume that M_m is represented either extensionally, or by the combination of formulaes in the vectors and s-boxes separately. There might be ways to represent M_m that put the s-boxes and the vectors into the same formula, but I will assume that since the s-boxes belong to the entire set of single cycle permutations, it will be infeasible to parameterize the entire key space using such formulae, and that it in particular will be infeasible to "do calculus" on such formulae, e.g. to take two arbitrary formulae and in linear time calculate the intersection of the two sets.)