Lucifer (ECB)

create

create("lucifer")

family

Feistel

options

--key

self-inverse

no

keyspace

2^128 keys

try it

ciphers lucifer "ATTACK AT DAWN" --key 0123456789abcdeffedcba9876543210

Horst Feistel and his team built Lucifer at IBM in the early seventies. The name is a pun, sort of. Feistel was working on a system called Demonstration, the operating system cut it down to Demon, and Demon turned into Lucifer. One version of it, DTD-1, ended up in banking. Then IBM sent a Feistel version to the DES competition, and the NSA got the key down to 56 bits and the block down to 64 before it became DES.

There's no single Lucifer. The patent from 1971 has 48-bit blocks, John Lynn Smith had one on 32 bits, and Feistel wrote about a 128-bit one in Scientific American in 1973. This one is the version Arthur Sorkin described in Cryptologia in January 1984, with a FORTRAN listing at the end. It's the one everybody means today, and the one the attacks are written against.

A block is 16 bytes, split into two halves of 8 bytes. Every round takes the upper half byte by byte:

• one bit of the transform control byte decides whether the two nibbles of the byte swap places,
• S0 replaces the high nibble and S1 the low one,
• the result gets XORed with a key byte, that's the key interruption,
• a fixed permutation shuffles the 8 bits, and diffusion spreads them over all 8 bytes of the lower half.

Then the halves swap, like in any Feistel cipher. Sixteen rounds of that, no initial or final permutation. The key sits in a 128-bit register. Each round reads 8 bytes of it, and the first of them doubles as the transform control byte. After the round the register turns by 56 bits. Decryption is the same rounds with the key bytes read from the last round back.

The key is 32 hex digits. Case doesn't matter and spaces are ignored. Text goes in as UTF-8 with PKCS#7 padding, ciphertext comes out as lowercase hex, and decode wants hex back. The mode is ECB, over 16-byte blocks like AES.

const lucifer = create("lucifer");
const key = "0123456789abcdeffedcba9876543210";
lucifer.encode("ATTACK AT DAWN", { key }).text; // "3511c560cf11d61ec299417602e29bc5"
lucifer.decode("3511c560cf11d61ec299417602e29bc5", { key }).text; // "ATTACK AT DAWN"

Two listings

The listing from January didn't agree with the article. The comments and the drawings count bits from 0 on the left, the FORTRAN counted them the other way in a few places. A reader noticed, and in the July 1984 issue Sorkin sent a letter that rewrote six lines of it. The implementation here has those lines in.

That matters, because code copied straight from the January listing gives other ciphertext. The key above over sixteen zero bytes:

with the correction      a201fc18d62c85ef5965a58295bbf609
January listing as is    c318179d5848d88c322f7462c4f82b2a

The second one is what the lucifer.c posted to Usenet in April 1984 gives, and a FORTRAN 77 port on GitHub. Richard Outerbridge wrote that lucifer.c, and his later versions give the first one. In 2015 he sent six test triples to Cryptologia, because Sorkin never published a single one. A reviewer turned them down as "of little minimal interest". The tests check all six, and they match the corrected FORTRAN. Whole texts are checked against Outerbridge's later C code, since OpenSSL never had Lucifer.

How strong is it

Not very, and not for lack of key. 128 bits is plenty for brute force. The problem is differential cryptanalysis. Biham and Shamir went after it in 1991, and in 1996 Ben-Aroya and Biham showed that for about half the keys 2^36 chosen plaintexts and 2^36 work are enough. DES came out with S-boxes hardened against that attack, which IBM and the NSA knew about years before anyone else.

The block is 128 bits, so at least the Sweet32 collisions that hit Blowfish and Triple DES aren't a problem here.

Why ECB leaks

Same as every ECB here. Thirty-two As are two equal blocks, and they come out as two equal blocks:

lucifer.encode("A".repeat(32), { key }).text;
// 82b100ca638d465d5b4f3ab021dd3aa0 82b100ca638d465d5b4f3ab021dd3aa0 c08ecb7db68c5dadbe4ccb075fe83d4c

Spaces added to show the blocks. The last one is only padding.

A key that isn't 32 hex digits is an InvalidOptionError, a missing one a MissingOptionError. On decode, ciphertext that isn't whole 16-byte blocks of hex is a CipherError. A wrong key almost always breaks the padding, and that's a CipherError too. So are decrypted bytes that aren't UTF-8. It's a museum piece. Puzzles and learning, not secrets.