Building and using a Paper Enigma

Leave a comment

img_20161130_122120

As part of the book about cryptography, math and programming I’m writing, I’m encouraging readers to assemble their own paper Enigma machine. Since it’s pretty involved, I thought I’d write an illustrated blog post about doing it. I’m going to start with a summary of the context of the Enigma – and as a summary, I’ll gloss over some likely-important stuff, and also probably get some things a bit wrong. Corrections are welcome, of course. So, here we go!

First, the whole idea of making a paper replica of the Enigma came from the amazing Alan Turing, the British mathematician who is the topic of a decent movie, a great book, and is generally credited as being a pioneer of computers, artificial intelligence, and for shortening World War II by two years (and dare I say, perhaps keeping the Nazi’s from winning?) The story isn’t all rosy: he was also gay at a time in the U.K. when that was a punishable crime, and he eventually killed himself due to his treatment by the government. It wasn’t until 2013 that the Queen pardoned and thanked him for his service. As Martin Luther King Jr. said, “The arc of the moral universe is long, but it bends towards justice.” That’s certainly true in this case.

Thinking back to World War II, the German military was kicking butt all over Europe, and their submarines were causing  all sorts of mayhem in the Atlantic. They were able to securely communicate across vast distances by sending radio messages that were encrypted with an Enigma machine. This meant that the Allies could hear their messages, but couldn’t understand them, because they didn’t have the key used to decode them. Polish mathematicians cracked the Enigma code in 1932, taking advantage of a subtle misconfiguration of how the Germans used the machines. By 1938, Germany fixed this flaw, and was able to send secure communications again.

One of the first things Turing did at Bletchley Park was to create a model of the Enigma machine using comic strips. Our paper Enigma, from Franklin Heath (a security firm in the UK), was inspired by his work. The first thing you’ll need is the PDF of the paper Enigma. Since paper in the US isn’t the same shape as in the UK (A4), I had good luck printing it on legal sized paper (11×14 inches). The kit is designed to be wrapped around a cardboard tube that is 75mm in diameter. It turns out a Pringles potato chip can has this diameter (they’re called “crisp tubes” in Britain). I didn’t want to buy Pringles, so I used a cereal box. Here’s my setup before assembly:

img_20161128_160503

Cardboard usually has a way it “likes” to be curled, and one that it resists (creases rather than curls). For this box, the preferred curl is horizontal. So I cut off the tabs at the top and bottom of the box, and curled it by hand a few times, to get the cardboard roughly in the right shape:

img_20161128_161820

Then cut out two of the strips (I chose the input/output strip and the Reflector B), and carefully tape them into bands, put the bands on both ends of the tube, and let it expand, like this:

img_20161128_161914

At this point, I put little tabs of tape inside the tube to help it hold its diameter, and fiddled with it until the bands were able to slide, but also didn’t have any slack. I tacked down the tube with a little tape, and pulled off the bands, then added a full-tube-length of packing tape to the outside-seam, like this:

img_20161128_162454

Finally, wrap the three “rotor” bands around the tube, and tape them, again checking that they can slide around the tube, without being too tight. With the three bands on, add the Input/Output and Reflector B band to the outside-ends of the tubes. Align the grey bars on these bands, and tape them to the tube: they stay put while the rotors move. When you’re done, from left to right, you’ll have the Reflector, Rotor I, Rotor II, Rotor III, then the I/O band. It should look something like this:

img_20161128_164439

Using your paper Enigma

(borrowing heavily from the Franklin Heath wiki – I will rewrite this with my own examples once the book chapter is done)

You can test your basic Enigma now. The “rotor position” part of the key is the letters between the grey bars. In the setup above, the rotor key is FAN. The next aspect of the machine is that each time you encode a character, you first “advance” the rotor, by carefully twisting its band towards you by one letter. Let’s pretend that the key was FAM, and we rotated the right band to make the rotor position FAN. After doing that, take the letter you’re encoding, and locate it on the I/O band on the right, and trace the lines from right to left. In this case, it’s nearly a straight line: A -> N -> A -> G at this point, we’re at the “reflector”, so trace the line on the reflector to see where it leads. It should be W. From there, trace the line back to the I/O band. When I did this, I got W -> I -> S -> K. K is the encrypted version of A. To encrypt the next character, you advance the right ring towards you and repeat the procedure.

With what you know so far, you should be able to decrypt the following message, with the rotors initially set at A B C:

A E F A E  J X X B N  X Y J T Y

If you get that, the rest of the Enigma is just minor tweaks to that process. We’ll go through each of them, because you need to do them all in order to decrypt real Enigma messages (which we’ll do at the end).

Advancing the Rotors

As you advance the right-most ring, eventually you’ll come back to the original configuration. If the Enigma did nothing else, it would be not too different from the Vigenère cipher – not a bad cipher (it was used during the Civil War) – but definitely not strong enough to protect against the codebreakers of the 1900’s. The next (and primary) advance of the Enigma machines was its rotor stepping process. When you are about to advance a band, look at whether the letters are grey in the line between the grey bars on the reflector and I/O bands, and

  • if the letter on the middle rotor is shaded grey, turn all three rotors one step towards you,
  • otherwise, if the letter on the right-hand rotor is shaded grey, turn the middle and right-hand rotors one step towards you,
  • otherwise, turn just the right-hand rotor one step towards you (this is the normal action).

Now the configuration won’t repeat for 26 * 26 * 26 (= 17,576) steps – much better.

To make sure you get it, here are some rotor  position scenarios. When you’re about to rotate, and the rotors are in positions:

  • F A V, because V is grey, you would advance both the right-hand and middle rotors toward you, resulting in position F B W
  • F E W, because E is gray, you advance all three rotors, resulting in G F X
  • G F X, because none of them are grey, only rotate the right-hand rotor, resulting in G F Y

Test your procedure by setting the rotors to A B R, and decrypt the message
M A B E K  G Z X S G

Double-stepping

One tweak to the above procedure (which is, so far, just like a car’s odometer), is that if, after you follow the above procedure, the middle rotor’s grey bar enters the start position, then all three rotors step again. I’m not sure if this is critical to the strength of the Enigma, but doing so is critical to compatibility with real Enigma machines.

You can test whether you understand this part by starting in position B F C, and decoding
R Z F O G  F Y H P L

Rings – changing the turnover points

The next-to-last feature of the Enigma is that which rotor positions trigger turnover could be adjusted. In the real machine, this was done by removing the rotor and moving a pin from one position to another. In our paper Enigma, it’s done by sliding rings over each of the rotors. Each ring covers up the letters underneath it, and its position determines a different configuration of the machine (is part of the message key). Ring positions are described by the position of the ring’s letter A with respect to the letter it covers. Position 1 means that the ring’s A covers the rotor’s letter A, 2 means A covers B, etc. For convenience, here’s a list of which ring letter A needs to cover for each ring setting.

Setting 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Ring A  A B C D E F G H I J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
 covers

Test whether you’ve got this by setting ring’s I, II and II to 10, 14 and 21. Then turn the rotors to set the message key (on the rings) to X Y Z  and decipher the following message:

Q K T P E  B Z I U K
Advertisements

Crypto-treasure hunt birthday party: a great success!

Leave a comment

I was surprised to hear Audra wanted “codebreaking” to be the theme of her party this year. Maybe she missed math circle, or maybe there’s cryptography in the air, maybe she knew it would bring Dad even more into the party preparation than normal (last year’s Pirate Party was also

a hoot to design).

Codebreaking is pretty abstract, so I knew we’d need something to drive the activity.  Treasure hunts are always fun (for parents and kids), so that seemed a natural combination. Over the days before the party, I thought of the collection of codes and activities we could put together. I knew it would be great to send kids home with something to remember the party by, so I designed a “secret agent ID badge”, and a “Top Secret Code Breakers Manual”. [pdf link]
Sally Browning, one of my friends and colleagues at Galois, had prepared a codebreaking tutorial for some visiting middle-schoolers, and as part of that, she prepared a “scytale” (sounds like s + “Italy”) activity – a bunch of dowels with different diameters, with ribbons to wrap around.  Heidi had found a simple substitution cypher for the invitation (some of our great attendees replied in code — I love it!)  And from there, I pretty much had a template for the activity.
The party started at 1:00. I started working on the final treasure hunt at 8 AM that morning. I finished just in time (!). All told, I think I spent 8 hours working on the treasure hunt activities. As often as possible, I tried to make the activities parallelizable among the 10 guests…this worked mostly, and it was definitely obvious when there was a one-person bottleneck to an activity.
Heidi and I agreed that we’d try to keep the tenor of help provided along the lines of “math circle”, which is pretty much hands-off, but perhaps with a few Socratic questions thrown in to accelerate things if needed.
Here’s the sequence of the treasure hunt:
Audra took a photo of each guest as they arrived.

  • We put out puzzles and thinking-activities from our “games and puzzles drawer out for people to play with as the party gathered. We also left out a set of the “code books”.
  • When everyone assembled, we said “instead of a cake, all we have here is this empty-feeling box”.  Inside the box were two ribbons with letters on them. The kids figured out that dowels would be needed, and thought of wrapping the ribbons around chair legs or other cylinders around the house…not noticing the pile of 10 dowels against a wall.  Eventually, the dowels were discovered, and one ribbon got decoded on the first try — what are the odds?  It took a lot more work to decode the second ribbon. Between the two ribbons, the message was “I have hidden your stuff in a secret location. You will find help where les oeufs are produced.” The two French dictionaries were sitting next to where the empty box started ended up helping out.  “The Chicken coop!” and they were off.
  • Inside the coop was a plastic egg with two smaller eggs nested. In that was a tiny USB thumb drive. I created a bunch of directories (A-Z) and a “readme.txt”.  The file said “Look in directory “D” for the next clue”. Inside directory D were another set of directories A-Z, and a readme.txt that said “What “are” you looking for”.  Inside directory “R” was another readme.txt: “what are “you” looking for, again?”.  Inside directory “U” were more directories, and a readme.txt: “mmmmmmmmmmm…I love cake.” Finally, inside directory “M” was a file that said “you’ve found the right place.”
  • The innermost directory (note the path was “D/R/U/M”) had a text file with morse code spelling out “The next clue is hidden inside an instrument you hit with your hands.” as well as an .mp3 file with morse code spelling out “DRUM”. I used this web site to generate the two files. The cryptographers broke into two groups, one group tried to decode the audio, the other asked me to print out the morse code for them to decode.  Even though I slowed the morse code audio way down, that team finally switched to decoding the text as well. Nobody noticed the path spelled out DRUM. Interesting!
  • Inside the drum was an envelope with a bunch of slips of paper in the original transposition code (I wrote a python program to generate this… see the bottom of this post). I wanted to allow this task to be parallelized, so I wanted to chop up the message into bits, and then added numbers so they’d know which order they went in. The slips decoded to the text “ONE LOOK”, “TWO UNDER”, “THREE THE THING”, “FOUR THAT HANGS”, “FIVE ON ROPE”, “SIX FROM A”, “SEVEN TREE AND”, “EIGHT CHILDREN”, “NINE PLAY ON”, “TEN FOR FUN”.  They quite quickly decoded the individual strips, but had a dickens of a time figuring out the ordering of the slips. They were thinking the numbers were another level of code, or were part of the message, or formed a more complex pattern (like 2 4 6 8 …).  Finally, they got them all on the floor at once, and with a little Socratic questioning help, they figured it out. “The Swing!”
  • Under the swing was an envelope with what caused the funniest moment of the party (for me, anyway). I wrote “Hermione shows up with fancy hair and a dress.” With no time at all, the rushed into the house, grabbed the single volume (book four) of the Harry Potter series, and took about 30 seconds to find the right chapter. On that page was another slip of paper, this time with another book title, and a math problem (110 * 3 – 10).  And so on for eight books. The last slip of paper was in an art book, on the page about Miro. They discarded the book before noticing the slip of paper said “look behind a painting that looks like this one.” They dug it back out, found the page, and behind the painting was another envelope, holding a paper saying “four legs eats here”.

“Cat bowl!” Under the cat bowl were two more scytale ribbons “Oh, no, not more?!?!”.  They were getting hungry for cake.  The scytale ribbons had a little-bit-too obscure clue (I think I was getting tired at this point in the puzzle-making process): Ribbon one: “Your next clue is hidden inside a musical instrument on the West wall of the house” and “If you go to Hawaii you will hear my strings”. It took way too long to find the Ukelele on the West wall of the house. I was busy upstairs laminating the ID cards, but heard the excitement of finding a slip of paper with the URL http://www.cheapimpostor.com/mecodegoodsomeday/secretCode. Heidi says she had to help them with the typing – theirs was too error-prone to get it right.

  • They recognized bits of the car, and my car-key’s bike-chain keyring. They finally found the cake in the trunk…but no goodie bags!  Fortunately, the icing had morse code (“Not again!”) that said “look under the bed” which is where they found their goodie bags.

Heidi heard more than one guest say “this is the best birthday party ever!” which blew me away, but totally reinforced the theme of a book I’ve been reading (

A Theory of Fun for Game Design, by Ralph Koster), which is that real “Fun” comes from the excitement of actually learning something new.

All told, it took 2.5 hours to solve the clues, and they just got to the cake as parents arrived to pick them up. It was an exhausting, but very rewarding, party.
As an aside, here’s the shell script I used to create the maze-on-thumbdrive (watch out – it’s slow, and the result takes up a lot of space!):
#!/bin/sh
export digits=”A B C D E F G H I J K L M N O P Q R S T U V W X Y Z”
for i  in $digits; do
mkdir $i
cd $i
cp /tmp/readme.txt .
        for j in $digits; do
                mkdir $j
cd $j
cp /tmp/readme.txt .
        for k in $digits; do
mkdir $k
cd $k
cp /tmp/readme.txt .
        for l in $digits; do
mkdir $l
cd $l
cp /tmp/readme.txt .
cd ..
done
cd ..
done
cd ..
        done
cd ..
done

Read and post comments | Send to a friend