Lorenz and Colossus — Volume 5 — Bill Tutte — Deducing a Machine from Its Output

5.1 About This Volume

Volume 4 left Bletchley Park in the autumn of 1941 holding 3,976 consecutive characters of key from an unknown German cipher machine. The key had been recovered from a depth; it was known to be added to the plain text impulse by impulse; the indicator hinted at twelve wheels. Beyond that, nothing. For about three months the key resisted every attempt to find a pattern in it.

This volume is about the man who found one, and about the two things he did that made Tunny breakable at scale. The first was diagnosis: working out, from the key alone, that the machine was built from twelve wheels of particular sizes, that their outputs were added in pairs, and that half of them moved irregularly under the control of the other two. The second, a year later, was the statistical method: a way of finding the wheel settings of a message without any depth at all, by counting. The first made the codebreaking possible; the second made the machines possible, and is the bridge to the Newmanry, Heath Robinson and Colossus in Volumes 7–9.

The volume draws heavily on Tutte’s own account, a lecture he gave at the University of Waterloo on 19 June 1998 under the title “FISH and I” (Tutte 1998). It is a characteristically dry and self-deprecating document, and in places Tutte’s memory, fifty-seven years on, slips on details that the wartime record fixes; those places are noted.

5.2 A Chemist from Newmarket

William Thomas Tutte was born on 14 May 1917 in Newmarket, Suffolk, the son of a gardener, William John Tutte, and a cook and housekeeper, Annie Newell, who were then working at Fitzroy House, a racing stable. The family moved several times — for a while his father worked at the Rutland Arms Hotel in Newmarket — before settling in the village of Cheveley. At eleven Bill won a scholarship to the Cambridge and County High School for Boys, where his favourite subject was chemistry and where he found in the library W. W. Rouse Ball’s Mathematical Recreations and Essays, with its puzzles about networks and maps (MacTutor, “William Thomas Tutte”).

In 1935 he went up to Trinity College, Cambridge, to read natural sciences, and graduated in 1938 with first-class honours in chemistry; his first two published papers were in chemistry. But at Trinity he joined the Trinity Mathematical Society, and with three undergraduate friends — R. Leonard Brooks, Cedric Smith and Arthur Stone — he spent his spare time on a famous puzzle: can a square be cut into smaller squares, all of different sizes? The four solved it by translating each dissection into an electrical network and using Kirchhoff’s laws of current flow, and published the result in the Duke Mathematical Journal in 1940. They also published jokes and puzzles under a shared pseudonym, Blanche Descartes. The habit of turning a puzzle into a network, and the network into a calculation, would serve Tutte well.

When war came, his college tutor, Patrick Duff, suggested him for code-breaking. After an interview and a short cryptographic course in London, Tutte joined the Research Section at Bletchley Park in 1941 — in May, according to both GCHQ and his own recollection (“in (I think) May 1941”); some biographies give January (GCHQ, “William Tutte”). His first job was the Hagelin C-38m cipher machine of the Italian Navy. “It was several months later,” he recalled, “that I encountered Tunny.”

5.3 “See What You Can Do with This”

By then Tiltman had read the depth and recovered the key. The Research Section, under Major Gerry Morgan, had been studying it, impulse by impulse, without success. Tutte’s own words describe what happened next:

Some three months later, the key still unbroken, Major G.W. Morgan, head of the Research Section, gave a copy of the key to me and said “See what you can do with this”.

— Tutte, “FISH and I” (1998)

5.3.1 The 575 rows

Tutte had learned at the cryptographic school a classical technique associated with the nineteenth-century Prussian officer Friedrich Kasiski: if a cipher is periodic, write the text out in rows whose length is the period, and repetitions will line up vertically in the columns. He decided to try it on one impulse of the key at a time — on the stream of dots and crosses that made up, say, the first impulse of every key character. But on what period?

The indicator gave a hint. Of its twelve letters, eleven appeared to range over 25 possibilities and the twelfth over only 23. Perhaps the wheels had 25 or 23 positions. Tutte decided to cover both at once:

Perhaps I should try periods of 23 or 25. Or why not try both at once by writing the impulse on a period of 23 × 25 = 575? I can’t say that I had much faith in this procedure but I thought it best to seem busy. So I wrote out the first impulse in 7 rows of length 575 and looked for repeats of short patterns of dots and crosses, vertical repeats from row to row.

— Tutte (1998)

He did this by hand, on squared paper: seven rows of 575 dots and crosses, some four thousand symbols, written out and scanned. A footnote in the lecture adds: “I hope noone is going to ask why I didn’t use a computer.”

5.3.2 The diagonal

As he expected, there were not significantly many vertical repeats. But there were repeats on a diagonal — each row’s patterns turning up again in the next row one place to the left. That meant the true period was one less than the width he had chosen:

It seemed that I would have got better results on a period of 574. So I wrote out the impulse again on that period and found pleasingly many repeats of dot-cross patterns of length 5 or 6.

Then I tried a period of 41, this being a prime factor of 574, with even better results.

— Tutte (1998)

574 is 2 × 7 × 41. Written out on a period of 41, the first impulse of the key was, in the words of the later accounts, a rectangle of dots and crosses “replete with repetitions”. Something in the machine contributed a pattern of exactly 41 characters to the first impulse, repeating over and over.

A simulation shows the effect, and also why it is subtle. Four thousand characters of SZ40 key were generated by the unit’s simulator (lorenz_sim.py, run by 03-outputs/tools/slot_examples.py) with invented wheel patterns, the psi patterns given short runs of like signs as the 1941 patterns had; with that motor the psi wheels stood still on 40 per cent of letters. This is a simulation, not the 1941 key. Written out at any width, the first impulse looks like noise, and a letter matches the one directly above it about half the time at every width from 38 to 44. The repetitions show in pairs: at the right width, two neighbouring letters in one row repeat the two above them, or repeat them with both signs reversed, far more often than chance.

Table 1 — The diagonal

Width	Letter same as the one above	Neighbouring pair same, or reversed, as the pair above
39	50.1%	49.9%
40	49.3%	51.3%
41	50.1%	65.0%
42	48.5%	50.2%
43	49.3%	50.1%

At width 41 every column holds the same cam of the 41-cam wheel, so that wheel’s contribution cancels between one row and the next, and what is left changes only when the stuttering second component changes. At 40 or 42 the 41-cam pattern slides one place per row and the pairs agree only by chance. The same test in Bletchley’s later language is a count of dots in ΔK1 + ΔK1 one row back — a first sketch of the differencing that Tutte made the centre of everything.

5.3.3 Two components

But the 41-character pattern did not explain the whole impulse. Tutte found that the first impulse of the key was the sum of two streams of dots and crosses. One, which he named χ1 (chi-one), was strictly periodic with period 41: it moved on one place with every character. The other, which he named Ψ1 (psi-one), was “basically periodic too, with period 43. But whereas χ1 moved on one place for each letter, Ψ1 sometimes moved on one place and sometimes stayed still” (Tutte 1998). When it stayed still, it went on contributing the same dot or cross to character after character.

That was the key to the key. A stream that stands still now and then produces long runs; and the psi patterns the Germans had set up in 1941 already contained, as Tutte put it, “too many sequences of 3 or more dots or 3 or more crosses”, which the stuttering motion stretched out further. So in the key, many stretches of five or six characters in an impulse were simply the corresponding stretch of the chi wheel’s pattern (or its reverse), with the psi contribution held constant beneath it. That is why short dot-cross patterns kept recurring at intervals of 41.

Tutte was candid about the role of luck. He thought that, had he not noticed the diagonal, he would have gone on to try 23 on the other impulses — and on the fifth it would have worked directly, because the fifth chi wheel turned out to have exactly 23 positions:

I suppose I would have been said to have broken the key by pure analytic reasoning. As it was I was thought to have a stroke of undeserved good luck. There must be a moral in this.

— Tutte (1998)

5.4 The Whole Machine

With the first impulse split into χ1 and Ψ1, “the whole Research Section joined in to analyse each other impulse into a χ-wheel and a Ψ-wheel” (Tutte 1998). The results, confirmed later when a captured machine could be examined, were:

Table 2 — With the first impulse split into χ1 and Ψ1, "the whole Research Section joined in to analyse each other impulse into a χ-wheel and a Ψ-wheel" (Tutte 1998). The results, confirmed later when a captured machine could be examined, were

Bletchley name	Positions (cams)	Motion
χ1, χ2, χ3, χ4, χ5	41, 31, 29, 26, 23	Step once with every character
Ψ1, Ψ2, Ψ3, Ψ4, Ψ5	43, 47, 51, 53, 59	All five step together, or all stand still
μ61 (motor 1)	61	Steps once with every character
μ37 (motor 2)	37	Steps when μ61 shows a cross

The psi wheels stepped when the second motor wheel, μ37, showed a cross, and stood still when it showed a dot. Each key character was the sum of the five chi wheels’ current positions, one per impulse, and the five psi wheels’ current positions — the psi stream with its repetitions, which Bletchley called extended psi, ψ′. In the notation of the General Report on Tunny, K = χ + ψ′.

A point of detail shows how carefully the wartime record has to be read against memory. In his 1998 lecture Tutte said that “the χ-wheels moved in step” under the control of the motor — the reverse of the true arrangement, in which the chi wheels step regularly and the psi wheels move together. Tiltman’s article and the General Report are unambiguous, as is the analysis Tutte himself describes a few lines earlier, in which χ1 “moved on one place for each letter” and Ψ1 did not. The slip is one of naming, not of substance, and this series follows the wartime sources.

The diagnosis was complete by January 1942 (Copeland 2010). Bletchley Park now knew the logical structure of a German cipher machine that none of its staff had seen, down to the size of every wheel and the rule by which they moved. It would be three more years before a real one was captured. The citation for Tutte’s appointment as an Officer of the Order of Canada in 2001 described the work as “one of the greatest intellectual feats of World War II.”

Tutte himself was characteristically careful about credit. “In ‘Code Breakers’ I am said to have worked out the whole of this by myself,” he said in 1998, referring to the 1993 collection of Bletchley memoirs edited by F. H. Hinsley and Alan Stripp, “but that is an exaggeration.” He named the whole Research Section, and Tiltman named Morgan and Tutte together. Jack Copeland, the leading historian of the subject, nevertheless writes that Tutte “single-handedly deduced the fundamental structure of the Tunny machine” from the depth key. Both can be true: the first insight, the method and the decisive split into chi and psi were Tutte’s; the full reconstruction was a team effort that followed his lead.

5.5 Reading Current Traffic

Knowing the structure of the machine was necessary but not sufficient. To read a message, the codebreakers needed the cam patterns in force — which the Germans changed periodically — and the start position of each wheel for that message.

The first attempts on current traffic, early in 1942, were a disappointment. A new depth was read and yielded about 1,000 characters of key, “but the Germans had corrected their Ψ-error”, Tutte recalled: the new psi patterns no longer had the long runs that had made the 1941 key so revealing. A near-depth helped — two messages whose indicators agreed in all but one letter, read with great labour by skilled linguists. Then, in July 1942, Alan Turing, on loan to the Research Section, devised a hand method for recovering the wheel patterns from a stretch of key, which became known as Turingery and is described in Volume 6. Tutte admired it — “a method requiring great artistry. I never used it successfully myself. But there were others with whom it worked well enough” (Tutte 1998).

With the patterns known, messages that were not in depth could be broken by dragging cribs: sliding a stereotyped phrase such as SPRUCHNUMMER or OBERKOMMANDO9WEHRMACHT along the cipher text until it yielded a plausible stretch of key. Tutte also recalled that wheel patterns could sometimes be recovered from the indicators alone, by exploiting which wheels in which messages shared settings — a method that defeated him but that Captain J. M. Wyllie, in civilian life an editor of the Oxford Latin Dictionary, made to work: “This is just the job for a lexicographer,” Wyllie said. The newly formed Testery under Major Ralph Tester (Volume 6) used all of these methods from July 1942, and for a few months read much of the traffic.

Then, in October 1942, the Germans replaced the twelve-letter indicators with numbers from a code book. The indicators no longer gave away which messages shared wheel settings, and depths became rare and hard to recognise. Tutte posed the question that followed:

Given a cipher message Z, and given the corresponding wheel-patterns, how were we to set those wheels so as to decipher the message?

— Tutte (1998)

5.6 The Statistical Method

His answer, worked out in November 1942, used an idea Turing had introduced that summer: differencing, written Δ (delta). The delta of a stream is the stream added to itself shifted by one place: each character is added to the next one. Differencing does something useful to each of the three ingredients of the cipher text.

• The chi stream. Δχ is still periodic with the chi wheel’s period, so it is still a fixed pattern that can be slid along a message.
• The psi stream. Whenever the psi wheels stand still, consecutive extended-psi characters are identical, so Δψ′ is all dots. Since the motor held the psis still a large part of the time, Δψ′ was dot far more often than half.
• The plain text. German military text, as sent on teleprinters, was full of doubled letters and repeated characters — double spaces, figure and letter shifts, padding — and wherever a character is repeated, its delta is all dots too.

Tutte then took the step that made the method work. Instead of looking at one impulse, he added two together. Writing the cipher text equation for impulses 1 and 2 and adding them:

(ΔZ₁ + ΔZ₂) = (Δχ₁ + Δχ₂) + (ΔΨ₁ + ΔΨ₂) + (ΔC₁ + ΔC₂)

— Tutte (1998), equation (2), where C is the clear (plain) text

He estimated that ΔΨ₁ + ΔΨ₂ would be about 70 per cent dot, and that ΔC₁ + ΔC₂, for German military text, would be “60% dot or a little more”. Two streams that are each mostly dot add to a stream that is also mostly dot. So the known quantity, ΔZ₁ + ΔZ₂, should agree with the unknown Δχ₁ + Δχ₂ rather more often than it disagreed — “in favourable cases there might be as much as 55% agreement.”

And Δχ₁ + Δχ₂, built from wheels of 41 and 31 positions, repeats every 41 × 31 = 1,271 characters. If the cam patterns are known, there are only 1,271 possible relative positions of the message and the combined pattern. Try them all; count, at each one, how often ΔZ₁ + ΔZ₂ agrees with Δχ₁ + Δχ₂; the position with the largest excess of agreements is very probably the true start of χ1 and χ2. Extensions of the same idea would then set χ3, χ4 and χ5. Once all five chi wheels were set, the chi component could be stripped from the cipher text — Bletchley called the result the de-chi — leaving plain text plus extended psi, which the Testery could break by hand.

A simulation shows the size of the effect. A message of 4,000 characters of real German teleprinter plain text (taken from the 2007 Cipher Event decipherment) was enciphered by the unit’s simulator on the Bream link wheel patterns of 14 April 1944 printed by Tiltman, with the SZ42A motor, and counted at every one of the 1,271 starts by colossus_count.py. Over the 3,999 differenced characters, ΔZ1 + ΔZ2 agreed with Δχ1 + Δχ2 at the true start (χ1 at 21, χ2 at 31) 2,159 times — 54.0 per cent. At the other 1,270 starts the counts averaged 1,999.4 (50.0 per cent) with a standard deviation of 33.6, and the best of them reached 2,105. The right setting stood 4.7 standard deviations above the crowd: a modest bulge, but unmistakable once the whole table is in view. (Theory predicts a standard deviation of √3999 / 2 ≈ 31.6 for a fair coin, close to what the wrong starts show.) Volume 14 runs the same count on a real SZ42 message.

The method was the first to set the wheels of a single message with no depth at all, and it rested on nothing more than the two statistical flaws noted in Volume 2: the psi wheels’ habit of standing still together, and the German language’s habit, on a teleprinter, of repeating characters. Tutte saw at once that it could be pushed further. Given a long enough message, the same kind of statistics could recover not just the settings but the unknown cam patterns themselves:

One day, having received a message 15,000 letters long I tried out the idea. It worked. I remember reporting to Major Tester, head of the appropriate Section (known as the Testery) with the news of “the first machine to be broken on a depth of one”.

— Tutte (1998)

5.6.1 Too much counting

There was one obstacle, and it was decisive. For a message of, say, 4,000 characters, setting χ1 and χ2 by Tutte’s method meant comparing 4,000 pairs of symbols at each of 1,271 positions — about five million comparisons — and then doing similar work for the other three chi wheels, for every message, every day. No hand section could do that. “I remember explaining the method to Gerry Morgan and Max Newman,” Tutte said. “There were rapid developments. Post Office engineers in consultation with applied mathematicians mechanized the process using first electrical relays and then vacuum tubes. This was the way to Bletchley’s pioneering electronic computer ‘Colossus’.”

The General Report on Tunny, written by the Newmanry’s statisticians at the end of the war, recorded that “when two or three messages had been set by the statistical method, it was seen that new machinery, and a new section to operate it, was needed, for the hand methods took far too long to be of much practical use” (General Report on Tunny, 1945, ch. 44). Max Newman was put in charge in December 1942. The counting that Tutte had shown to be possible became the job of Heath Robinson and then of Colossus — the 1+2 break-in, as the Colossus operators called the first run on every message. Volumes 7 to 9 tell that story; Volume 14 builds a bench-top machine to run the same statistic.

Tutte’s method was soon strengthened by the statisticians who joined the Newmanry, above all Jack Good, who put the scoring on a firm footing using Turing’s Bayesian ideas, and it grew into a family of runs for setting and breaking all five chi wheels. Tutte’s own summary of what had made Tunny vulnerable stands as the verdict on the whole German design: “the main weakness of the Tunny machine was that the five Ψ-wheels kept in step. They either all moved on one place or they all stayed still. Turing’s method and the statistical method all depended on this” (Tutte 1998).

5.7 After the War

When the war ended Tutte returned to Cambridge as a graduate student in mathematics; Trinity elected him to a research fellowship though he had no formal mathematical qualifications. He took his PhD in 1948 under Shaun Wylie — himself a Bletchley codebreaker — with a thesis titled An Algebraic Theory of Graphs. That year H. S. M. Coxeter invited him to the University of Toronto. In 1949 he married Dorothea Mitchell. In 1962 he moved to the new University of Waterloo, where he helped found the Department of Combinatorics and Optimization, and he remained there until he retired in 1985 (Wikipedia, “W. T. Tutte”).

In the next forty years Tutte became one of the founders of modern graph theory. His results on matchings in graphs, on the theory of matroids, on the enumeration of planar maps, and the polynomial that bears his name, are part of the foundations of the subject; he wrote its standard texts and edited its main journal. He was elected a Fellow of the Royal Society of Canada in 1958 and of the Royal Society of London in 1987. Almost none of his colleagues knew what he had done at Bletchley. The General Report on Tunny was declassified only in 2000; Tutte was 81 when he first spoke about Fish in public, at his 80th-birthday celebrations and in the 1998 lecture.

Recognition came late and mostly after his death. He was appointed an Officer of the Order of Canada in 2001. His wife Dorothea had died in 1994; he spent a few years back in Newmarket, returned to Canada in 2000, and died in Kitchener, Ontario, on 2 May 2002, aged 84. In 2011 Canada’s signals intelligence agency, the Communications Security Establishment, named its research institute the Tutte Institute for Mathematics and Computing. In September 2014 his home town unveiled a memorial at Rutland Hill (GCHQ, “William Tutte”). In 2025 he was one of ten people honoured on Royal Mail stamps marking the eightieth anniversary of VE Day (University of Waterloo, 2025).

5.8 The One-Paragraph Version

Bill Tutte, a Newmarket gardener’s son who had read chemistry at Trinity and helped solve the squared-square problem with electrical networks, joined Bletchley’s Research Section in 1941. About three months after Tiltman’s break, with the key still unbroken, Major Morgan gave him a copy. Tutte wrote its first impulse out by hand in rows of 575, saw repeats on a diagonal, tried 574 and then its prime factor 41, and found that the impulse was the sum of a regular 41-character stream (χ1) and an irregular one of period 43 (Ψ1) that sometimes stood still. The Research Section split the other impulses the same way and by January 1942 had the whole machine: five regular chi wheels, five psi wheels moving together under two motor wheels, 501 cams in all. When the Germans’ indicator change of October 1942 starved the hand methods of depths, Tutte devised, in November, a statistical method that set the first two chi wheels by counting agreements between the differenced cipher text and the 1,271-long chi pattern — too much counting for people, which is why Heath Robinson and Colossus were built. He spent the rest of his life as one of the founders of graph theory in Canada, his wartime work unknown until he was nearly eighty.

---

Next — Volume 6: The Testery — Breaking Tunny by Hand. Four German speakers in a wooden hut in July 1942, and by 1945 a section of 118 working three shifts round the clock. Major Ralph Tester’s codebreakers — Jerry Roberts, Peter Ericsson, Denis Oswald, Peter Hilton, Roy Jenkins and their colleagues — read Tunny with pencils, cribs, depths and Turing’s methods before any machine existed, then took the de-chi tapes from Colossus and finished the job by hand. How they did it, and what the October 1942 indicator change did to them.