Highlights of Alan Turing and Colleagues' Cryptanalysis Work at Bletchley Park

On September 1, 1939 Germany invaded Poland, beginning World War II. Two days later, on September 3, Britain and France declared war on Germany. The following day Alan Turing appeared for work at the Code Code and Cypher School at Bletchley, England, with the goal of deciphering military communications encoded by means of Enigma machines.

As early as December 1932 the Biuro Szyfrów ("Cipher Bureau") in Warsaw, the Polish interwaragency charged with both cryptography  and cryptanalysis, had broken the German Enigma machine cipher.Over the next nearly seven years before World War II, the Polish "Cipher Bureau" overcame the growing structural and operating complexities of the plugboard-equipped Enigma, the main German cipher device during the Second World War.

Prior to the beginning of World War II, in October 1938 Polish Cipher Bureau mathematician and cryptologist Marian Rejewski designed the bomba, or bomba kryptologiczna  ("bomb" or "cryptologic bomb,") a special-purpose machine for breaking German Enigma machine  ciphers. On July 25, 1939 the Biuro Szyfrów revealed Poland's Enigma-decryption techniques and equipment, which it had achieved using the bomba device, to the French and British. Poland thereby made possible the western Allies' vitally important decryption of Nazi German   secret communications (Ultra) during World War II.

"Up to July 25, 1939, the Poles had been breaking Enigma messages for over six and a half years without telling their  French  and British allies. On December 15, 1938, two new rotors, IV and V, were introduced (three of the now five rotors being selected for use in the machine at a time). As Rejewski wrote in a 1979 critique of appendix 1, volume 1 (1979), of the official history of British Intelligence in the Second World War, 'we quickly found the [wirings] within the [new rotors], but [their] introduction [...] raised the number of possible sequences of drums from 6 to 60 [...] and hence also raised tenfold the work of finding the keys. Thus the change was not qualitative but quantitative. We would have had to markedly increase the personnel to operate the bombs, to produce the perforated sheets (60 series of 26 sheets each were now needed, whereas up to the meeting on July 25, 1939, we had only two such series ready) and to manipulate the sheets.'

"Harry Hinsley suggested in British Intelligence . . . that the Poles decided to share their Enigma-breaking techniques and equipment with the French and British in July 1939 because they had encountered insuperable technical difficulties. Rejewski refuted this: 'No, it was not [cryptologic] difficulties [. . .] that prompted us to work with the British and French, but only the deteriorating political situation. If we had had no difficulties at all we would still, or even the more so, have shared our achievements with our allies as our contribution to the struggle against Germany' ' (Wikipedia article on Bomba (cryptography), accessed 12-21-2008).

In the first few months after arriving at Bletchley Turing made a key deduction that led to his development of Banburismus, a cryptanalytic process used by Turing and his co-workers at Bletchley's Hut 8 to help break German Kriegsmarine (Naval) messages enciphered by Enigma.

"The process used sequential conditional probability to infer information about the likely settings of the Enigma machine. It gave rise to Turing's invention of the ban as a measure of the weight of evidence in favour of a hypothesis. This concept was later applied in Turingery and all the other methods used for breaking the Lorenz cipher.

"The aim of Banburismus was to reduce the time required of the electromechanical Bombe machines by identifying the most likely right-hand and middle wheels of the Enigma. Hut 8 performed the procedure continuously for two years, stopping only in 1943 when sufficient bombe time became readily available. Banburismus was a development of the "clock method" invented by the Polish cryptanalyst Jerzy Różyck

To develop Banburismus Turing

"deduced that the message-settings of Kriegsmarine Enigma signals were enciphered on a common G rundstellung (starting position of the rotors), and were then super-enciphered with a bigram and a trigram lookup table. These trigram tables were in a book called the Kenngruppenbuch (K book). However, without the bigram tables, Hut 8 were unable to start attacking the traffic. A breakthrough was achieved after the Narvik pinch in which the disguised armed trawler Polares, which was on its way to Narvik in Norway, was seized by HMS Griffin in the North Sea on 26 April 1940. The Germans did not have time to destroy all their cryptographic documents, and the captured material revealed the precise form of the indicating system, supplied the plugboard connections and Grundstellung for April 23 and 24 and the operators' log, which gave a long stretch of paired plaintext and enciphered message for the 25th and 26th.

"The bigram tables themselves were not part of the capture, but Hut 8 were able to use the settings-lists to read retrospectively, all the Kriegsmarine traffic that had been intercepted from 22 to 27 April. This allowed them do a partial reconstruction of the bigram tables and start the first attempt to use Banburismus to attack Kriegsmarine traffic, from 30 April onwards. Eligible days were those where at least 200 messages were received and for which the partial bigram-tables deciphered the indicators. The first day to be broken was 8 May 1940, thereafter celebrated as "Foss's Day" in honour of Hugh Foss, the cryptanalyst who achieved the feat.

"This task took until November that year, by which time the intelligence was very out of date, but it did show that Banburismus could work. It also allowed much more of the bigram tables to be reconstructed, which in turn allowed April 14 and June 26 to be broken. However, the Kriegsmarine had changed the bigram tables on 1 July. By the end of 1940, much of the theory of the Banburismus scoring system had been worked out.

"The First Lofoten pinch from the trawler Krebs on 3 March 1941 provided the complete keys for February - but no bigram tables or K book. The consequent decrypts allowed the statistical scoring system to be refined so that Banburismus could become the standard procedure against Kriegsmarine Enigma until mid-1943" (This and the earlier quotation are from the Wikipedia article on Banburismus, accessed 01-04-2015.)

About December 1940 Alan Turing and Gordon Welchman at Bletchley Park designed an improved Bombe cryptanalysis machine for deciphering Enigma messages.

Between 1940 and 1941 Max Newman and his team at Bletchley, including Turing, created the top-secret Heath Robinson cryptographic computer named after the cartoonist-designer of fantastic machines. This special-purpose relay computer successfully decoded messages encrypted by Enigma, the Nazis' first-generation enciphering machine.

In July 1942 Turing developed  the hand codebreaking method known as Turingery or Turing's Method (playfully dubbed Turingismus by Peter Ericsson, Peter Hilton and Donald Michie)  for use in cryptanalysis of the Lorenz cipher produced by the SZ40 and SZ42 teleprinter rotor stream cipher machines, one of the Germans' Geheimschreiber (secret writer) machines. The British codenamed non-Morse traffic "Fish", and that from this machine "Tunny".

"Reading a Tunny message required firstly that the logical structure of the system was known, secondly that the periodically changed pattern of active cams on the wheels was derived, and thirdly that the starting positions of the scrambler wheels for this message—the message key—was established.The logical structure of Tunny had been worked out by William Tutte and colleagues over several months ending in January 1942. Deriving the message key was called "setting" at Bletchley Park, but it was the derivation of the cam patterns—which was known as "wheel breaking"—that was the target of Turingery.

"German operator errors in transmitting more than one message with the same key, producing a "depth", allowed the derivation of that key. Turingery was applied to such a key stream to derive the cam settings" (Wikipedia article on Turingery, accessed 01-04-2015).

In 1943 Alan Turing traveled to New York to consult with Claude Shannon and Harry Nyquist at Bell Labs concerning the encryption of “speech signals” between Roosevelt and Churchill.

In January 1944 the top-secret Colossus programmable cryptanalysis machine designed by Tommy Flowers and his team at the Post Office Research Station, Dollis Hill, in North West London, was installed at Bletchley Park to crack the higher level encryption of the Nazi Lorenz SZ40 machine. Colossus employed vacuum tubes and was between one hundred and one thousand times faster than Heath Robinson. "It exceeded all expectations and was able to derive many of the Lorenz settings for each message within a few hours, compared to weeks previously" (http://googleblog.blogspot.com/2012/03/remembering-colossus-worlds-first.html, accessed 03-0-2012). The Colossus machines have been called the first operational programmable electronic digital computers.

On June 1, 1944 the first improved Colossus Mark 2 with 2400 vacuum tubes was operational at Bletchley Park just in time for the Normandy Landings. By the end of the war there were ten Colossus computers operating. They enabled the decryption of 63,000,000 characters of high-grade German messages. Even though these machines incorporated features of special purpose electronic digital computers, and had incalculable influence on the outcome of WWII, they had little influence in the conventional sense on the development of computing technology because they remained top secret until about 1970.

"The Colossus computers were used to help decipher teleprinter  messages which had been encrypted using the Lorenz SZ40/42 machine — British codebreakers referred to encrypted German teleprinter traffic as "Fish" and called the SZ40/42 machine and its traffic as 'Tunny'. Colossus compared two data streams, counting each match based on a programmable Boolean function. The encrypted message was read at high speed from a paper tape. The other stream was generated internally, and was an electronic simulation of the Lorenz machine at various trial settings. If the match count for a setting was above a certain threshold, it would be sent as output to an electric typewriter" (Wikipedia article on Colossus computer, accessed 11-23-2008).

In March 2012 the Colossus Rebuild Project at the National Museum of Computing at Bletchley Park had completed an operating reconstruction of a Colossus II, after 10 years and over 6,000 man-days of volunteer effort. The Rebuild stands in its historically correct place, the room in H Block, in Bletchley Park, where Colossus No. 9 stood in WW II.