The Caesar cipher is purported to have been used by the ancient Roman Caesars, such as Julius Caesar, hence the name. This method is also referred to as a substitution cipher. Almost every introductory cryptography book in existence mentions the Caesar cipher. It is even mentioned in the course material for several prominent network security certifications. It is actually quite simple to do. You choose some number by which to shift each letter of a text and substitute the new alphabetic letter for the letter you are encrypting. For example, if the text is

• A CAT

and you choose to shift by two letters, then C replaces A, E replaces C, C replaces A, and V replaces T, and the encrypted message is

• C ECV

Or, if you choose to shift by three letters, the encrypted message becomes

• D FDW

You can choose to shift by any number of letters, either left or right. If you choose to shift 2 to the right, that would be a +2; if you choose to shift 4 to the left, that would be a –4. If you get to the end of the alphabet, just keep going back to the beginning. So if you are shifting to the right, and need to go past Z, just start over at A. Julius Caesar was reputed to have used a shift of three to the right.

Because this is a very simple method to understand, it is a good place to start your study of encryption. It is, however, extremely easy to crack using the two major forms of attacking text for decryption. The first is a brute-force attack. If a Caesar cipher is suspected, modern computers can simply try all possible combinations and see if recognizable text emerges. Frankly, you could do this with pen and paper. With any cipher there is the concept of key space; that is, the total number of possible keys. With a Caesar cipher applied to the English language, there are only 26 possible keys. You could easily try all of those in just a few minutes.

The second approach is based on the attacker’s knowledge of the underlying language. The Caesar cipher is easy to crack using an academic approach because of letter and word frequency. Any language has a certain letter and word frequency, meaning that some letters are used more frequently than others. In the English language, the most common single-letter word is a. The most common three-letter word is the. Those two rules alone could help you decrypt a Caesar cipher. For example, if you saw a string of seemingly nonsense letters and noticed that a three-letter word was frequently repeated in the message, you might easily surmise that this word was the, and the odds are highly in favor of this being correct. Furthermore, if you frequently noticed a single-letter word in the text, it is most likely the letter a. You now have found the substitution scheme for a, t, h, and e. You can now either translate all of those letters in the message and attempt to guess the rest or simply analyze the substitute letters used for a, t, h, and e and derive the substitution cipher that was used for this message.

Decrypting a message of this type does not even require a computer. Someone with no background in cryptography could do it in less than 10 minutes using pen and paper. There are other rules that help make cracking this code even easier. For example, in the English language, the two most common two-letter combinations are ee and oo. That gives you even more to work with.

The substitution scheme you choose (e.g., +2, +1) is referred to as a substitution alphabet (i.e., b substitutes for a, u substitutes for t, and so on). Thus, the Caesar cipher is also referred to as a monoalphabetic or single-alphabet substitution method, meaning that it uses a single substitution for the encryption. That just means that all letters in the plaintext are shifted by the same number.

In any cryptographic algorithm, be it a simple one like the Caesar cipher or a more modern one, the number that is used by the algorithm to encrypt or decrypt a message is called the key because it unlocks the scrambled information. In the case of the Caesar cipher, it is a single digit (like +2); in the case of modern algorithms like Advanced Encryption Standard (AES), it is a 128-bit number. Even though the Caesar cipher may have a much simpler algorithm (shift the letters by whatever number and direction is in the key) and a smaller key (a single digit, or at most two digits, as in +12 or –11), it is still an example of the basic concepts you see in more sophisticated modern cryptographic algorithms.

The Caesar cipher also introduces two more basic concepts of cryptography. The text you want to encrypt is referred to as the plaintext. After it has been subjected to the algorithm and key, the resultant text is called the ciphertext. So, although simple, the Caesar cipher introduces cryptography algorithms, keys, plaintext, and ciphertext.

This gives you a primitive introduction to cryptography and encryption. It must be stressed that this is no longer a secure method of encrypting messages, but it is an interesting exercise to begin introducing the basic concepts of encryption.

Hebrew scribes copying the book of Jeremiah used this cipher. This cipher is very simple— just reverse the alphabet. This is, by modern standards, a very primitive and easy-to-break cipher, but it will help you get a feel for how cryptography works.

The Atbash cipher is a Hebrew code that substitutes the first letter of the alphabet for the last letter and the second letter for the second-to-last letter, and so forth. It simply reverses the alphabet. A becomes Z, B becomes Y, C becomes X, and so on. This, like the Caesar cipher, is a single-alphabet substitution cipher.

This is another single-alphabet substitution cipher. It is, in fact, the simplest of all of them. It is really just a permutation of the Caesar cipher. All characters are rotated 13 characters through the alphabet. The phrase

• A CAT

becomes

• N PNG

It is essentially the Caesar cipher, but always using a rotation or shift of 13 characters. This is very simple and not sophisticated enough for any real security. But, again, it can be done with pen and paper, or with a simple computer program.

The scytale, which rhymes with Italy, is a cylinder or baton used by the Greeks, and is often specifically attributed to the Spartans. This physical cylinder was used to encrypt messages. Turning the cylinder produced different ciphertexts. Although it is not clear exactly how old this cipher is, it was first mentioned in the 7th century BC by the Greek poet Archilochus. The recipient used a rod of the same diameter as the one used to create the message. He then wrapped the parchment around the rod to read the message. To encrypt, he simply wrote across a leather strip attached to a rod. To decrypt, the recipient would just wrap the leather strip around the rod and read across. This was a simple process; it just required both parties to have the same size rod and the leather “key.”

The Playfair cipher was invented in 1854 by Charles Wheatstone; however, it was popularized by Lord Playfair, thus it bears his name. Although it was first rejected by the British government as being too complex, it was actually used by the British military in World War I and to some extent in World War II. This cipher works by encrypting pairs of letters, also called digraphs, at a time.

The Playfair cipher uses a 5 × 5 table that contains a keyword or key phrase. To use the Playfair cipher, one need only memorize that keyword and four rules. To use the cipher, first break the plaintext message into digraphs; so, for example, “Attack at dawn” becomes “At ta ck at da wn.” If the final digraph is just a single letter, you can pad it with a letter z.

Any square of 5 × 5 letters can be used. You first fill in the keyword, then start, in order, adding in letters that did not appear in the keyword. I/J are combined. You can see this in the table below. In this example, the keyword is “falcon.”

Because the 5 × 5 matrix is created by starting with a keyword, then filling in letters that did not appear in the keyword, the matrix will be different when different keywords are used. The next step is to take the plaintext, in this case “attack at dawn,” and divide it into digraphs. If there are any duplicate letters, replace the second letter with an x; for example, “dollar” would be “dolxar.” Playfair does not account for numbers or punctuation marks, so you will need to remove any punctuation from the plaintext and spell out any numbers. Next, you take the plaintext, in our case At ta ck at da wn, and find the pairs of letters in the table. Look to the rectangle formed by those letters. In our example, the first letters are AT, thus forming the rectangle shown below, with A in the upper-left corner and T in the lower-right corner.

Then you will take the opposite ends of the rectangle to create the ciphertext. A is in the upper-left, so you replace it with whatever appears in the upper-right, which in this case is the letter C. T is in the lower-right corner, so you replace it with whatever letter is in the lower-left, which in this case is the letter R. So AT gets enciphered as CR. Continuing on, the next pair of letters is TA and will form the same rectangle. However, because T is the first letter of the plaintext, R will be the first letter of the ciphertext, yielding RC. Next we have CK. Those letters form the rectangle shown here.

C becomes A, and K becomes M, so we have AM. If you continue this process through to the end of the plaintext, you will have “Attack at dawn” encrypted to yield

• CRRCCKCRBLVB

Eventually, a slight improvement on the Caesar cipher was developed, called multialphabet substitution. In this scheme, you select multiple numbers by which letters in the plaintext will be shifted; in other words, multiple substitution alphabets are created. For example, if you select three substitution alphabets (+2, -2, +3), then A CAT becomes C ADV. Notice that the fourth letter starts over with another +2, and you can see that the first A was transformed to C and the second A was transformed to D. This makes it more difficult to decipher the underlying text. Although this is harder to decrypt than a Caesar cipher, it is not overly difficult. It can be done with simple pen and paper and a bit of effort. It can be cracked very quickly by a computer. In fact, no one would use such a method today to send any truly secure message because this type of encryption is considered very weak.

One of the most widely known multialphabet ciphers was the Vigenère cipher. This cipher was invented in 1553 by Giovan Battista Bellaso. It is a method of encrypting alphabetic text by using a series of different monoalphabet ciphers selected based on the letters of a keyword. This algorithm was later misattributed to Blaise de Vigenère, and so it is now known as the Vigenère cipher, even though Vigenère did not really invent it.

You use the table (shown in FIGURE 5-9) along with a keyword you have selected. Match the letter of your keyword on the top with the letter of your plaintext on the left to find the ciphertext. For example, if you are encrypting the word cat and your keyword is horse, then the ciphertext is jok.

Multialphabet ciphers are more secure than single-alphabet substitution ciphers; however, they are still not acceptable for modern cryptographic usage. Computer-based cryptanalysis systems can crack historical cryptographic methods (both single-alphabet and multialphabet) very easily. This chapter presents the single-alphabet substitution and multialphabet substitution ciphers just to show you the history of cryptography and to help you get an understanding of how cryptography works.

In World War II, the Germans made use of an electromechanical rotor-based cipher system known as the Enigma machine. The Enigma machine is pivotal in the history of cryptography. It is a multialphabet substitution cipher using machinery to accomplish the encryption. There are multiple variations on this machine.

The machine was designed so that when the operator pressed a key, the encrypted ciphertext for that plaintext was altered each time. So, if the operator pressed the A key, he or she might generate an F in the ciphertext, and the next time it might be a D. Essentially, this was a multialphabet cipher, consisting of 26 possible alphabets.

Allied cipher machines used in World War II included the British TypeX and the American SIGABA. Both of these were quite similar to the Enigma machine, but with improvements that made them more secure. The Enigma machine and its variations were essentially mechanical implementations of multialphabet substitution.

Symmetric cryptography refers to those methods where the same key is used to encrypt and decrypt the plaintext. One widely used step is to use two different encryption keys, one from sender to receiver and one from receiver to sender. This is still symmetric cryptography because the same key is used for encryption as is used for decryption—having different keys in both directions just provides additional security if the keys are learned or disclosed. This is historically the type of encryption that has been used exclusively until recently.

Data Encryption Standard (DES)

One of the oldest of the modern symmetric ciphers is the Data Encryption Standard (DES). DES was developed by IBM in the early 1970s. DES is a block cipher. It was a U.S. government standard until the 1990s. IBM had originally developed a cipher called Lucifer, which was designed by Horst Feistel. When the U.S. government began seeking a standardized encryption algorithm, IBM worked with the National Security Agency (NSA) to alter Lucifer to fit the government’s needs, thus DES was created. As you may guess, DES is a Feistel cipher.

The basic concept of DES, is as follows:

1. Data is divided into 64-bit blocks.

2. That data is then manipulated by 16 separate steps of encryption involving substitutions, bit-shifting, and logical operations using a 56-bit key.

3. Data is then further scrambled using a swapping algorithm.

4. Data is finally transposed one last time.

Those four steps provide a simplified, high-level view of DES. As you can see, it works on splitting the block into two sections, as with all Feistel ciphers. The idea is to continually scramble the underlying message to make it appear as random as possible.

To generate the keys for each round, the 56-bit key is split into two 28-bit halves, and those halves are circularly shifted after each round by 1 or 2 bits. In other words, the halves are first subjected to a round function, then the keys are shifted by 1 to 2 bits each time so they can be used in the next round as a different key. Then 48 bits from those two halves are selected and permuted to form the round key. This means there is a different round key for each round. But, it is related to the previous round key. In fact, it is derived from the previous round key.

DES uses eight S-boxes. The term S-boxes means substitution boxes. They are simply lookup tables. Each S-box basically has a table that determines, based on the bits passed into it, what to substitute for those bits. Each item passed into the box is substituted with the item that matches it in the lookup table. This is a very common tactic in symmetric key algorithms. Each of the DES S-boxes takes in 6 bits and produces 4 bits. The middle 4 bits of the 6-bit input are used to look up the 4-bit replacement.

The round F function works as follows:

1. Expand the 32-bit half that was input to 48 bits; this is done by replicating some bits.

2. XOR the resultant 48 bits with the 48-bit round key.

3. Split the result into eight 6-bit sections.

4. Pass each of these 6-bit portions through a different S-box. Each S-box produces a 4-bit output, giving a total of 32 output bits. Note in Step 1 the expansion of the 32 bits into 48; it’s now taken back to just 32 bits, which demonstrates yet another way to scramble the resultant ciphertext.

5. Transpose the output bits.

This is done for each round of DES. DES has 16 rounds, so this is an effective way to scramble the plaintext.

The only reason DES is no longer considered secure is the short key. The 56-bit key is simply not long enough to prevent brute-force attacks. Brute force is trying every possible key. DES has a total number of possible keys (also called keyspace) of 2⁵⁶. A modern computer system can break this in a reasonable amount of time.

Cryptographic hashes were introduced earlier in this book. In this section we will explore hashes in more detail. A hashing is a type of cryptographic algorithm that has some specific characteristics. First and foremost, it is one-way, not reversible. That means you cannot “unhash” something. The second characteristic is that you get a fixed-length output no matter what input is given. The third is that the algorithm must be collision resistant. A collision occurs when two different inputs to the same hashing algorithm produce the same output (called a hash or digest). Now, ideally we would like to have no collisions. But the reality is that with a fixed-length output, a collision is possible. So the goal is to make it so unlikely as to be something we need not think about.

Cryptographic hashes are how many systems, including Microsoft Windows, store passwords. For example, if your password is “password”, then Windows will first hash it, producing something like this:

• 0BD181063899C9239016320B50D3E896693A96DF

Windows will then store that in the Security Accounts Manager (SAM) file in the Windows System directory. When you log on, Windows cannot unhash your password. Instead, what Windows does is take whatever password you type in, hash it, and then compare the result with what is in the SAM file. If they match (exactly), then you can log in.

There are various hashing algorithms. The two most common are MD5 and SHA. (It was SHA-1, but more recent versions like SHA-256 are becoming more common.)

Asymmetric cryptography is cryptography wherein two keys are used: one to encrypt the message and another to decrypt it.

This is the basic tool for breaking most classical ciphers. In natural languages, certain letters of the alphabet appear more frequently than others. By examining those frequencies, you can derive some information about the key that was used. This method is very effective against classic ciphers like Caesar, Vigenère, and so on. It is not effective against modern methods of cryptography. Remember, in English, the words the and and are the two most common three-letter words. The most common single-letter words are a and I. If you see two of the same letters together in a word, it is most likely ee or oo.

Kasiski examination was developed by Friedrich Kasiski in 1863. It is a method of attacking polyalphabetic substitution ciphers, such as the Vigenère cipher. This method can be used to deduce the length of the keyword used in a polyalphabetic substitution cipher. Once the length of the keyword is discovered, the ciphertext is lined up in n columns, where n is the length of the keyword. Then, each column can be treated as a monoalphabetic substitution cipher and each column can be cracked with simple frequency analysis. The method simply involves looking for repeated strings in the ciphertext. The longer the ciphertext, the more effective this method will be. This is sometimes also called Kasiski’s test or Kasiski’s method.

Cracking modern cryptographic methods is a nontrivial task. In fact, the most likely outcome is failure. However, with enough time and resources (i.e., computational power, sample cipher/ plaintexts, etc.), it is possible. Following are some techniques that can be employed in this process:

• Known plaintext attack: This method is based on having a sample of known plaintexts and their resulting ciphertexts, and then using this information to try to ascertain something about the key used. It is easier to obtain known plaintext samples than you might think. Consider email. Many people use a standard signature block. If you intercept encrypted emails, you can compare a known signature block with the end of the encrypted email. You would then have a known plaintext and the matching ciphertext to work with.

• Chosen plaintext attack: In this attack, the attacker obtains the ciphertexts corresponding to a set of plaintexts of his or her own choosing. This can allow the attacker to attempt to derive the key used and thus decrypt other messages encrypted with that key. This can be difficult, but is not impossible.

• Ciphertext-only: The attacker only has access to a collection of ciphertexts. This is much more likely than known plaintext, but also the most difficult. The attack is completely successful if the corresponding plaintexts can be deduced, or even better, the key. But obtaining any information at all about the underlying plaintext in this situation is still considered a success.

• Related-key attack: This attack is like a chosen plaintext attack, except the attacker can obtain ciphertexts encrypted under two different keys. This is actually a very useful attack if you can obtain the plaintext and matching ciphertext.

There are other methods based on more advanced cryptanalysis techniques—for example, differential and integral cryptanalysis. However, this section should give any forensic examiner a good basic understanding of cryptanalysis.

A number of tools can aid in cracking passwords and encrypted data. Remember that if the encryption was implemented correctly and is strong, you may not be able to crack it. But passwords can often be cracked (encrypted information less often). It is also possible to obtain keys or copies of information before encryption via a number of nontechnical means that fall in the category of social engineering, which includes going through the trash, also known as dumpster diving; lying to a person to obtain the keys, passwords, phrases, or unencrypted information; or even getting a job at the target company and stealing the desired information.

Rainbow tables

In 1980, Martin Hellman described a cryptanalytic time–memory tradeoff, which reduces the time of cryptanalysis by using precalculated data stored in memory. Essentially, these types of password crackers work with precalculated hashes of all passwords available within a certain character space, be that a–z or a–zA–z or a–zA–Z0–9, and so on. These files are called rainbow tables because they contain every letter combination “under the rainbow.” They are particularly useful when trying to crack hashes. Because a hash is a one-way function, the way to break it is to attempt to find a match. The attacker takes the hashed value and searches the rainbow tables seeking a match to the hash. If one is found, then the original text for the hash is found.

Popular hacking tools like Ophcrack depend on rainbow tables. Ophcrack is usually very successful at cracking Windows local machine passwords. The steps are very simple:

1. Download Ophcrack and burn the image to a CD.

2. Put the CD in the target computer and boot through the CD.

3. Wait as it boots as Linux grabs the Windows password file, then uses cracking tools to crack that file and produces a text file with usernames and passwords.

You can see Ophcrack in use in FIGURE 5-11. Note, this is from a live machine so some information has been redacted. Many forensics tools, such as OSForensics, provide mechanisms for you to create your own smaller, more focused rainbow tables. For example, you can enter every word you believe might be associated with a suspect, and a rainbow table can be generated from those words and variations of them. This makes a much smaller, and thus faster, rainbow table.