M209-Computermuseum-solved-bar

Israeli codebreaker and reader of this blog, George Lasry, has solved cryptogram #42 from my top 50 list.

Click here for the complete top 50 list

With about 140,000 copies built, the M-209 is probably the most produced encryption machine ever. The US military used this device in World War II, and it remained in active use through the Korean War.  The photographs shown here were provided to me by my friends Marc Simons and Paul Reuvers from the Cryptomuseum.

M-209-Cryptomuseum-01

A medium security device

The M-209 was used as a field cipher. It was designed to be small, robust, and lightweight. Instead of a keyboard (like the Enigma) it contained a letter wheel (the grey wheel on the left side). For each letter to be encrypted, the operator had to adjust this letter with the letter wheel and press a lever, which made the machine print the corresponding ciphertext letter on a paper strip. A great M-209 simulator has been programmed by Dirk Rijmenants.

The M-209 uses three different keys (the recipient needs all of them to decrypt a message):

  • Wheels: The position of the six wheels at the front is a key (this key was usually different for every message encrypted). Wheels #1, #2, #3, #4, #5, and #6 are labeled with 26, 25, 23, 21, 19, and 17 letters, respectively.
  • Pins: Every wheel has a pin for every letter, which can be active or inactive. Activating or deactivating a pin is only possible when the cover is open.
  • Lugs: Inside the machine there’s a rotating cage with 27 bars. Each bar in the cage has two movable lugs. Each lug may be set against any of the six wheels or set to a neutral position.
———–
Off-topic

Kryptogesellschaft-SchweizBlog reader Christian Meier from Switzerland has founded a crypto association (“Kryptologiegesellschaft Schweiz”).

So, if you live in Switzerland and are interested in encryption, codebreaking, and steganography, consider to join this organisation. Christian will be happy to get in contact with you.

Christian’s email address is kryptologiegesellschaftschweiz@gmx.ch.

———–

The M-209 was less secure than the Enigma and other encryption machines of the time. The cryptologists of the US Army, which belonged to the best in the world, were aware of this weakness. However, the M-209 had not to be unbreakable, as it was only used as a field cipher. Typically, M-209 encrypted messages contained information like position reports, material orders, weather reports or warnings, which usually lost their value within days or even hours.

During World War II several German crypto units independently from each other found ways to break the M-209. In 2004 I had the chance to talk to a German WW2 codebreaker named Reinold Weber, who reported about a codebreaking machine German specialists constructed in order to decipher M-209 messages.

M-209-Cryptomuseum-03

Even decades later, when the M-209 was long out of use, crypto experts developed new attacks on this machine. E.g., in the late 1970s, Jim Reeds, Robert Morris, and Unix inventor Dennis Ritchie introduced a ciphertext-only method for recovering keys from M-209 messages. In 1977 US cryptologist Wayne G. Barker published a book named Cryptanalysis of the Hagelin Cryptograph. It describes a method for breaking the M-209 and includes a number of M-209 ciphertexts for the reader to solve.

 

An unsolved challenge

Jean-Francois Bouchaudy published another series of 40 M-209 challenges with increasing difficulty on his website. This series starts with 12 cryptograms referenced on the main page. The remaining 28 problems are referred to as Bonus Challenges.

Currently, the leading expert on breaking the M-209 is George Lasry, a reader of this blog and friend of mine. George is a great codebreaker specialising in historical cryptograms that were encrypted in a known cipher (i.e., the challenge is to find the key). The following picture shows George (left) with crypto legend Whitfield Diffie:

Lasry-Diffie

George’s favorite codebreaking technique is hill climbing. He has broken many different historical ciphers with this method. Especially, he found two very powerful hill climbing attacks on the M-209. He published them in a Cryptologia paper and presented his results at the European Historical Ciphers Coloquium in Bratislava.

 

The Bonus #22 mystery

With his new methods George solved all challenges from Wayne G. Barker’s book and 39 of the 40 challenges published by Jean-Francois Bouchaudy.

The only challenge he could not solve was #22 of the Bonus Challenges.

Bonus #22 consists of a series of 78 messages, two of which are in depth (i.e., encrypted with same key settings). Here’s the first one (for space reasons I don’t want to provide the remaining 77 messages here):

R2M4 V M8E3
ONR01 LLANJ RFGLB HYKHK TCYDQ DULTU XUPGL RFOHR XZIWY BLHJK
THRPO QFUUI XXWZJ GOBVH MOKPT ASAOZ RHNVN HJPLJ IQUPT QVMKY
FPDSM OARHR WCUMK UAEAC JTOHR FOEAU FMWGR DSIFB GMRAQ GWMCQ
IILGS TLKFK KZMVE XCVQF BTGHC KVBRT OHLQP QFMOF XGVJB YNGGE
PKCUJ XQDLY KBJDN CENXX HIELL RSHEI QWGJM ZQIPI OZQHM FAQYE
YYSEE ZJHVL OHPSE MOCLK VERKI GKYPG EQHWZ NCBAM LPXPP GGDMU
FIUKT UBJZT HXIPM HFDJA NKIUN ESOAK GSBIZ SYXXX LLANJ RFGLB
0630A

A complete list is available here.

Last year in March I introduced the Bonus #22 challenge in my series about the top 50 unsolved cryptograms.

 

The solution

Yesterday I received an email from George Lasry. He told me that he had solved Bonus #22.

The following paragraphs are based on the explanation George provided me:

Bonus #22 consists of 78 messages in English, enciphered using the same M-209 daily key (internal key), but with different message keys (external keys). Solving a challenge of this kind requires:

  1. Detecting a pair of messages with either full depth (same external key), or partial depth (also known as “key overlap”, so that the first part of one message is encrypted with the same key as the last part of the second one).
  2. Recover the plaintext using standard trial-and-error guessing techniques. Guess a probable word for one message, compute the resulting decryption for the second, and see if it makes sense.
  3. Recover the M-209 key from a plaintext-ciphertext pair.

The external keys are sent encrypted. They appear as ten-letter indicators at the beginning and at the end of each message. From observing them, it became clear that no (two) messages of Bonus #22 have the same indicator, which means that there are no cases of full depth. So, George had to look at partial depth (key overlap) only.

Detecting two segments of ciphertext in depth was a known problem in WW2, also relevant to other additive cipher systems, like the Lorenz SZ-42. To do so with M-209 messages, a German codebreaking service developed a method, which is described here. The idea is that if two plaintexts P1 and P2 are encrypted using the same key K, then for their corresponding ciphertexts C1 and C2, we have:

C1 = KP1 (the M-209 encrypts by subtracting the plaintext from the key, which is also known as Beaufort cipher)

C2 = KP2

=> P2P1 = C1C2

We can divide the (C1C2 = P2P1) sequence into trigrams and look at their frequencies. For example, the difference between ING and ION is (I-I modulo 26, N-O modulo 26, and G-N modulo 26) = (0, 1, 19). The concept is that for two messages in depth, the frequencies of the trigram differences have a typical (non-random) distribution, and those not in depth will have a more random distribution.

George wrote a program implementing this idea, after extending it to 5-grams. It can find depths with a high precision in simulated examples. However, for Bonus #22, this program failed.

After working on the problem from various angles, George decided to apply his new ciphertext-only method, which works on messages with 500 symbols (and which he used to solve challenge #12), on the longest message in Bonus #22 (more than 500 symbols). He was finally able to recover the key, including the internal key and external/message key, and using that internal key, to recover the external keys for all the other messages.

The challenge was solved.

 

Congratulations

To be honest, I haven’t asked George about the cleartext of the messages he solved (as we are dealing here with a challenge cipher, the cleartext is not very relevant anyway). George: Perhaps, you can post a few decrypted passages in the comments section.

The only question remaining was why George’s statistical method (differences of 5-gram frequencies) had previously failed. It turned out that the Bonus #22 messages uses a special military/operational language with many abbreviations and slang expressions, whereas the statistics he had built were based on standard English. When he recalibrated his statistics he was able to detect an actual partial depth between two of the messages.

In his mail George wrote: “This was indeed one of the toughest problems I have been working on.”

I want to congratulate George Lasry on this great success! Another important crypto mystery is solved now!


Further reading: New improvements in Enigma cryptanalysis

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Gib Deine E-Mail-Adresse an, um diesen Blog zu abonnieren und Benachrichtigungen über neue Beiträge via E-Mail zu erhalten.

Kommentare (5)

  1. #1 George Lasry
    21. Januar 2018

    Thanks for your kind words. I could provide the plaintexts, however, the author of the challenge would like to keep it open for other contestants. So he prefers that we do not publish solutions. I can only hint that those are original war-time messages, (re)encrypted with the M-209 using some unknown key.

    One comment about the security of the M-209. The claim that the Enigma is more secure than the M-209 is disputable.

    1) The best modern ciphertext-only algorithm for Enigma (Ostward and Weierud, 2017) requires no more than 30 letters. My new algorithm for M-209 requires at least 450 letters (Reeds, Morris, and Ritchie needed 1500). So the M-209 is much better protected against ciphertext-only attacks.
    2) The Turing Bombe – the best known-plaintext attack against the Enigma needed no more than 15-20 known plaintext letters. The best known-plaintext attacks against the M-209 require at least 50 known plaintext letters.
    3) The Unicity Distance for Enigma is about 28, it is 50 for the M-209.
    4) The only aspect in which Enigma is more secure than M-209 is about messages in depth (same key). To break Enigma, you needed a few tens of messages in depth. For M-209, two messages in depth are enough. But with good key management discipline, this weakness can be addressed.

    Bottom line – if no two messages are sent in depth (full, or partial depth), then the M-209 is much more secure than Enigma.

  2. #2 Narga
    22. Januar 2018

    Congratulations! Great work, George!

  3. #3 Klaus Schmeh
    22. Januar 2018

    Richard SantaColoma via FaceBook:

    Well done, George!

  4. #4 Klaus Schmeh
    24. Januar 2018

    Bart Wenmeckers via Facebook:
    Good job on solving the M209.
    I think i have an emulator for it somewhere.

  5. #5 Jean-François BOUCHAUDY
    France (près de Paris)
    28. Januar 2018

    Congratulations George! You still managed to solve one of my challenges. I think you are one of the best (if not the best) cryptanalyst of classical ciphers. The problem you solved was important because the M-209 was used by the embassies of many small countries until the 1970s and only the approach that you used allows to decipher the messages. At the time, only the NSA had the computing resources to get there.

    I thank Klaus for putting one of my problems in his famous list of unresolved encrypted messages.
    Klaus knows both modern and classic ciphers and he knows how to share his passion!

    George has solved all my M-209 problems but he has not (yet) managed to solve my other problems concerning the other cipher machines (Kryha, RED, Hebern, C-36, Enigma, …). Hurry up if you want to beat him! http://www.jfbouch.fr/crypto/challenges/index.html