Lucifer (cipher)

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 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 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 DES (compare the more recent AES process). After some redesign (a reduction to a 56-bit key and 64-bit block, but strengthened against differential cryptanalysis) it became the Data Encryption Standard in 1977.

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 (nibbles) 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.

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.
* Eli Biham, Adi Shamir (1991). Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. CRYPTO 1991: pp156–171
* Ishai Ben-Aroya, Eli Biham (1996). Differential Cryptanalysis of Lucifer. "Journal of Cryptology" 9(1), pp. 21–34, 1996.
* Whitfield Diffie, Susan Landau (1998). Privacy on the Line: The Politics of Wiretapping and Encryption.
* Stephen Levy. (2001). Crypto: Secrecy and Privacy in the New Code War (Penguin Press Science).

External links

* [http://www.quadibloc.com/crypto/co0401.htm John Savard's description of Lucifer]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Lucifer (disambiguation) — Lucifer is most frequently another word for Satan. It may also refer to:People and Characters * Lucifer, the primary fallen angel * Hendrick Lucifer, famous pirate and brute * Saint Lucifer, a 4th century bishop * Lucifer, an early bishop of… …   Wikipedia

  • Lucifer (cryptographie)) — Lucifer (cryptographie) Pour les articles homonymes, voir Lucifer (homonymie). Lucifer …   Wikipédia en Français

  • Lucifer (cryptographie) — Pour les articles homonymes, voir Lucifer (homonymie). Lucifer Résumé Concepteur(s) Horst Feistel, IBM Première publication 1971 Dérivé de …   Wikipédia en Français

  • Cipher security summary — This article summarizes publicly known attacks against ciphers. Note that not all entries may be up to date. Table color key No known successful attacks Theoretical break Attack demonstrated in practice The Best attack column lists the complexity …   Wikipedia

  • Cipher Block Chaining — Mode d opération (cryptographie) En cryptographie, un mode d opération est la manière de traiter les blocs de texte clairs et chiffrés au sein d un algorithme de chiffrement par bloc. Chacun des modes possède ses propres atouts. Plusieurs modes… …   Wikipédia en Français

  • Feistel cipher — In cryptography, a Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German IBM cryptographer Horst Feistel; it is also commonly known as a Feistel network. A large proportion of block ciphers use… …   Wikipedia

  • 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 (for example) a 128 bit block of plaintext as… …   Wikipedia

  • Stream-cipher — Stromverschlüsselung (engl. stream cipher) ist ein kryptographischer Algorithmus, bei dem Zeichen des Klartextes mit den Zeichen eines Schlüsselstroms einzeln (XOR bei nur zwei verschiedenen Zeichen) verknüpft werden. Der Schlüsselstrom ist eine… …   Deutsch Wikipedia

  • Block cipher modes of operation — This article is about cryptography. For method of operating , see modus operandi. In cryptography, modes of operation is the procedure of enabling the repeated and secure use of a block cipher under a single key.[1][2] A block cipher by itself… …   Wikipedia

  • Cryptomeria cipher — The Feistel function of the Cryptomeria cipher. General Designers 4C Entity First published …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.