A Crash Course in Cryptography Part I – A History of Cryptography
Welcome Ladies and Gentlemen to A Crash Course in Cryptography. The words of importance here are “A Crash Course”. This will not be a terribly advanced course, it’s designed to introduce people to some of the concepts and methodologies used in Cryptography. There will be some technical talk but mostly the conversation will be focused at the conceptual aspects. Today’s class specifically will be aimed at getting people familiar with terms used in cryptography. We will also be explaining why cryptography is important both now and in the past.
A lot of this tutorial will be stories of various cryptographic tales. Much of what I’ll be talking about can be found in many books, specifically on the subject of the Enigma machine. One book I’ll specifically be focusing on is The Code Book by Simon Singh. A lot of the material can be further read about in this excellent book.
What is Cryptography?
Well here it is, the most important part of cryptography, defining it! So… what is cryptography? let’s see what the dictionary has to say:
1.the science or study of the techniques of secret writing, esp. code and cipher systems, methods, and the like.Compare cryptanalysis (def. 2).
2.the procedures, processes, methods, etc., of making and using secret writing, as codes or ciphers.
3.anything written in a secret code, cipher, or the like.
Cryptography is the product of two Greek words “kryptos” meaning hidden and “graphein” meaning to write. Why Greek? Well a Greek, Herodotus, was the first person to really mention cryptography and sited it as the reason they weren’t captured by Xerxes (King of the Persians). That pretty much covers it but let’s maybe make a little more sense of that.
Cryptography is the art of concealing information by obscuring it. This can be done in a number of ways but the important thing to remember is that it works on information. For instance a text document can be encrypted, but a lamp can’t.
Another related term is Steganography which is just the art of concealment. This doesn’t attempt to obscure the data but rather hide it. This could be as simple as the age old “lemon juice writing trick”. What is that? you take a piece of paper a little on the firm side. For instance you can’t use a piece of notebook paper it’s just too thin. Take a lemon or some lemon juice (not lemonade…) and a paintbrush, then using the juice write your message on the paper.
The juice will dry and become invisible. This is why it’s important to use a thick piece of paper, a thin piece will just become… bumpy from the moisture and your message will be visible. When the receiving party gets the paper they will hold it over a heat source, typically a candle, and the sugar from the lemon juice will caramelize causing the words to appear in brown on the paper.
Another distinction we need to make is that between cryptography and encoding. The purpose of encryption is to obscure the data, make it hard to get the plain text back. Encoding on the other hand just changes the representation of data. Encoding does not attempt to hide the data. Two common examples of Encoding are ASCII and Base64. These two methods allow information to be represented in another way.
All encryption is basted on a key. The key space is how many keys are possible. With computers this is usually represented in bits as all computation is binary. An easy way to figure out the key space is to use simple math. Say you have a 128 bit key (considered the minimum for secure communications) then it’s quite easy 128^2 or 340 tredecillion (34 followed by 43 0’s). If you could try 1 trillion keys every second it would take you 2 pentillion years to exhaust the key space.
However, don’t let this give you a false sense of security. A key is only as strong as it’s implementation. As any security professional will tell you, that while the UID (user ID) and password combination is the most popular, it’s the least secure. A password scheme is only is powerful as the password used. If you use 4096 bit key space, but pick “a” as your password guess how long it will take to brute force.
Another thing to keep in mind is the implementation of the cipher (that is, the encoding mechanism or algorithm). A now famous example is WEP or Wired Equivalent Privacy used in many wireless installations. WEP is capable of using 128 bit keys, technically 104 since 24 are use for the initialization vector (IV).
WEP is based on the RC4 cipher which is a stream symmetric cipher (don’t worry if you don’t understand all that now, you will). While this cipher is quite secure the problem is with the implementation, specifically that 24 bit IV which only gives you roughly 6 million possibilities. Thus your 2 pentillion years becomes something like 10 minutes (more information). If you’re still using WEP upgrade to WPA(2)… now! Stop reading this and update your settings, this tutorial isn’t going anywhere.
I just used the term symmetric, which has obvious geometry implications, but what does it mean for encryption? Well there are two fields of encryption, symmetric, and asymmetric. These often go by other names as well. For instance symmetric is also known as “secret key” or “private key” though not as often as it can be confusing. Asymmetric ciphers are also commonly called “public key”. The reason that some people shy from using the term “private key” for symmetric ciphers is that public key encryption uses a private key which can confuse some people.
What does this all mean? Symmetric ciphers rely upon one shared secret. Something that only 2 or more entities knows. This is the key. This is the most common form of encryption. There’s one major flaw with this system though that some of you might have picked up on. Say the two, or more, entities are located at geologically distant places? How does one get the secret key to the other without someone intercepting it along the way?
There’s a number options here, the most common, of course, is using key escrow, but then you still have to trust a third party. To over come this limitation was the dream of many cryptographers and mathematicians alike, though the line drawn between the two is often very vague. Enter the asymmetric cipher. Asymmetric ciphers use properties of mathematics allowing them to create two keys. One, the private key, is used for decryption (or creation of digital signatures) and the other, a public key, for encryption (or verification of digital signatures).
These are just the basics of the two methods of encryption which will be covered in much more detail in the next two parts of this series: Symmetric and Asymmetric ciphers. Now that we have some of the basics of cryptography down I’d like to spend the rest of the lesson discussing two historical applications of cryptography.
Mary Queen of Scots
The first story has to do with someone many of you have probably heard of, Mary the Queen of Scots. For those of you whom don’t know who she was, she was the
Queen of Scotland from 1542 to 1567. As a Catholic she was forced to abdicate in favor of her son and fled to England where she was imprisoned by Elizabeth I. When Catholic supporters plotted to put her on the English throne she was tried and executed for sedition.
The part we’re going to be focusing on is the plotting aspects. A quick little bit of history first. Mary was the Queen of Scotland when she was 2 weeks old, being formally crowned at the age of 9. She married a French guy, he died. She married another guy (her cousin) who gave her a son, but he was an ass so she (or the nobles) had him killed. Married another guy but ends up imprisoned shortly thereafter. After an attempt to retake the thrown things got even worse for her so she runs alway to England hoping her cousin (Queen Elizabeth I) will help her out, upon arriving she’s imprisoned. She spends the rest of her life in jail.
See, Elizabeth was afraid that she would try and steal the crown from her since the Catholics in England didn’t recognize Elizabeth as the queen considering her a bastard child and having no claim to the thrown and poor Mary was next in line. So, she’s chillin’ in jail for awhile, no correspondence then one day this dude hooks her up with a bunch of letters. How did they get them to her? by hiding them in a barrel that was used to seal some alcohol. In a classic example of steganography.
Now it so happened that this one guy wanted to get her the hell out of jail and get her on the thrown. Him and a couple of his friends were going to bust her out. You can’t just charge into jail and hope to come out alive so they needed to do some plotting. They were already pretty successful with the stego approach, nobody had caught them yet, but for some added protection they encoded the messages as well. A simple alphabet was constructed of symbols and a couple code words, 4 nulls and one dowbleth (doubles the previous char).
Remember, encoding offers no real protection. He’s the catch though, that guy that was the hook up transferring the barrels was actually a double agent. He would make a stop along the way and they would make a copy of the message and then a smart guy did a regular old frequency analysis, to be covered in the next installment.
The guy doing the cryptanalysis was so good that even after they had all the evidence they needed to convict the man and Mary they wanted more and he forged a postscript asking for the names of the friends! In the end all 8 of them (Mary, Correspondent and 6 friends) were caught and killed. Moral of the story? Don’t rely on encoding (monoalphabetic ciphers) or you could die.
The other story I wanted to share with you is probably the one most widely known story of cryptanalysis in the world. Libraries of books have been written focusing solely on this event in history and numerous movies have used the gripping tale. There is another reason that it’s particularly of interest to me, and that it’s pretty much the only story in the world where the Polish are the heroes.
The Enigma
Now, before we can eve talk about what the enigma is or what it did we have to kind of set the stage a bit here. WWI is over and a couple of people want to work on making the encryption process better. In 1918 two German friends Arthur Scherbius and Richard Ritter found a company aptly named “Scherbius and Ritter” to invent things. Scherbius was the R&D guy and one thing he wanted was to work on some electronic thing to make encryption better. The result of all this was The Enigma.
Basically, it was a machine that had 3 (and later 5+) disks that rotated, a plug board in the front, a keyboard and at first just another “keyboard” that would light up. You’d arrange your disks, plug some cables into the plug board, and type out your message. Then the letters would light up and you’d write or type that up.
On the outside it looks pretty simple. Once we start to dissect it however, the elegance is really quite remarkable and was the driving force for many inventions. What made this so hard to crack? Let’s explain a few things.
The plug board, this was a simple aspect of the overall design but could really offer a lot of flexibility. It connects two letters and reverses them. For instance you could plug the L into the E and the two would be reversed. love -> eovl. What was really impressive though were the disks. As you would type they would increment one wheel, one notch at a time. When the first wheel made a complete rotation the next would move one notch and so on. Of course, this meant you had to reset the disks for each message, but it was well worth it.
The disks had 26 starting spots, indicated by each letter of the alphabet, and with 3 disks you have 17, 576 starting positions to choose from. The disks were also modular meaning you could put them in any of 6 orders. Don’t forget the plug board which came with six cables allowing you to swap 6 of the 26 letters which gives you 100,391,791,500 possible permutations.
Now if we multiple all of those we get a key space of about 10 pentillion, not bad. On top of this, at the end was a “reflector” which shot the signal back though the disks on a different path before they got to the lights. While this doesn’t add to the keyspace, it adds to the complexity and frustration of cracking. Those of you paying attention realize the one major drawback here though, distributing those starting positions.
An issue, yes, but it was worth it and was done. Of course this leads to the possible capture of the code books, but the operators were ordered to destroy them if they were captured. The paper was printed on water soluble paper so that made it easier to destroy them quickly. One book was captured though, later in the war when more disks were used and couldn’t be broken. Quite an interesting tale that, but we’re not really focusing on that particular bit of history, were more interested in how the enigma was eventually cracked.
In WWI there was a place called “Room 40” in London but in 1926 when the first Enigma ciphered messages started coming in, they were stumped. The French and Americans didn’t fair any better and the Germans had perfect secrecy, at least, in the beginning.
Before we go any further I want to talk about Bletchley Park for just a moment. Bletchley Park took over the task of cipher breaking from Room 40 and at its height had several *thousand* people working there. The set up was quite interesting as well, the center was this Gothic looking mansion and it was surrounded by these little huts ingeniously labeled “hut X” with X being the number of the hut. They were known to employ a wide range of individuals from crossword puzzle junkies to mathematicians and linguists. It is really quite an amazing place, historically speaking, numerous books talk about it both fiction and non.
I’ve kinda jumped ahead of myself so let’s back track a bit here. See, the British, the French and the Americans just weren’t all that motivated to crack Enigma. They had just beaten the Germans and kinda had an ego issue and didn’t think it was A) possible or B) worth while.
There was one very paranoid country though, Poland. With the threat of invasion on both sides (From the Russians and Germans) they were incredibly motivated to find *some* way to crack Enigma. The French had signed an information sharing treaty with Poland and when their secret service managed to get their hands on two documents from a man on the inside (Hans-Thilo Schmidt) they just handed them off to the Poles thinking the information basically useless.
The documents didn’t give any of the codes, nor did it even come out and say “this is how to build and Enigma device”, but it did hint at the construction. The Polish, in Biuro Szyfrów, started to get to work. One of their great foresights was in employing mathematicians. The reasoning was that since the Enigma was mechanized it would take a mind trained in engineering to break it.
They rounded up some people from Poznán which was special, not because of level of intelligence, but because it was, until 1918, part of Germany and thus the citizens there were fluent in German. The guy we’re going to focus on is Marian Rejewski. He had studied statistics looking for a career in insurance. He worked his way through basic code breaking at Biuro and eventually headed the Enigma team.
What Rejewski realized was that the key to breaking the Enigma lay in the message key. Wait! stop! message key? what’s the message key? Good question, let’s find out. The Germans were smart, they realized that vast amounts of information encoded with the same key would lead to lots of cipher text and that would be a cryptanalyst’s dream come true. With massive amounts of information, deciphering the key is made much simpler. What the Germans did was issue code books once a month.
To send a message the Enigma operator would set his machine up with the day’s settings which included which disk when in which slot, which letters to connect on the plug board and which spot on each disk to set (A-Z). The operator would then chose a new orientation for the disks (A-Z) and type this out twice (on the day’s settings) to provide insurance against operator error, or noise on the signal. Therefore the first 6 chars of a message would be the message key (starting positions for the 3 disks) repeated. Say you got a message and the first 6 chars are SFKBJM, that would be the message key encoded by the “day key” twice.
The receiver would set his machine up with the day key, type in the first 6 chars which should be the same thing twice, “BCU” for example. He would now know the message key and could line up his disks to the message key and type out the rest of the message.
Rejewski saw great potential in this realizing that repetition is the bane of security. You just can’t have both. He knew that the first and fourth letter of any message were somehow related, S and B in our example, since it was the same letter encoded at two different positions on the disk. Likewise F and J, as well as K and M were equally related in some manner. How they were related though he wasn’t exactly sure yet.
If he had enough messages he could create three sets of tables linking letters. He would need to have enough that he could link each first letter to each fourth letter. In other words, he would need to know what A-Z for the first letter were stepped down as the fourth. He would have one for the 1-4, 2-5 and 3-6 relationships. One might look something like:
first letter 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 fourth letter E D I G M P K N C T S Z C F U A H D B O Q L V J W R
Notice the S from the first line links up with the B from the second. Similar tables would be drawn up for the other letter’s relationships.
Rejewski saw a pattern that one could make, if one started at the top, and followed to the bottom, finding then that letter on the top, moving to the bottom again you would eventually end up back and where you started. Using our example, a chain might look something like S -> B -> D -> G -> K -> S having 5 “links”. What’s more, the number of links in a chain was completely independent of the plug board settings. The letters might jumble around some, but the actual number of links would not change.
Now we have something manageable, instead of trying to find 1 of 10 pentillion keys we only have 105, 456 keys. Sure, that’s not exactly child’s play, but when your freedom is at stake it looks a hell of a lot better than 10 pentillion and so Rejewski’s team started the arduous task of making the chains for every possible key. It took them a year, but at the end of that year all Rejewski had to do was make his chains for that day, look it up in his catalog and he would have the day key. Well, he would have the orientation of the disks anyway.
The plug board switched letters around on him and he didn’t know which of the many possibilities the machine was set at for the day. That didn’t prove much of an issue though and he relied on just picking it up from the text. If, for example, the message said “Belrin” one might deduce that the l and r were switched.
Rejewski and his team had done it, they had cracked the impregnable Enigma and all was good. It came to pass, however, that the Germans made some minor adjustments and rendered Rejewski’s catalog completely useless. Instead of throwing his hands up Rejewski came up with and ingenious contraption. He named his devices “bombes,” the exact reason is not known though a couple hypothesis exist including one involving ice cream. What better way to combat mechanized encryption than with mechanized code breaking?
He made a machine that would be able to check all of the 17,576 possibilities quickly, and since there were 6 orientation, then he would need 6 such machines working in parallel to find the key. This overall machine with 6 “sub-machines” was the bombe and would crunch away at finding the day key for them, usually in less than a few hours.
Of course, they really didn’t need to go through the whole process. As it turned out the informant was still meeting with the French and handing over whole codebooks, 38 month’s worth in fact. The director of the Buiro (Gwido Langer) never told Rejewski considering it prudent realizing one day the books would stop coming and they didn’t have time to become complacent.
The day did come, right after the Germans switched over to a yet another new system. Now instead of 3 disks there were 5, but the machine still only used 3 disks at a time. The task now became finding out the wiring of the new disks, then they had to figure out which of the 5 were used, and in what orientation. Where there was once only 6 possible ways to arrange the disks there was now 60. On top of that, instead of 6 cables for the plug board there were now 10, switching 20 letters.
The German threat was rising and the Poles decided to come clean to the British and French inviting them over. On July 24th of 1939 a French and British representative meet Langer where he unveiled the bombe and told them the story. He gave them each a spare Enigma and plans for the bombe hoping they would be able to take it the next step to combat the new system.
Just in time too, since a little over a month later (September 1st) the Germans invaded Poland and the war began. In many respects the story just starts here, and much has been said about the British involvement and Alan Turning in particular. I highly recommend reading more on this aspect of WWII history.
In the next installment we will be talking about symmetric ciphers, what they are, how to spot them, and how to crack them. Until then, thanks reading and I hope you had fun/learned something!