[Next] [Up/Previous] [Index]

LUCIFER: the first block cipher

One could perhaps quarrel with the title of this section. What about Playfair, or the Hill cipher? But LUCIFER, part of an experimental cryptographic system designed by IBM, was the direct ancestor of DES, also designed by IBM.

Like DES, LUCIFER was an iterative block cipher, using Feistel rounds. That is, LUCIFER scrambled a block of data by performing an encipherment step on that block several times, and the step used involved taking the key for that step and half of that block to calculate an output which was then applied by exclusive-OR to the other half of the block. Then, the halves of the block were swapped, so that both halves of the block would be modified an equal number of times.

Incidentally, this page refers to LUCIFER as actually implemented, and described in an article in the journal Cryptologia by Arthur Sorkin. An article in Scientific American discussed plans for LUCIFER on a more general level, and described what was essentially a different kind of block cipher.

LUCIFER enciphered blocks of 128 bits, and it used a 128-bit key.

The F-function in LUCIFER had a high degree of symmetry, and could be implemented in terms of operations on one byte of the right half of the message at a time. However, I will describe LUCIFER here in the same general fashion that DES is described.

Subkey generation

Each round uses a 72-bit subkey. The subkey for the first round consists of the first byte of the key repeated twice, followed by the next seven bytes of the key. Rotate the key left by seven bytes, then generate the subkey for the next round.

The f-function

XOR the right half of the block with the last eight bytes of the subkey for the round.

Based on the bits of the first byte of the subkey for that round, swap nibbles in the eight bytes of that result for those bytes which correspond to a 1 bit.

Use S-box 0 for the most significant nibble of each of these eight bytes, and S-box 1 for the least significant nibble of each byte:

Input:           0  1  2  3  4  5  6  7
S-box 0 output: 12 15  7 10 14 13 11  0
S-box 1 output:  7  2 14  9  3 11  0  4

Input:           8  9 10 11 12 13 14 15
S-box 0 output:  2  6  3  1  9  4  5  8
S-box 1 output: 12 13  1 10  6 15  8  5

Permute the 64 bits of the result, numbered from 0 (for the most significant bit) to 63 (for the least significant bit), by the following permutation:

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

The General Structure

LUCIFER has sixteen rounds. In each round, the f-function is calculated using that round's subkey and the left half of the block. The result is then XORed to the right half of the block, which is the only part of the block altered for that round.

After every round except the last one, the right and left halves of the block are swapped.

Comments

Although LUCIFER has a larger block and key size than DES, it is considerably more vulnerable to attacks from differential cryptanalysis, and is also weak due to the regular nature of its key schedule.

However, this does not mean that the LUCIFER algorithm is useless. If a reasonably good stream cipher is used both before and after LUCIFER, its weaknesses essentially become irrelevant, and its strengths are still present. It might indeed be argued that this kind of precaution ought to be used with DES as well.


[Next] [Up/Previous] [Index]

Next
Chapter Start
Skip to Next Section
Table of Contents
Main Page Home Page