Thursday, August 4, 2016

My ride accross Colorado



I’ve been thinking of doing a multi stage bike ride for probably eight years. A couple times I even progressed to the planning stage and had a route picked out. But something always came up and I kept thinking no hurry, I’ll do it in the next couple of years. But after years of saying that I was still “a couple years” out.

Last year Britta and I were talking about how quickly time flies after you have kids. We talked about some goals we had and resolved to do some of them (it’s a favorite topic of Britta’s, they hammer in goal setting early in the Monson family). I didn’t immediately decide to do the ride, but the idea kept coming back until suddenly I found myself looking at maps and planning a route.

I like that cycling slows you down and lets you experience the country you are going through. There are so many things you don’t see when you moving in a car, and even on this ride I have tried to plan it so that I wasn’t in a rush. It has been an experience to savor. I also appreciate the opportunity, the good health, and the support of family, things which should not be taken for granted.


One of my goals with this ride is to raise money for the Jason Timmerman Memorial Scholarship. This scholarship is for a Math Education major and is in honor of my friend who died in Iraq. Jason and I were in many of the same clubs and activities at college. We both tutored math at Dakota State University. It’s a small college and most of the time there were only a couple of us tutoring at a time.

I’m very grateful for both an education, and the scholarship that helped me pay for it. If you have enjoyed following my ride I hope you will consider donating to the scholarship. It’s for a very good cause.

How to donate to the Jason Timmerman Memorial Scholarship

 You can donate with a check made out to the Dakota State University Foundation. Put “Jason Timmerman Memorial Scholarship” in the memo.

 To donate online there are two steps you need to take to enter the Jason Timmerman fund.


 There is a “Select a Fund” drop down where you select “Annual Academic Scholarships”.
 Then in the “Scholarship Designation” field enter “Jason Timmerman Memorial Scholarship”.

Tuesday, February 2, 2016

WW2 Ciphers Part 3: Using A Daily Key



In the example above I used a daily key of {0,2,5,2}. At least one virtual wheel will turn each time a letter is ciphered, and that will produce a completely different wheel cipher byte. The table below shows what this looks like. The wheel cipher changes every letter.

Wheel Setting {0,2,5,2}
Plain text (Ascii)
Wheel Cipher
Cipher Text
69
135
194
108
172
192
32
185
153
77
215
154
97
237
140
99
151
244
104
57
81
111
171
196


Input
Output
A
B
A φ B
0
1
1
1
0
1
1
1
0
0
0
0

The principle of reciprocity is important, you can change the order of A and B and get the same results, the process of encrypting and decrypting is mathematically the same for this cipher. To encrypt we take plain text φ key = cipher text. Because of reciprocity we decipher by the formula key φ cipher text = plain text. You could even compute the key from the cipher text and plain text (plain text φ cipher text = key). The Tunny machine was completely cracked years before they even saw the machine or the wheels. A library of cipher texts and plain texts eventually allowed the code breakers to recreate the key sight unseen.

It's important to use a different wheel setting for each message. I know from my readings that messages which overlapped on the wheel settings were a key source when breaking the encryption. I figured I would have the most fun illustrating that concept by trying to break my own codes, so that will be the next post. I am working on a basic program for cracking using letter frequencies and I think it shows promise. Understanding this weakness will lead us to talk about the shortcoming of the daily key and why each message had an additional random message key.

Things to Try:

2. Try this online XOR (exclusive-or) calculator.

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.