Frequent Links
Lucifer (cipher)
General  

Designers  Horst Feistel et al. 
First published  1971 
Successors  DES 
Cipher detail  
Key sizes  48, 64 or 128 bits 
Block sizes  48, 32 or 128 bits 
Structure  Substitutionpermutation network, Feistel network 
Rounds  16 
In cryptography, Lucifer was the name given to several of the earliest civilian block ciphers, developed by Horst Feistel and his colleagues at IBM. Lucifer was a direct precursor to the Data Encryption Standard. One version, alternatively named DTD1, saw commercial use in the 1970s for electronic banking.
Contents
Overview
One variant, described by Feistel in 1971,^{[1]} uses a 48bit key and operates on 48bit blocks. The cipher is a Substitutionpermutation network and uses two 4bit Sboxes. The key selects which Sboxes are used. The patent describes the execution of the cipher operating on 24bits at a time, and also a sequential version operating on 8bits at a time. Another variant by John L. Smith from the same year^{[2]} uses a 64bit key operating on a 32bit block, using one addition mod 4 and a singular 4bit Sbox. The construction is designed to operate on 4 bits per clock cycle. This may be one of the smallest blockcipher implementations known. Feistel later described a stronger variant that uses a 128bit key and operates on 128bit blocks.^{[3]} The cipher is a Substitutionpermutation network and uses two 4bit Sboxes. The key selects which Sboxes are used.
Sorkin (1984) described a later Lucifer was a 16round Feistel network, also on 128bit blocks and 128bit keys.^{[4]} This version is susceptible to differential cryptanalysis; for about half the keys, the cipher can be broken with 2^{36} chosen plaintexts and 2^{36} time complexity.^{[5]}
IBM submitted the Feistelnetwork 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.^{[6]}
Description of the Sorkin variant
The variant described by Sorkin (1984) has 16 Feistel rounds, like DES, but no initial or final permutations. The key and block sizes are both 128 bits. The Feistel function operates on a 64bit halfblock of data, together with a 64bit subkey and 8 "interchange control bits" (ICBs). The ICBs control a swapping operation. The 64bit data block is considered as a series of eight 8bit bytes, and if the ICB corresponding to a particular byte is zero, the left and right 4bit halves (nibbles) are swapped. If the ICB is one, the byte is left unchanged. Each byte is then operated on by two 4×4bit Sboxes, denoted S_{0} and S_{1} — S_{0} operates on the left 4bit nibble and S_{1} operates on the right. The resultant outputs are concatenated and then combined with the subkey using exclusive or (XOR); this is termed "key interruption". This is followed by a permutation operation in two stages; the first permutes each byte under a fixed permutation. The second stage mixes bits between the bytes.
The keyscheduling algorithm is relatively simple. Initially, the 128 key bits are loaded into a shift register. Each round, the left 64 bits of the register form the subkey, and right eight bits form the ICB bits. After each round, the register is rotated 56 bits to the left.
References
 ^ Horst Feistel. Block Cipher Cryptographic System, US Patent 3,798,359. Filed June 30, 1971. (IBM)
 ^ John Lynn Smith. Recirculating Block Cipher Cryptographic System, US Patent 3,796,830. Filed Nov 2, 1971. (IBM)
 ^ Horst Feistel, (1973). Cryptography and Computer Privacy". Scientific American, 228(5), May 1973, pp 15–23.
 ^ A. Sorkin, (1984). LUCIFER: a cryptographic algorithm. Cryptologia, 8(1), 22–35, 1984.
 ^ Ishai BenAroya, Eli Biham (1996). Differential Cryptanalysis of Lucifer. Journal of Cryptology 9(1), pp. 21–34, 1996.
 ^ Konheim, Alan G. (2007), Computer Security and Cryptography, John Wiley & Sons, p. 283, ISBN 9780470083970.
Additional reading
 Eli Biham, Adi Shamir (1991). Differential Cryptanalysis of Snefru, Khafre, REDOCII, LOKI and Lucifer. CRYPTO 1991: pp156–171
 Whitfield Diffie, Susan Landau (1998). Privacy on the Line: The Politics of Wiretapping and Encryption.
 Steven Levy. (2001). Crypto: Secrecy and Privacy in the New Code War (Penguin Press Science).
External links
