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.[6][7] Hut 8 performed the procedure continuously for two years, stopping only in 1943 when sufficient bombe time became readily available.[8][9] Banburismus was a development of the "clock method" invented by the Polish cryptanalyst Jerzy Różycki.[10]
Hugh Alexander was regarded as the best of the Banburists. He and I. J. Good considered the process more an intellectual game than a job. It was "not easy enough to be trivial, but not difficult enough to cause a nervous breakdown".[11]
History
In the first few months after arriving at Bletchley Park in September 1939, Alan Turing correctly deduced that the message-settings of Kriegsmarine Enigma signals were enciphered on a common Grundstellung (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.[12] A breakthrough was achieved after the Narvik pinch in which the disguised armed trawlerPolares, which was on its way to Narvik in Norway, was seized by HMSGriffin in the North Sea on 26 April 1940.[13] 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 23 and 24 April and the operators' log, which gave a long stretch of paired plaintext and enciphered message for the 25th and 26th.[14]
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 14 April and 26 June to be broken. However, the Kriegsmarine had changed the bigram tables on 1 July.[15] 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.[15]
Principles
Banburismus utilised a weakness in the indicator procedure (the encrypted message settings) of Kriegsmarine Enigma traffic. Unlike the German Army and Airforce Enigma procedures, the Kriegsmarine used a Grundstellung provided by key lists, and so it was the same for all messages on a particular day (or pair of days). This meant that the three-letter indicators were all enciphered with the same rotor settings so that they were all in depth with each other.[16] Normally, the indicators for two messages were never the same, but it could happen that, part-way through a message, the rotor positions became the same as the starting position of the rotors for another message, the parts of the two messages that overlapped in this way were in depth.
The left hand end of a "Banbury Sheet" from World War II found in 2014 in the roof space of Hut 6 at Bletchley Park.
The principle behind Banburismus is relatively simple (and seems to be rather similar to the Index of Coincidence). If two sentences in English or German are written down one above the other, and a count is made of how often a letter in one message is the same as the corresponding letter in the other message; there will be more matches than would occur if the sentences were random strings of letters. For a random sequence, the repeat rate for single letters is expected to be 1 in 26 (around 3.8%), and for the German Navy messages it was shown to be 1 in 17 (5.9%).[17] If the two messages were in depth, then the matches occur just as they did in the plaintexts. However, if the messages were not in depth, then the two ciphertexts will compare as if they were random, giving a repeat rate of about 1 in 26. This allows an attacker to take two messages whose indicators differ only in the third character, and slide them against each other looking for the giveaway repeat pattern that shows where they align in depth.
The comparison of two messages to look for repeats was made easier by punching the messages onto thin cards about 250 millimetres (9.8in) high by several metres (yards) wide, depending on the length of message.[citation needed] A hole at the top of a column on the card represented an 'A' at that position, a hole at the bottom represented a 'Z'. The two message-cards were laid on top of each other on a light-box and where the light shone through, there was a repeat. This made it much simpler to detect and count the repeats. The cards were printed in Banbury in Oxfordshire. They became known as 'banburies' at Bletchley Park, and hence the procedure using them: Banburismus.[18]
The application of the scritchmus procedure (see below) gives a clue as to the possible right-hand rotor.
Example
Message with indicator "VFG": XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
Message with indicator "VFX": YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
Hut 8 would punch these onto banburies and count the repeats for all valid offsets −25 letters to +25 letters. There are two promising positions:
This offset of seven shows just a single trigram in an overlap of 57 letters.
Turing's method of accumulating a score of a number of decibans allows the calculation of which of these situations is most likely to represent messages in depth. As might be expected, the former is the winner with odds of 5:1 on, the latter is only 2:1 on.[19]
Turing calculated the scores for the number of single repeats in overlaps of so many letters, and the number of bigrams and trigrams. Tetragrams often represented German words in the plaintext[clarification needed] and their scores were calculated according to the type of message (from traffic analysis), and even their position within the message.[20] These were tabulated and the relevant values summed by Banburists in assessing pairs of messages to see which were likely to be in depth.
Bletchley Park used the convention that the indicator plaintext of "VFX", being eight characters ahead of "VFG", or (in terms of just the third, differing, letter) that "X = G+8".
Scritchmus
Scritchmus was the part of the Banburismus procedure that could lead to the identification of the right-hand (fast) wheel. The Banburist might have evidence from various message-pairs (with only the third indicator letter differing) showing that "X = Q−2", "H = X−4" and "B = G+3". He or she[21] would search the deciban sheets for all distances with odds of better than 1:1 (i.e. with scores ≥ +34). An attempt was then made to construct the 'end wheel alphabet' by forming 'chains' of end-wheel letters out of these repeats.[22] They could then construct a "chain" as follows:
G--B-H---X-Q
If this is then compared at progressive offsets with the known letter-sequence of an Enigma rotor, quite a few possibilities are discounted due to violating either the "reciprocal" property or the "no-self-ciphering" property of the Enigma machine:
G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is possible G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (G enciphers to B, yet B enciphers to E) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (H apparently enciphers to H) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (G enciphers to D, yet B enciphers to G) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (B enciphers to H, yet H enciphers to J) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (Q apparently enciphers to Q) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (G apparently enciphers to G) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (G enciphers to H, yet H enciphers to M) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is possible G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is possible G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is possible G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (H enciphers to Q, yet Q enciphers to W) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (X enciphers to V, yet Q enciphers to X) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (B enciphers to Q, yet Q enciphers to Y) G--B-H---X-Q ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (X enciphers to X) Q G--B-H---X-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is possible -Q G--B-H---X-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (Q enciphers to B, yet B enciphers to T) X-Q G--B-H---> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is possible -X-Q G--B-H--> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (X enciphers to B, yet B enciphers to V) --X-Q G--B-H-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is possible ---X-Q G--B-H-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (X enciphers to D, yet B enciphers to X) H---X-Q G--B-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (Q enciphers to G, yet G enciphers to V) -H---X-Q G--B-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (H enciphers to B, yet Q enciphers to H) B-H---X-Q G--> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is possible (note the G enciphers to X, X enciphers to G property) -B-H---X-Q G-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is impossible (B enciphers to B) --B-H---X-Q G-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... is possible
The so-called "end-wheel alphabet" is already limited to just nine possibilities, merely by establishing a letter-chain of five letters derived from a mere four message-pairs. Hut 8 would now try fitting other letter-chains — ones with no letters in common with the first chain — into these nine candidate end-wheel alphabets.
Eventually they will hope to be left with just one candidate, maybe looking like this:
Not only this, but such an end-wheel alphabet forces the conclusion that the end wheel is in fact "Rotor I". This is because "Rotor II" would have caused a mid-wheel turnover as it stepped from "E" to "F", yet that's in the middle of the span of the letter-chain "F----A--D---O". Likewise, all the other possible mid-wheel turnovers are precluded. Rotor I does its turnover between "Q" and "R", and that's the only part of the alphabet not spanned by a chain.
That the different Enigma wheels had different turnover points was, presumably, a measure by the designers of the machine to improve its security. However, this very complication allowed Bletchley Park to deduce the identity of the end wheel.
Middle wheel
Once the end wheel is identified, these same principles can be extended to handle the middle rotor, though with the added complexity that the search is for overlaps in message-pairs sharing just the first indicator letter, and that the overlaps could therefore occur at up to 650 characters apart.[23]
The workload of doing this is beyond manual labour, so BP punched the messages onto 80-column cards and used Hollerith machines to scan for tetragram repeats or better. That told them which banburies to set up on the light boxes (and with what overlap) to evaluate the whole repeat pattern.
Armed with a set of probable mid-wheel overlaps, Hut 8 could compose letter-chains for the middle wheel much in the same way as was illustrated above for the end wheel. That in turn (after Scritchmus) would give at least a partial middle wheel alphabet, and hopefully at least some of the possible choices of rotor for the middle wheel could be eliminated from turnover knowledge (as was done in identifying the end wheel).
Taken together, the probable right hand and middle wheels would give a set of bombe runs for the day, that would be significantly reduced from the 336 possible.
Alan Mathison Turing was an English mathematician, computer scientist, logician, cryptanalyst, philosopher and theoretical biologist. Turing was highly influential in the development of theoretical computer science, providing a formalisation of the concepts of algorithm and computation with the Turing machine, which can be considered a model of a general-purpose computer. He is widely considered to be the father of theoretical computer science and artificial intelligence.
The Enigma machine is a cipher device developed and used in the early- to mid-20th century to protect commercial, diplomatic, and military communication. It was employed extensively by Nazi Germany during World War II, in all branches of the German military. The Enigma machine was considered so secure that it was used to encipher the most top-secret messages.
In cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers.
The Lorenz SZ40, SZ42a and SZ42b were German rotor stream cipher machines used by the German Army during World War II. They were developed by C. Lorenz AG in Berlin. The model name SZ was derived from Schlüssel-Zusatz, meaning cipher attachment. The instruments implemented a Vernam stream cipher.
Irving John Good was a British mathematician who worked as a cryptologist at Bletchley Park with Alan Turing. After the Second World War, Good continued to work with Turing on the design of computers and Bayesian statistics at the University of Manchester. Good moved to the United States where he was professor at Virginia Tech.
The bombe was an electro-mechanical device used by British cryptologists to help decipher German Enigma-machine-encrypted secret messages during World War II. The US Navy and US Army later produced their own machines to the same functional specification, albeit engineered differently both from each other and from Polish and British bombes.
Cryptanalysis of the Enigma ciphering system enabled the western Allies in World War II to read substantial amounts of Morse-coded radio communications of the Axis powers that had been enciphered using Enigma machines. This yielded military intelligence which, along with that from other decrypted Axis radio and teleprinter transmissions, was given the codename Ultra.
Peter Frank George Twinn was a British mathematician, Second World War codebreaker and entomologist. The first professional mathematician to be recruited to GC&CS. Head of ISK from 1943, the unit responsible for decrypting over 100,000 Abwehr communications.
Hut 8 was a section in the Government Code and Cypher School (GC&CS) at Bletchley Park tasked with solving German naval (Kriegsmarine) Enigma messages. The section was led initially by Alan Turing. He was succeeded in November 1942 by his deputy, Hugh Alexander. Patrick Mahon succeeded Alexander in September 1944.
The cyclometer was a cryptologic device designed, "probably in 1934 or 1935," by Marian Rejewski of the Polish Cipher Bureau's German section (BS-4), to catalog the cycle structure of Enigma permutations, thereby facilitating the decryption of German Enigma ciphertext.
In cryptography, the clock was a method devised by Polish mathematician-cryptologist Jerzy Różycki, at the Polish General Staff's Cipher Bureau, to facilitate decrypting German Enigma ciphers. The method determined the rightmost rotor in the German Enigma by exploiting the different turnover positions. For the Poles, learning the rightmost rotor reduced the rotor-order search space by a factor of 3. The British improved the method, and it allowed them to use their limited number of bombes more effectively.
The grill method, in cryptology, was a method used chiefly early on, before the advent of the cyclometer, by the mathematician-cryptologists of the Polish Cipher Bureau in decrypting German Enigma machine ciphers. The Enigma rotor cipher machine changes plaintext characters into cipher text using a different permutation for each character, and so implements a polyalphabetic substitution cipher.
The B-Dienst, also called xB-Dienst, X-B-Dienst and χB-Dienst, was a Department of the German Naval Intelligence Service of the OKM, that dealt with the interception and recording, decoding and analysis of the enemy, in particular British radio communications before and during World War II. B-Dienst worked on cryptanalysis and deciphering (decrypting) of enemy and neutral states' message traffic and security control of Kriegsmarine key processes and machinery.
John William Jamieson Herivel was a British science historian and World War II codebreaker at Bletchley Park.
Marian Adam Rejewski was a Polish mathematician and cryptologist who in late 1932 reconstructed the sight-unseen Nazi German military Enigma cipher machine, aided by limited documents obtained by French military intelligence. Over the next nearly seven years, Rejewski and fellow mathematician-cryptologists Jerzy Różycki and Henryk Zygalski developed and used techniques and equipment to decrypt the German machine ciphers, even as the Germans introduced modifications to their equipment and encryption procedures.
Turingery or Turing's method was a manual codebreaking method devised in July 1942 by the mathematician and cryptanalyst Alan Turing at the British Government Code and Cypher School at Bletchley Park during World War II. It was for use in cryptanalysis of the Lorenz cipher produced by the SZ40 and SZ42 teleprinter rotor stream cipher machines, one of the Germans' Geheimschreiber machines. The British codenamed non-Morse traffic "Fish", and that from this machine "Tunny".
Cryptanalysis of the Lorenz cipher was the process that enabled the British to read high-level German army messages during World War II. The British Government Code and Cypher School (GC&CS) at Bletchley Park decrypted many communications between the Oberkommando der Wehrmacht in Berlin and their army commands throughout occupied Europe, some of which were signed "Adolf Hitler, Führer". These were intercepted non-Morse radio transmissions that had been enciphered by the Lorenz SZ teleprinter rotor stream cipher attachments. Decrypts of this traffic became an important source of "Ultra" intelligence, which contributed significantly to Allied victory.
The Short Weather Cipher, also known as the weather short signal book, was a cipher, presented as a codebook, that was used by the radio telegraphists aboard U-boats of the German Navy (Kriegsmarine) during World War II. It was used to condense weather reports into a short 7-letter message, which was enciphered by using the naval Enigma and transmitted by radiomen to intercept stations on shore, where it was deciphered by Enigma and the 7-letter weather report was reconstructed.
The Discriminant Book shortened to K-Book (K. Buch), and also known as the indicator group book or identification group book was a secret distribution list in booklet form, which listed trigraphs in random order. The Kenngruppenbuch was introduced in May 1937, and used by the Kriegsmarine during World War II as part of the Naval Enigma message encipherment procedure, to ensure secret and confidential communication between Karl Dönitz, Commander of Submarines (BdU) in the Atlantic and in the Mediterranean operating German submarines. The Kenngruppenbuch was used in the generation of the Enigma message Key that was transmitted within the message Indicator. The Kenngruppenbuch was used from 5 October 1941, for the Enigma Model M3, and from 1 February 1942 exclusively for the Enigma M4. It must not be confused with the Kenngruppenheft which was used with the Short Signal Book.
The Schlüsselgerät 39 (SG-39) was an electrically operated rotor cipher machine, invented by the German Fritz Menzer during World War II. The device was the evolution of the Enigma rotors coupled with three Hagelin pin wheels to provide variable stepping of the rotors. All three wheels stepped once with each encipherment. Rotors stepped according to normal Enigma rules, except that an active pin at the reading station for a pin wheel prevented the coupled rotor from stepping. The cycle for a normal Enigma was 17,576 characters. When the Schlüsselgerät 39 was correctly configured, its cycle length was characters, which was more than 15,000 times longer than a standard Enigma. The Schlüsselgerät 39 was fully automatic, in that when a key was pressed, the plain and cipher letters were printed on separate paper tapes, divided into five-digit groups. The Schlüsselgerät 39 was abandoned by German forces in favour of the Schlüsselgerät 41.
↑ Although this method is frequently stated to be an example of Bayesian inference, Donald Gilles has argued (Gilles, Donald (1990), "The Turing-Good Weight of Evidence Function and Popper's Measure of the Severity of a Test", Br. J. Phil. Sci., vol.41, pp.143–146), that the process is not really Bayesian, but rather Popperian.
↑ Copeland, Jack (2004), "Enigma", in Copeland, B. Jack (ed.), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Oxford: Oxford University Press, p.261, ISBN0-19-825080-0
↑ Murray, Joan (1992), "Hut 8 and naval Enigma, Part I", in Hinsley, F.H.; Stripp, Alan (eds.), Codebreakers: The inside story of Bletchley Park, Oxford: Oxford University Press (published 1993), p.118, ISBN978-0-19-280132-6
↑ Sale, Tony. "Banburismus". The 1944 Bletchley Park Cryptographic Dictionary. The National Archives and Records Administration (NARA) 8601 Adelphi Road, College Park, Maryland. Retrieved 15 November 2009.
Good, Jack (1993), "Enigma and Fish", in Hinsley, F.H.; Stripp, Alan (eds.), Codebreakers: The inside story of Bletchley Park, Oxford: Oxford University Press, ISBN978-0-19-280132-6
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
