Lucifer (cipher)
Encyclopedia
In cryptography
, Lucifer was the name given to several of the earliest civilian block cipher
s, developed by Horst Feistel
and his colleagues at IBM
. Lucifer was a direct precursor to the Data Encryption Standard
. One version, alternatively named DTD-1, saw commercial use in the 1970s for electronic banking.
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.
s) are swapped. If the ICB is one, the byte is left unchanged. Each byte is then operated on by two 4×4-bit S-boxes, denoted S0 and S1 — S0 operates on the left 4-bit nibble and S1 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 key-scheduling 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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, Lucifer was the name given to several of the earliest civilian block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s, developed by Horst Feistel
Horst Feistel
Horst Feistel was a German-born cryptographer who worked on the design of ciphers at IBM, initiating research that would culminate in the development of the Data Encryption Standard in the 1970s....
and his colleagues at IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
. Lucifer was a direct precursor to the Data Encryption Standard
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
. One version, alternatively named DTD-1, saw commercial use in the 1970s for electronic banking.
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 networkSubstitution-permutation network
In cryptography, an SP-network, or substitution-permutation network , is a series of linked mathematical operations used in block cipher algorithms such as AES .Other ciphers that use SPNs are 3-Way, SAFER, SHARK, and Square....
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
Substitution-permutation network
In cryptography, an SP-network, or substitution-permutation network , is a series of linked mathematical operations used in block cipher algorithms such as AES .Other ciphers that use SPNs are 3-Way, SAFER, SHARK, and Square....
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
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
; 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
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
(compare the more recent AES process
Advanced Encryption Standard process
The Advanced Encryption Standard , the block cipher ratified as a standard by National Institute of Standards and Technology of the United States , was chosen using a process markedly more open and transparent than its predecessor, the aging Data Encryption Standard...
). It became the DES after the National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
reduced the cipher's key size to 56 bits, reduced the block size to 64 bits, and made the cipher resistant against differential cryptanalysis
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
, 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.
Description of the Sorkin variant
The variant described in (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 64-bit half-block of data, together with a 64-bit subkey and 8 "interchange control bits" (ICBs). The ICBs control a swapping operation. The 64-bit data block is considered as a series of eight 8-bit bytes, and if the ICB corresponding to a particular byte is zero, the left and right 4-bit halves (nibbleNibble
In computing, a nibble is a four-bit aggregation, or half an octet...
s) are swapped. If the ICB is one, the byte is left unchanged. Each byte is then operated on by two 4×4-bit S-boxes, denoted S0 and S1 — S0 operates on the left 4-bit nibble and S1 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 key-scheduling algorithm is relatively simple. Initially, the 128 key bits are loaded into a shift register
Shift register
In digital circuits, a shift register is a cascade of flip flops, sharing the same clock, which has the output of any one but the last flip-flop connected to the "data" input of the next one in the chain, resulting in a circuit that shifts by one position the one-dimensional "bit array" stored in...
. 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.