Метод Банбуризма: Взлом шифров "Энигмы" Аланом Тьюрингом

Cryptanalytic process developed by Alan Turing during World War II

Banburismus was a cryptanalytic process developed by Alan Turing at Bletchley Park in Britain during the Second World War. It was used by Bletchley Park's Hut 8 to help break German Kriegsmarine (naval) messages enciphered on Enigma machines. 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óżycki. 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".

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. 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 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 23 and 24 April 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 14 April and 26 June 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. 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 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%). 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 high by several metres (yards) wide, depending on the length of message. 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. The application of the scritchmus procedure (see below) gives a clue as to the possible right hand rotor.

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. 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.