[Next] [Up] [Previous] [Index]

LOKI97

Designed by Dr. Lawrie Brown, of the Australian Defence Force Academy with assistance from Dr. Josef Pieprzyk (who designed the S-boxes) and Dr. Jeniffer Seberry, and named after the Norse god of trickery and cunning, LOKI97 is a successor to the 64-bit block ciphers LOKI89 and LOKI91. (Fittingly enough, Dr. Brown spent part of the sabbatical year during which he designed it at a University in Norway!)

A paper (in Adobe Postscript format) describing LOKI97 is available at

but a full description is also presented here, for the convenience of those without a convenient means to view or print items in Postscript form.

LOKI97 is an iterative block cipher with 16 modified Feistel rounds.

In each round, two 64-bit subkeys are added (yes, using normal 64-bit addition including carries) to the right half of the 128-bit block. Its value, after the first subkey is added, but before the second subkey is added, is used as the input to the f-function for that round. This is a nicely symmetrical way of both modifying the input to the f-function and modifying the right half of the block as well.

A third 64-bit subkey is used as an input to the f-function; it is not directly added or XORed to the right half of the block or a transformed version of it, but instead controls the f-function's nonlinearity. For purposes of the key schedule, this 64-bit subkey is the second one; the two added to the right half are the first and third, respectively. The output of the f-function is, as in DES, XORed to the left half of the block.

The f-function

Unlike the f-function in DES, which includes the step of XORing the 48-bit subkey with the right half of the block after the expansion permutation, the addition of subkeys to the right half of the block is, in LOKI97, performed outside the f-function, as we have seen.

The first step in the f-function involves applying the least significant and rightmost (numbered from 31 to 0 in the convention used in the paper describing LOKI97) 32 bits of the subkey input (the entire 64-bit subkey input is called input B to the f-function) to the current value of the right half of the block (after one of the two additions, as noted above, and which is called input A to the f-function) as follows: a 1 bit in the 32 bits of subkey input used indicates that corresponding bits of the two halves of the right half of the block are to be swapped. A bit swap of this nature can be easily implemented by means of AND and OR instructions, and was earlier used in the ICE block cipher.

LOKI has two distinct S-boxes; S1 contains 8192 values from 0 to 255, and S2 contains 2048 values from 0 to 255. After the expansion permutation which is the next step, these S-boxes will be used in the order:

S1, S2, S1, S2, S2, S1, S2, S1

to produce a 64-bit output.

So the expansion permutation will produce groups of 13, 11, 13, 11, 11, 13, 11, and 13 bits corresponding to each byte output from the bit-swapping step.

This is done by appending to the beginning of each byte either 5 or 3 bits, as needed, from the least significant part of the preceding byte (going around the circle to append the least significant 5 bits of the last byte to the front of the first one). This is simpler than the expansion permutation of DES, which augmented each nybble of the input with one bit taken from each of the two adjacent nybbles.

The output of the expansion permutation is then input to the S-boxes.

The output of the S-boxes, considered as consisting of bits 63 to 56 from the first S-box, bits 55 to 48 from the second S-box, and so on, is then permuted by the following permutation P:

7, 15, 23, 31, 39, 47, 55, 63,   6, 14, 22, 30, 38, 46, 54, 62,
5, 13, 21, 29, 37, 45, 53, 61,   4, 12, 20, 28, 36, 44, 52, 60,
3, 11, 20, 27, 35, 43, 51, 59,   2, 10, 18, 26, 34, 42, 50, 58,
1,  9, 18, 25, 33, 41, 49, 57,   0,  8, 16, 24, 32, 40, 48, 56

where this listing is of the output bits, each number showing from which input bit that output was obtained. (Remember, the input bits are numbered from 63 down to 0 here.)

Finally, the 32-bit result is again submitted to the S-boxes, but this time in the following order:

S2, S2, S1, S1, S2, S2, S1, S1

with the additional five or three more significant bits of input required for each S-box supplied by the leftmost or most significant half of the subkey input to the f-function. (One starts from the left, and takes the leftmost bits of the subkey input for this purpose.)

The S-box contents

Each entry in the two S-boxes is equal to the cube of the one's complement of that entry's position, modulo a polynomial in the Galois fields GF(2^13) for S1 and GF(2^11) for S2.This technique is more familiar from calculating cyclic redundancy checks; a binary number, such as 1101, is considered to be a polynomial:

1 * x^3 + 1 * x^2 + 0 * x + 1
in this case, the coefficients of which are modulo 2 numbers that can only be either 0 or 1.

For S1, the polynomial is 10100100010001, and for S2 the polynomial is 101010100111. In each case, the polynomial is one bit wider than the S-box inputs, so it can be used, shifted to the right if necessary, to XOR away every bit by which the cube extends past the width of the S-box input. After that is done, only the last 8 bits of the result are used as the S-box entry, but the reduction from either 13 or 11 bits to 8 is done by simple chopping.

Subkey generation

Subkeys for LOKI97 are generated by a modified version of the cipher itself.

The input to the subkey is considered to be composed of four 64-bit pieces, called K4, K3,K2, and K1. When a 256-bit key is used, its first 64 bits become K4, its second K3, and so on.

A 192-bit key is converted to a 256 bit key as follows: the given key becomes the first 192 bits of the 256-bit key to be used, and the last 64 bits are calculated by using the LOKI97 f-function, with the first 64 bits acting as input A (the "righthalf" input) and the second 64 bits acting as input B (the "subkey" input).

A 128-bit key is converted to a 256 bit key as follows: the given key becomes the first 128 bits of the 256-bit key to be used, the third group of 64 bits (K2) is the f-function of the second 64 bits submitted as input A and the first 64 bits submitted as input B, and the fourth group of 64 bits (K1) is the f-function calculated with the first 64 bits submitted as input A and the second 64 bits as input B, exactly as in the 192-bit case.

Once the input key is in 256-bit form, as K4, K3, K2, and K1, the 48 subkeys used are calculated as follows:

The LOKI97 f-function is calculated with the following inputs: the A input is K1 plus K3 plus the hexadecimal constant 9E3779B97F4A7C15 multiplied by the number of the subkey generation round (from 1 to 48), and the B input is K2.

K4 is XORed with this result, and the result of this XOR is the subkey generated as well.

Then, before the next f-function calculation, the subkeys are rearranged: the old K1 value becomes the new K2 value, K2 goes to K3, K3 goes to K4, and K4, after the XOR (the same as the subkey value) goes to K1.

For round 1, subkey 1 is what is first added to the right half of the block; subkey 2 is the B input to the f-function, and subkey 3 is what is added secondly to the right half of the block. This pattern continues with the remaining subkeys for theremaining rounds.

For decryption, subkey 1 becomes the additive inverse of subkey 48, subkey 2 becomes subkey 47, subkey 3 becomes the additive inverse of subkey 46, and this repeats for each group of three subkeys.

Analysis

LOKI97 was the first submission to the Advanced Encryption Standard process to be publicly disclosed by its authors. Unfortunately, it was also the first one to be found to have flaws.

The fixed S-boxes, which took 11 or 13 bits of input, consisting of three or five supplemental bits "borrowed" from the previous byte, plus the eight bits of the byte for which they provided a substitute, simply consisted of apparently random bits. While their contents were designed to have some good properties, the fact that the S-boxes did not contain eight or thirty-two successive permutations of the numbers from 0 to 255 meant that the S-box output was biased. An attack was found by Vincent Rijmen and Lars Knudsen that exploited this. (Note that a key-dependent S-box, like that of Blowfish, does not need to be composed of bijections. Wide fixed S-boxes, as used in CAST-128 and MARS, also don't appear to face that constraint.)

The structure of the S-boxes was only a problem because in the second S-box stage, the extra bits of input to the S-boxes came only from the subkeys, so the biases in the S-boxes would tend to leak those subkey bits.

In DES, additional efficiency can be gained by storing a table of the S-box values after they have gone through permutation P. Here, the same S-box goes into the one fixed permutation, after the first S-box stage, at different places, and then the second S-box stage is not followed by a permutation. This complicates implementation, and loses the additional diffusion an extra permutation layer (which would be available "for free", if identical) would provide.

[Next] [Up] [Previous] [Index]