How does the Vernam cipher work?

The Vernam cipher uses the XOR operation to combine five-bit teleprinter codes with a random key stream, producing an encrypted character. It was a promising technique but faced synchronization issues with paper tapes.

What was the 'Z-Mug' indicator and why was it important?

The 'Z-Mug' (or 'Zed-Mug') was the initial setting indicator sent with German messages. Bletchley Park had a lucky break using it, and analysis of its limited character set hinted at the machine's design.

How did Bill Tutt investigate the 'Tony' machine?

Bill Tutt suspected cog wheels were used and analyzed the limited character set of the indicator. He focused on the bit streams, looking for repeating patterns, which led to the discovery of a 41-tooth wheel.

What is the significance of prime and relatively prime numbers in cipher machines?

In machines with cog wheels, using prime numbers or relatively prime numbers for the number of teeth helps ensure longer, less predictable repetition cycles in the key stream, making decryption harder.

What was the full structure of the 'Tony' machine's key generation?

The machine used two sets of five cog wheels. The first set (41, 31, 29, 26, 23 teeth) generated the core key stream, while the second set (43, 47, 51, 53, 59 teeth) added a 'stutter' or obscuring mechanism.

Why did the Germans eventually stop sending the indicator?

The Germans stopped transmitting the indicator in mid-1942. While they believed it made the system totally secure, it was pointless and ultimately removed, which was a missed opportunity for the Allies to gather key settings.

Key Moments

Exploiting the Tiltman Break - Computerphile

Computerphile

Education3 min read26 min video

Sep 5, 2018|313,046 views|5,636|226

computers computerphile computer science Computer Science University of Nottingham Professor Brailsford UHD 4K Lorenz Cipher Decryption

Save to Pod

Key Moments

TL;DR

Exploiting the Tiltman Break: How Bletchley Park deciphered German teleprinter ciphers using a unique attack on indicator settings.

Key Insights

The 'Tony' or 'Lorenz' cipher, used by the Germans, was a sophisticated teleprinter cipher employing the Vernam cipher principle.

Bletchley Park had to overcome challenges in synchronizing two paper tapes for the Vernam cipher, leading to the development of machines that generated key streams automatically.

The 'Tiltman Break' or 'Z-Mug' indicator provided crucial information, revealing non-random patterns in the German key stream generation.

Bill Tut's analysis of the indicator's limited alphabetic characters (23 in one position, 25 in others) suggested the use of cogwheels with prime or relatively prime numbers of teeth.

Through meticulous analysis, codebreakers deduced the structure of the German machine, identifying two sets of cogwheels and an obscuring mechanism that sometimes skipped.

The realization that wheel patterns were changed monthly, not daily, and that the indicator setting was provided, allowed for extensive decryption.

THE NECESSITY OF COLOSSUS AND THE MYSTERY OF TELEPRINTER TRAFFIC

The development of the Colossus machine was driven by the need to break a specific type of German cipher traffic, known enigmatically as 'Tony' by Bletchley Park. Initial analysis of intercepted signals revealed it to be broadcast teleprinter traffic, a technology familiar to the codebreakers. However, its precise nature and the machine generating it remained a mystery, prompting a deep dive into its cryptographic underpinnings, which were based on the Vernam cipher principle.

UNDERSTANDING THE VERNAM CIPHER AND ITS IMPLICATIONS

The Vernam cipher, conceptualized by Gilbert Vernam, involves XORing a plaintext message with a random key stream, character by character, to produce ciphertext. This method offers perfect secrecy if the key stream is truly random and used only once. Bletchley Park's understanding of this principle was crucial, but practical implementation faced challenges, particularly with synchronizing two paper tapes, leading to difficulties with slippage and alignment.

THE BIRTH OF THE TILTMAN BREAK AND THE 'Z-MUG' INDICATOR

A breakthrough in deciphering 'Tony' traffic came with the analysis of a specific indicator setting, dubbed 'Z-Mug' (or 'Zed-Mug'). This setting, which was transmitted before longer messages, provided a crucial clue. The Germans, like the Allies with Enigma, sent initial settings, but for 'Tony', these indicators consistently used only 25 alphabetics, with one position limited to 23. This deviation from the expected 26 alphabetics hinted at a non-random element in the key generation process.

BILL TUT'S ANALYSIS: COGWHEELS AND PERIODICITY

Bill Tut, a new recruit with a background in puzzles, was tasked with analyzing the 'Z-Mug' indicator. Recognizing the significance of the limited character sets (23 and 25), he hypothesized that the machine employed cogwheels for key stream generation, similar to other crypto machines. He reasoned that if cogwheels were used, their number of teeth would influence the repeat patterns of the generated key stream. The product of 23 and 25, 575, became his initial focus for analyzing potential periodicity.

UNRAVELING THE MACHINE'S STRUCTURE: COGWHEELS AND OBSCURATION

Tut's initial analysis of a long strip of bits, expecting repeats every 23 or 25 positions, unexpectedly revealed a diagonal pattern suggesting a period of 41. This led to the deduction that a cogwheel with 41 teeth was involved. Further investigation by a team revealed a complex structure: two sets of five cogwheels each. The first set had teeth counts of 41, 31, 29, 26, and 23, providing the primary key stream. A second set of five cogwheels (43, 47, 51, 53, 59 teeth) acted as an obscuring mechanism, occasionally skipping positions.

THE STRATEGIC ADVANTAGE: WHEEL PATTERN CHANGES AND DECRYPTION

A critical realization was that the Germans did not change the patterns on the cogwheels daily, but rather monthly, using the 'Z-Mug' indicator to set the initial state. Once the number of teeth on each wheel and the patterns were deduced, Bletchley Park could decrypt messages for an entire month. This strategic advantage, combined with the eventual understanding of the 'stutter' mechanism used by the Germans to disguise wheel movements, enabled the effective decryption of 'Tony' traffic.

Mentioned in This Episode

●Products

●Software & Apps

●Tools

●Companies

●Concepts

●People Referenced

Common Questions

The 'Tony' cipher was a German encryption machine used during WWII. Colossus was needed to help decrypt the traffic from this machine, which was broadcast via teleprinters.

Topics

Cipher Machines Vernam Cipher XOR Teleprinter Computational History Enigma Cog Wheels Key Stream

Mentioned in this video

Software & Apps

Siemens cipher machine

Mentioned as one of the other electro-mechanical machines being investigated for providing key streams.

haggle inside for machine

An electromechanical machine investigated in Sweden for generating key streams, mentioned as a precursor or similar technology to 'Tony'.

Hagglin machine

A cipher machine used for Italian ciphers that was simpler than 'Tony' and served as good training for Bill Tutt.

macOS

Mentioned as an example of an operating system in a general discussion about software.

BSD

Mentioned as an example of an operating system in a general discussion about software.

Concepts

relatively prime numbers

Numbers that do not share any common factors other than 1, important for ensuring longer repetition cycles in cog wheels, like 3 and 4.

Lorenz cipher

Referred to as the 'Lawrence cipher' by Bletchley Park in 1941, it was a different cipher machine that would not have been recognized by that name.

Vernam cipher

A concept developed by Gilbert Vernam at Bell Labs, involving XORing teleprinter codes with a key stream for encryption.

Tony cipher

A cipher machine used by the Germans, which Bletchley Park initially called 'Tony' because they didn't know the manufacturer.

teleprinter traffic

The type of broadcast identified from a strange trace, indicating the use of teleprinter machines which were common in the 1940s.

Bill Tutt's investigation of the Z-Mug indicator

Bill Tutt's analysis of the Z-Mug indicator revealed that one position consistently used only 23 out of 26 possible alphabetic characters, suggesting a prime number might be involved.

prime number

Numbers like 23 that have only two factors (1 and themselves), suspected by Bill Tutt to relate to the number of teeth on cog wheels in the cipher machine.

Z-Mug indicator

The 'indicator' setting famously used by the Germans, which Bletchley Park had a lucky break with. It was spelled 'hquibpexic mug' and later known as 'Z-Mug' or 'Zed-Mug'.

impulse one

What Bletchley Park called the leftmost stream of bits in the teleprinter characters, which Bill Tutt focused his initial analysis on.

Tools & Products

47-tooth wheel

Part of the second set of wheels used for obscuring the key stream in the 'Tony' machine.

cog wheels

The conceptual components Bill Tutt suspected were used in the 'Tony' machine, with varying numbers of teeth influencing key stream periodicity.

26-tooth wheel

A cog wheel in the 'Tony' machine's initial set. While not prime (2x13), it was relatively prime to others, making it safe.

23-tooth wheel

One of the initial cog wheels identified in the 'Tony' machine, present on stream five, confirming Bill Tutt's earlier hypothesis.

29-tooth wheel

One of the initial cog wheels identified in the 'Tony' machine, part of the five-wheel setup for generating the key stream.

43-tooth wheel

Part of the second set of wheels used for obscuring the key stream in the 'Tony' machine.

51-tooth wheel

Part of the second set of wheels used for obscuring the key stream in the 'Tony' machine. Non-prime (3x17), but relatively prime to others.

41-tooth wheel

The first identified cog wheel in the 'Tony' machine, discovered through analysis of the 'impulse one' bit stream's periodicity.

31-tooth wheel

One of the initial cog wheels identified in the 'Tony' machine, part of the five-wheel setup for generating the key stream.

53-tooth wheel

Part of the second set of wheels used for obscuring the key stream in the 'Tony' machine.

dots and crosses

A representation used for zeros (dots) and ones (crosses) on grids, found to be easier for spotting patterns than numerical binary sequences.

59-tooth wheel

Part of the second set of wheels used for obscuring the key stream in the 'Tony' machine.

Products

teleprinter machines

Common electromechanical devices used for sending and printing messages, providing a familiar technology to Bletchley Park staff.

People

Gilbert Vernam

Developer of the Vernam cipher, which involved XORing teleprinter codes with a random key stream.

Bill Tutt

A recruit at Bletchley Park who initially studied chemistry and transitioned to mathematics, tasked with analyzing the 'Tony' cipher.

Jack Good

A statistician who analyzed the 'Tony' system, noting that the 'stutter' mechanism of the second set of wheels was eventually a disfavor to the Germans as it became predictable.

Donald Michie

A statistician who, along with Jack Good, analyzed the 'Tony' system and its effectiveness.

Jerry Morgan

Head of the research section at Bletchley Park who assigned Bill Tutt to work on the 'Tony' machine and provided him with key information.

Jack Copeland

A historian who emphasizes mentioning that 'Tony' was the Bletchley Park name and 'Lawrence' would not have been known in 1941.