That particular phrase isn't mentioned as one that the team at Bletchly Park used in order to decode Enigma but others were. These phrases, which are called cribs (in the sense of "crib notes" or "cheats"), weren't a way to fix the Bombe code breaking computers. Instead they were used to more quickly figure out the settings that were used for each message. The idea is that if you know what part of the message says then you can search through the message until things line up properly. The larger a piece the better for both probabilistic reasons and because of some specific details about how the Enigma worked.

One of these cribs that we know of was "WETTERVORHERSAGEBISKAYA" which means "weather forecast for biskaya". Because weather reports generally mention that they are a weather reports and they will mention their own location it was a very good way to get long cribs for the systems. The phrase "Heil Hitler" is a bit short for a useful crib, the filmmakers chose it because its punchier. It tells a better story to have an iconic Nazi phrase used to break the system than weather reports.

The Germans were aware that Engima could be attacked like this, the technique is an old one, and tried to take steps to prevent it. The navy distributed code books (Kurzsignale) that both made messages shorter and removed cribs that attackers could guess. In fact the German navy was extremely paranoid about the security of their encryption system because submarines had no other way to coordinate or make reports. So they also had a special changes made to their version of Engima just in case the version used for the army and air force was broken. (And indeed the army Engima was broken early on and most of Turing's work was specifically on how to break the naval Enigma.)

So, first things first “Imitation Game” is not an accurate portrayal of the efforts to break Enigma, largely because it ignores the efforts made by other nations (particularly Poland) and other counter-intelligence operations conducted by Great Britain, including the capture of U-110 in May 1941 (which inspired another WW2 movie called U-571 which I also have problems with). There was far more that went on in the codebreaking efforts than just Bletchley Park.

With that out of the way, lets start with a background:

BACKGROUND

Following the end of the First World War, a German engineer by the name of Arthur Scherbius patented an electromechanical cipher machine called Enigma. The original machine worked on the principle of several rotating rotors, each with 26 distinct electrical pathways that corresponded to swapping letters of the Latin alphabet. With each key pressed, the rotors would rotate and a new pathway (or machine state) would be used to encipher characters. The use of multiple rotors increased the number of possible machine states astronomically and made the device difficult to break using brute force attacks. Without knowing the original state of an enigma machine, an attacker would spend a significant portion of time checking every combination.

Despite the Enigma’s advantages, it was not adopted by the German Navy until 1925 and the Army followed in 1928. However, the rotors alone were not deemed to be secure enough and a plugboard was added to the device in 1930. The plugboard added more possible machine states as letter substitutions could be overwritten to a new letter. This vastly improved the security of Enigma and the device was believed to be uncrackable. These features, of course, didn’t stop others from trying to break the code.

EARLY EFFORTS TO BREAK ENIGMA

One of the early efforts to break Enigma was that of Poland’s Cipher Bureau. Within a few months of Enigma’s adoption in Germany, Polish cryptanalysts acquired commercial variants of enigma and recruited mathematicians to analyze and break the code. Though this enabled the codebreakers to understand how the Enigma functioned, the military version of the machine had different rotors with unique pathways. Thus, they couldn’t decode. A breakthrough was made thanks to French Intelligence which managed to acquire technical documents and manuals from a financially desperate member within the German army.

With these documents, the Polish codebreakers developed methods for finding daily keys (i.e. start settings for the rotors) and building their own copy of the military Enigma. However, in the lead-up to the war in September 1939, the Germans introduced new rotors and encoding procedures which nullified many of the Polish methods at the time. Polish cryptanalysts had to adapt or redo their methodology to break new codes. As they weren’t able to quickly break these German messages, and with the threat of war looming, the Polish Cipher Bureau began to share their work with both the British and the French.

After the fall of Poland, the Polish Cipher Bureau escaped to France where they continued their efforts. By this time, Alan Turing joined the project and attended various crypt analytic conferences with the Polish codebreakers. Years prior, Turing had theorized that any human computer could be replaced by a mechanical substitute. It is this theory that supported his Bombe machine.

Working with Gordon Welchman in Bletchley Park, Turing’s Bombe was designed to identify the settings used in Enigma-encoded messages. It was essentially a bank of several enigma devices which tested multiple machine states at the same time. Once a setting was found, it could be tested on an enigma and the code could be decoded. The original Bombe could break an encoded message in about 20 minutes, though later models built by the United States could reduce it to under 5.

BREAKING ENIGMA: 101

To understand how Turing and Welchman were able to use their Bombe to break the enigma, you must first understand how enigma functioned. The M3 Enigma, as used by the German Army and Air Force, consisted of 3 rotors, a reflector, and a plugboard. The choice of rotors, reflector, and plugs were detailed in codebooks which changed frequently. Thus, if codebooks did fall into enemy hands, they were only valid for a short time. Enigma operators were given 3 reflectors, 5 rotors (of which there were 8 unique designs in total), and 10 plugs. Each rotor could be set to any of 26 initial settings and they could be placed in any order.

With all of these possible settings, the Enigma had approximately 158,962,555,217,826,000,000 unique machine states. To understand how large that number really is, if you could check 1,000,000 possible states each second, it would still take over 5 million years to traverse all possible states. It is largely for this reason that people felt the Enigma couldn’t be broken. The Kriegsmarine, or German Navy, took it step further and added a 4th rotor to the system. This was done by making reflectors thinner and the 4th rotor did not rotate like the other 3. Though this certainly made the device more secure, it had flaws which could be exploited.

In Enigma, any letter once encoded will never encode as itself. Even if you were to repeat the same input indefinitely, it will give you a seemingly randomized string of letters that will never include the original input. This was the flaw that was exploited. In the movie, “Heil Hitler” was the phrase they used as a “crib” or guessed message to be found within an encrypted message. In reality, it was “wettervorhersage” or weather report. By comparing an encrypted string to a guessed string, it was possible to reduce the number of possible states significantly. If you assume a plugboard swap and record your outputs, you can work your way through the system until either you run into a contradiction or you run through the message. Contradictions occurred when you find that letters are paired with more than one other letter. This is, of course, not possible with the Enigma and thus you can move on to the next set of settings more easily.

The Bombe machine did this all electromechanically. When it stopped, it stopped at a series of settings where no contradictions were found. For shorter messages, this may not have been the correct settings. False stops were possible where a crib could be found in the encrypted message for a specific setting. If the message was checked and found to be garbled, then the machine was run again from the next setting or the crib was moved to another possible location.