Sunday, 5 February 2017

Modern breaking of Enigma ciphertexts

The title on this posting is also the title of my latest Cryptologia article co-authored with Olaf Ostwald. The purpose is of course to give the article some publicity because we think it is worth reading  at least for those who are interested in the German cipher machine Enigma and especially for those who are interesting in cryptanalysis and codebreaking. Modern breaking of Enigma ciphertexts is, as the title says, our attempt to document what can be achieved using modern computer based methods for ciphertext-only attacks on authentic German Army messages from World War II.

But before going into more details about the article’s content I think it is interesting to first look at its history and background. The story starts of course on 22 June 1941, when the first of the German Army messages was sent and when the German attack on the Soviet Union, Operation Barbarossa, began. However, we have to wait until the end of the 1980’s before the messages reappear and arrive in the hands of our good friend and fellow researcher, Michael van der Meulen. Michael had by then done extensive research into German cryptologic history and he had become friendly with Oberstleutnant (Lieutenant Colonel) Waldemar Werther who during the Second World War was a signal intelligence (Sigint) officer in the German Air Force (Luftwaffe). His main responsibility was deciphering of Russian signals. Immediately after the war he had several civilian jobs until he in 1953 started to work for the French intelligence service, SDECE. He seems to have been attached to their Sigint organization, GCR, working on Soviet and East German problems. He stayed with the French for about four years until he joined the newly created German Air Force Sigint organization in 1957.

Exactly how the messages came into his hands is not known but probably through his post-war work in the German Sigint organization. However, it is known that Waldemar Werther was instrumental in saving these messages from destruction and he made sure the material would survive his death.  On his death in the late 1980’s, his widow Hetty followed his wishes and transferred the Army messages to Michael van der Meulen. The first attempt to attack these messages was made in 1996 by James Gillogly. In October 1995 he had published his groundbreaking article  “Ciphertext-only Cryptanalysis of Enigma” in Cryptologia. When he wrote his article he did not have access to any original or authentic Enigma ciphertexts. He based himself on English translations of German messages decrypted at Bletchley Park (BP) but these messages were summaries of multiple Enigma messages and rewritten to help disguise their source. Some of these summaries contained 1500 letters and one was even 2300 letters long where most were in the order of 350 to 550 letters, far above the prescribed maximum limit for Enigma cipher messages of 250 letters. Ralph Erskine and I pointed out this problem to Jim and in an e-mail to me in March 1995 he replied: “I do wish I had access to more actual German Enigma messages, though!”

Well, that changed in January 1996 when I sent Jim an e-mail to tell him I had heard that Michael van der Meulen had sent copies of some of these messages to him via Lou Kruh, a well known cryptologist, editor and activist — but foremost of all an avid collector of cryptologic memorabilia. Jim immediately started to transcribe the messages and put them into an electronic format but what happened after that I am not so sure. I never heard back from Jim that he had any success in breaking the messages he had received. I was also interested in getting copies of these messages but first in February 2001 did I received a selection of the messages from Michael. I immediately started to transcribe some of the messages and share them with Geoff Sullivan, our Crypto Simulation Group (CSG) simulator guru.

The CSG members at Oxford in June 2000.
From left to right: Ralph Erskine, Frode Weierud, David Hamer, Philip Marks
 and Geoff Sullivan. Wes Freeman joined in March 2002.
The CSG was started with three members, Geoff, David Hamer and me, back in May 1997. Phil Marks joined the team at the end of 1997 and Ralph Erskine joined us in January 1998, when we coined the name Crypto Simulation Group. Wes Freeman became a member in March 2002. The basic idea was to get access to real cipher machines or at least sufficient technical details such that the machines could be simulated on a computer. Our goal was also to verify the simulations against the real machines or at least by using plain- and ciphertext generated on these machines. And the final aim was to use the simulations to thoroughly study the machines with the hope of perhaps being able to cryptanalyse and break their ciphers. During the period 1997 to 2005 we were very active with Geoff Sullivan turning out one simulator after the other, which resulted in several publications about the CSG simulated machines and attempts to break their ciphers. After about 2005 professional obligations at work and elsewhere, new and diverging interests among the members and perhaps a little sense of fatigue resulted in a slowly diminishing activity within CSG. Today CSG is dormant, but not dead, and the members are still in regular contact with each other.

In January 2002 Geoff and I started to look at the German Army messages again and throughout the year ideas on how to find the first few Enigma Steckers bounced back and forth between us. However, things dragged on as we were also busy with our Cryptologia article on PURPLE and other interesting projects. Geoff build a hillclimbing Enigma breaker, our EBreaker, and finally in March 2003 Geoff could report the first break of one of the messages. The details you can read in our Cryptologia article “Breaking German Army Ciphers” published in July 2005 and on our BGAC Web page. The article and the story of amateur codebreakers solving German Army Enigma messages created a considerable media interest. Especially our decrypted message from the Nazi concentration camp Flossenb├╝rg was a media magnet and even Russian TV came to Geneva to visit and interview me about this story. The media circus was intense, interesting and short, but what brought us the most persistent joy was all the feedback and interest the article created among fellow amateur codebreakers. New projects based on our ideas started in several places, among the better known are the M4 Message Breaking ProjectEnigma@Home and Breaking German Navy Ciphers. Geoff and I wanted if possible to interest and involve the readers in breaking authentic Enigma messages. We therefore posted a selection of messages we already had broken and found to be not too difficult to solve, Five or six Easy Pieces in the key of E.

Many took this challenge and also attempted to attack the unbroken messages we had posted on our BGAC Web page. Some of the solvers and their solution you can discover on the Codebreaker’s Honour Roll and on the 1941 Message Overview. A small caveat is that none of these two lists are fully up-to-date. Several solvers are, as you can see, excellent codebreakers but over time one, through his perseverance, stood above them all. He originally did not wanted to be in the limelight and he is therefore only mentioned by his first name, Olaf. As I am sure you have already guessed he is my co-author Olaf Ostwald. In 2009 both Geoff and I were too occupied professionally to continue breaking and transcribing the rest of the unbroken messages. Seeing Olaf’s track record and sensing his commitment we therefore decided to let him have full access to all the scanned message forms, which happened in 2011. In a sense we were happy to have found a worthy successor.

It should now be clear that the existence of our article “Modern breaking of Enigma ciphertexts” depends entirely on the perseverance of Olaf and the lucky decision of Geoff and me to let him singlehandedly  take over our codebreaking project in 2011. Now having full access to the message collection Olaf could choose freely his ciphertexts and hence fine tune his codebreaking algorithms. Another great advantage is of course that being German Olaf does not have the same difficulties with the language as Geoff and me. His understanding of the plaintexts is close to instant and he is also in a much better position to deliver faultless translations in English.

Well now a few words about the article itself. Of course it builds on the ideas of Geoff and me as described in our 2005 Cryptologia article, but goes much deeper into the problems of breaking short Enigma ciphertext and messages with many garbles. It also explains in detail how the plugboard (Steckerbrett) encryption works and how this affects our codebreaking effort. Many of the previously puzzling observations Geoff and I made during our work has now found their explanation. We show that for a rotor machine like the Enigma, with cyclometric stepping, it is possible to break messages close to the unicity distance. However, to arrive at such results it is necessary to fine tune the codebreaking algorithm such that it is well adapted to the real cryptanalytical problem and also be use a language database that is as close as possible to the underlaying plaintext. Hence, the more messages you solve the better is your chance of breaking the real short ones.

We wish you happy reading and we sincerly hope that you will find it both interesting and thought provoking. We also invite you to report any errors or typos that you might discover. A few are already known and they will be reported shortly on the MBEC Web page. Here you will also find information and documents related to our article.

No comments: