Lucifer (cipher) - Overview

Overview

One variant, described in (US Patent 3,798,359; June 1971), uses a 48-bit key and operates on 48-bit blocks. The cipher is a Substitution-permutation network and uses two 4-bit S-boxes. The key selects which S-boxes are used. The patent describes the execution of the cipher operating on 24-bits at a time, and also a sequential version operating on 8-bits at a time.

Another variant, described in (US Patent 3,796,830; Nov 1971), uses a 64-bit key operating on a 32-bit block, using one addition mod 4 and a singular 4-bit S-box. The construction is designed to operate on 4 bits per clock cycle. This may be one of the smallest block-cipher implementations known.

A stronger variant, described in (Feistel, 1973), uses a 128-bit key and operates on 128-bit blocks. The cipher is a Substitution-permutation network and uses two 4-bit S-boxes. The key selects which S-boxes are used.

A later Lucifer was a 16-round Feistel network, also on 128-bit blocks and 128-bit keys, described in (Sorkin, 1984). This version was shown to be susceptible to differential cryptanalysis; for about half the keys, the cipher can be broken with 236 chosen plaintexts and 236 time complexity (Ben-Aroya and Biham, 1996).

IBM submitted the Feistel-network version of Lucifer as a candidate for the Data Encryption Standard (compare the more recent AES process). It became the DES after the National Security Agency reduced the cipher's key size to 56 bits, reduced the block size to 64 bits, and made the cipher resistant against differential cryptanalysis, which was at the time known only to IBM and the NSA.

The name "Lucifer" was apparently a pun on "Demon". This was in turn a truncation of "Demonstration", the name for a privacy system Feistel was working on. The operating system used could not handle the longer name.