The Lorenz cipher

The Lorenz cipher, built into the Lorenz SZ40 and SZ42 machines, protected the most senior German Army communications in the Second World War. The Enigma encrypted letters one at a time by hand. The Lorenz was bolted onto a teleprinter and encrypted whole streams of five-bit characters automatically. British codebreakers called the traffic "Fish" and the machine "Tunny", and breaking it, without ever having seen one, led to Colossus, one of the first electronic digital computers.

How it worked

A teleprinter sends each character as five on-or-off pulses (the ITA2 code, a descendant of the Baudot code). The Lorenz machine sat between the operator's keyboard and the radio transmitter and combined each character with a key character using XOR, the "add without carrying" operation on bits: 0 + 0 = 0, 1 + 1 = 0, 0 + 1 = 1. It's the same trick as the one-time pad, and just as there, running the same operation again with the same key returns the plaintext. The difference is where the key came from. It didn't come from a random tape but from a set of wheels, which generated a long, apparently random, but repeating, stream.

The machine had twelve wheels, each with a ring of pins that could be pushed to either side, giving a 0 or a 1 at each position. There were five χ (chi) wheels, five ψ (psi) wheels and two motor wheels:

At each character, each of the five bit positions was the XOR of one χ wheel and one ψ wheel. The five resulting bits were XORed with the five bits of the character to be sent. The χ wheels moved every time and the ψ wheels only some of the time, so the key stream didn't repeat as simply as a set of independently turning wheels would. Multiply the wheel sizes and the number of ways to set the wheels comes to 16,033,955,073,056,318,658, about 1.6 × 10¹⁹, roughly 64 bits. (The χ wheels alone have 22,041,682 positions, and the ψ wheels 322,303,017.)

The mistake that gave it away

The wheel settings were meant to change with every message, and in 1941 they were announced to the receiver in a twelve-letter indicator at the start of the message. On 30 August 1941 a message of about 4,000 characters was sent from Athens to Vienna. The receiving operator asked for it to be sent again, and the sender, instead of resetting the wheels, sent it again with the same settings, with small changes of wording and abbreviations. The British now had two messages encrypted with the same key stream: a depth.

That's a disaster for any stream cipher. The XOR of the two ciphertexts is the XOR of the two plaintexts, and the key stream cancels out. Here's the effect, computed in scripts/examples/machines-examples.mjs with letters standing in for five-bit codes (numbers 1 to 26, not the real teleprinter code). Encrypt ATTACKATDAWN and RETREATATDUS with the same key stream, and XOR the two ciphertexts. You get 19 17 0 19 6 10 21 21 16 5 2 29, exactly the XOR of the two plaintexts, with no key in it. Guess that the first message begins ATTACK and XOR that into the result, and the other message comes out as RETREA. John Tiltman used exactly this reasoning, with real language and a lot of patience, to recover both plaintexts and, from them, the whole key stream of about 4,000 characters.

Tutte reconstructs the machine

With a long stretch of key stream and no machine, the mathematician Bill Tutte spent about three months, from late 1941, working out how it had been made. He wrote the stream in rows and looked at differences, and he spotted a repetition every 41 places. That meant one part of the key came from a wheel of 41 pins. By January 1942, working from that thread, the team had worked out the complete logical structure of the machine, the wheels and the way they moved, without any hardware to look at. The first physical Lorenz machine Bletchley Park saw was in 1945, as Germany surrendered.

Knowing the structure wasn't enough, because the wheel patterns changed (monthly, later daily), and each time the pin patterns had to be found again from the intercepted messages. A group called the Testery, under Ralph Tester, did the decrypting by hand, using machines to help. Max Newman's group, the Newmanry, built machines to find the χ wheel settings. Their first machine, Heath Robinson, compared two paper tapes at about 2,000 characters a second and suffered from the tapes going out of step. Tommy Flowers, an engineer at the Post Office Research Station, designed a different one, Colossus, using thousands of valves and an optical tape reader running at about 5,000 characters a second. The first Colossus became operational in December 1943, and ten were in use at the end of the war. Colossus wasn't a general-purpose computer, but it was electronic, programmable in a limited way, and fast. After the war most of the machines were dismantled, on Churchill's orders, and GCHQ kept two.

In October 1942 the Germans replaced the twelve-letter indicator with a book of one-use settings, a change that closed off a source of depths. The decryption of Lorenz messages continued, since the machines and the structure of the key stream were known, and it gave the Allies high-grade intelligence on German strategy.

Why it isn't secure, and what it shows

• A key stream that repeats isn't a pad. The wheels generated a long stream fixed by the settings, and two messages with the same settings gave a depth.
• The key stream has structure. A one-time pad is random. The Lorenz stream was made of wheels with known sizes, and Tutte found those sizes from the stream itself. A stream cipher has to make its output look random to anyone who doesn't know the key, and modern ones such as ChaCha20 are designed with that as the main goal.
• Procedure matters. The break came from an operator resending a message with the same settings. The same lesson applies to AES-GCM, where reusing a nonce breaks it.

The code

// The principle of the Lorenz machine, simplified: five chi wheels and five psi wheels each give one key bit; the two motor wheels decide when the
// psi wheels move. Each wheel is an array of pins (0 or 1). `text` and the result are arrays of five-bit numbers (0 to 31); the same call decrypts.
function lorenz(text, chi, psi, mu61, mu37) {
  var pos = { chi: [0, 0, 0, 0, 0], psi: [0, 0, 0, 0, 0], m61: 0, m37: 0 };
  return text.map(function (ch) {
    var key = 0;
    for (var i = 0; i < 5; i++) key |= (chi[i][pos.chi[i]] ^ psi[i][pos.psi[i]]) << i;   // bit i is chi i XOR psi i
    var out = ch ^ key;                                                                  // XOR: the key stream cancels on the way back
    for (i = 0; i < 5; i++) pos.chi[i] = (pos.chi[i] + 1) % chi[i].length;               // the chi wheels move every character
    var move37 = mu61[pos.m61] === 1;                                                    // the 61-pin motor wheel moves every character
    pos.m61 = (pos.m61 + 1) % mu61.length;
    var movePsi = move37 && mu37[pos.m37] === 1;                                         // the 37-pin wheel moves only if the first says so
    if (move37) pos.m37 = (pos.m37 + 1) % mu37.length;
    if (movePsi) for (i = 0; i < 5; i++) pos.psi[i] = (pos.psi[i] + 1) % psi[i].length;  // and the psi wheels only if both motors allow
    return out;
  });
}

Common questions