Score:5

What were Alan Turing and their team searching before doing KPA in the movie "The imitation game"?

id flag

I just watched the movie "The imitation game" (2014) which is based on Alan Turing's biography.

At some point in the movie the machine built by Turing wasn't fast enough to decrypt the Germans' messages, so they had the idea to search for the Enigma setting that deciphers a secret message into a plaintext that contains a known phrase (it was "Heil Hitler" in the movie but I have read that Turing actually searched for the word "eins" in the plaintext). As far as I can understand this is a form of KPA (Known Plaintext Attack).

In the movie Turing says something like "What if we don't have to search through all the possible combinations? What if we only search through the ones that produce a word we know will be in the message?".

I don't understand what it does mean for a machine to "search through all the possible combinations". i.e. I don't understand what was the machine doing before Turing and their teams "upgraded" it to search for "Heil Hitler" in the decrypted plaintext. Suppose they had enough time to let the machine run until it searched through all the possible combinations: how could it know which one was correct? I know that in principle a human could read all the possible generated plaintexts, but that would be unfeasible in practice because it requires a lot of time, so I suppose that's not what was happening. What else, then?

DannyNiu avatar
vu flag
The reality was that they were using KPA (then known as cribs) to attack Enigma from the very start, the movie made the impression that it was the other way around. It's explained in the Wikipedia page for the movie if I remember correctly.
melfnt avatar
id flag
@DannyNiu thank you, I see it now
Score:5
ru flag

It's wrong to treat a Hollywood historical movie as a documentary. It's also wrong to think of Enigma as a single problem with a single solution. There were many variants of the Enigma machine which added many complexities. As well as the machines evolving and becoming more complex, their usage in communications evolved. The Enigma story is therefore a story of a cat-and-mouse chase with the system becoming increasingly complex, old attack methods failing (sometimes abruptly), and new ideas being required. The cryptanalytic story has many heroes. Below are some of the different ideas and events that contributed over time in roughly chronological order. I don't claim that the list is exhaustive.

  • In 1925 GC&CS acquires some early versions of the Enigma machine (without plugboards). They are passed to Hugh Foss who proposes an attack based on "cribs" (KPA). His ideas were used in practice to break a Japanese signal in 1934.
  • In the 1930s Dilly Knox built on Foss's methods and derived a more algebraic attack using manual tools, known as rodding. These methods were used to break traffic in the Spanish Civil War.
  • In 1931 Rodolphe Lemoine and Gustave Bertrand acquire the technical specifications for the German military Enigma (with plugboard). After finding little interest from the French and British intelligence services, the documents are passed to the Polish Biuro Szyfrów.
  • Over the next few years, the Polish mathematicians (Marian Rejewski, Jerzy Różycki, Henryk Zygalski) make astonishing breakthroughs in reconstructing the machine but also in diagnosing the use of a repeated three letter message indicator at the start of each message. Observe that this is not a known plaintext, but it is knowledge of a repeated section of plaintext. The repetition combined with permutation theory allows them to develop an attack to recover the rotor settings independently of the plugboard. They develop manual and electromechanical tools to implement the attack. Their methods struggled to scale when the German increased the number of possible rotors from three to five in 1938.
  • In January 1939 GC&CS share their methods with the French and Poles in Paris. This helped to pave the way to an exchange in Warsaw in July where the Poles shared their work. Their work was seized upon by GC&CS.
  • On 1st May 1940 the German's suddenly stopped sending repeated message indicators. This caused decryption using the Polish methods to fail. Bletchley Park is able to compensate by a variety of ideas such as John Herivel's tip, cillis (highly predictable indicator settings named after the girlfriend of a particular operator who would regularly use her name as an indicator), and the "Nigelian method" (the observation that the same rotor would not be used in the same position on two consecutive days). Note that these methods relied insecure usage rather than cribs, though cribbing was still central part of the subsequent analysis. Importantly, the change occurs at the same time as a military escalation and hence also increase in traffic. These stop-gap methods therefore provide not only intelligence, but also a large and vital corpus of messages which help to produce more and better cribs.
  • Bletchley Park adapt the design of the Polish Bomba to the British Bombe which uses cribs (expressed as "menus")rather than indicators. A number of improvements are made. Perhaps Alan Turing's greatest contribution is to implement a feedback mechanism to rapidly eliminate impossible settings (an incorrect guess for a rotor setting and input wire produced one or more other incorrect guesses for wires which could be fed back until all 26 guesses are eliminated or only one survives). Overall this sped up the Bombe attack by a factor of 26. Gordon Welchman's diagonal board (attributed to Hugh Alexander in "The Imitation Game") achieved a similar speed-up, but importantly also greatly reduced the amount of successful crib (or menu) needed for a successful run.
  • Hundreds of Bombe machine were produced and the methods were even able to scale to cope with the introduction of the even more complex naval Enigma. The attacks were augmented with additional ideas such as Turing's Banburismus which did not use known plaintext, but relied on coincidences between plaintext letters and hence coincidences in cipher texts when two messages were arranged on cut.
melfnt avatar
id flag
So is the short answer "Nothing, they were always doing some sort of KPA?"
Daniel S avatar
ru flag
I would not count the Polish indicator method nor Banburismus (nor any of the stop-gap helper methods) as KPA. However, the majority of Enigma attacks did fall back on KPA.
Score:0
kz flag

The could keep using a "crib" because the Germans assumed the enigma was unbreakable. It is said they didn't know it was broken when the war ended. Also, the Germans also had a standard format and headers, "weather report" was at the beginning. The "Heil Hitler" as mentioned. I also believed I read that there were a few more cribs they used.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.