Preliminary Analysis of LOKI97

DRAFT - 19 Dec 97

Dr Lawrie Brown
School of Computer Science, Australian Defence Force Academy, Canberra, Australia


This paper presents an initial analysis of the security of LOKI97 against known attack methods.


LOKI97 is a 16 round Feistel cipher on 128-bit data using a complex non-linear function 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:

This paper will address some issues implied by this in analysing the proposed LOKI97 cipher.

Key Search

LOKI97 uses 128, 192, or 256-bit keys in a 256-bit key schedule. Even with the shortest key size of 128-bits, exhaustive searches are currently infeasible, and likely to remain so for some considerable time (barring revolutionary advances like the development of practical quantum computers). The cost of such a search would, on average, be approx 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).

Characteristics of the Key Schedule

Given the use of the non-linear function 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:
SK1 = 0 implies
      K4 = f(K3+K1+D,K2)
SK2 = SK1 = 0 implies
      K3 = f(K2+2D,K1), and
      K4 = f(f(K2+2D,K1)+K1+D,K2)
SK3 = SK2 = SK1 = 0 implies
      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))
SK4 = SK3 = SK2 = SK1 = 0 implies
      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))
so there is only 1, completely specified value, which gives this.
SKn and lower = 0
implies that 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.

Analysis of the S-boxes

The proposed LOKI97 S-boxes are:
      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.

XOR Profiles

The XOR profiles of the S-boxes are remarkably regular and relatively flat.

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).

Avalanche Properties

The avalanche characteristics of the chosen functions were evaluated by exhaustively testing for each input bit position, for all other bit values, the effect of flipping that bit on the output value. Counts were kept of which output bits changed (the result being very even for both), as well for when no bits changed, or just one bit changed (ie no avalanche occured). As shown in the table below, these cases occured a small percentage of the time.
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:

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)

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.

Differential Cryptanalysis

Want to see if we can construct any mechanism to leverage off pairs of encryptions using the same key with some known "difference".

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.

Linear Cryptanalysis

I haven't the foggiest - this is one area I'm not yet familiar enough with to suggests any directions or results.

Help Appreciated!

Overall Cipher Characteristics

Some preliminary trials have been run to characterise the overall cipher. In particular, some random trials have been run to determine its avalanche characteristics. Avalanche is one of the key desired properties of bloxk ciphers, where changing 1 bit of input should result in approx half the output bits changing, and for each specific output bit to change about half the time. It is impossible to totally characterise avalanche for a cipher like LOKI97 as there are too may possibilities. However have run some random trials (with random key and data, and then flip each bit of data in turn). Results are as follows:
LOKI97 avalanche: 640384 tests, 63.99617 mean no bits changed per test,
out bit avalanches range over 0.49830258 - 0.5021237
Which look pretty good. More runs with more tests will be done.


This paper presents an initial, tentative analysis of the proposed LOKI97 encryption algorithm. It sketches an outline of an approach to differential cryptanalysis, without getting very far; and shows how to select keys which generate some pre-determined subkey values.


The work was conducted during my special studies program in 1997, whilst visiting NTNU in Trondheim, Norway, and CCSR, UOW, Wollongong. I'd like to thank my colleagues at these institutions for their discussions and support.


"Advanced Encryption Standard Call", NIST, 1997.
L. Brown, "Preliminary Thoughts on the Redesign of LOKI", Australian Defence Force Academy, Canberra, Australia, Technical Note, Sep 1997.
Lars Knudsen, "Practically Secure Feistel Ciphers", in Fast Software Encryption, Lecture Notes in Computer Science, Vol 809, Springer-Verlag, pp 211-221, 1993.

The latest version of this paper may be found at:
Last updated: 19 Dec 97.