f(A,B), with a 256-bit key schedule
which can be initialised using 128, 192, or 256-bit keys.
It is described in [BrLO97a], and is to
be submitted as a candidate proposal for the Advanced Encryption Standard
[AES97].
As documented in my previous discussion paper [BrLO97a], Knudsen [Knud93] notes some necessary conditions for a secure feistel cipher are:
O(2127) trials, each of which involves
a cost of about 4 encryptions (approx 3 for the key schedule
and 1 for the actual test encryption).
g(K1,K3,K2)
in the key schedule, it is clear that there are no simple relations
between any of the subkey bits, rather they depend in a complex manner
on all the input key bits. Thus there are no obvious weak keys (those
which result in constant, or repeated subkey values).
The best I can see doing is to derive those key values which result
in up to the first 4 subkeys (affecting only the first 1 1/3 data rounds)
being zero. These can obviously be derived by using relationships between
the input key values, which take the form:
[K40|K30|K20|K10],
and linear relations between the subkeys.
One round of the LOKI97 key schedule looks as follows:
SKi = K1i = K4i-1 xor f(K1i-1+K3i-1+(Delta*i),K2i-1)
K4i = K3i-1
K3i = K2i-1
K2i = K1i-1
In more specific cases, we could attempt to coerce the first few subkey
values to some known (preferably 0) value - we need to do this to create
some of the test data the AES people want anyway. Now the first few
rounds of the key schedule, given a 256-bit input key of
[K4|K3|K2|K1], can be specified as follows:
SK1 = K4 ^ f(K3+K1+D,K2) nb. D = Delta
SK2 = K3 ^ f(K2+SK1+2D,K1)
SK3 = K2 ^ f(K1+SK2+3D,SK1)
SK4 = K1 ^ f(SK1+SK3+4D,SK2)
SK5 = SK1 ^ f(SK2+SK4+5D,SK3)
SK6 = SK2 ^ f(SK3+SK5+6D,SK4)
.....
so, attempting to solve for successive zero subkeys, we get:
K4 = f(K3+K1+D,K2)
eg.
[f(D,0)|0|0|0]
[A6ACC1AD4F7D648E000000000000000000000000000000000000000000000000]
K3 = f(K2+2D,K1), and
K4 = f(f(K2+2D,K1)+K1+D,K2)
eg.
[f(f(2D,0)+D,0)|f(2D,0)|0|0]
[D56AEDDD378763C8B3F8B84B61E6FD2D00000000000000000000000000000000]
K2 = f(K1+3D,0), and
K3 = f(f(K1+3D,0)+2D,K1), and
K4 = f(f(f(K1+3D,0)+2D,K1)+K1+D,f(K1+3D,0))
eg.
[f(f(f(3D,0)+2D,0)+D,f(3D,0))|f(f(3D,0)+2D,0)|f(3D,0)|0]
[CC3533C1DAE8E39076AC4AAAF1F443A7802D899C87BB07FD0000000000000000]
K1 = f(4D,0), and
K2 = f(f(4D,0)+3D,0), and
K3 = f(f(f(4D,0)+3D,0)+2D,f(4D,0)), and
K4 = f(f(f(f(4D,0)+3D,0)+2D,f(4D,0))+f(4D,0)+D,f(f(4D,0)+3D,0))
eg.
[DF74B90CE9D04479AF42CF6ACD63B8526E989FA699AB078E6BB007E91228F095]
so there is only 1, completely specified value, which gives this.
SKn = 0 = f(nD,0), which is not true for
any n=1,48 (ie all values of use in the LOKI97).
So as a general statement, we can coerce the first 4 subkeys to zero (or indeed any desired value), with exponentially decreasing possibilities as we fix successive subkeys. After that, there are no obvious related values.
If we consider the shorter keys, then in fact the initialisation which
specifies K2 = f(K3,K4), and
K1 = f(K4,K3), make it extremely
difficult to solve the above equations, even for just
SK1 = 0, at all.
S1[x] = ((x xor 1FFF)3 mod 2911) & FF, in GF(213)
S2[x] = ((x xor 7FF)3 mod AA7) & FF, in GF(211)
These are designed to have maximum non-linearity (hence the choice of
cubing in an odd polynomial galois field), have good immunity to differential
cryptanalysis, and have good avalanche properties.
The input values are inverted in order to remove the mapping of 0->0, 1->1, that otherwise would occur.
A number of generator polynomials are available in each field (630 in GF(2^13) and 180 in GF(2^11)). All of these seem to generate basically equivalent XOR profiles, so this was not a determiner in their selection. There were however minor differences in their avalanche characteristics, which led to the final selection.
Analysis shows that for S1, the maximum value is 64 (occuring 32640
times) out of a maximum of 8192; and further, in the zero output column
(ie where different inputs give the same output value), the maximum
value is just 32 (occuring 7936 times). Should a characteristic be
constructed using one of these entries, it would have a probability
of just Pr(32/8192) = Pr(1/256).
For S2, the maximum value is 16 (occuring 32640 times) out of a maximum
of 2048; and further, in the zero output column (ie where different
inputs give the same output value), the maximum value is just 8
(occuring 1792 times). The individual row profiles are either all 8's,
or combinations of 0 and 16 in various arrangements. A characteristic
constructed using one of these entries, would also have a probability
of just Pr(8/2048) = Pr(1/256).
Whilst these results imply that there are many possibilities with these values, the actual probability of success is much lower than that seen in other ciphers (eg LOKI91).
LOKI97 Candidate S:(x+1fff)^3 mod 2911 GF(2^13) S_test - Avalanche Test & 1-bit Changes (rule 3) Col Tot 0 0 0 0 0 0 0 0 0 0 0 0 0 ( 0) No aval 16 16 16 16 16 0 0 16 16 16 16 16 16 ( 176) 1bit av 128 128 128 128 128 96 128 128 128 128 128 128 128 (1632) LOKI97 Candidate S:(x+7ff)^3 mod aa7 GF(2^11) S_test - Avalanche Test & 1-bit Changes (rule 3) Col Tot 0 0 0 0 0 0 0 0 0 0 0 ( 0) No aval 4 0 0 4 4 0 4 4 4 4 4 ( 32) 1bit av 32 24 32 32 32 16 32 32 32 32 32 ( 328)
In summary:
S1 Output bits flip exactly 1/2 the time, For any given input bit, 0 change occurs in at most 16/4096 (ie 1/256) For any given input bit, 1 bit change occurs in at most 128/4096 (ie 1/32) S2 Output bits flip exactly 1/2 the time, For any given input bit, 0 change occurs in at most 4/1024 (ie 1/256) For any given input bit, 1 bit change occurs in at most 32/1024 (ie 1/32)These results are comparable with those seen in the LOKI89 and LOKI91 S-box function, which have been shown to be well designed with good security.
One round of the LOKI97 data encryption computation looks as follows:
Ri = Li-1 xor f(Ri-1+SK3i-2,SK3i-1)
Li = Ri-1+SK3i-2+SK3i
where the non-linear function f(A,B) is specified as:
f(A,B) = Sb(P(Sa(E(KP(A,B)))),B)
The first thing to note is that the use of integer addition in the R data value should result in the loss of any desired fixed XOR difference (but must try and determine what fraction of cases this will not be true for). This a standard differential cryptanalysis would seem blocked. I did consider a modified variant which used additive differences on the R data path, however the initial keyed permutation KP in f will ensure that fixed additive differences will be destroyed as the bits are exchanged.
So back to conventional DC. Even assuming we have some fraction of cases where the difference survives the addition, the presence of KP ensures that we end up attacking through either S1 or S2 in any round, but we don't know which. Given the attack probability is the same, this suggests that a conventional 2-round characteristic, using S(x')->0 with Pr(1/256) could iterate at best (modulo the massive difficulties imposed by the additions of subkey values) over 16 rounds with Pr(2^-64). I dont expect this probability to be achieved in practise with any likelyhood at all.
Use of the S(x')->0 characteristic enables the second column of S-boxes in the round to be ignored (since same input leads to same output). Any other characteristic type (eg S(x')->x') will not be able to do this, and will thus have vastly lower probablilities.
Help Appreciated!
LOKI97 avalanche: 640384 tests, 63.99617 mean no bits changed per test, out bit avalanches range over 0.49830258 - 0.5021237Which look pretty good. More runs with more tests will be done.