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.
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
Blog 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.
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:
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:
- 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).
- 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.
- 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 = K – P1 (the M-209 encrypts by subtracting the plaintext from the key, which is also known as Beaufort cipher)
C2 = K – P2
=> P2 – P1 = C1 – C2
We can divide the (C1–C2 = P2–P1) 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!
Follow @KlausSchmeh
Further reading: New improvements in Enigma cryptanalysis
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Kommentare (5)