The Poles

Bob: Alrighty. So, let's find out whether Enigma was broken. First up, we have Marian Rejewski, Henryk Zygalski, and Jerzy Różycki. These were three Polish students studying mathematics at a university in Poland in the late 1920s, and in 1929, they were among a select group chosen to attend a secret cryptography course at a nearby military facility. The course was designed to introduce top Polish mathematics students to the field of cryptography, and it was organised by the Polish Cipher Bureau—a Polish military unit focused on intelligence gathering and cryptography. The hope was that the students would develop strong codebreaking skills that would make them valuable assets for the Bureau. Rejewski, Zygalski, and Różycki excelled in the course and eventually ended up working at the Polish Cipher Bureau after they finished school.

Alice: And just to put things in perspective, World War II officially started on September 1, 1939, when Germany invaded its neighbour, Poland. However, long before the invasion, the Poles were aware of the volatile political situation developing in Germany and recognised the threat posed by the Enigma machine—a cipher machine capable of concealing the German military's plans. As a result, they made it their top priority to break Enigma.

Hanne: I see. And were the Poles successful?

Bob: They were! From the early 1930s up until the start of World War II, the Polish Cipher Bureau successfully decrypted many Enigma-encrypted messages. This was largely thanks to the brilliant work of the three young mathematicians: Marian Rejewski, Henryk Zygalski, and Jerzy Różycki.

Hanne: Amazing!

Alice: However, it's worth pointing out that breaking Enigma wasn't a one-time event. Rather, it was a continuous process that took years of persistent effort. The Poles had to constantly refine their techniques and devise new methods to keep up with the Germans' improvements to the Enigma machine. We won't delve into all of their codebreaking techniques, but some standouts include:

• The perforated sheets—also known as the Zygalski sheets
• The cyclometer
• The Bomba

If you're interested, you can research them further. For now, we'll briefly talk about their most famous one—the Bomba.

Bob: The Bomba was a machine designed to quickly explore the different starting configurations of the Enigma machine and narrow down the possibilities for the key. It was initially designed by Marian Rejewski but was later refined and developed by the entire team.

Hanne: A machine to break a machine. Neat. Why was it called "Bomba"?

Bob: Well, there is some uncertainty regarding the etymology of the name. Some say that the Polish mathematicians were eating an ice cream dessert called "Bomba" when the idea for the machine came to them. Others say that the machine dropped weights just as an aircraft drops bombs, so the cryptographers called it "Bomba"—the Polish word for "bomb". However, to this day, no one knows for certain why it was called "Bomba". Even Marian Rejewski, reflecting years later, couldn't remember how the name came about; its etymology remains a mystery.

Hanne: Etymology?

Bob: Oh, etymology is the study of the origins of words and how their meanings and usage change over time.

Hanne: Oh, okay. So, it's like the life story of a word?

Bob: Pretty much. When learning a new word, looking up its etymology can be a fun little bonus, as you get to see where the word came from and how it evolved over time. For instance, some words whose etymologies you may be interested in exploring are "nice", "robot", "salary", and "sandwich".

Hanne: Okay.

Alice: But getting back to the Polish Bomba, it turns out that the Poles needed to build one Bomba for each possible Enigma wheel order. This would have allowed the work to be split up and the correct Enigma starting configuration to be worked out quickly. In the early days, Enigma had 3 rotors, which meant there were 6 possible wheel orders. Building 6 Bomby—the plural of Bomba—was something that the Polish Cipher Bureau could do. However, in December of 1938, the Germans added two more rotors, increasing the possible wheel orders from 6 to 60. Unfortunately, building 60 Bomby was beyond the bureau's budget and engineering capacity.

Hanne: Oh.

Alice: And while we're not going to delve into the specifics of how these Bomby worked, we should mention that they relied on a certain Enigma-operating procedure that the Germans used. However, the Germans changed this operating procedure early in the war. This meant that even if the Poles had managed to build all 60 Bomby, they still wouldn't have been able to break Enigma for most of World War II.

Hanne: I see. So, the Poles were able to break Enigma from the early 1930s up until December of 1938.

Alice: That's right.

Bob: Now, around late 1938 to early 1939, there was another major development—this time a diplomatic one. The British and French were finally beginning to grasp the full scale of the threat that Germany posed, so they began discussing the idea of combining their intelligence operations to tackle the Enigma machine. The French, in particular, encouraged the British to include the Poles in this joint operation, as they knew that the Poles were working on Enigma—though they didn't know the extent of their progress.

Hanne: Interesting.

Bob: Eventually, the British and French agreed to collaborate and include the Poles. In January of 1939, they formalised this agreement at a three-country conference held in Paris, France.

Hanne: Yay!

Alice: Now, it was expected that a lot would come out of this conference, as there was now the shared knowledge of three countries' intelligence groups working on Enigma. However, during the conference, no one shared anything of real value. The British and the French were far behind the Poles in understanding Enigma, and the Poles withheld information about the progress that they had made in breaking Enigma over the years.

Hanne: Oh?

Alice: However, what the conference did achieve was that it provided an opportunity for each country to assess the key figures leading the intelligence operations of the others. They were able to "read one another", so to speak, and determine whether they felt comfortable trusting the other intelligence groups with their insights into Enigma.

Bob: After this January 1939 conference, the Poles continued refining their techniques to break Enigma. However, the two new rotors that the Germans had added were posing a challenge. Then, as the year progressed and the German political situation worsened, the Poles decided it was time to share their previous breakthroughs with their allies. In July of 1939, they notified the British and the French that they had new developments related to Enigma. This prompted key personnel from British and French intelligence to travel to Poland for a second conference.

Hanne: Ooooh… round two.

Bob: Indeed. And this second conference spanned two days, during which the Poles shared everything that they knew about the Enigma machine with the British and French. They explained how the military version of Enigma worked and how the Germans used it. They described the various methods that they had developed to break Enigma and the multiple changes that the Germans had made to the machine over the years.

Hanne: Wait, why did the Poles need to explain how the military version of Enigma worked and how the Germans used it? Wouldn't the British and French already have known this?

Alice: Actually, no. The British and French did not know how the military version of Enigma worked, let alone how to break it.

Hanne: Oh! How come?

Alice: The military version of Enigma had a different internal wiring setup than the commercial version.

Hanne: Internal wiring?

Alice: Yes. "Internal wiring" refers to how the wires are connected between the keyboard, rotors, reflector, and lampboard. There were many ways to set this up, but users did not need to worry about it since it was built into the machine. However, if you were trying to break the Enigma machine without having one, then things got complicated. You needed to either find a way to get an Enigma or build one yourself—both of which were incredibly difficult tasks.

Bob: Right. While accessing the commercial version was relatively easy, the Germans were very careful not to let the military version slip into enemy hands. If you were not in the German military, then getting access to a military Enigma was nearly impossible. Sure, during the chaos of war, things may have been different. For instance, if you defeated a German unit, you could recover their intelligence materials and get a military Enigma. However, in the 1930s, before World War II began, sneaking into the German military and yoinking an Enigma machine was out of the question. The more feasible option, although also extremely difficult, was to figure out the internal wiring of the military Enigma.

Alice: And this is what the Poles achieved by the end of 1932!

Hanne: Waw! That makes their work even more impressive! How did they figure out the internal wiring of the military Enigma?

Alice: Well, it was a combination of Marian Rejewski's ingenuity, some assistance from the French, and a stroke of luck that made it possible. Rejewski first applied some advanced mathematical theorems to create a set of equations that described the internal wiring of the military Enigma. But these equations had too many unknowns, which made them difficult to solve. The French then came along and shared some documents they had obtained regarding the military Enigma. This information enabled Rejewski to simplify his equations, making them more manageable. However, one major challenge remained: figuring out the wiring connections in a certain part of the machine known as the "entry disk". In the commercial version, the connections followed the Enigma keyboard order—QWERTZ…—but this was not the case in the military version. Marian Rejewski needed to figure out how these wires were connected in the entry disk.

Hanne: Oh, 26 wires and \(26! \approx 4.03 \times 10^{26}\) possible ways of arranging them.

Alice: Exactly. However, Rejewski, having done some school in Germany and grown up in an area in Poland with strong German influence, knew that the Germans liked order. So, he simply guessed that the wires were arranged alphabetically—ABCDEF…

Hanne: Okay?

Alice: And he was right! Out of the \(26!\) possible ways that the wires could have been connected, the Germans had chosen alphabetical order. It was this guess, combined with the intelligence provided by the French, that enabled Marian Rejewski to solve his equations and determine the internal wiring of the military Enigma. He achieved this towards the end of 1932, and by 1933, the Poles were able to build their own military Enigma machine and begin developing methods to break it.

Hanne: Wow! That's incredible!

Alice: Absolutely.

Bob: And while we're at it, we might as well give you some more information about the Enigma-related documents that the French shared with the Poles. For instance, you might be wondering: How exactly did the French manage to obtain documents related to the tightly guarded military Enigma?

Hanne: Oh… yeah? How did the French get those documents?

Bob: Well, it all started with the Schmidt brothers, Rudolf and Hans-Thilo. These two served in the German military during World War I and were awarded medals for their bravery. However, the younger brother, Hans-Thilo, was injured during the war, and it took him several years to recover. When he eventually got back on his feet, Germany's post-war economy was in shambles, and this made it very difficult for Hans-Thilo to find work and support his family. As for Rudolf, he remained in the German military and steadily rose through the ranks—a path Hans-Thilo's career might have also taken had he not been injured.

Hanne: Right.

Bob: Aware of his brother's plight, Rudolf used his influence to help Hans-Thilo secure a job at the German Cipher Bureau. But despite being a high-ranking position, the salary was not enough for Hans-Thilo to pay off all his debts. However, Hans-Thilo had an idea. He recognised the significance of the work being done at the German Cipher Bureau and realised that other countries might be willing to pay a lot of money for access to this sensitive German intelligence material. So, one fine day in June of 1931, he walked into the French embassy in Germany and expressed interest in selling secret documents to the French. He provided his address for further correspondence, and after a few exchanges of letters, he met with French intelligence personnel in November of 1931.

Hanne: Huh!

Bob: Before this meeting with Hans-Thilo Schmidt, French intelligence conducted background checks to ensure he was a reliable source and not a German agent sent to mislead them. They discovered that he held a high position in the German Cipher Bureau but were curious about how he had obtained it. They were also interested in knowing why he wanted to sell documents, as it was uncommon for someone of such high rank to do so. During the meeting, they learnt about his World War I injury, his financial struggles, and how his brother had helped him secure the high-ranking position in the cipher bureau. This gave them a deeper insight into Hans-Thilo Schmidt and helped them better understand his motivations for wanting to sell secret documents.

Alice: Hans-Thilo appeared to be a trustworthy source who could provide the French with sensitive information from inside the German military. This view was further reinforced when they recognised the importance of the documents that he had brought to the meeting—military Enigma manuals and key sheets. French intelligence paid him a substantial sum for copies of these secret documents, and from that point on, Hans-Thilo Schmidt became a spy for the French, secretly providing them with valuable intelligence from within the German military.

Bob: Now, French intelligence shared the initial documents with the French Cipher Bureau, but upon analysis, their bureau found that the military Enigma manuals were not as useful as French intelligence had hoped. This was because the manuals were user manuals and therefore did not describe the machine's internal wiring. The French then shared these documents with the British, who also concluded that they were insufficient to recreate a military Enigma. Eventually, the French passed them on to the Poles, who, thanks to Marian Rejewski, were able to make better use of them.

Hanne: Right. Marian Rejewski had already developed a set of equations to describe the internal wiring of the military Enigma.

Bob: Exactly. Notice how the British, French, and Poles all had access to these secret documents, but it was only the Poles who, thanks to the brilliance of Marian Rejewski, were able to make effective use of them.

Hanne: Right.

(Hanne thinks.)

Hanne: I remember you mentioned that in the set of equations that Rejewski developed, there were too many unknowns, which made them difficult to solve. Did these secret documents from Hans-Thilo Schmidt simply speed things up, or were they essential to the solution?

Alice: Ah, great question. The documents were essential to the solution. Without them, Marian Rejewski would have had a very slim chance of solving his equations.

Hanne: Oh… wow! So the Poles were very fortunate that Hans-Thilo Schmidt decided to sell documents to the French.

Alice: Yes, they were. Without Hans-Thilo, the Enigma codebreaking story might have been very different—especially when you consider that it was extremely rare for German officials, much less one of such high rank, to sell intelligence to foreign powers. Hans-Thilo Schmidt was the right person in the right place at the right time.

Hanne: I see.

Bob: And just to wrap up Hans-Thilo's story, from 1931 onwards, he continued working with French intelligence, supplying them with valuable information about the German Enigma machine. Notably, the first time that the British, French, and Poles learnt about the plugboard on the military Enigma was from an image provided by Hans-Thilo—the commercial versions of Enigma did not have a plugboard.

Hanne: Oh!

Bob: And in addition to Enigma-related information, Hans-Thilo also provided details about German military plans. However, it has been said that the French did not act on this information as effectively as they could have. For example, if Hans-Thilo informed them of imminent German troop movements, the French often failed to take adequate measures to counter the threat. Nevertheless, the intelligence that he sold to the French over the years was highly valuable, and it significantly contributed to other countries' understanding of German military operations.

Alice: Eventually, though, in 1943, a French intelligence officer who regularly interacted with Hans-Thilo was captured by the Germans. To save himself, he revealed that Hans-Thilo was working for French intelligence. As a result, Hans-Thilo Schmidt was arrested and later committed suicide while in prison. His brother, Rudolf Schmidt, also lost his job due to suspicions that he too was a spy.

Hanne: Oh.

Bob: So that's the story of Hans-Thilo Schmidt and how the French were able to get documents related to the tightly guarded military Enigma. However, as a bit of an aside, there's one final thing that we'd like to say about Hans-Thilo. His espionage story presents us with an interesting moral dilemma—well, maybe "moral conundrum" is the better term. You'll soon learn how crucial the Enigma codebreaking efforts were in World War II and how the success of these operations likely shortened the war and saved many lives. Thus, by extension, Hans-Thilo Schmidt's decision to sell documents to the French would have contributed to the shortening of the war and the saving of lives.

Hanne: Right.

Bob: But while it was the case that after World War I Hans-Thilo Schmidt struggled financially, he also lived, and desired to live, a rather promiscuous and luxurious lifestyle. In this manner, he wasn't a virtuous man selling secret documents to support his wife and two kids. Rather, his actions were largely driven by lust and greed.

Hanne: Oh.

Bob: And yet, his actions ended up contributing to a greater good. So… the conundrum is: If one can act so selfishly and have such a positive impact on the lives of others, what does that say about those who choose to act selflessly but never achieve the same kind of impact?

Hanne: Hmm…

Bob: And taking it a step further, we might ask: Does the value lie in the overall impact of one's actions or in the way in which one chooses to act? Or is it a bit of both? We don't know. But you can ponder this, if you like.

Hanne: Huh… okay. I'll give it some thought—at my leisure.

Bob: Lovely. So, that's all we have to say on Hans-Thilo Schmidt and more generally on the Enigma codebreaking efforts leading up to World War II. To recap:

• The Polish Cipher Bureau began focusing intensively on the Enigma machine around 1930.
• Hans-Thilo Schmidt began selling documents to the French in 1931.
• The Poles were able to solve the internal wiring of the military Enigma towards the end of 1932, build their own machine in 1933, and develop several methods to break Enigma in the years that followed—with the Bomba being their most renowned method.
• In December of 1938, the Germans introduced two additional rotors to the Enigma machine, which significantly complicated the Polish codebreaking efforts.
• In January of 1939, the first conference between the British, French, and Poles was held in France.
• In July of that same year, the Poles shared all their Enigma breakthroughs with the British and French in a second conference that was held in Poland. And this second conference took place just in the nick of time, as it was mere weeks before September of 1939, when Germany invaded Poland, marking the beginning of World War II.

Hanne: Incredible.

Bob: Indeed.

Alice: So, naturally, the next step would be to discuss the Enigma codebreaking efforts that took place during the war. However, before we get to that, let's just say a few words about how the Germans used the Enigma machine, as this will strengthen your understanding of the codebreaking operations.

Hanne: Okay.

Alice: Recall that the key in Enigma is its starting configuration, which consists of the wheel order, rotor settings, and plugboard connections. And we found that Enigma had around 159 quintillion possible keys.

Hanne: Yep.

Alice: Well, how do you think the Germans managed the keys in Enigma?

(Hanne thinks.)

Hanne: Well, out of the 159 quintillion possibilities, they would have chosen a key to use to secure their communication. And because it is difficult to detect a compromised key, for additional security measures, they would have changed this key ever so often. Maybe… once a month.

Alice: Okay. And how do you think they securely communicated this new key to all their military units?

Hanne: I'd say they probably had trusted messengers who would physically deliver the new key to all military units towards the end of the month, so they'd be ready to use for the following month.

Alice: Fair enough. You're not totally correct, but you're pretty close—kind of. Instead of changing the key every month, the Germans changed it every day.

Hanne: Every day!? So they securely communicated a new key among themselves every day?

Alice: Not exactly. They had trusted messengers who would deliver monthly key sheets to each unit in a sealed envelope. However, as opposed to communicating a single key, these monthly key sheets contained a list of keys, and they communicated what key to use each day of the month—that is, the wheel order, the rotor settings and the plugboard connections to use each day of the month.

Hanne: Okay. So they changed the key every day, and they securely communicated the daily key using monthly key sheets—I was pretty close.

Alice: Well, that's not all the Germans did.

Hanne: Oh.

Alice: This daily-key approach in Enigma would have introduced one problem—a large amount of ciphertext would be generated from a single key every day.

Hanne: Ummm… okay? But how is this a problem? Isn't the goal of cryptography to share a key through a secure but slow channel and then use it to secure mass communication through an insecure but fast channel?

Alice: Yes, ideally, we would want to use a single key to secure mass communication. But attempting to do this with the Enigma machine would not have been secure.

Hanne: Why not?

Alice: Well, while the Enigma machine was a major advancement in the field of cryptography, it was still essentially a polyalphabetic cipher. And by the 1930s, there were advanced statistical methods for attacking polyalphabetic ciphers. However, these methods were only effective if they had large amounts of ciphertext to work with—similar to how frequency analysis is only effective at breaking simple substitution ciphers if you have large amounts of ciphertext to work with.

Hanne: Oh, okay. So, the Germans would have been aware of these advanced statistical methods and would have put measures in place to limit the amount of ciphertext being generated from a single key in Enigma.

Alice: Correct.

Hanne: Hmm… but how did they do it? Did they restrict the number of messages that could have been sent in a day?

Alice: No, limiting messages would have been impractical, especially in the context of war. Instead, the Germans did something clever—they used the daily key to securely communicate a message key and then used the message key to encrypt the message.

Bob: Well, just to elaborate on that a bit, the sender would randomly choose the message key and then:

• Encrypt the message using the message key.
• Encrypt the message key using the daily key.
• Attach the encrypted message key to the beginning of the message before sending it.

The receiver would then:

• Decrypt the message key using the daily key.
• Decrypt the message using the message key.

In this way, it was only the message key—and not the entire message—that was encrypted using the daily key. This significantly reduced the amount of ciphertext produced by the daily key and made the advanced statistical attacks less effective.

Hanne: I see. Pretty clever stuff.

(Hanne thinks.)

Hanne: And what did the message key look like?

Bob: The message key was a string of three letters.

Hanne: Wait—what? How could you communicate the wheel order, rotor settings, and plugboard connections using only a string of three letters?

Bob: Ah, good catch. You would need more than a string of three letters to communicate the full key for the Enigma machine. However, the reason the Germans were able to use only a three-letter string for the message key was because the message key always used the same wheel order and plugboard connections as the daily key; it was only the rotor settings that needed to be communicated.

Hanne: Ohhh…

Bob: And with three rotors, each having 26 possible starting positions, the three-letter string would tell the receiver how to adjust the starting position of each rotor—'A' would correspond to position 1, 'B' to position 2, and so on. So, if the message key was "BYE", this would mean to set the leftmost rotor to 2, the middle rotor to 25, and the rightmost rotor to 5, then start decrypting.

(Hanne thinks.)

Hanne: Okay. But… I'm thinking, isn't it a bit of a security vulnerability to have the message key be so similar to the daily key? The message key and the daily key share the same wheel order and plugboard connections, and it is only the rotor settings that are different.

Alice: Well, this is where the challenge of security versus usability pops up yet again. Sure, changing the wheel order and plugboard connections for every message key would be more secure, but doing so every time would drastically slow down communication. Instead, it is much more practical to use the same wheel order and plugboard connections and simply change the rotor settings for each message. And, as far as security goes, this approach is effective enough since it reduces the amount of ciphertext being produced from a single key and protects against the advanced statistical attacks on polyalphabetic ciphers.

Hanne: Okay, fair enough.

Alice: Splendid. So, that's essentially how the Germans used the Enigma machine—they communicated the daily keys via monthly key sheets and used the daily key to encrypt a message key at the start of each message. They then used the message key to encrypt the message.

Hanne: Got it.

Alice: Wonderful.

Bob: Now, the last little area that we'd like to mention is how, in the early days, the message key was actually the first six letters of the message, rather than the first three. This was because German procedure required the message key to be repeated for error-checking purposes. So, if the message key was "BYE", instead of encrypting "BYE", the sender would encrypt "BYEBYE" using the daily key.

Alice: Right. And at first glance, this may not seem like a big deal. After all, in the Enigma machine, repeated groupings in the plaintext do not necessarily show up as repeated groupings in the ciphertext. So, encrypting "BYEBYE" using the daily key might produce "ADGTKW".

Hanne: Right, an adversary wouldn't get much information from that ciphertext.

Alice: Well, it turns out that Marian Rejewski was able to exploit it. Knowing that the message key was always repeated at the start of each message, he realised that there was some relationship between the 1st and 4th letters, the 2nd and 5th letters, and the 3rd and 6th letters in the ciphertext. So, in the ciphertext "ADGTKW", he noted that there was a relationship between 'A' and 'T', 'D' and 'K', and 'G' and 'W'.

Hanne: Oh.

Alice: And after analysing a lot of ciphertext, he noticed that cycles of varying lengths were forming. For instance, he might have found that 'A' was related to 'T' in one ciphertext, then 'T' was related to 'L' in a second ciphertext, and 'L' was related to 'A' in a third ciphertext. This formed a cycle of length three: A→T→L→A. So, by intensively analysing these different cycles and applying some advanced mathematical theorems, Rejewski was able to develop a set of equations that described the internal wiring of the military Enigma.

Hanne: Okay! So, it was this repetition of the message key that allowed Rejewski to develop his set of equations.

Alice: That's right.

Bob: Also, if you recall, we mentioned earlier that the effectiveness of the Polish Bomba heavily relied on a German Enigma operating procedure, but the Germans changed this procedure early in World War II.

Hanne: Yes.

Bob: Well, the German Enigma operating procedure that we were talking about was this repetition of the message key.

Hanne: Huh! So, the repetition of the message key not only helped the Poles solve the internal wiring of the German military Enigma, but it also allowed them to develop methods to break it.

Bob: That's right.

Hanne: Interesting how something as simple as repeating the message key led to such a huge security flaw.

Bob: Yep. If the Germans hadn't repeated the message key in the early days, the Poles probably wouldn't have made all the progress that they did in breaking Enigma. This just goes to show how risky repetition can be in cryptography.

Hanne: Right. It can leak information that adversaries can exploit.

Bob: Correct. And when those adversaries are as brilliant as Marian Rejewski, any weaknesses in your cryptosystem are bound to be exploited.