M-138 Challenge

The M-138 (also known as CSP-845) is a strip cipher system used by the US Armed Forces in the first half of the 20th century. See here for a description.

The purpose of the M-138 was to provide reasonable cipher security at low costs. It was not a high security system. It was used when a cipher machine (for instance the M-209 or the SIGABA) was not available. This happened quite often, as cipher machines were by orders of magnitude more expensive than strip ciphers and harder to transport. Before and at the beginning of WW2 a great deal of reliance was placed on the M-138 because of the shortage of cipher machines. Later it remained in use as a backup system.

In my view the M-138 served its purpose extremely well. It was a very cheap tool (consisting only of paper strips and a simple frame), it was easy to carry, it was easy to operate, and it provided high security given the circumstances. To my knowledge not much has been published about cryptanalysis of the M-138. Therefore, it is not known how much effort it takes to break an M-138 message and if this effort was realistic for a codebreaking unit in World War 2. In addition, it would be interesting to know whether the M-138 could have been improved without major effort (for instance by putting 30 strips into the frame instead of 25). To stimulate research I have created the M-138 challenge introduced on this page.

How the M-138 worked

For explaning how the M-138 works I use a fictive model, which is not compatible with an original M-138 device. An M-138 consists of 100 paper strips (the strips of my fictive model are given at the end of this page in an easy-to-read format). On each strip the alphabet is printed twice in a random order. For encryption the cipher clerk had to take a maiximum of 25 strips from the strip set and put them into the frame. In the following example the strips 66, 11, 52, 55, 04 and 90 of my fictive M-138 version are taken to encrypt the word CRYPTO.

The key of this encryption procedure is (66, 11, 52, 55, 04, 90 / 11). It consists of the strip numbers used followed by the offset between the cleartext column and the ciphertext column. In this example the ciphertext is UKLAGW. The number of strips used may not exceed 25 (only 25 strips fit into the frame). No strip may be put into the frame twice. This means that a key like (20, 12, 20, …) is not allowed.

If the cleartext is longer than 25 letters, it must be devided into 25 letter blocks. In the following example the cleartext THIS TEST MESSAGE CONTAINS NO CONFIDENTIAL INFORMATION is encrypted. It consists of 48 letters. We start with the first 25 letters as the first block. The key is (42, 19, 26, 28, 02, 17, 49, 38, 87, 08, 94, 64, 92, 88, 37, 63, 39, 35, 30, 31, 05, 27, 34, 78, 60 / 6).

Now the remaining 23 letters are encrypted (the key stays the same).

The ciphertext is BYKWH CXGTX DXFBV HHSEC JMAHT LRLUB FCCNJ WKAPJ LVVXO JQQ.

The Challenge

In the following, three ciphertexts generated with my fictive M-138 model are given. The task of the reader is to break the encryption and find the cleartext. All cleartexts are in English. Part 1 is the easiest, as the cleartext is the longest. It contains 75 letters, which means that each strip in the frame is used three times. The complexity rises considerably with part 2 and 3 because the ciphertexts become shorter (50 and 25 letters). In my view parts 1 and 2 can be solved while part 3 is extremely difficult, if not unbreakable. The key is different for each part, but there is no key change within a part.

Part 1 (75 letters)

PTIJJ HDJPK YTMTK UVEPD HYKLH DEYMG LIJLN WKXVG ZILQN CJRHW JNBJF UAQHN BJGXW ZBESX NXPZH

Part 2 (50 letters)

BEYXX ZRFWO WMJCA QIUZY KYLID NBYEC UBCDC UBQHZ AVJES UNECV

Part 3 (25 letters)

PJVYN PYIXG RPJRW YBMBA FQQPE

The Strips

The 100 strips used by the fictive M-138 are as follows (each strip contains the alphabet twice in the same order, to save space each alphabet permutation is only listed once):

00 DTYLUKCNOIVSEPFQJWRGMBZAXH
01 LOGKWPRMDUVSYFJNTQIHEAZCBX
02 YGSKCJETRMUWNHQXIZFAOVBLDP
03 BERHJYKWCSLNPDZIGFUAOXVQTM
04 JLSGAOPZEMBVQCUIYDTHXRWFKN
05 IPWSURJTOQGEVDBMYKLNHAXZFC
06 CGLXSIBTJHOKNDMQPVRZAYEFUW
07 YGHKDVLQEXUOASZWPJFBCNRITM
08 ACZLSOGEDPYWFXHBVIMUKNTJQR
09 XTHNIBAFEUQSGLJDWOZKMPVCYR
10 MFKGNURPJZTBQWLCASIHVYOXDE
11 NHTEPCFDXRYZBAIMSGVJKUOQWL
12 AHFPGVUKLMNCTSRDEIWZXYQBOJ
13 SAHIKWDQJNPVUTZCBYLOGFMREX
14 GPNWMTOSQHJVYKFEALXCIRDBZU
15 GPCWQOSVZKINJHERUABDTMXLFY
16 NKAELXYVRDOGZIMTFUBSPJQHWC
17 EFTXLBCAWHUJGVOMYRSNKDQIZP
18 ZLNRQBAVYMJUDOTSHXCWGPKIEF
19 YAGDUTFIXMBWLOJQVNERHKSZPC
20 THRAWJEMNFKYZCIGOBXVSULDQP
21 INESDOMTPBQGHYFUZCRVWLKJXA
22 YIRAELHQOSXGCWTPJVZUNFMDKB
23 ITLFAXYCMOPVGZHURDBWNSJQKE
24 QRJGEFWVLKSUHPCXYBMOITNZAD
25 VYGNODPUJEMFCZIXASKBWHRTLQ
26 ANZIFPCLOKMHSJDEWVBYQXTURG
27 NEBZCRMKDPATGLSOWHFIJQVUYX
28 EQJTZFYSINAUBWCVDXRKHPLGMO
29 KDOTRBZWIAUYPLNHEGFQSJMCXV
30 XVSRDIUZFCQTMPLHYEGJAKNWOB
31 MVELIBQAFGJNPCKWXUSTZRDYHO
32 BMOITNEWDAUVPHZJXYSLRQCFGK
33 UYWVFPNHDCRSMZQGXOBTEKLAIJ
34 LBTNMCYODQIKHSFUJEVARPXWGZ
35 NFGUQPSTMCKOXJVWELIABRHYZD
36 CWMFKHPLOVIQXDARBUTEGZJSNY
37 ITOPAJWHEDZKMCVUXBYQSNLRGF
38 EODXLUVTSYHMFGAJNWPZQBCIKR
39 HZACTFNPIXMQRDUBYKVJOGWLES
40 KYFAZHCLPNQGXWDTVBORUJIMSE
41 NSWZTGXHKVBPCORLYQEAIJDFUM
42 XSYLMPKQIZWEANTOVHRDBFUCGJ
43 XYISKJVQMTRCAUNGZEOHFWLBDP
44 KDMEPYHGQZTSUVJFXOILRANBWC
45 GEVKJRNFBXWQPHDOAMTLIZYUCS
46 MZEKBDFIGQTLJPOWUXSHCRNYVA
47 AZLETRUFIPJHBXKOSYQMNGDCVW
48 KNEOJVXFQWCHTDGUMZLYSRAIPB
49 UIROVSWAGEQXTHZCFYLBDJPKMN
50 XBDQIFRUVENLHOAZPWGMKJTCSY
51 BPJZGEVCNTMAOIKHDWSRFUXQLY
52 CXEDARNFZGLSPWKQHTVIUBMOJY
53 IZMLCRNWAKTBUHJSPFOEGYQXDV
54 JOBCRSIAHGZKNYQLDFEPVXWMUT
55 WPCKJMQTZIELARUBSOXFVYHDNG
56 KHVUDGMOJWPYRFSQBLZACITNXE
57 VFIZLTQPMKRACDSOGJXEUNBWYH
58 GFYVTDQLHWJPKMBAZNIUOSCXER
59 QKMSFAZBVPHGWIODEXUCNYJLTR
60 IAPDHNYVFCMOERLUJTQBWSZXKG
61 ARZOWSMPBKJLVDGUIYNXFHCETQ
62 DHOXKZWVTCPBRMGIQALYJFUNES
63 TJFPRHKUWQOMXNIBLYVDZEAGSC
64 ACBZGTPNSJYDVLXRHOWKUEFMQI
65 FPHEOKUXNQMZWIVRTCSGBDLJAY
66 DJABIUXEYQOKRZNSLMPGCTVHFW
67 AIHDGCNLPQOVTKMJFSRZEBUYXW
68 JKULTOCZYWNDBIXHQMPSFGEARV
69 BZJTGQCFKWRPODNLYMSEVHIUAX
70 CQDBVGIZRNJKFLUXAWYTESPMOH
71 TADSIQMURKNHYVXCELWOPZGFJB
72 VSYUFWHJKOBNTIEDRXMLACZPGQ
73 ILCBVHDKSURWXJNFAEYOPQMGZT
74 WHVQOLDZPURMGEXTSFYBAICJKN
75 EZKTAMWIYJQXPLOVBCHNGUDFRS
76 VCLSBQWEDKGTYIFXHARMZUNPJO
77 FYAJDGSOVPRCHQWUNITEBKZLMX
78 BXQWVTCEURIZKAGPNLODFJHMYS
79 MJPKITCUYZSXBOGLADEWVFQNHR
80 IZEXRFDHAGSQNPTVBMLWKOUJCY
81 CTPONKGRMUJWQEYXZVALHIDBFS
82 HVFBTXSJLNAYPZUQOMRGWICKED
83 UCSBJDZOTEIQHARVYNWLPMGKFX
84 LUJHAXCWIRPMVDQNTGBZEFYOKS
85 AHUKMVEPFNBXYCTORQDSIWZGJL
86 XWLNYZGIAKJSURDHMQCETFVPBO
87 VSIJNAXHZLPOQYGRDKMUWFBETC
88 EMWOFAKYTNQZGXJPLVBRCIUDSH
89 RSLIHTMPNJXGOCKDUQFAZYWVBE
90 XCJIGNOKFEHMTADBYWPLSZRUQV
91 AJCKXTMLDWHEZBNYORUIVGPSQF
92 RZEWMCBXITNQLYADSOVGFUPHKJ
93 JMSOVGIPCLYUNDRTFEWQBHXKZA
94 FYCRPOJNHLSKVUBIDMXAEQZTGW
95 UXZRBFIQNYLWDKCHSJTPAVEGMO
96 SRJTMXUZBWGFYDKEVOPAHILQCN
97 QOHEWVDSTAKJIBNXPGCLRYMZFU
98 OKSGRZYCDEWVJPAHXFLIMUNBTQ
99 ULDOMNSRCYGVBPXQWAZJFKEITH

Kommentare (18)

#1 Dave
11. Januar 2014

Die M-138 ist auf jedenfall sicherer als viele Handverfahren, besonders interresant ist auch das man sich diese mit wenig Mitteln einfach selber bauen könnte.

Mal sehen wie lange die M-138 Challenge hält.

Sorry, das ich hier Deutsch schreibe aber mein Englisch ist noch schlechter als mein Deusch 🙂
#2 Bernhard Gruber
22. August 2014

Nur für dieses Beispiel besteht ein Strip nur aus den 26 Buchstaben, richtig? Im Gegensatz zu den originalen Strips mit 2×26 Buchstaben!
- #3 Klaus Schmeh
  22. August 2014
  
  Im Original sind es zweimal 26 Buchstaben, allerdings handelt es sich jeweils um die gleichen Buchstaben (das komplette Alphabet) in der gleichen Reihenfolge.
#4 Dmitry
Russia
4. September 2014

How does one solve this? It seems nearly impossible considering we don’t know the key. And you would have to write a program that tested all combinations of the strips to see if there is recognisable text lining up in any of the other coloumns.
- #5 Klaus Schmeh
  5. September 2014
  
  Challenge 3 indeed seems unsolvable to me. However, there should be ways to break challenges 1 and 2.
#6 Toma Tomov
Neuss
6. September 2014

Ich denke, Teil 3 wäre lösbar, wenn man es stückeweise machen würde (z.B. nach sinnvollen Wort(teilen) in den ersten 6-7 Buchstaben suchen. So eine Brute-Force-Attacke dürfte die verbleibenden möglichen Verschlüsselungen erheblich reduzieren und somit den Rechenaufwand für ein weiteres Vorgehen nach der gleichen Art und Weise verringern oder andere Lösungsansäte möglich machen. Leider fehlt mit die Zeit und die Muße, mich daran zu versuchen…
#7 Nils Kopal
11. September 2014

Hi, we found a “solution” for the third one 😉

73,01,15,66,27,08,85,12,75,98,13,74,90,91,92,55,51,94,35,70,71 / 2

regards,
Nils
- #8 Klaus Schmeh
  11. September 2014
  
  Can you tell us the cleartext?
#9 Nils Kopal
Kassel
19. September 2014

The “solution” which we found is:

HELOXKLAUSTHISISAXMESAGEX

=> Hello Klaus, this is a “message”

with the key shown above.

Unfortunately, the first key elements were cut of 🙁

Here is the key again with linebreaks,

12,30,25,17,73,01,15,66,27,
08,85,12,75,98,13,74,90,91,
92,55,51,94,35,70,71 / 2

Clearly this is not the “correct” solution, isnt it 🙂 ?

As already discussed, with very short ciphertext messages you can generate a huge amount of “cleartext” messages, which all make sense 🙂

Regards,
Nils
- #10 Klaus Schmeh
  19. September 2014
  
  Interesting solution, but not the correct one.
  
  >As already discussed, with very short ciphertext messages
  >you can generate a huge amount of “cleartext” messages, which all make sense
  You’re right. This shows that the method is very secure, if not unbreakable. To make it easier we currently work on a new version of the challenge.
#11 Dario
19. September 2014

> The “solution” which we found is:
> HELOXKLAUSTHISISAXMESAGEX
> Here is the key again with linebreaks,
12,30,25,17,73,01,15,66,27, 08,85,12,75,98,13,74,90,91, 92,55,51,94,35,70,71 / 2

Sorry, this is not a valid solution because you are using strip number 12 twice, at positions 1 and 12. Another problem is that you are using strip 25 at position 3 as if it had two alphabets printed on it: the plaintext L is to the right of the ciphertext, so, to have it on the left, we have to imagine that it is on another copy af the alphabet, as in the original M138; however, Klaus’ fictive model has only one copy of the alphabet per strip.

A valid solution for the same message which only uses one alphabet per strip is the following:

41, 0, 19, 55, 82, 24, 23, 14, 44, 37, 40, 50, 70, 58, 32, 10, 97, 3, 16, 7, 27, 9, 15, 34, 33 / 4

Dario
#12 Nils Kopal
Kassel
19. September 2014

Yeah, i copied some wrong stripes 🙂 You have to look carefully, thx. Since you have several “equivalent” stripes and I did not automize the “unique” selection yet, i made some errors.

But there are several thousands of equivalent keys… so challenge 3 is definetily not solvable 🙂
#13 Nils Kopal
19. September 2014

> Another problem is that you are using strip 25 at position 3
> as if it had two alphabets printed on it: the plaintext L is to the
> right of the ciphertext, so, to have it on the left, we have to
> imagine that it is on another copy af the alphabet, as in the
> original M138; however, Klaus’ fictive model has only one
> copy of the alphabet per strip.

I thought that Klaus` Model uses the same procedure: alphabet 2 times printed on a stripe.
On Klaus` example figures, there are all alphabets printed two times. Otherwise, an attack would be much easier since you can cut off possible slides. In my implementation i used the offset modular 26. Thus, if i run “out” of a stripe, i just go in on the left side.

@Klaus: You use stripes with 2x the same alphabet printed on it? I think the stripes (as printed only with 26 letters 1 alphabet) are printed in this way to “save” space 🙂 ?
#14 Dario
19. September 2014

Elaborating on my previous comment, I notice that to have one alphabet per strip has two bad consequences: first, not all messages can be encoded with a given key (suppose your key’s first strip is number 00: there is no way to encode a message starting with that strip’s last letter, “H”); second, it reduces the amount of possible solutions and makes the system easier to break.

I have experimented a little devising messages and trying to find keys which encode those messages to challenge part 3. It is extremely easy, but it taught me a lot.

1) First, no plaintext letter can be equal to the ciphertext letter in the same position, because the distance has to be at least 1. This is true for the original M138, too. It’s the weakest point of the system: the distance must be the same (and nonzero) on all strips. Of course, this didn’t help much in real-life situations where the letter permutations on individual strips were unknown, but it does help us a lot with Klaus’s model.

2) In practice, there are so many strips, that for any tentative solution, for any tentative distance, for any position from first to 25th, there will be an average of three/four possible strips. However, most distances will be impossible because there will be positions where no strip can be used, or pairs of positions where only the same strip can be used for both (as in Nils’s solution above), or similar problems with larger sets of positions. There will be one of two distances however, where no such problems occur and you can find a solution.

A practical example: you have intercepted challenge part 3 as an enemy message and decoded it with the key
18, 28, 65, 45, 12, 2, 23, 1, 4, 27, 7, 9, 50, 60, 32, 0, 36, 24, 44, 51, 53, 61, 79, 8, 29 / 2

So you have your plaintext “WE WILL ATTACK MONDAY AT SEVEN” and prepare your defenses. You have no luck. The real
key was

18, 28, 65, 45, 12, 2, 23, 1, 4, 27, 7, 9, 16, 49, 32, 0, 36, 24, 44, 51, 53, 61, 79, 8, 29 / 2

and the real message was “WE WILL ATTACK SUNDAY AT SEVEN”. The enemy attacks one day before, you are totally unprepared, and you lose.

This is what “unbreakable code” means.

Have a good weekend
Dario
#15 Dario
19. September 2014

@Nils
>I thought that Klaus` Model uses the same procedure: alphabet 2 times printed on a stripe.

Well, above here is Bernhard Gruber’s German-language comment about that. Klaus answered that twice 26 letters were printed on the original strips, but at this point it is not clear to me if solutions modulo 26 are acceptable for this challenge or not. It would be great if this point was made clear in the revised challenge.

Bye
Dario
#16 Klaus Schmeh
20. September 2014

@Dario, Nils: All strips of the M-138 contain the alphabet twice, in the same order. In the strip list given here I omitted the second part, as it is redundant. Using the second part is equivalent to a modulo addition on a strip.
#17 Dan Girard
6. Oktober 2014

There’s something I’ve been wondering about. Did you purposely make the challenge messages so short in order to make automated computer attacks like hillclimbing ineffective, being more interested in techniques that would have been available to World War II codebreakers?

The reason I ask is that I’ve been working on a hillclimber to try to break message 1, but although it is able to break test messages of about 125 letters or more, and can occasionally get a partial solution for messages of 100 letters, it can’t get even a partial solution if the message is only 75 letters. It seems that when each of the 25 strips is used only three times, the n-gram statistics don’t give enough information to distinguish a wrong alignment of strips from the right one.

I think one simple way to make the challenges easier would be to just make the messages longer.

Regards,

Dan
- #18 Klaus Schmeh
  6. Oktober 2014
  
  >Did you purposely make the challenge messages so short
  No, certainly not. My intention was to make one of the challenges really hard, if not unsolvable, but the others were planned to be a lot easier. I thought a 25, a 50 and a 75 letter message would be ideal for this purpose. Maybe I was a little too optimistic. If this turns out to be the case we will certainly take you advice and take longer messages.

How the M-138 worked