Lucifer (cipher)
| Company type | Cipher |
|---|---|
| Industry | Cryptography |
| Founded | 1970s |
| Founder | Horst Feistel and team at IBM |
| Products | Block cipher algorithms (Lucifer variants) |
In cryptography, the term Lucifer denotes some of the earliest civilian block ciphers created by Horst Feistel and his team at IBM. Serving as a direct forerunner to the Data Encryption Standard (DES), one variant known as DTD-1 was implemented commercially during the 1970s in electronic banking applications.
Overview
Lucifer utilizes a combination of substitution and transposition methods. A version outlined by Feistel in 1971 employs a 48-bit cryptographic key and processes data in 48-bit blocks. This substitution–permutation network incorporates two 4-bit S-boxes, selected based on the key. The patent specifies operation on 24-bit segments and a sequential mode handling 8 bits at a time. Another design from the same year by John L. Smith features a 64-bit key working on 32-bit blocks, involving one mod-4 addition and a single 4-bit S-box, optimized to handle 4 bits per clock cycle—making it one of the most compact block-cipher implementations.
Feistel later introduced an enhanced version with a 128-bit key size and block length.
A subsequent Lucifer iteration described by consists of a 16-round Feistel network processing 128-bit blocks and keys. This model is susceptible to differential cryptanalysis, which can break approximately half of all keys using around 236 chosen plaintexts with similar computational effort.
IBM proposed this Feistel-network Lucifer as a contender for the Data Encryption Standard. The NSA altered it by reducing the key length to 56 bits, shrinking block size to 64 bits, and improving defenses against differential cryptanalysis—techniques then known only to IBM and NSA—culminating in the creation of DES.
The name "Lucifer" is believed to be a pun on "Demon," itself derived from "Demonstration," an earlier privacy system developed by Feistel. Due to filename length restrictions in the operating system, the shorter name was adopted.
Description of the Sorkin variant
The Sorkin variant operates over 16 Feistel rounds, similar to DES, but excludes initial and final permutation steps. It utilizes both key and block sizes of 128 bits. The Feistel function takes a 64-bit half-block along with a 64-bit subkey and eight interchange control bits (ICBs) that dictate swapping behavior. The half-block is split into eight bytes of 8 bits each; if an ICB bit is zero, the byte’s left and right 4-bit sections (nibbles) are swapped; if one, the byte remains as is. Each byte then passes through two distinct 4×4-bit S-boxes, S0 and S1, which act on the left and right nibbles respectively. Their outputs are concatenated and combined with the subkey using an exclusive or (XOR) operation called "key interruption." This is followed by a two-step permutation: first rearranging bits within each byte, then mixing bits across bytes.
The key schedule is uncomplicated: the full 128-bit key is loaded into a shift register. For each round, the leftmost 64 bits serve as the subkey while the rightmost eight bits provide the ICBs. After completing a round, the register rotates left by 56 bits.
Further reading
- Eli Biham, Adi Shamir (1991). Differential Cryptanalysis of Snefru, Khafre, REDOC-II, 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).