A Crash Course in Cryptography Part II – Symmetric Ciphers

Today we will be delving into symmetric ciphers. I will remind you that this course is an introductory one. That means we won’t be digging deeply into the specifics. Yes, we will talk a little about the algorithms and their applications, however it will mostly be abstract. For instance we will talk about what a hash is, but not pick out the mathematical differences between SHA-1 and MD5.

What is a symmetric cipher? Symmetric, secret, private key, these are all synonyms for a specific class of cryptography. Symmetric ciphers all have one thing in common, a secret. That’s it. The encryption is only as strong as this secret and who knows it. As the old saying goes, “Three can keep a secret if two of them are dead.” That said, let’s get one with it and find out what implications that has.

Part I – Ciphers

There is a massive wealth of symmetric ciphers and there’s simply no way we could cover them all. One of the very first recorded uses for cryptography was by none other than Julius Caesar and as such has come to be known as the Caesar Shift. By today’s standards it’s breakable by a five year old, however at that time it was quite clever. What he decided to do was shift the letters in his messages five places, thus A became F, B became G and so forth.

All encryption is based on two things: A key and a cipher. The cipher is also known as an algorithm, perhaps more commonly so. Let’s take these terms and define them now for you. What is a cipher/Algorithm? Well, if you’ve taken much math in school the latter will surely sound quite familiar, and for good reason. An algorithm is nothing more than a method, a series of steps one preforms. A recipe of sorts, indeed one could say that beating 3 large eggs in a medium bowl with a pinch of salt and then heating in a pan over medium heat until solid would be the algorithm for making scrambled eggs.

It’s important to note that the algorithm was not “3 large eggs, pinch of salt” that would simply be the ingredients, what one needs. The algorithm is what one needs to do. What was the algorithm in our Caesar Shift? It’s not difficult, The algorithm is to shift the letters. Notice I didn’t say that it was to shift the letters five places. Why not? Well, five would be the key, the secret. Understand? The algorithm has 25 possibilities (a shift of 0 or 26 would be identical) It is true that you can find shifts of say 256 but you simply end up moding by 26 to get the answer: 256 % 26 = 22.

Moding, also known as clock counting, is division where you throw away the whole number and return the remainder. Modulus math is particularly important in asymmetric ciphers and will be covered in greater detail in the final installment.

Given the very limited keyspace this offers no real security. One does not even need more than a couple minutes to crack this encryption, seconds if one uses a computer. The shift cipher is also known as a rotational cipher. Many of you may be more used to the former name which is usually shortened to rot-X where X specifies the key. The most popular of course being rot-13. Why is this so popular? Well the encryption and decryption are perfectly mirrored. If A = N then N = A.

Shifts aka rotational ciphers are a subset of one of the high reaching groups of symmetric ciphers. substitution. The idea behind substitution ciphers is to substitute the letters with some other representation. The other major group of symmetric ciphers would be transposition which we will be covering shortly. Substitution ciphers also have two subsets, poly and mono alphabetic.

Our shift cipher falls into the monoalphabetic section. What do these two mean? Let’s look at those prefixes: mono – one, poly – more than one. Well there ya go, figure it out?
Monoalphabetic ciphers use a single instance of the alphabet by substituting the various letters with other letters. You could, for instance randomly pick the associations. This is really quite common. Children especially like to use them for secret notes and they make usual appearances in newspapers as the “crypto quote” or other such puzzles. These also can usually be easily decrypted and are more commonly used for fun, they offer no real security.

Now then, that leaves the polyalphabetic ciphers. There’s one particularly prominent example of this that’s known as “Le Chiffre Indéchiffrable” or more commonly vigenère. I’ll talk more about the interesting history of this cipher during the cryptanalysis section of today’s tutorial. For now I’ll just give you the basics of it. Vigenère is quite interesting, it’s one of the only truly unbreakable ciphers, IF used in a certain way, otherwise it becomes even more simple to crack than monoalphabetic ciphers. Interesting indeed.

So, how’s this all work then? You need the vigenère grid which looks something like this:

As you can see what we have is a grid of the alphabet, there are 26 alphabets each starting with a letter and then looping back on themselves. Now, to encipher your message(s) what you need to do is come up with your key. Let’s use “goats” as an example and our message will be “encryption is easy and fun!”. One thing to note is that because the grid is symmetric diagonally it doesn’t matter whether you use the row for the key and column for the plain text or the reverse. Just find where those two intersect. For the first letter in our message, in this case “e”, and first letter of the key “g” we see they intersect at “k”, which is the first letter of our cipher text.

You continue in this fashion until all of the message text is enciphered. But wait! I hear you shout, “What do we do when we run out of letters in our key?” Simple, just repeat it. This will become very important later, but let’s just continue on with our example. Finishing up our message becomes: kbckqvhihf og etke onw xab

encryption is easy and fun!
goatsgoats go atsg oat sgoa
kbckqvhihf og etke onw xab

There’s a couple things we should note here.

One: The same letter enciphered does not always create the same cipher letter. Notice how s is enciphered to both g and k.

Two: The same letter in the cipher text doesn’t always equal the same plain text letter. Again, notice how k was derived from e,r and s.

Three: The cipher text can be, and often is, stripped of punctuation such as spaces to help baffle analysis. Although it’s not shown here, it’s also common to do “five character group message form” where you break the cipher text up into groups of five letters. This is common to many symmetric ciphers, not just vigenère.

Like I said we’ll come back to this algorithm again later so let’s move on for now. That leaves us with the other major group of symmetric ciphers known as transposition ciphers. Again, this is a simple concept to grasp. You simply move the letters around with some order. This last part is important, otherwise you wouldn’t be able to recover the plain text. There are several methods accomplish this goal, a staggering amount really. As an example let’s use a line algorithm with a key of 3 and we’ll use the same message text padding with X’s should the need arise:

ertneydn
nyiiaafx
cpossnux

If we read the columns top to bottom, left to right, we see our message clearly now if we read the rows instead we get a cipher text of: ertneydnnyiiaafxcpossnux which may or may not be spaced properly depending on who’s doing the enciphering. The exact same method can be written a different way though:

enc
ryp
tio
nis
eas
yan
dfu
nxx

Yielding the same result, again it just depends on personal preference. Perhaps the most well known transposition algorithm is the “rail road cipher”. Which is basically the same thing, just using a key of two and looks like this:

e c y t o i e s a d u  
 n r p i n s a y n f n

Where you alternated between the rows creating the following cipher text: ecytoiesadunrpinsaynfn

Of course this is easily defeated by finding the midpoint (u in this case) and wrapping ie:

ecytoiesadu
nrpinsaynfn

Now we can read it quite clearly one column at a time.

We’ve talked about the two main groups of symmetric ciphers and a couple of their specific algorithms, but that isn’t to say every symmetric cipher falls neatly into one or the other group. In fact, the most powerful will use a combination of the two in multi-tiered approaches.

A long time ago (ok not that long…) people started to take notice of cryptography in an increasingly digital world, when the question arose: How would they keep things confidential? In 1972 the NBS (National Bureau of Standards) now known as NIST (National Institute of Standards and Technology) decided to get in the game to create some kind of standard. In 1974 they announced the DES (Data Encryption Standard) which was based heavily on the IBM submitted Lucifer cipher developed by Horst Feistel with consulting help from the NSA (National Security Agency).

Originally Feistel wanted to call it Dataseal, but IBM called it demonstration cipher which was shortened to Demon and later became Lucifer. No doubt in part to the phonetic inclusion of “cipher”. The term Feistel blocks is still used to describe his method and is common in many of today’s ciphers.

DES was a block cipher which means it works on blocks of information at a time as apposed to stream ciphers which work on a single character at a time. The most prevalent use of a stream cipher, which some of you may know, is RC4 (pronounced arc four, the RC stands for Rivest Cipher – The R in RSA which we’ll talk more about in part 3). DES worked on 64-bit chunks of data at a time using a 56-bit key which seemed adequate at the time, though not to everyone. The original specification called for 128-bit keys but the NSA shortened it to 56-bit on the pretext that it wasn’t meant to last for more than 10 years anyway.

In 1977 DES was accepted as the (US) federal standard for unclassified documents. NIST specified that DES would undergo revision every 5 years to see if it was still up to the job so to speak. While DES passed without problems in the 1983 review, NIST originally said it would not recertify it again in 1987, but as there was no viable alternative it was signed on with the stipulation that it would not be approved in 1993.

With the computing power of 1975 it was estimated it would take about 300 years to crack DES. In 1997 RSA offered a challenge to crack DES and winner Rocke Verser managed the feat in a mere 96 days. Not quite a year later a team from Distributed.net cracked it in 41 days. In July of 1998 the EFF using a computer dubbed Deep Crack (in homage of Deep Blue) valued at approximately 1/4 Million USD cracked it in 56 hours. Then in January of 1999 Distributed.net using Deep Crack as a node broke DES in a speedy 22 hours.

To the surprise of many DES actually was recertified in 1993, however applications were then being taken for AES (Advanced Encryption Standard). Before I talk about AES though I wanted to let you know that there is an improvement to DES, in fact there’s two. Double DES and Triple DES which is really quite self explanatory, however due to the quirks of the system Double DES only provides an applicable 57-bit key, not much of an improvement.

Triple DES aka: TDES or (more commonly) 3DES offers 168-bit security and does something quite interesting. One might assume that triple DES would mean going through DES three times, and while this is true, it’s misleading. 3DES can use two or three keys depending on its implementation and most importantly it doesn’t provide three encryptions. Confused? Don’t be! What 3DES does is alter encryptions and decryptions. While the first pass is encrypted with Key “A”, round two will use the algorithm to decrypt the cipher text with Key “B” then that gets encrypted with Key “C”. Of course there’s also variations on this as well. Some may use two decryptions and one encryption, or there may only be two keys involved as I mentioned.

Ok, getting back on track we were talking about AES. NIST was really pushing the limits when they recertified DES in ’93 and needed something new. The challenge was open to anyone with the following guidelines: AES must be a block symmetric cipher supporting key sizes of 128, 192, and 256 bits. In 1999 NIST announced the 5 finalists for AES which were: MARS, RC6, Rijndael, Serpent and Twofish (which uses an interesting rubix cube style cipher). Then in October of 2000 NIST decided on Rijndael which was based largely on Square which was also written by the authors (Joan Daemen and Vincent Rijmen). The authors actually wrote a book on the cipher if you want some more information. This actually brings us to a close for ciphers, let’s move on!

Part II – Hashes

So, What the hell is a hash anyway? A hash is not a symmetric cipher, but I decided to cover it here anyway. In fact, hashes aren’t really ciphers at all as they are “one way functions”. What does that mean? That means once you preform the hash you can’t recover the plain text.

What a hash does is take the input and crunch it down to a little string usually represented in hexadecimal. Ok, so we know what a hash is… what’s it good for? Hashes are popular for data integrity checks. (The I in the CIA information security model). Since no two sources can have the same hash value, at least in theory, it’s possible to determine if the data was changed during transit.

Ethernet frames use CRC (cyclical redundancy check) which is a 32-bit checksum (another name for a hash). More commonly you’ll see hashes used in conjunction with public key cryptography to provided nonrepudiation which is very important. It’s also become popular to provide MD5 or SHA1 hashes for file downloads, particularly in the Linux world to make sure those large ISO files you’re downloading made it from the server to you without any bits getting flipped.

IDS (Intrusion Detection System) and virus scans often employ hashes to create a hash database of system files after install to compare future hashes against to check for root kits, unauthorized access and the like. Not only does this provide some level of security, but it can also reduce scan times. Tripwire is one such program that is founded on hash values.

There’s a few different hashes floating around out there but surely the most common are Secure Hash Algorithm-1 (SHA-1) (RCF 3174) and Message Digest 5 (MD5) (RFC 1321). SHA-1 provides a 160-bit hash value and MD5 computes a 128-bit value, and they’re commonly presented as 48 and 32 character hexadecimal strings, respectfully.

Just a moment ago I mentioned that no two data sources should have the same hash value, but this is only true in theory and not so much in practice. If you think about it, it should be fairly obvious. There’s an infinite number of permutations for data, but even SHA-1 is limited to 160 bits. Both SHA-1 and MD5 are vulnerable to what’s known as collision attacks.

Now before you start getting all paranoid about the world coming to an end or something you have to realize the reality of collisions. Collisions can’t be crafted, that is to say someone can’t create a new program and give it the same MD5 hash as the latest version of pidgin‘s tarball. Ergo, the practical application of collisions are very limited indeed. The only known collisions are based on such minor variations that in fact they probably won’t even matter. I believe in the MD5 paper you’ll read about “fire and ice” and personally I just don’t see any potential for this so called vulnerability however, feel free to draw you own conclusions.

How can you mitigate these issues? well you can use a double hashing approach. Create both a SHA-1 and MD5 hash, the possibilities of a collision in each of these hashes on the same data is a as close to a mathematical impossibility as you can get without actually presenting a proof. You may also consider using SHA-256 which, as the name implies, creates a 256 bit hash instead.

Part III – Cryptanalysis

Now then, the very first step in determining how to attack a given cipher text and/or hash value is to determine what exactly was used to get the data in the state your looking at. That is to say, you need to deduce what cipher was used. There’s some things you’ll be able to figure out quite easily and then there’s some trial and error.

For instance, if you see a string of hexadecimal values 32 characters long you’ll probably assume it’s an MD5 and you’ll probably be correct. Likewise all crypt(1), which is an implementation of DES, strings will be 13 characters long (the first two of which incidentally are the salt). Something to note, if you’re looking at an /etc/shadow file and the password field is the aforementioned 13 chars, it will be a crypt() digest, if the first characters are $1 then it will be an MD5 digest and lastly if it starts with $2 then it’s blowfish. Of course most password cracking programs will figure this out all on their own and make the necessary choices, but it’s handy to know never-the-less.

Base64 which as we discussed is *not* encryption, is common and is easily spotted by a = or two used to pad the result on the end of the string. If you just have a bunch of letters starting at you though you have quite a few options. If you’re lucky it’ll be a simple shift and you can BF (Brute Force) the key, given there’s only 26, exceptionally easy which is why I personally always start with this method.

If that comes up dead you can try frequency analysis which is a simple concept. All letters, in any language, have a certain frequency attributed to them. Since this is a tutorial in English I’ll use that language for an example. In English the most commonly used letter is “e”, just look at how many times it appears in this sentence alone. If you were to count up all the letters in your cipher text and you can make a fairly decent assumption that the letter that shows up the most is an “e”. Of course, the smaller your data set the more skewed from the assumed frequency it’s likely to be.

After “e” comes “t” and so forth as you can see in this table:

Letter	Freq	Letter	Freq
E	12.702%	M	2.406%
T	9.056%	W	2.360%
A	8.167%	F	2.228%
O	7.507%	G	2.015%
I	6.966%	Y	1.974%
N	6.749%	P	1.929%
S	6.327%	B	1.492%
H	6.094%	V	0.978%
R	5.987%	K	0.772%
D	4.253%	J	0.153%
L	4.025%	X	0.150%
C	2.782%	Q	0.095%
U	2.758%	Z	0.074%

Data courtesy Wikipedia

We can also infer other frequency related aspects of the message. For instance the most common combinations of letters th and so forth. We can look for two and three letter words. 2 letter words are especially good to attack because in English it’s a given that one of them will be a vowel, of which there are only 5 with a possible 6th. If, for example, you had the cipher text of “jt” and you’ve already made the assumption that t = e given the vast quantity of t’s in the cipher text then your job becomes easier. Now there’s only 26 possibilities and of those only a handful that are legitimate English words, quickly you can start gaining a foot hold.

Another tactic to use would be using a crib. A crib is a some plain text you’re relatively certain is contained within the cipher text. If for example you were decrypting something from your significant other you might assume the word “love” was in there some where. Of course, why they’re enciphering their love letters and not giving you the key is another issue entirely. You could find 4 letter words and say “if this were ‘love’ then “X” must equal L”.
This, of course, all hinges on the cipher text being a generated from monoalphabetic cipher. It may seem like it would be a lot easier than trying to decipher a polyalphabetic cipher. Remember that I said Vigenere could even offer perfect encryption. The keyword here of course, is “could”. In reality Vigenere is often much easier to crack than your traditional monoalphabetic cipher!

First: How can vigenere offer perfect encryption? The only way is to use a random key equal in length to the message to be enciphered. Simple enough. I say random which is the only true way to perfection, however even non-true will be nearly unbreakable. The reason behind this is that if each letter of the message is enciphered with its own alphabet then there’s no telling what it was to begin with. There’s no way to get any type of pattern. The only way to attack it would be through brute force which could take literally forever if the message is long enough. If you use a random key you’re essentially creating a one-time pad.

Ok, so that’s how it can be unbreakable, how can it be easier to break than monoalphabetic? Good question, let’s find out. There’s two different ways to go about step one. 1a, as we’ll call it, is the easiest to explain and requires nothing beyond the ability to factor numbers in terms of mathematical prowess. 1b has to do with something called “the index of coincidence” and “the mutual index of coincidence” and involves probability computations and a funky equation using that sigma character.

Guess which one we’re gunna talk about. Remember this is a crash course, nothing too intensive going on here. I should note that Charles Babbage was actually the first person to come up with this technique after a challenge was made to him. If that name doesn’t ring a bell… pick up a book once and awhile, moving on! The fact still remains that with a key length smaller than the plain text the possibilities for duplicates can and most often do occur. For instance the word “the” will most likely appear several times in the course of any message. Three times in that sentence alone! We don’t really even care if it’s a word though, it could just be a series of letters that are the same.

If we limit ourselves to only looking for repeating sequences of four characters or more we can be pretty sure it’s because the same plain text was enciphered at the same point in the key, thus producing identical cipher text. What we have to do is find all such occurrences in our cipher text and make ourselves a little matrix. On the x-axis you’ll have “possible key length” which will be the factors of whatever the spacing for that patter was. On the y-axis you’ll have “pattern”, the actual pattern you’ve detected and the spacing between them. Then you simply put a check mark in each box. You should find a column that has a check mark for each sequence you’ve identified (7 in the example below), and that’s your key length and part one is done. It should look something like this:

		Possible Length
Sequence	Spacing	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
A-K-Y-Z	35
N-T-O-Q-L	63
E-Q-C-I	84
K-P-I-D-B	49

Now you break up the cipher text into groups separating them by the letter used in the key. If the key was 4 letters long, then you’d have 4 groups, the first group would be the 1st, 5th, 9th, etc. characters. From here you can do your standard frequency analysis. It often helps to draw yourself up a few histograms to provide a visual cue. On the X axis you put each of the letters and the y is the frequency. At this point you’ve broken your polyalphabetic cipher into “X” shift ciphers, which we all now know offer no protection. Using the histograms you’ve created you can compare them to a histogram based on the frequency table we mentioned earlier. Now you just over lay them until they line up and you’ll find how many characters the shift was.

One little tid-bit to know is that multiple enciphering with different keys offers no real added security when it comes to the cryptanalysis. The multiple enciphering simply creates a mutated key.

Now that we’ve attacked poly and mono alphabetic ciphers, let’s say you figured out your cipher text was an MD5 hash. We know already that this can’t be reversed, there is no key after all. How then do we attack these? Well I’m going to make an assumption here that I feel fairly confident in, and that is that the most common use for attacking MD5 hashes is that it’s been used on a password. There’s two major attacks we can employ: Dictionary and BF or Brute Force.

I list these two options in the order in which you should attempt them. Using a dictionary is incredibly easy, tends to be significantly faster and users tend to be… less than intelligent when it comes to picking passwords. Often times a password will be a family member’s name, favorite movie, etc. Something easy they can remember. The problem with making it easy for them is that it makes it easy for an attacker as well.

You can load your cracker of choice (discussed next) and word list of choice and crunch through every English word in a matter of seconds (depending on processor speed of course). Even using “The Argon List” (a 250MB word list, with many duplicates) it’s possible to run through the entire thing in a few minutes. Most crackers also support options for permutations on the word list, like converting letters to numbers (e->3) appending numbers, and so on. Many people will think they’ve made their password strong by adding a date to the end. This is false security as it’s a trivial matter (in most crackers) to have them appended to every word in the word list without even altering the list. If the date has any specific meaning (say they were born on 67 and have a cat named fluffy thus creating Fluffy67 for their password) then it’s only that much easier to crack. “Fluffy67” may look good at first glance. It would even pass Microsoft’s complexity test, and meets the common 8 character minimum. However, given a minute on a crackers machine and anything protected with that password will be singing.

The other option is to resort to BF, which there simply is no protection against. A BF attack will simply try every possible option, one at a time. Granted, they may set up their attack based on false assumptions, only lower and upper case characters for example, but eventually it will crumble. It’s only a matter of time. That being said, many ciphers use such large key spaces that this “matter of time” actually exceeds the life the universe using machines capable of exceedingly fast analysis currently impossible with current technologies.

So, we’ve figured out what the cipher text was enciphered with (hopefully) and we’ve devised a strategy for attack, now we could probably use a tool or two to give us a hand. One of the most popular will of course be john the ripper or jtr for short. Jtr is available for both windows and *nix and is exceptionally fast, supports word lists and a number of BF options. In the most basic set up you simply need to have a file containing a username and hash value colon deliminated (username:hash) then simply type: john file.txt and off you go on a BF attack (in “incremental” mode). Windows users may also want to check out Cain & Able and L0phtCrack for your windows password needs. There’s really too many options to discuss here, but suffice it to say they’re very powerful.

You might also consider so called “rainbow” tables which are precomputed tables and they work on the principles of the time/memory trade off. Basically you trade the time it takes to compute all the hash values with the memory it takes to store all the values directly. Of course when these tables get huge (multiple terabytes) you also have a lookup delay to factor in as well. If you can’t spare the space to store these tables several look up sites do exist with varying degrees of scope. Some are free, some pay, some freemium where pay a fee to get pushed to the head of a queue and/or access to larger tables.

Another common obstacle people may face is a lost or misplaced zip password. Two tools I’ve personally used and consider to be quite up to the task are Fast Zip Crack (FZC) and Visual Zip Password Recovery. They each work equally well and it’s really a matter of whether you like a pretty GUI or can live without it. We also have the capability of password protecting Word documents, Excel spread sheets and myriad other file types. Elcomsoft offers a wide range of products targeted at recovering these passwords dubbed “Advanced X Password Recovery” where the X is whichever application is to blame. As an interesting side note, Dimitry Sklyarov, who worked for Elcomsoft, was the first person arrested under the DMCA at DefCon 11 in Las Vegas on July 16th.

The last tool I want to talk about is cryptool. This is an exceptionally useful little program and can handle a great number of tasks for you such as creating and analyzing histograms, preforming frequency analysis etc. While this program is a win32 application source code is available via SVN and there’s currently a cross platform version beta based on java.

We’ve come to the end of another lesson. I hope you learned something and had some fun, in part 3 we’ll be talking about asymmetric Ciphers, I hope to see all of you there.