2001-02-19

Differential analysis

Steak was designed with several types of differential attacks in mind:

Different keys -> Different cipher/plain text:
The key set up scheme and the error propagation of PCFB mode ensures that two different keys used to encrypt the same plain text will result in cipher text without any traceable relation. There is however a small number of exceptions to this rule. If the keys result in key data with identical vectors A and V and S-boxes that are equal but in a couple of positions (at least two), the same plain text will be encrypted to the same cipher text up to expectedly k=(2⁷)/n Once the variable B at step (2.2) or (4) of the encryption algorithm has taken a value such that E will be different, error propagation will take off and no traceable relation will any longer be found. The key pairs in question can actually be found, but as far as we know at least one member of each such pair (all keys belongs to the same number of such pairs) is of maximum size (i.e. 837 bytes plus two times the size of the vectors).

Different plain text -> Different cipher text:
Steak is two way error propagating and has a block size of 8 bits, so this kind of analysis would have to focus on what happens to the cipher text the first few bytes after a change to one byte of the plain text. This is what happens after P₁ has changed to P₁':

• (P₁ xor P₁') = (C₁ xor C₁')
• The value of (P₂ xor C₂) and of (P₂' xor C₂') will be determined by the choice of key and of P₁ or P₁' respectively. In an experimental situation where the key and (P₁ xor P₁') are constant but the plain text changes, the values of (C₂ xor C₂') will be distributed in about the same way as the sequence of bit differences of 256 pairs of random bytes would: A frequency of one would be most probable (~0.37) and a frequency of zero almost as probable, some values would have a relatively high frequency etc. However, these results depend on a random selection of both P₁ and P₁'. An exhaustive test of all 256 times 255 possible combinations for a fixed key would be equivalent to doing the corresponding test on the frequency of f(x) xor f(x') for a random function f from [0..255] to [0..255] and would hence result in a probability of ~0.6 for a frequency of zero, ~0.30 for a frequency of two, etc. (Obviously, all frequencies would be even since f(x) xor f(x') = f(x') xor f(x).)
• In the same kind of experimental situation, the distribution of the values (C_k xor C_k') will rapidly converge to an equal distance distribution as k and the amount of tests increases. The speed of convergence corresponds practically exactly to what should be expected for a deterministic but unpredictable byte valued function of a limited number of bytes. Our tests reveals no unexpected distribution of bit difference frequencies for any key or any plain text.

Different cipher text -> Different plain text:
The expected results as well as the results we actually got are identical to the results from the converse test described above.

Inner workings of the Steak Algorithm:
Changing P_k results in a change of V_k+1[n][3]. This change will be reflected in a change of PV for I=n at step (2.3) of the encryption algorithm, such that four least significant bits and four most significant bits of PV will change. Let PV' denote the altered value. For I=n-1 at step (2.1), addition with A[n-1] will possible induce a change through a carry on some more of the least significant bits of PV'. At step (2.2) B' will (in theory) first pass through the S-boxes. If the S-boxes are unknown, the values of (SBox(0,B[0]) xor SBox(0,B'[0])) and (SBox(3,B[3]) xor SBox(3,B'[3])) will both be unpredictable with an equal distance distribution. Since the MT-transform matrix is known, the 255 times 255 possible values of (E xor E') would be known (provided that bit 8 of B did not change at step (2.1)). However, most of the 255 times 255 possible values of (E xor E') are non-zero in all four bytes, so for I=n-1 at step (2.3) the same is probable to be true for PV. Our testing shows that a vector size of n=8 is sufficient to eliminate significant key dependent differential tracks from (P_k xor P_k') to (C_k+1 xor C_k+1').