Sunday, January 24, 2016

WW2 Ciphers Part 2: On teamwork and the little mistakes that made the difference

Before I move forward with explaining Tunny and the German ciphers, I'm going to take a few minutes and explain at the highest level how they failed. I'm also going to mention one difference I have with Hollywood's recent portrayal of Alan Turing in The Imitation Game.

The movie portrays Turing as socially hostile, fighting against his coworkers and the British Government who had little belief in his work. That is not what happened. Bletchley Park cracked those codes through the determined efforts of hundreds of people, it was an incredible story of team work, not hostility. And it was fully backed by the British Government at the highest levels, and why wouldn't they back it, because early Enigma ciphers had been cracked before World War II even started.

The German Government continued to tinker with the machines, making them more complicated as the war dragged on. The British would crack the codes for a while, and then they would hit a dry patch for a few months with little success before reestablishing a new method. Sometimes they would only crack a few messages a day, sometimes they had wide success. As the Germans continued to add rotors eventually the Colossus machine (featured prominently in the movie) became more and more necessary to assist the scores of young women "computers" that every day followed the mathematical scripts to decode messages.

Both Enigma and Tunny were incredibly powerful ciphers and should have provided enough protection, it was the little mistakes of the hundreds (or thousands) of daily users of those machines that provided the keys to cracking it. The following are some of the failures that enabled the code breakers.

·        The short weather reports were rather easy to guess and allowed the code breakers to propose a starting message and find a key that would match the output. Senders were instructed to not follow forms and to switch up these types of messages but they didn't do so often enough.

·        Each message was sent with a daily key, and an added message key that kept all of the day's messages from being encoded exactly the same way. If users choose the same message key, or reused their own message key it would lead to multiple messages being coded the same. In one of my later posts I'm going to show how you can crack those examples.

·        Sending the exact same message in different ciphers was a different problem. Sometimes an important message would be transmitted verbatim in Enigma or Tunny, and also in a really simple field cipher for those who didn't have an enigma machine. The field ciphers were so easy to crack that they could find the original message and then use that to find the key for the complex ciphers. Once they had the daily key for the complex cipher they could crack hundreds of other messages.

·        Messages were often personally addressed to the main Generals. The code breakers would look for that General's name in the message.

·        When they were in really dire straits, the British would go fishing for the small German weather monitoring boats that had only a couple sailors and an enigma machine. They successfully captured several along with the daily code keys for a month's worth of messages. They successfully did this several times.

·        The information to crack Tunny mostly came from one really intriguing message. In August of 1940 a huge message (4,000) characters was sent with Tunny. But the receiving end didn't get it correctly. They broadcast and unencrypted request for the message to be resent which told the allies what was happening. The sender should have changed the public part of the key before resending but they didn't which left it coded the exact same way. The second problem was that it was almost impossible to exactly key in the 4,000 characters the same way, and the sender used an abbreviation early in the message that offset the twomessages by a few characters. Out of this one small window the British teased out a huge amount of the underlying pseudo-random data used for the enciphering.

I hope you found that interesting, it was a lot more history then the examples of what I'm doing with my example program. Next post we will get back into the program and how it uses exclusive-or arithmetic.

Thursday, January 21, 2016

Encryption in World War 2: The Wheelset


Have you ever wondered how some of the German WWII ciphers worked? After reading a couple books on the subject I decided to write an encryption program based on the spirit of the WWII Tunny (fish) ciphers. This is modern interpretation based on the German Lorenz cipher machine, and I primarily did this to teach myself more about the process.


Tunny was a binary cipher, all input was converted to ones and zeros. It was also transmitted (in binary) using electronic machines. There were no human radio operators for Tunny which was unlike Enigma which was not binary and was transmitted by radio operators sending alphabetic characters.

Today's post is an introduction to the wheels and setting up a wheelset. The German machines had a series of wheels that rotated. Each wheel was covered with random bits, and that random data was combined with the letters producing encrypted messages. Each time a letter was enciphered one or more wheels changed locations which changed the random data.

Here is a simple two wheel example. Wheel A is set in location 2 which has a value of 149. Wheel B is set in location 4 which has a value of 203. As the wheels turn in a virtual way they change locations providing a combination of pseudo-random values.

Loc
Wheel A
Loc
Wheel B
0
93
0
11
1
27
1
41
->
2
149
2
165
3
161
3
76
4
30
->
4
203
5
89
6
54

 

A good question that I pondered was how many wheels to have. This is primarily for teaching, so I didn't feel like I need 12 wheels. The starting location of the wheels is a type of message key for the cipher. So it's useful to look at an example of how the number of wheels affects the strength of the message cipher.

Let's say that we have 120 numbers to partition out amongst an undecided number of wheels. If we created two wheels each one could have 60 numbers, if three wheels each could have 40 and so on. Below I built a table showing the number of possible starting key combinations for some example setups.

Number of wheels
Size of wheel
Key Combinations
1
120
120
2
60
3,600
3
40
64,000
4
30
810,000
5
24
7,962,624
10
12
61,917,364,224
20
6
3.65616E+15
60
2
1.15292E+18

 

As you can see, even though we cap the total numbers, choosing a higher number of wheels significantly increases the complexity of your key. For this example program I decided that 4 wheels would provide enough complexity to give some good examples. If I was a little more serious I would increase the wheel count to 8 and the number count to something larger like 240. Even then my program would not have a very powerful key, the security of the program would be less in the key, and more in the wheelset. As long as no one got the 240 numbers in your wheelset you would be relatively safe sending a lot of short messages.

With the original machine, the wheels were physical and had to be replaced to introduce a new set of random values, but with my program I can readily regenerate the wheelset when needed. But remember that both parties need to securely exchange the wheelset before they start sending messages.

Below is an example of the program. Notice that there are 4 wheels in the Daily Wheel Key. Each day all participants would set the starting value to a predetermined setting. Notice that this method requires the users to share keys and the wheels before they go their separate ways and start sending messages. In WWII there were hundreds of navel vessels and army outposts that all had matching codebooks with daily keys that had to be kept safe or the messages would be at risk.


Things to Try:

  • Enter a message and encrypt it. Copy the xml output to the input field and decrypt.
  • Change a key setting when decrypting and verify that you can't decrypt if the settings have changed.
  • Encrypt the message "pppppp" and notice that each letter translates to a completely different number. This is not a cryptogram where all letters map to the same thing.

Friday, January 1, 2016

All Books Review - 2015

Last years review of every book I read was seen by at least 5 people. I feel compelled by my past success to keep up the tradition.

Fiction

The Martian by Andy Weir - Exciting and funny. It reminds of Nel Stephenson or Michael Crighton in the scientific technical delight of the author.

All The Light We Cannot See by Anthony Doerr - How can one book contain so many characters that I care deeply about? Marie-Laure goes blind while every loss seems matched by a discovery of the world around her. Werner escapes poverty but loses himself in the Nazi’s. Frederick stands out unique to his core, and is brutally crushed for it. Etienne overcomes the demons of an older war and finds a reason to live again.

Life After Life by Kate Atkinson - Early on I struggled to understand the rules of this reincarnation tale. Then I got caught up in it and the nuanced portrait of Ursula’s family as you see them over and over. But in the end it fell flat. Ursala lives her life in a loop of minor (and major) variation, but do any of them make an impact?

Open City - A book of deep and philosophical boredom. Julius goes on long walks and thinks about stuff. About half way though you start hoping for an alien invasion, or maybe Julius could decide to hike Mount Kilimanjaro, or join a fight club, anything really.

Non-Fiction

Inside Box 1663 by Eleanor Jette - I bought this at the Los Alamos bookstore, it's a great little book about life for the families working on the manhattan project. Sometimes locally published books can be amazing.

Seizing the Enigma: The Race to Break the German U-boat Codes, 1933-1945 - Highly recommended if you like encryption and war books.

Code Breakers: The inside story of bletchley park - Each chapter is written by a different author about their experience cracking German and Japanese codes. It’s a great book, and shows the wide variety of people working on the project and how isolated some of their jobs were.

The Moffat Line: David Moffat’s Railroad Over and Under the Continental Divide - I really wanted this to be good, but sometimes locally published books can lack a coherent story.

River of Doubt - Theodore Roosevelt’s Darkest Journey by Candice Millard - There was  interesting material in this book, but there are other Roosevelt books to read first.