Recent Cryptologic Bytes
The Hacker Who Saved Thirty Million Lives
Posted on 07/08/2014
The Hacker Who Saved Thirty Million Lives
by Wojciech Oleksiak
3 July 2014
View the article & more photos online at Culture.Pl HERE.
Photo included here is: Marian Rejewski, photo: Irena Jarosinska / Forum
Modern hackers may be considered criminals, but we owe many lives to their cryptologist predecessors. A Polish mathematician played an instrumental role in ending WWII when he finally hacked the secret Nazi cipher called Enigma.
On the 11th of November 1918 Poland regained independence after being occupied for 123 years by Prussia, Austria and Russia. The long awaited freedom wasn’t long-lasting. Shortly after, it turned out that Poland’s neighbours are going through the most violent times in their history and that establishing any kind of peaceful relationships with them is impossible.
On the other side of the western border there was Weimar Republic, whose turbulent youth resulted in its becoming Das Ditte Reich –Nazi Germany. On the eastern side there was the Russian Soviet Federative Socialist Republic (poised to become the Soviet Union), who had a straightforward mission of forcefully spreading the communist revolution across Europe. Newly-reborn Poland was in danger from the very first days of its existence, and in addition to the challenging task of rebuilding and reuniting the country, it needed to ensure its security.
Keeping those facts in mind, the brand new Polish intelligence services decided to immediately create an agency specialising in cryptography (the use of ciphers and codes) and cryptology (the study of ciphers and codes, particularly for the purpose of "breaking" them) in order to be able to figure out the secret plans of its two threatening neighbours. The Agency was called the Cyphers’ Section, and it was a precursor of the famous Cypher Bureau which was the main responsible for breaking the Enigma code.
Choosing the best of the best
The German Army introduced machine ciphers in early 1928 and Polish Intelligence started working on them immediately. During next four years, the soon-to-be-famous cypher section, which deciphered more than 100 ciphers during The Polish–Soviet War (February 1919 – March 1921), was experiencing nothing but failures and setbacks. In 1932 it became obvious that the resources of Cypher section were not sufficient to tackle German machine codes. The General Staff decided to organise a rudimentary training in code breaking for hundreds of students and research associates, the secret aim of which was to retrieve cryptology talents.
The most promising person found was Marian Rejewski – a well-trained mathematician who studied at University in Poznań but also had a one-year scholarship in Gottingen in his resume (he spoke impeccable German). The two others selected were Henryk Zygalski and Jerzy Różycki - also graduates of the Mathematical Institute at University in Poznań. Immediately they started working for the Cypher Bureau and were chosen to devote themselves exclusively to breaking the Enigma code.
For more about the rising fear and tension of the interwar years in Poland, read our article: The Most Unusual Jewish Publication of Interwar Poland
What is Enigma?
The Enigma is an electro-mechanical cipher rotor machine which was brought onto the market in the early 1920s. It was widely available (yet expensive) and was primarily destined for ciphering and deciphering information in commercial and everyday use. In the late 1920s, the German army first acquired Enigma, and it instantly became the primary ciphering machine of the German army, most notably for the naval and air forces. Why did the German army choose Enigma? Probably because instead of being based on linguistic cipher (popular during World War I), it used polyalphabetic cipher enhanced by the opportunity to implement mathematical permutations. The exact functioning of Enigma requires detailed explanations, but here is a general outline of a few of its features:
Rotors are discs made from hard rubber with brass spring-loaded pins on one face arranged in a circle; on the other side are a corresponding number of circular electrical contacts. The pins and contacts represent the alphabet—typically the 26 letters A–Z. What a single rotor did was simple – a single substitution cipher. For example a pin with letter O may have been wired to the letter Z. Advanced Enigma machines, however, used three to four rotors at a time and each of them could have been set in any of the possible 26 initial positions. To muddle things even more, rotors were ‘stepping’ which means that each of them was changing each positions every time a key on the keyboard was hit. The rotors altogether made a single letter transmute many times before it was ready to send as a ciphered message.
The key to break information ciphered with Enigma was changed daily. First it was determined by the choice of rotors and their initial position. The other device used for this purpose was a plugboard called a Steckerbrett. It allowed any user to easily reconfigure and enhance the cryptographic strength of the cypher by rewiring the connection between keys on the keyboard even before they even entered the rotor unit. Because there was no mathematical explanation for how the letters are substituted one for another (it was simply the fantasy of the user, who could randomly change the position of the wires), an Enigma with a plugboard was much more difficult to solve than a regular one.
Thus, an operator using the military version of Enigma had to know following elements to decipher any message:
1. Wheel order – the choice of rotors (there were five types of them) and the order in which they were fitted.
2. Initial position of the rotors – chosen by the operator, different for each message/day/period. This was determined by what was known as ‘cribs’. Before the encrypted message was delivered, a key message, composed of letters visible in the initial position of rotor wheels, was sent.
3. Plug connections – the connections of the plugs in the plugboard / Steckerbrett.
Due to the complexity of its features, Enigma was unanimously recognized as unbreakable, therefore the intelligence agencies of France and Great Britain believed that the only way to decipher the Nazis’ messages was by stealing one of their machines and having a double agent supply them every day with daily settings. This plan was short-lived. Any disappearing of a single Enigma machine would be noticed, and the machine would be transformed again. And as for double agents spying on Nazis, they were also short-lived...
Murlyn Hakon MBE explains how the Enigma machine worked
The French and British intelligence services didn’t have a single success until late 1931. That year, a German aristocrat, Hans Thilo-Schmidt, who worked as a sidekick for a Lieutenant Colonel in the German signal corps, was assigned the task of destroying out-dated code charts of Enigma, including the procedures for setting up of Enigma on various days. For some reason, possibly financial, he decided to sell the charts to Gustave Bertrand, a French intelligence service agent. Bertrand immediately formed a special team destined to analysing the data, but the information was diagnosed useless because out-dated and still insufficient to even show where to start.
Bertrand then decided to pass on these documents to Poles and Brits. Rejewski, who already owned a ‘civil’ copy of Enigma (bought in Germany) instantly understood that success was at hand. He used the material acquired from Bertrand, and by comparing plaintext to the encoded messages he was able to discover the equations that allowed to find the wiring of the rotors in the Enigma version used by the German army. It required implementation of the most sophisticated permutations theory.
Once the equations were solved and the wiring of each of the five types of rotors determined, Rejewski ordered his engineers to rewire a replica of the German Enigma, set the initial position of the rotors in a way corresponding to the encoded text, entered the coded message and… out came gibberish. Only a chaotic set of letters looking just like any other encoded message.
Close to giving up, Rejewski checked his equations once again. He was certain that the functioning of the rotors and the plugboard had been properly solved. Whatever was missing in his calculations had to be deceptively simple. It could only be the wiring of the keys of the machine to the respective lights above the keys.
In commercial Enigma machines (like the one Rejewski used) the keys were arranged according to German typewriters, according to the scheme A->Q B->W C->E and so on, so that every letter of the alphabet was substituted with the corresponding letter from a QWERTZ keyboard. Even though this wiring could have been set in a hundreds thousands of other ways Rejewski was determined to try out every combination.
He thus settled down to his task, starting out with the standard alphabetical order. A->A, B->B, C->C and… out came plain text! Rejewski had broken the code. Polish intelligence was now in possession of a fully functioning replica of the German army’s Enigma! Why was the arrangement so simple? No one ever found out. There was much left to do still since the settings were changed daily, but at least the code had been cracked.
The Enigma settings (meaning the rotors’ initial position and plugboard configuration) were changed regularly - usually every day. It was the Nazis’ way to ensure that Enigma messages would remain incredibly demanding to decipher even if the code got broken. In order to communicate the encoded message to the recipient, the sender had to send a key message composed of encrypted letters visible in the initial position of rotor wheels. The key message had to be sent twice in order to avoid mistakes.
Rejewski soon noticed the weak point of the German procedure. Firstly, the key messages were identical for the entire communication network throughout a given day, moreover the users were slacking and very often chose obvious positions such as AAA, ZZZ, or QAY. Data collected from a vast number of encrypted messages enabled to minimize the number of indicator settings from 10,000 trilion to 105,456, and to start of cataloguing them. Rejewski invented a machine called cyclometer that did it mechanically. He said of it:
The process of cataloguing with a cyclometer was laborious and took over a year, but when it was ready, obtaining daily keys was a question of [some fifteen] minutes.
The catalogue was ready in 1936 and worked perfectly until 1937. Almost 100% of German messages were successfully decoded. In late 1937, the Germans realised that their Enigma ciphering was not working properly and changed the method of encoding, which resulted in Rejewski’s method becoming useless. Yet the Polish Cipher Bureau was nowhere close to giving up.
The Zygalski Sheets
When Rejewski faced this major setback, another of the students recruited in 1928 came up with a life- saving solution. Henryk Zygalski invented what was later called the Zygalski Sheets, which exploited the repetitiveness of the signs in a key message. By designing specifically perforated sheets of paper, he was able to track down the indicator setting and the daily key. Rejewski was full of admiration for this method even though it was not automatic, and pushed the operators to grind their fingers raw trying to find the accurate combination:
When the sheets were superposed and moved in the proper sequence and the proper manner with respect to each other, in accordance with a strictly defined program, the number of visible apertures gradually decreased. And, if a sufficient quantity of data was available, there finally remained a single aperture, probably corresponding to the right case, that is, to the solution. From the position of the aperture one could calculate the order of the rotors, the setting of their rings, and (…) the entire cipher key.
The settings had to be tried one by one an Enigma replica and, if the cryptologists were unlucky, it could take a lot of time. With war approaching, the Cipher Bureau knew that they needed something much quicker and more efficient.
The Cryptologic Bombs
Rejewski again proved himself to be the ultimate engineering genius by designing a machine called cryptologic bomb. It was an electro-mechanical device whose functioning was rooted in Zygalski’s idea – the tracing of repeating letters in the key messages. The name ‘bombs’ probably comes from the ticking sound it made while working, which reminded its constructor of a ticking bomb.
The bomb method, invented in the autumn of 1938, consisted largely in the automation and acceleration of the process of reconstructing daily keys. Each cryptologic bomb (six were built in Warsaw for the Cipher Bureau before September 1939) essentially constituted an electrically powered aggregate of six Enigmas. It took the place of about one hundred workers and shortened the time for obtaining a key to about two hours – wrote Rejewski.
Bombs were very efficient on both ends: quick and precise. Yet, there was no time to celebrate at the Cipher Bureau. They knew that the political situation in Europe was becoming increasingly alarming, and that it was only a matter of time before the German experts discovered that their code has been broken again.
On the 15th of September 1938, the German Army increased the complexity of the Enigma by adding two additional rotor wheels. It complicated the process of code breaking tenfold (with three rotor wheels they could be arranged in 6 ways, with five in 60 ways). Even though Rejewski quickly figured out the internal wiring of the new rotor wheels, finding out daily keys became a much longer process. Meanwhile political tensions continued to rise.
In April 1939, Germany withdrew from the German-Polish Non-Aggression Pact. This forerunner of future aggression pushed the Polish Cipher Bureau to share their knowledge with the allies: France and Great Britain. So far, the head of the Polish Army had shared all the decrypted messages with its allies, but had never revealed the method of decryption for fear of counter spying. During a secret meeting near Warsaw on the 26th of July, Polish experts revealed to French and British military heads that the Enigma code was broken and pledged to supply them with the replicas of the military version as well as with know-how concerning procedures of code breaking and reacting to future code modifications. On September 1st, 1939 Nazi Germany invaded Poland.
Those interested in learning more about the heroic Polish resistance during Nazi occupation may read our article: Crash Course on the Warsaw Uprising
From Poland to England via France
The entire team of the Cipher Bureau decided to flee from Poland on September 5th, only four days after German invasion. They managed to sneak into France where they worked at PC Bruno – a Polish-French intelligence service devoted entirely to military code breaking. Until the Fall of France in July 1940, when all experts from PC Bruno were forced to move to Great Britain, almost one out of five messages encoded in Enigma were solved there. The Nazis captured some members of the team on their way but despite the drastic torture methods used, none of them revealed the secret of the Enigma code being broken.
In England, Marian Rejewski and Henryk Zygalski were inducted in the Polish Army in exile, and started working on breaking German hand ciphers at a Polish signals facility in Boxmoor. Due to their having been in occupied France, and imprisoned by Franco’s army on their way to Great Britain, it was thought too risky to invite them to work at Bletchley Park – the headquarters of code breaking of the British Army.
The ideas primarily developed by Rejewski and his colleagues from the Polish Cipher Bureau served as strong foundations for further works on breaking the constantly changing codes of Enigma. After 1940 it was the team of Bletchley Park that took the leading role in dealing with Enigma coding. The engineers of Bletchley Park invented their own version of ‘the bomb’ and by the end of the war almost 100% of German messages were properly decoded. Dwight Eisenhower said that breaking of the Enigma code was ‘decisive’ for the allied forces victory and many historians say that it shortened the war by two years, therefore sparing millions of human beings.
Henryk Zygalski stayed in England after World War II. He died in 1978.
Marian Rejewski returned to Poland where he died in 1980 at the age of 74.
Both mathematicians were awarded the Highest Ranking Medals of Merit of the Republic of Poland as well as War Medals by the British Army.
Author: Wojciech Oleksiak 3.07.2014 with edits by Lea Berriault. Source: Rejewski Marian, Woytak Richard (1984), A Conversation with Marian Rejewski, Rejewski Marian, Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys, and of German Efforts to Frustrate Those Methods.
Return to HOME PAGE.
To go to the Cryptologic Bytes archives page to see more articles such as this one, please click below on the "Return to List" link.