LOKI89 and LOKI91

The LOKI89 Block Cipher

• LOKI is a cipher designed at ADFA as a result of the detailed analysis of existing block ciphers, particularly of the DES, and is the subject of Dr Brown's PhD
• several papers have been published since analysing it
• LOKI was intended to be interface compatible with the DES, so it could be a direct replacement
• hence it uses 64-bit data and a 64-bit key (this being the minimum resonable, and mostly compatible with DES)
• design criteria were to be published for critique

LOKI89 Design

• overall design is based on design principles developed from a detailed analysis of the DES, including:
  • permutation P and its role in growth of dependence of cipher bits on input bits
  • permutation PC2 and key rotation schedule and its role in growth of dependence of cipher bits on key bits
• design of the LOKI S-Boxes is based on the non-linearity criteria developed by Seberry and Pieprzyk, verified against known design criteria for S-boxes
• aim was for structure to be as simple as possible without compromising security
• LOKI is a Feistel class cipher, a form of Substitution-Permutation (S-P) network (Shannon)
• key properties of such S-P networks are:
  • the avalanche property
  • the completeness property
• provision of these have been achieved by a two phase design
  • overall structure assuming S-boxes have these properties
  • S-boxes with these properties

LOKI Expansion Function E

• duplicates input + key bits to provide autoclaving
• is based on a regular selection of bits
• is designed to use 32-bit inputs for ease of software implementation

LOKI Permutation P

• sends the output bits from each S-box to the inputs of S-boxes in turn
• can be generated by a difference function on the S-box number of [+3 +2 +1 0 +3 +2 +1 0]

LOKI Key Schedule

• uses a large key rotation removing the need for PC2
• with a rotation value of 12 to match the S-box size
• with 8 rotations of each half, final key is the initial key
• 16 rounds were chosen based on Biham-Shamir results suggesting that less would be insecure

Overall LOKI89 Structure

LOKI Function f

LOKI Keys

• LOKI Keys are 64-bit blocks, with no parity bits, which may be written in hex as hhhhhhhhhhhhhhhh₁₆
• Weak, Semi-weak, and Demi-semi-weak keys are those which generate 1, 2 or 4 internal sub-keys only and which should be avoided
  • for LOKI all these keys have the form:

a total of 2¹⁶ out of a possible 2⁶⁴

LOKI S-Box Design

• a suitable family of S-boxes with avalanche and completeness properties were required
• key principle was the concept of boolean functions with maximum non-linearity, by Pieprzyk and Seberry
• non-linearity of a function f in the set F_n of all Boolean functions of n variables, is the minimum Hamming distance between f and the set of all linear Boolean functions L_n existing in F_n
• further they determined that exponentiation in a Galois field can be used to form boolean functions with maximum non-linearity

LOKI89 S-Boxes

• LOKI S-boxes were chosen to have 12 inputs and 8 outputs
  • to maximise growth of bit dependencies
  • as largest values storable in pre-computed tables
• this is partitioned into 16 row functions with 256 columns
• each function is exponentiation in GF(2⁸) as follows:

• this field has 30 irreducible polynomials, and 24 exponents (of 13 inverse pairs) which form functions of maximum non-linearity (of 112)
• a number of other exponents exist which form functions of slightly less than maximum non-linearity, which may also be suitable for use
• exponent 31 was chosen as the smallest that gives maximum non-linearity
• 16 irreducible polynomials were chosen from the 30 available based on tests against principles S4 to S7, the results showing little significant variation between the alternatives.
• the resultant S-functions have non-linearities over all inputs and outputs of between 1896 and 1936 out of a possible 1984.
• they are combined in the following structure to form the LOKI S_box:

LOKI89 Cryptanalysis

• LOKI89 with up to 10 rounds can be attacked by differential cryptanalysis using:

B.(0,00000510)->(00000510,0) Pr(118/2^20)

found independently by Biham, Knudsen

• LOKI89 with up to 14 rounds can also be attacked using a 3 round characteristic:

B.(0,00400000)->(00400000,00400000) Pr(28/4096)

C.(00400000,00400000)->(00400000,0) Pr(28/4096)

found independently by Kwan, Knudsen

• LOKI89 key space is 2^60 due to the following relation:

LOKI(P(+)pppppppppppppppp,K(+)mmmmmmmnnnnnnnn)

where p=m(+)n, m,n arbitrary hex values

found independently by Biham, Knudsen, and Kwan

The LOKI90 Block Cipher

LOKI91 Design

• used the following additional guidelines:
• analyse key schedule to minimize generation of equivalent key, or related (key, plaintext) pairs
• minimise probability of f(x')->0 by requiring XOR differences giving zero output to be due to those bits permuted (by E) to more than one S-box input
• ensure cipher has sufficient rounds so exhaustive search is the optimal attack (ie have insufficient pairs for differential cryptanalysis)
• ensure cannot make all S-boxes give zero outputs, increasing security when for hashing modes.

LOKI91 Specification

• the following changes were made to LOKI89

1

change the key schedule so the halves were swapped after every second round

2

change the key rotation schedule to alternate between ROT12 (odd rounds) and ROT13 (even rounds)

3

remove the initial and final XORs of key with plaintext and ciphertext respectively

4

alter S-box function to:

generator polynomials gen_r as in LOKI89

Overall LOKI91 Structure

LOKI91 Cryptanalysis

• removal of initial and final XORs necessary due to other changes - increases ciphertext dependence on key from 3 to 5 rounds, still good compared to DES (5/7 rounds)
• key schedule changes:
• greatly reduce number of weak (*) & semi-weak keys:

Encrypt Key                        Decrypt key                                  
0000000000000000                   0000000000000000  *                          
00000000aaaaaaaa                   aaaaaaaa00000000                             
0000000055555555                   5555555500000000                             
00000000ffffffff                   ffffffff00000000                             
aaaaaaaa00000000                   00000000aaaaaaaa                             
aaaaaaaaaaaaaaaa                   aaaaaaaaaaaaaaaa  *                          
aaaaaaaa55555555                   55555555aaaaaaaa                             
aaaaaaaaffffffff                   ffffffffaaaaaaaa                             
5555555500000000                   0000000055555555                             
55555555aaaaaaaa                   aaaaaaaa55555555                             
5555555555555555                   5555555555555555  *                          
55555555ffffffff                   ffffffff55555555                             
ffffffff00000000                   00000000ffffffff                             
ffffffffaaaaaaaa                   aaaaaaaaffffffff                             
ffffffff55555555                   55555555ffffffff                             
ffffffffffffffff                   ffffffffffffffff  *                          

• also leave just single bit complementation property:

			_________       _ _
			LOKI(P,K)= LOKI(P,K)

• the S-box function redesign:
• ensures zero input gives non-zero output
• improves LOKI91 immunity to differential cryptanalysis,can be attacked in up to
  • 10 rounds using a 2 round characteristic
  • f(x')->0'with Pr(122/1048576)
  • 12 rounds using a 3 round characteristic
  • f(x')->x'with Pr(16/4096) (twice)
• insufficient pairs to attack 16 round LOKI91
  • require 2⁸⁰ pairs for 3 round char
  • require 2⁹² pairs for 2 round char
  • but only have 2⁶³ possible plaintext pairs

Latest Analysis of LOKI91

• Knudsen presented a paper at Auscrypt'92
  • confirmed there are no characteristics with high enough probability to attack LOKI91 faster than keyspace search
  • showed size of image of LOKI f function is F(8,13) x 2 ^(32) significance of this is debateable
  • presents chosen plaintext attack reducing exhaustive keyspace search by 4 using 2 ^(32) + 2 chosen plaintexts
• Biham has presented his related key attacks
  • only applicable if attacker can force rekey by pattern
• seem to confirm security of LOKI91 at present
• is now susceptible to exhaustive keyspace search, though harder than for DES (60-64 bits vs 56 for DES)