William Tutte

Last Updated: 12 May 2017
Bill Tutte's diagnosis of the TUNNY cipher machine has been described as "the single biggest intellectual achievement at Bletchley Park"; the 24-year old's triumph was far from being the last of his remarkable life.

Tutte was the son of a gardener and a housekeeper. His early years were consumed with a love of nature, science and mathematics. His academic flair allowed him to win a scholarship at the Cambridge and County High School, 18 miles from his family home near Newmarket. The daily commute by bike and train was a long one. Tutte thrived at school and his scholarship allowed him to consider preparing for university. 

Again with the help of scholarships from the state, the college, and the county, Tutte was able to enter Trinity College Cambridge to study natural sciences, specialising in chemistry. However, from the start Tutte also attended lectures in mathematics and socialised with the Trinity Mathematical Society. Tutte and his associates were soon publishing elegant mathematical results and he gained a reputation as a natural problem solver. He completed his first-class chemistry degree in 1938 and although he began graduate work in chemistry, he looked to arrange a transfer to mathematics just as World War II was breaking out.

It was at this time that Tutte was interviewed by the Government Code and Cypher School (GC&CS). After a period of training, he was assigned to the research section at Bletchley Park in May 1941. The research section was concerned with ciphers that could not yet be exploited and so it was that Tutte was introduced to the TUNNY problem in October 1941. 

It is not easy to compare the TUNNY story with its more famous cousin Enigma. GC&CS had been in possession of an early Enigma machine in the 1920s and Bletchley was able to build on the work of Foss, Knox, and Rejewski in dealing with ever more complex evolutions and very large quantities of traffic that needed processing. By contrast, TUNNY signals had only been detected in 1940 and the design of the machine was complete mystery. Likewise, there were many fewer TUNNY messages to inform the cryptanalysis, however it was clear that these were the messages of the German high command and so of great intelligence value. 

Initially the only clue to TUNNY's design was a 12 letter indicator1 accompanying each message where 11 of the 12 indicator positions could take 25 different values, but the 12th position could only take 232. This seemed to indicate that TUNNY consisted of 12 rotors (the most complex Enigma variants used 4). Comparing messages with the same indicator provided evidence that TUNNY was an additive cipher that produced a long, seemingly random, stretch of key that was combined with messages using binary arithmetic. 

On August 30th 1941 the TUNNY story began in earnest. An operator made a fatal error and sent two near-identical messages with the same indicator. This allowed the veteran cryptanalyst John Tiltman to recover the underlying key over a marathon 10 days of manual cryptanalysis. The resulting 4000 letters of key would prove to be cryptanalytic gold-dust.

Although everyone in the research section was in no doubt as to the value of Tiltman's key, no-one could discern any structure to it; eventually the problem was passed to Tutte. Tutte elected to consider the key as a binary sequence and, knowing that letters were represented by 5 binary digits (bits), decided to look at every 5th bit hoping that this might be a simpler pattern. Guided by the indicators, he wrote this sequence in 7 rows of 575 (23x25) columns hoping to see repeats aligned by columns. He was surprised to instead see repeats aligned by diagonals. 

Chasing this phenomenon, Tutte was able to see that his sequence had a tendency to repeat at distances that were a multiple of 41 apart. Tutte realised that his sequence could be explained as a repeating sequence of 41 bits added to another sequence of bits which could remain the same for long stretches. He called these two sequences chi and psi and found that they could easily be explained with a rotor mechanism. 

This initial breakthrough only explained 1/5 of the Tiltman key, but with the help of the rest of the research section a similar explanation was found for the rest of the key. They were able to show that the TUNNY machine consisted of 5 chi wheels of different periods that stepped regularly, 5 psi wheels that sometimes stepped and sometimes remained stationary and 2 motor wheels that controlled the stepping of the psi wheels. Applying this knowledge to other messages revealed that each wheel could be configured in many different ways (known as a wheel pattern), but that these patterns would remain the same throughout a month. However, each wheel was placed in a different start position (known as a wheel setting) for each message as shared by the indicators. Thus even if the wheel patterns were known, quadrillions of different key patterns could be produced.

Fortunately, Tutte's diagnostic triumph was not his final contribution to the TUNNY problem. The research section could now move on to the task of developing attacks on TUNNY. Firstly, Tutte showed how the manual methods used by Tiltman could still be brought to bear in cases where indicators differed only in single places. Next, while Alan Turing was briefly on loan to the research section, he came up with the Turingery method for deducing wheel patterns from much shorter stretches of key. Thirdly, given the wheel patterns Tutte came up with a means to recover wheel settings for messages whose indicators agreed in one place with a message that was already recovered. 

The ideas reinforced each other and Tutte soon came up with a method to recover patterns by grouping together messages where one of the chi wheels was at the same setting (as shown by the indicator). These methods served Bletchley well until late in 1942. Even as the brilliance of the research section improved, so did the German operators. In November 1942 the Germans stopped using indicators and TUNNY decryption ground to a halt.

Again, Tutte came to the rescue. It was still possible to tell if two messages had exactly the same setting, which in turn allowed for recovery of patterns using the methods of Tiltman and Turing. Even given the patterns for a month, new methods were needed to recover each message's setting. Tutte realised that because the psi wheels all stepped in sync or all remained stationary, there was a great deal of structure in the transitions from one key position to the next. Although not a linguist he also realised that there was structure in the transition from one letter to the next in the German language. By concentrating on the cipher transitions rather than the cipher letters this structure could be used to derive the most likely transitions in the chi wheels and so set them. 

Tutte's observation was brilliant but the process was much too complex to perform by hand. Electrical engineering provided the solution and baroque machines known as Heath Robinsons were built to deal with Tutte's complex method. Production resumed, but Tutte did not stop. The methods still relied on knowing the chi patterns, but Tutte envisioned having long messages where many periods could be observed so that enough information was available to recover both the patterns and settings for chi wheels. This made the calculations significantly harder and better machines were needed. 

The COLOSSUS machines built by Tommy Flowers to implement Tutte's ideas represent a milestone in the history of computing. They proved their worth in July 1944 when the Germans began changing wheel patterns on a daily basis rather than monthly. The COLOSSUS machines allowed Bletchley to keep pace, with one source saying how in one week in 1945 Tutte's ideas and the COLOSSUS machines were able to recover 23 sets of wheel patterns and 358 sets of wheel settings.

After the war, Tutte returned to academia. He had been elected a Fellow of Trinity College in 1942, but still had not studied for a PhD. He began to research a thesis under the supervision of his Bletchley colleague Shaun Wylie. Tutte's most fruitful ideas were in the area of graph theory, a subject first developed by Euler to tackle the famous "Bridges of Konigsberg" problem. By 1945 graph theory was not considered a serious area of study. Wylie advised Tutte to apply himself in other areas, but Tutte persisted. In this way he became one of the founding fathers of modern graph theory and rose to international eminence. 

Graph theory abounds with concepts named after Tutte and his work laid the foundations for its greatest results such as the proof of the famous four colour theorem. When Tutte completed his PhD in 1948 however, there was little interest in graph theory at British universities. The great geometer Coxeter took interest in Tutte's work and helped him to find a post at the University of Toronto. 

In Canada, Tutte's mathematics went from strength to strength as did his love of cycling and hiking, through which he met his wife Dorothea. In 1962 Tutte took up a position at the relatively new University of Waterloo in Canada. The change of scenery allowed Tutte to manage a much-loved, large garden of wild plants alongside the Grand River. His reputation continued to grow and he collected many accolades, including Fellowship of the Royal Society and an Officer of the Order of Canada. 

Towards the end of the twentieth century the secrecy around Bletchley Park began to lift and Tutte was able to speak of some of his wartime work. This led to yet more recognition as he was named honorary director for the Centre for Applied Cryptographic Research at Waterloo. Even after his death in 2002 recognition continued. Canada's Communications Security Establishment (CSE) founded the Tutte Institute for Mathematics and Computing in 2011. His former hometown of Newmarket unveiled a memorial to him in 2014. 

One of Tutte's obituaries notes that although "a very shy man [with a] placid temperament", "in his quiet way he enjoyed the recognition". In a letter to Tutte's niece in 2012 David Cameron wrote "I understand that, partly owing to the secrecy of his work, Professor Tutte was never honoured officially in his lifetime, although he undoubtedly held the respect of those in his field [...] I can say without a doubt that Bill Tutte deserves the thanks of the British people." Bill Tutte's reputation deserves to only grow with time. 

To contribute to the Bill Tutte Memorial Fund, please visit http://billtuttememorial.org.uk/the-fund/




1 The indicators were understood to communicate a way to set up the machine on a per message basis. Each message was supposed to have the machine set up in a different way and so one should not expect to see the same indicator in two different messages. In practice, indicators would occasionally repeat.

2 This means that several quadrillion different indicators were possible and presumably that the machine could be set up in several quadrillion different ways.