The Beginnings of Modern Cryptanalysis with Computers

The world’s first programmable, electronic, digital computer was created to aid in cryptanalysis during World War II. Named the Colossus, it was a set of computers designed by the British between 1943-1945. Colossus used vacuum tubes to perform calculations and Boolean operations in the cryptanalysis of the German rotor stream cipher, the Lorenz cipher. The Lorenz machines were designed to be attached to any teleprinter and encrypt its traffic. In essence, the Lorenz SZ40/42 was a rotor Vernam cipher machine.

Each letter in the teleprinter traffic would be divided into 5-bit binary numbers and XOR-ed with a key, resulting in cipher text. The key stream was generated by the machines using a ѱ (“psi”) component and a χ (“chi”) component, which was determined by the machines twelve wheels: five ѱ wheels, five χ wheels, and two motor wheels (or “mu” (µ) wheels). The Lorenz machines also had a varying number of pins on each wheel. Each χ wheel would move one position after every letter while the five ѱ wheels moved more irregularly (about half the time – an interval determined by the final two µ wheels).

            Key = χ-key ⊕ ѱ-key

Symbolically, the generated key is XOR-ed with the plaintext to encrypt, and XOR-ed with the ciphertext to decrypt.

Unlike the ciphers employed by the Lorenz machine, monoalphabetic ciphers (e.g. the Caesar cipher) can be broken easily through frequency analysis of ciphertext and looking at the distribution of letters. Considering that some letters are used more commonly in each language than others, a correlation will eventually reveal itself, given enough ciphertext. Despite polyalphabetic ciphers acting as a counter to letter frequency analysis, British cryptanalysts were able to reveal patterns by exploiting the fact that only one set of the machine’s wheels (χ wheels) would turn with every character while the other did not. Bill Tutte developed a cryptanalysis attack to exploit this weakness, known as the “1+2 break in,” or “double-delta attack.”

To summarize the double-delta attack very generally, Tutte would take two consecutive letters of the encrypted message and two consecutive letters of the ψ-key and would then add together the first two symbols of each:

Δ C1 Δ C2 + Δ ψ’1 Δ ψ’2

Tutte realized that these terms would each add up to zero more than half the time. While the ѱ-wheels were designed to only move half the time to add an extra element of randomness, it became apparent that when the ѱ-wheels both remained the same then the delta of the two would be zero. Because both ѱ-wheels change position 50% of the time, and when they do move there is a 50% chance that both will move, this results in Δ ψ’1 Δ ψ’2 being zero about 75% of the time. Given these probabilities, Tutte figured out that if the χ-wheels were in the correct position you should be getting more zeroes than ones. Colossus was designed to run Bill Tutte’s procedure to count the zeroes and look for patterns, enabling the British to work out the position of the ψ-wheels and χ-wheels (and later Colossus II enabled them to work out the positions of the pins on each wheel as well).

The reason I wanted to write about the Lorenz machines, Bill Tutte, and the Colossus is to show the link that has always existed between programmable computers and cryptanalysis. In the modern era where information systems are ever-present and critical for many functions of society, there is a need for effective and secure cryptographic routines.

Leave a Reply

Your email address will not be published. Required fields are marked *