The Bletchley Park Codebreakers

by Michael Smith

  The same method worked well on the other levels producing chipatterns (χ-patterns) of lengths 31, 29, 26 and 23 and associated psipatterns (ψ-patterns) of lengths 47, 51, 53 and 59. It then emerged that all the psi-patterns could be regarded as having moved or having stood still together, suggesting a motor stream. This was soon diagnosed as a pattern of length 37, called μ37, extended by a regularly moving pattern of length 61, called μ61. The Tiltman–Tutte triumph was complete.

  The Usage

  This diagnosis determined all that had to be known about the Tunny machine for that pair of transmissions – its structure, the allocation of pattern-lengths to levels and the wheel patterns themselves. The research section then had to find out how long the wheel patterns stayed unchanged, and whether the allocation of lengths to levels could be changed. They had valuable help from a depth sent on 3 July 1941. They had by now (from Tiltman’s earlier success with the depth) a long sample of plaintext; with that to help them they read two stretches of lengths 500 and 300 characters of this July depth. Tutte’s method was successfully applied to the resulting stretches of key. They found that the allocation of pattern-lengths to levels was unchanged. Another depth of July 1941 was also solved. For all three depths the psi-patterns were the same; for both the July depths the chipatterns were the same, but different from those in the August depth; and the μ-patterns were all different.

  Early Wheel-Setting

  There were, of course, many transmissions in July 1941 that were not in depth. The research section had the chi-patterns and psi-patterns and they used a highly laborious method of setting the wheels and so deciphering the transmissions. It involved trying likely cribs as plain-text at the start to give putative key; then subtracting from the putative key the chi-pattern at all possible settings for each level; and hoping to recognize possible fragments of the extended psi-streams. It was a long time before their first success, but by April 1942 they had deciphered several transmissions.

  A Change in Tunny

  Various features of Tunny that favoured the analyst were, from time to time, abandoned by the Germans. The first of these concerned the psi-patterns, and is best described in terms of an important symbol Δ. Δ before a symbol describing a stream of bits or characters means the stream formed by adding together each pair of consecutive bits or characters. So

  In all Tunny ever recovered, both the χi and the Δχi patterns for the ith level had as nearly as possible equal numbers of dots and crosses. Initially this was also true for the ψi and the Δψi patterns. It was this feature of the Δψi patterns that had let Tutte in. In order for a particular bit in Δψi' to be a cross, both the total motor and Δψi must be a cross. If a is the proportion of crosses in the total motor and b the proportion in Δψi, then the proportion in Δψi' is a b. In early Tunny b was nearly ½, so that ab was much less than ½ and Δψi' had considerably more dots than crosses. That meant that Δχi was equal to ΔKi considerably more often than not, so that ΔKi written on a width appropriate for the ith level would be expected to give a majority of bits in each column that were equal to that bit in Δχi. That was the feature that allowed Tutte to reconstruct Δχi (and so χi) for each level separately.

  By the end of 1941, the German cryptographers plugged this gap. Thereafter the total motors and psi-patterns were always designed in such a way that a b ≅ ½.

  Second Generation Wheel-Breaking and Setting

  After a drought, depths started to reappear in February 1942, and the research section read some of them and tried Tutte’s method without success. That was, of course, because by then a b ≅ ½ and no attack in single streams could work.

  They did eventually break the patterns for March and April 1942. In each month, there was a ‘near depth’, a pair of transmissions whose indicators differed only in the letters that gave the setting for two or three chi-wheels. They contrived a long and highly resourceful method of exploiting the differences of the χ-settings of those wheels, and eventually prised the whole thing open. They found that between March and April both the psi-patterns and the chi-patterns were different. Perhaps the psi-patterns changed quarterly, the chi-patterns monthly, and the μ-patterns daily.

  The wheel settings were given by indicator letters, but they were not in letter order. When, however, two indicators had the same letter in a position, the wheel for that position started at the same place for the two transmissions. This meant that wheel-setting during a month gathered pace. The research section had such success setting wheels for March and April 1942 that it became clear that they needed a machine to do the decryption. The first was ordered and was delivered in June 1942.

  For any month with no usable near-depth, a new method was needed to break the patterns. Another quite different (and equally laborious and resourceful) method was found. It exploited the twelve-letter indicators, a special feature of what Tunny did at the first few letters of a transmission, and the routine starts to the plain-text. It was used to break the patterns of May, June and July 1942.

  The Testery

  In July 1942 work on Tunny was handed over to a new section headed by Major Tester and named after him. It was formed from people already at Bletchley Park and they were supplemented by people from the Army and the ATS. The section inherited from the research section various methods but no royal road to success. Moreover, the two methods of wheel-breaking just mentioned were both defeated by German improvements. In August 1942 they began starting their transmission with ‘Quatsch’ (meaningless German words), so the method that depended on standard initial cribs was no use. In October 1942, the original experimental Tunny link was closed; in its place they started more and more links (on slightly modified machines) each with its own wheel-patterns. Thereafter, on all links, the clear twelve-letter indicator was replaced by a ‘QEP’ number; it referred to some list of settings available to the operators but not to Bletchley Park. Depths could be recognized from the repetition of the QEP number; but near-depths could not, even if there were any. So the method of wheel-breaking that used the letter-indicators was also denied to the Testery. Depths were still sent and read but there was at first no way of breaking wheel-patterns from the key-streams they provided.

  Turingery

  In the summer of 1942, Alan Turing, already a legendary figure of Enigma cryptanalysis, attacked this problem of breaking patterns from key. He worked entirely on ΔK = Δχ + Δψ', exploiting a weakness of Δψ', namely that the chance that two bits of a character of Δψ' should be the same is b. (The two bits can only differ if, for that Δψ' character, there was a total motor cross so that there Δψ' = Δψ. The probability, therefore, that they differ is a×2b(1-b) = 1-b when a b = ½.)

  The method started by making the assumption that, at some arbitrarily chosen point, there had been a total motor dot, so that there Δψ' = / (the all dot character – a space in the teleprinter code). If that is right, at that place Δχ = ΔK and one Δχ bit is known at each level. These bits are cycled through the depth to give (by subtracting from ΔK) isolated bits of Δψ', ‘correct’ under the initial assumption. Since in a Δψ' character each pair of bits has a probability b of being equal, each such ‘correct’ Δψ' bit spawns putatively equal bits of Δψ' in the other four levels. Each such putative bit gives, by subtraction from ΔK, a putative Δχ bit that has a probability b of being right (under the initial assumption). These putative Δχ bits are then assembled onto a blank Δχ pattern for each of the five levels.

  For instance, with a depth of 1,000 characters the original assumption places about twenty-four ‘correct’ Δχ1, bits, about thirty-two Δχ2 bits, about thirty-four Δχ3 bits and about thirty-eight Δχ4 bits. Each spawns a single putative Δχ5 bit, giving nearly 130 putative bits; so there will be five or six putative bits at each place on the twenty-three-long blank Δχ5 pattern.

  At this stage for all the levels the number of agreements and disagreements (between putative bits at the same place on a Δχ pattern) is counted. If the agreements do no
t exceed the disagreements convincingly the initial assumption is rejected, and another place is chosen to start the process and the whole thing is repeated.

  Eventually the agreements do exceed the disagreements convincingly; fragmentary Δχi patterns can be formed from the places where the putative Δχi bits give a clear preference between dot and cross. These fragmentary patterns are then cycled through and subtracted from ΔK to give bits of Δψ'. At a place where Δψ' has three probable dots, it is assumed that there has been a motor dot and the remaining bits are taken to be dots, yielding two more Δχ bits. In this way the Δχ patterns are massaged against each other until complete correct Δχ patterns establish themselves. The rest is easy.

  With this weapon known as Turingery, the Testery were in a position to break the patterns for each link/month that offered a substantial readable depth. The recovered patterns could be set against any other depth that could be read for twenty or more characters. There remained, however, the important problem of setting the bulk of the transmissions, that were not in depth.

  Setting Transmissions

  In November 1942 Tutte proposed a way of setting known χ1 and χ2 patterns against a long enough stretch of cipher. He suggested comparing Δχ1 + Δχ2 with ΔZ1 + ΔZ2. The idea is that (ΔZ1 + ΔZ2) – (Δχ1 + Δχ2) = (ΔP1 + ΔP2) + (Δψ1' + Δψ2'). For each character the probability that (Δψ1' + Δψ2') is a dot is b (when, as now, ab = 1/2). The value of b tended to be about 0.7. Results from statistics of plain-text had shown that (ΔP1 + ΔP2) is also considerably more likely to be dot than cross. Consequently (Δχ1 + Δχ2) is expected to be equal to (ΔZ1 + ΔZ2) noticeably more often than not.

  Tutte devised a way of testing all the possible pairs of settings for χ1 and χ2 against a transmission of about 4,000 characters, and found a significantly good answer. The other chi-wheels were then set using similar methods and the psi-wheels and motor wheels followed. This was a striking achievement, but too slow to open an avenue to the goal of setting known patterns in useful quantities. It did, however, in March 1943, play an important part in diagnosing a new motor limitation.

  Motor Limitations

  In February 1943, the new Tunny machines had new features. These were ‘limitations’ that influenced the extension of the psi-stream. The basic motor was as before, but the psi-stream was only extended when the basic motor stream was at a dot and also the limitation stream was a cross. On a link known to Bletchley Park as Codfish, when chi-and psi-patterns had been set, the extensions of the psi-stream only partly agreed with any possible μ'37. The Testery analysed the divergences and found that they only came when (the bit of χ2 one place back) was a dot; the psi-stream was extended only when μ'37 was a dot and was a cross.

  In March 1943, the link known as Herring introduced as the limitation stream + , the sum of χ2 one back and P5 two back. When in a system the key depends on previous plain-text, it is said to be ‘autoclave’, self-keying. This has two effects, one serious for us. Two transmissions with the same QEP numbers would have the same starting positions for their wheels, but, having different P5 bits, they would eventually have different extensions to their psi-wheels and so have different keys. Apparent depths would soon cease to be in depth and could no longer be read. The second feature was unfortunate for the Germans. Poor radio reception would often cause the receiver to get a false Z5 bit and so a false P5 bit, which could throw the decipherment out from then on. They had so much trouble with this autoclave feature that it was soon abandoned and only resumed in December 1943.

  This limitation might have taken the Testery a long time to diagnose, but fortunately it was introduced in mid-March after the March patterns had been broken from a normal depth.

  Among the later unbreakable depths was one 6,000 characters long. They applied Tutte’s method by hand and set the known chi-patterns and stripped them. They set the ψ's on both de-chis and compared the total motor patterns for both. Again they noted the discrepancies and found that at all of those also differed. That enabled them to diagnose the limitation stream as + .

  The Newmanry

  Although Tutte’s method of setting known chi-wheels on a long transmission had proved successful, it took too long. In November 1942, Max Newman, an established Cambridge mathematician, was a member of the Tunny team. He pointed out that the 41×31 comparisons of Δχ1 + Δχ2 with ΔZ1 + ΔZ2 could be made by comparing rotating loops of punched paper tape. One would carry Z and the other, of length 41×31, would carry the 31-fold repetition of χ1 on one level and the 41-fold repetition of χ2 on another. These tapes would rotate in step, and (provided the length of the Z tape was prime to 41×31) the start of the Z-stream would eventually come opposite to all possible starts for χ1 and χ2. Suitable photo-electrical machinery could count the number of dots in (ΔZ1 + ΔZ2) – (Δχ1 + Δχ2) between the start and the stop signs on the Z tape. Whenever the count exceeded a given threshold (or ‘set-total’), it could record the count and the number of rotations the Z tape had made. If the design was flexible enough, it could make fast counts also of other combinations and the other chi-patterns could be set in a similar way.

  The scheme was approved and Newman was given the job of implementing it. His first move was to talk to engineers about the machines he needed. The most important was the machine to compare fast-moving loops of tape and to count combinations of bits. It was designed by Dr C. E. Wynn-Williams of the Telecommunications Research Establishment at Malvern and by members of Tommy Flowers’ Post Office Research Department at Dollis Hill. The first was specified in January 1943 and delivered to Bletchley Park in June 1943. Apart from Post Office racks it had two systems of adjustable pulleys, called bedsteads, around which loops of paper tape could be threaded. It looked unlikely and was christened Heath Robinson (plain Robinson to its friends).

  Other machines were needed and provided. One called Tunny mimicked the German machine and could produce such things as the 41×31 long tape of χ1 and χ2, and a great deal else. Another had five heads and could combine in various ways up to five inputs to produce four tape outputs. It was known as Mrs Miles in honour of a lady of that name who had leapt to fame by having quadruplets.

  By April 1943, Newman had in his section sixteen Wrens and Donald Michie. Michie was an unprecedentedly young recruit: he had won a Classics scholarship at Oxford in the days when most of the brightest boys did Classics. He was outstandingly inventive, open-minded and vigorous, one of the heavyweights in the attack on Tunny. The Wrens were held in a typing school until June 1943 when the machines arrived. They were then divided into four watches and set about learning how to use the machines – and very good at it they became. By that time Jack Good and seven engineers had joined the section. Good came from Hut 8, where, as well as doing the standard things very well, he had helped with an influential statistical review of the material. In the Newmanry, among a mass of other contributions, he took the lead in establishing proper statistical tools for evaluating results. He once told me that he wanted to win the war by himself, and, from the way he set about Tunny, you could tell that he meant it. In the course of time other analysts like me were sent from Huts 6 and 8 and the research section; other engineers came from Dollis Hill, and other Wrens joined the original sixteen.

  In the early days, the machines had teething problems and so did the analysts, but eventually the section discovered how to set all the wheels on a long enough transmission. After χ1 and χ2 had been set, the other chi-patterns could be attacked, one by one or in pairs. They were subtracted from Z on Tunny to provide the de-chi, D = ψ' + P. Strong features of ΔP would appear in ΔD much more strongly against dots than against crosses in μ'37 where Δψ' = /. The whole length of μ'37 was run against ΔD, counting some strong feature of ΔP against dots of μ'37. This set the motor wheels. The D stream was then ‘contracted’ by omitting the characters that came against motor dots; that gave a stream of ‘contracted’ P added to the unextended psi-stream. The psi-patterns were set by subtracting them at al
l settings and counting for dots (say) in levels of the contracted P-stream.

  This airy description slides over the surface. Under the surface a lot was going on and a lot was going wrong. We were analysing statistical properties of samples of ΔP, and found great differences between samples. We had to identify robust features and devise efficient strategies for setting the χ’s after setting χ1 and χ2. Our earliest efforts were often inefficient. At the places where a count exceeded its set-total threshold, the count and the number of revolutions the Z tape had made were shown on a screen and the operator wrote them down. The output of a run was a list of these. The screen, however, was quite hard to read and even the operator’s handwriting could be misread. The place on the χ1 χ2 tape that corresponded to the number of revolutions could be miscalculated; the stated length of the Z tape could be wrong. The looped tapes could stretch and they could break. It soon became clear that time spent on checking everything was time saved. Checking became an integral part of all the Newmanry routines.

  Early on successes came slowly, but eventually it became clear that Robinson could indeed set known patterns in useful quantities. But new Tunny links were coming on the air, each with its own wheel-patterns; there were ten in the autumn of 1943 and eventually twenty-six; and many of them carried important strategic intelligence. Most of the long transmissions could be deciphered if only we could get at them; Robinson was overloaded and more machinery was essential.