Chapter 6

Encryption Fundamentals

This chapter offers a basic overview of encryption and an explanation of how it works to help you make good decisions for your organization. A complete examination is beyond the scope of this book, but this chapter provides a “manager’s understanding” of cryptography to help you ask the right questions about your organization’s encryption needs.

For much of human history private communications meant encrypting written communiqués. Over the past century that has expanded to radio transmission, telephone communications, and computer/Internet communications. In the past several decades the encryption of computerized transmissions has actually become commonplace. In fact you can find computer/Internet communications encrypted more often than phone or radio. The digital environment makes implementing a particular type of encryption much easier.

Whatever the nature of the data you are encrypting, or the mode of transmitting the data, the basic concept is actually quite simple. Messages must be changed in such a way that they cannot be read easily by any party that intercepts them but can be decoded easily by the intended recipient. In this section you will examine a few historical methods of encryption. Note that these are very old methods, and they cannot be used for secure communication today. An amateur could easily crack the methods discussed in this section. However, they are wonderful examples for conveying the concept of encryption without having to incorporate a great deal of math, which is required of the more complex encryption methods.

A cat

and you choose to shift by two letters, then the message becomes

C ecv

Or, if you choose to shift by three letters, it becomes

D fdw

In this example, you can choose any shifting pattern you want. You can shift either to the right or left by any number of spaces you like. Because this is a simple method to understand, it makes a good place to start your study of encryption. It is, however, extremely easy to crack. You see, 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. Knowing these two characteristics 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 surmise 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 ten minutes using pen and paper.

Caesar ciphers belong to a class of encryption algorithms known as substitution ciphers. The name derives from the fact that each character in the unencrypted message is substituted by one character in the encrypted text. The particular substitution scheme used (for example, 12 or 11) in a Caesar cipher is called a substitution alphabet (that is, b substitutes for a, u substitutes for t, etc.). Because one letter always substitutes for one other letter, the Caesar cipher is sometimes called a mono-alphabet substitution method, meaning that it uses a single substitution for the encryption.

The Caesar cipher, like all historical ciphers, is simply too weak for modern use. It is presented here just to help you understand the concepts of cryptography.

The phrase

A CAT

becomes

N PNG

ROT 13 is a single-substitution cipher.

The Atbash cipher is a Hebrew code that substitutes the first letter of the alphabet for the last and the second letter for the second to the last, etc. It simply reverses the alphabet; for example, A becomes Z, B becomes Y, C becomes X, etc.

This, like the Caesar and ROT 13 ciphers, is also a single-substitution cipher.

A CAT

becomes

C ADV

Notice that the fourth letter starts over with another 12, and you can see that the first A was transformed to C and the second A was transformed to D. This makes deciphering the underlying text more difficult. Although this is harder to decrypt than a Caesar cipher, it is not overly difficult to decode. It can be done with simple pen and paper and a bit of effort. It can be cracked quickly with a computer. In fact, no one would use such a method today to send any truly secure message, for this type of encryption is considered very weak.

One of the most widely known multi-alphabet ciphers was the Vigenère cipher. This topic is discussed in detail later in this chapter. This cipher was invented in 1553 by Giovan Battista Bellaso. It is a method of encrypting alphabetic text by using a series of different mono-alphabet 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.

Multi-alphabet ciphers are more secure than single-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 multi-alphabet) easily. The single-substitution and multi-substitution alphabet ciphers are discussed just to show you the history of cryptography, and to help you get an understanding of how cryptography works.

A      t      c      a      d      w

      t      a      k      t       a      n

Next, you write down the text reading from left to right as one normally would, thus producing

atcadwtaktan

In order to decrypt the message, the recipient must write it out on rows:

A      t      c      a      d      w

      t      a      k      t       a      n

Then the recipient reconstructs the original message. Most texts use two rows as examples; however, this can be done with any number of rows you wish to use.

A (1) + 2 = 3 or C

T (20) –1 = 19 or S

T (20) +1 = 21 or U

A (1) +3 = 4 or D

C (3) +2 = 5 or E

K (11) –1 = 10 or J

So, the ciphertext is CSUDEJ. Given that each letter has four possible substitutions, the letter and word frequency is significantly disrupted.

Perhaps the most widely known polyalphabetic cipher is the Vigenère cipher. This cipher was actually invented in 1553 by Giovan Battista Bellaso, though it is named after Blaise de Vigenère. It is a method of encrypting alphabetic text by using a series of different mono-alphabet ciphers selected based on the letters of a keyword. Bellaso added the concept of using any keyword one might wish, thereby making the choice of substitution alphabets difficult to calculate.

Some military texts encrypted using a version of Enigma were broken by Polish cryptanalysts Marian Rejewski, Jerzy Rozycki, and Henryk Zygalski. The three basically reverse engineered a working Enigma machine and used that information to develop tools for breaking Enigma ciphers, including one tool named the cryptologic bomb.

The core of the Enigma machine was the rotors, or disks, that were arranged in a circle with 26 letters on them. The rotors were lined up. Essentially, each rotor represented a different single substitution cipher. You can think of the Enigma as a sort of mechanical polyalphabetic cipher. The operator of the Enigma machine would be given a message in plaintext and then type that message into Enigma. For each letter that was typed in, Enigma would provide a different ciphertext based on a different substitution alphabet. The recipient would type in the ciphertext, getting out the plaintext, provided both Enigma machines had the same rotor settings.

There were actually several variations of the Enigma machine. The Naval Enigma machine was eventually cracked by British cryptographers working at the now famous Bletchley Park. Alan Turing and a team of analysts were able to eventually break the Naval Enigma machine. Many historians claim this shortened World War II by as much as two years. This story is the basis for the 2014 movie The Imitation Game.

1 1 0 1
1 0 0 1
-------
1 0 0 1

1 1 0 1
1 0 0 1
-------
1 1 0 1

1 1 0 1
1 0 0 1
-------
0 1 0 0

XORing has a an interesting property in that it is reversible. If you XOR the resultant number with the second number, you get back the first number. And, if you XOR the resultant number with the first number, you get the second number.

0 1 0 0
1 0 0 1
-------
1 1 0 1

Binary encryption using the XOR operation opens the door for some rather simple encryption. Take any message and convert it to binary numbers and then XOR that with some key. Converting a message to a binary number is a simple two-step process. First, convert a message to its ASCII code, and then convert those codes to binary numbers. Each letter/number will generate an eight-bit binary number. You can then use a random string of binary numbers of any given length as the key. Simply XOR your message with the key to get the encrypted text, and then XOR it with the key again to retrieve the original message.

This method is easy to use and great for computer science students; however, it does not work well for truly secure communications because the underlying letter and word frequency remains. This exposes valuable clues that even an amateur cryptographer can use to decrypt the message. Yet, it does provide a valuable introduction to the concept of single-key encryption, which is discussed in more detail in the next section. Although simply XORing the text is not the method typically employed, single-key encryption methods are widely used today. For example, you could simply include a multi-alphabet substitution that was then XORed with some random bit stream—variations of which do exist in a few actual encryption methods currently used.

Modern cryptography methods, as well as computers, make decryption a rather advanced science. Therefore, encryption must be equally sophisticated in order to have a chance of success.

What you have seen so far regarding encryption is simply for educational purposes. As has been noted several times, you would not have a truly secure system if you implemented any of the previously mentioned encryption schemes. You might feel that this has been overstated in this text. However, having an accurate view of what encryption methods do and do not work is critical. It is now time to discuss a few methods that are actually in use today.

The following websites offer more information about cryptography:

Cryptography I course on Coursera: https://www.coursera.org/course/crypto

Applied cryptography course on Udacity: https://www.udacity.com/course/applied-cryptography--cs387

Cypher Research Laboratories: www.cypher.com.au/crypto_history.htm

Understanding the simple methods described here and other methods provided by the aforementioned websites should give you a sense of how cryptography works as well as what is involved in encrypting a message. Regardless of whether you go on to study modern, sophisticated encryption methods, having some basic idea of how encryption works at a conceptual level is important. Having a basic grasp of how encryption works, in principle, will make you better able to understand the concepts of any encryption method you encounter in the real world.

In some cases the algorithm behind these methods requires a sophisticated understanding of mathematics. Number theory often forms the basis for encryption algorithms. Fortunately for our purposes having the exact details of these encryption algorithms is not important; this means that you don’t require a strong mathematics background to follow this material. More important is a general understanding of how a particular encryption method works and how secure it is.

1. The data is divided into 64-bit blocks, and those blocks are then transposed.

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

3. Finally, the data is transposed one last time.

More information about DES is available at the Federal Information Processing Standards website at https://csrc.nist.gov/csrc/media/publications/fips/46/3/archive/1999-10-25/documents/fips46-3.pdf. A more detailed description of DES is given below, but you can skip this if you wish.

DES uses a 56-bit cipher key applied to a 64-bit block. There is actually a 64-bit key, but one bit of every byte is actually used for error detection, leaving just 56 bits for actual key operations.

DES is a Feistel cipher with 16 rounds and a 48-bit round key for each round. A round key is just a sub key that is derived from the cipher key each round, according to a key schedule algorithm. DES’s general functionality follows the Feistel method of dividing the 64-bit block into two halves (32 bits each; this is not an unbalanced Feistel cipher), applying the round function to one half, then XORing that output with the other half.

The first issue to address is the key schedule. How does DES generate a new sub key each round? The idea is to take the original 56-bit key and to slightly permute it each round, so that each round is applying a slightly different key, but one that is based on the original cipher key. To generate the round keys, the 56-bit key is split into two 28-bit halves and those halves are circularly shifted after each round by one or two bits. This will provide a different sub key each round. During the round key generation portion of the algorithm (recall that this is referred to as the key schedule) each round, the two halves of the original cipher key (the 56 bits of key the two endpoints of encryption must exchange) are shifted a specific amount.

Once the round key has been generated for the current round, the next step is to address the half of the original block that is going to be input into the round function. Recall that the two halves are each 32 bits. The round key is 48 bits. That means that the round key does not match the size of the half block it is going to be applied to. You cannot really XOR a 48-bit round key with a 32 bit half block, unless you simply ignore 16 bits of the round key. If you did so, you would basically be making the round key effectively shorter and thus less secure, so this is not a good option.

The 32-bit half needs to be expanded to 48 bits before it is XORed with the round key. This is accomplished by replicating some bits so that the 32-bit half becomes 48 bits.

This expansion process is actually quite simple. The 32 bits that is to be expanded is broken into 4-bit sections. The bits on each end are duplicated. If you divide 32 by 4 the answer is 8. So there are eight of these 4-bit groupings. If you duplicate the end bits of each grouping, that will add 16 bits to the original 32, thus providing a total of 48 bits.

It is also important to keep in mind that it was the bits on each end that were duplicated; this will be a key item later in the round function. Perhaps this example will help you to understand what is occurring at this point. Let us assume 32 bits as shown here:

11110011010111111111000101011001

Now divide that into eight sections each of 4 bits, as shown here:

1111 0011 0101 1111 1111 0001 0101 1001

Now each of these has its end bits duplicated, as you see here:

1111 becomes 111111

0011 becomes 000111

0101 becomes 001011

1111 becomes 111111

1111 becomes 111111

0001 becomes 000011

0101 becomes 001011

1001 becomes 110011

The resultant 48-bit string is now XORed with the 48-bit round key. That is the extent of the round key being used in each round. It is now dispensed with, and on the next round another 48-bit round key will be derived from the two 28-bit halves of the 56-bit cipher key.

Now we have the 48-bit output of the XOR operation. That is now split into eight sections of 6 bits each. For the rest of this explanation we will focus on just one of those 6-bit sections, but keep in mind that the same process is done to all eight sections.

The 6-bit section is used as the input to an s-box. An s-box is a table that takes input and produces an output based on that input. In other words, it is a substitution box that substitutes new values for the input. The s-boxes used in DES are published, the first of which is shown in Figure 6-1.

Notice this is simply a lookup table. The 2 bits on either end are shown in the left hand column and the 4 bits in the middle are shown in the top row. They are matched, and the resulting value is the output of the s-box. For example, with the previous demonstration numbers we were using, our first block would be 111111. So you find 1xxxx1 on the left and x1111x on the top. The resulting value is 13 in decimal or 1101 in binary.

At the end of this you have produced 32 bits that are the output of the round function. Then in keeping with the Feistel structure, they get XORed with the 32 bits that were not input into the round function, and the two halves are swapped. DES is a 16-round Feistel cipher, meaning this process is repeated 16 times.

There are only two parts still left to discuss regarding DES. The first is the initial permutation, called the IP, then the final permutation, which is an inverse of the IP.

One advantage that DES offers is efficiency. Some implementations of DES offer data throughput rates on the order of hundreds of megabytes per second. In plain English, what this means is that it can encrypt a great deal of data very quickly. You might assume that 16 steps would cause encryption to be quite slow; however, that is not the case using modern computer equipment. The problem with DES is the same problem that all symmetric key algorithms have: How do you transmit the key without it becoming compromised? This issue led to the development of public key encryption.

Another advantage of DES is the complexity with which it scrambles the text. DES uses 16 separate rounds to scramble the text. This yields a scrambled text that is very difficult to break. DES is no longer used, because the short key size is no longer adequate against brute force attacks. However, the overall structure, called a Feistel network or Feistel cipher, is the basis for many algorithms that are still used today, such as Blowfish.

As has been mentioned, DES uses a key that is no longer considered long enough. Modern computers can brute-force crack a 56-bit key. The algorithm used in DES is actually quite good. It was the first widely used Feistel structure, and that structure is still a good basis for block ciphers.

As computers became more powerful, the search began for a DES replacement. Ultimately, the Rijndael cipher would be used for the Advanced Encryption Standard (AES) and would replace DES. In the interim, the idea was to use multiple DES keys to encrypt. Ideally, three separate 56-bit keys were used, thus this interim solution was called triple-DES or 3DES. In some cases only two DES keys were used, and the algorithm alternated applying them.

AES specifies three key sizes: 128, 192, and 256 bits. By comparison, DES keys are 56 bits long, and Blowfish allows varying lengths up to 448 bits. AES uses a block cipher. Interested readers can find detailed specifications for this algorithm, including a detailed discussion of the mathematics, at https://csrc.nist.gov/csrc/media/publications/fips/197/final/documents/fips-197.pdf.

This algorithm is widely used (as shown in the firewall discussion in Chapter 4, “Firewall Practical Applications”), considered very secure, and therefore a good choice for many encryption scenarios.

For those readers who want more detail, here is a general overview of the process used in AES. The algorithm consists of a few relatively simple steps that are used during various rounds. The steps are described here:

AddRoundKey: Each byte of the state is combined with the round key using bitwise XOR. This is where Rijndael applies the round key generated from the key schedule.

SubBytes: A nonlinear substitution step where each byte is replaced with another according to a lookup table. This is where the contents of the matrix are put through the s-boxes. Each of the s-boxes is 8 bits.

ShiftRows: A transposition step where each row of the state is shifted cyclically a certain number of steps. In this step the first row is left unchanged. Every byte in the second row is shifted one byte to the left (with the far left wrapping around). Every byte of the third row is shifted two to the left, and every byte of the fourth row is shifted three to the left (again with wrapping around).

MixColumns: A mixing operation which operates on the columns of the state, combining the 4 bytes in each column. In the MixColumns step, each column of the state is multiplied with a fixed polynomial.

With the aforementioned steps in mind, this is how those steps are executed in the Rijndael cipher. For 128-bit keys, there are 10 rounds. For 192-bit keys, there are 12 rounds. For 256-bit keys, there are 14 rounds.

Key Expansion: The first step is that the round keys are derived from the cipher key using Rijndael’s key schedule. The key schedule is how a key is generated for each round, based on the cryptographic key that was exchanged between the sender and receiver.

Initial Round: This initial round will only execute the AddRoundKey step. This is simply XORing with the round key. This initial round is executed once, then the subsequent rounds will be executed.

Rounds: This phase of the algorithm executes several steps, in the following order:

SubBytes

ShiftRows

MixColumns

AddRoundKey

Final Round: This round has everything the rounds phase has, except no MixColumns:

SubBytes

ShiftRows

AddRoundKey

In the AddRoundKey step, the sub-key is XORed with the state. For each round, a sub-key is derived from the main key using Rijndael’s key schedule; each sub-key is the same size as the state.

The 128-bit key is split into eight 16-bit keys, which are the first eight sub-keys.

The digits of the 128-bit key are shifted 25 bits to the left to make a new key, which is then split into the next eight 16-bit sub-keys.

The second step is repeated until the 52 sub-keys have been generated. The encryption consists of eight rounds of encrypting.

If you encrypt large amounts of data, then speed of the encryption might be almost as important as security.

If you have standard business data, then almost any of the well-known, accepted encryption methods will probably be secure enough, and you can focus on things such as key length and speed in your decision-making process. However, if you are sending highly sensitive data, such as research or military data, you should be more concerned about security, even at the expense of speed.

Variable-length keys are important only if you need them. If you have some encryption products used inside the United States and some outside, then at least two lengths are needed. If you have some data you want more strongly encrypted even if it means slower speed, and other data that needs to be fast but not as secure, then a variable-length key is also important.

PBKDF2 (Password-Based Key Derivation Function 2) is part of PKCS #5 v. 2.01. It applies some function (like a hash or HMAC) to the password or passphrase along with salt to produce a derived key. (The salt concept is discussed later, in the “Hashing” section.)

bcrypt is used with passwords, and it essentially uses a derivation of the Blowfish algorithm, converted to a hashing algorithm, to hash a password and add salt to it.

Uncorrelated sequences: The sequences are not correlated. You cannot take a given stretch of numbers (say 16 bits) and use that to predict subsequent bits.

Long period: Ideally, the series of digits (usually bits) should never have any repeating patterns. However, the reality is that there will eventually be some repetition. The distance (in digits or bits) between repetitions is the period. The longer the period the better.

Uniformity: Pseudo-random numbers are usually represented in binary format. There should be an equal number of 1s and 0s, though they need not be distributed in any discernible pattern. The sequence of random numbers should be uniform and unbiased.

The German Federal Office for Information Security (BSI) has established four criteria for quality of random number generators:

K1: A sequence of random numbers with a low probability of containing identical consecutive elements.

K2: A sequence of numbers that is indistinguishable from “true random” numbers according to specified statistical tests.

K3: It should be impossible for any attacker to calculate, or otherwise guess, from any given sub-sequence, or from any previous or future values in the sequence.

K4: It should be impossible for an attacker to calculate, or guess from an inner state of the generator, any previous numbers in the sequence or any previous inner generator states.

One significant advantage of RSA is that it is a public key encryption method. That means there are no concerns with distributing the keys for the encryption. However, RSA is much slower than symmetric ciphers. In fact, in general, asymmetric ciphers are slower than symmetric ciphers.

The steps to create the key are as follow:

1. Generate two large random primes, p and q, of approximately equal size.

2. Pick two numbers so that when they are multiplied together the product will be the size you want (that is, 2048 bits, 4096 bits, etc).

3. Now multiply p and q to get n.

4. Let n = pq.

5. Multiply Euler’s totient for each of these primes. If you are not familiar with this concept, the Euler’s Totient is the total number of co-prime numbers. Two numbers are considered co-prime if they have no common factors. For example, if the original number is 7, then 5 and 7 would be co-prime. It just so happens that for prime numbers, this is always the number minus 1. For example, 7 has 6 numbers that are co-prime to it (if you think about this a bit you will see that 1, 2, 3, 4, 5, 6 are all co-prime with 7).

6. Let m = (p – 1)(q – 1).

7. Select another number; call this number e. You want to pick e so that it is co-prime to m.

8. Find a number d that when multiplied by e and modulo m would yield 1. (Note: Modulo means to divide two numbers and return the remainder. For example, 8 modulo 3 would be 2.)

9. Find d, such that de mod m ≡ 1.

Now you publish e and n as the public key and keep d and n as the secret key.

To encrypt you simply take your message raised to the e power and modulo n:

= Me % n

To decrypt you take the ciphertext, and raise it to the d power modulo n:

P = Cd % n

If all this seems a bit complex to you, you must realize that many people work in network security without being familiar with the actual algorithm for RSA (or any other cryptography for that matter). You can also get a better understanding of RSA by walking through the algorithm utilizing small integers.

Normally RSA is done with very large integers. To make the math easy to follow, this example uses small integers (Note: This example is from Wikipedia):

1. Choose two distinct prime numbers, such as p = 61 and q = 53.

2. Compute n = pq giving n = 61 × 53 = 3233.

3. Compute the totient of the product as Φ(n) = (p − 1)(q − 1) giving Φ(3233) = (61 − 1)(53 − 1) = 3120.

4. Choose any number 1 < e < 3120 that is co-prime to 3120. Choosing a prime number for e leaves us only to check that e is not a divisor of 3120. Let e = 17.

5. Compute d, as shown before such that de mod m ≡ 1; yielding d = 2753.

6. The public key is (n = 3233, e = 17). For a padded plaintext message m, the encryption function is m¹⁷ (mod 3233).

7. The private key is (n = 3233, d = 2753). For an encrypted ciphertext c, the decryption function is c²⁷⁵³ (mod 3233).

RSA is based on large prime numbers. You might think, “Couldn’t someone take the public key and use factoring to derive the private key?” Well, hypothetically, yes. However, it turns out that factoring really large numbers into their prime factors is pretty difficult. No efficient algorithm exists for doing it. By “large numbers,” we mean that RSA can use 1024-, 2048-, 4096-bit and larger keys. Those make for some huge numbers. Of course, if anyone ever invents an efficient algorithm that will factor a large number into its prime factors, RSA would be dead.

RSA has become a popular encryption method. It is considered quite secure and is often used in situations where a high level of security is needed.

This cryptographic protocol allows two parties to establish a shared key over an insecure channel. In other words, Diffie-Hellman is often used to allow parties to exchange a symmetric key through some unsecure medium, such as the Internet. It was developed by Whitfield Diffie and Martin Hellman in 1976. An interesting factoid is that the method had actually been developed a few years earlier by Malcolm J. Williamson of the British Intelligence Service, but it was classified.

The security of Elliptic Curve cryptography is based on the fact that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is difficult to the point of being impractical to do.

The size of the elliptic curve determines the difficulty of the finding the algorithm, and thus the security of the implementation. The level of security afforded by an RSA-based system with a large modulus can be achieved with a much smaller elliptic curve group. There are actually several ECC algorithms. There is an ECC version of Diffie-Hellman, an ECC version of DSA, and many others.

The U.S. National Security Agency has endorsed ECC (Elliptic Curve Cryptography) by including schemes based on it in its Suite B set of recommended algorithms and allows their use for protecting information classified up to top secret with 384-bit keys.

Some part of the message, often a hash of the message, is encrypted (or signed) with the user’s private key. Of course, because anyone can access that sender’s public key, this process does nothing for confidentiality. But any recipient can verify the signature using the sender’s public key, and be confident the sender really sent the message.

Although no guaranteed way to detect fraud exists, the following guidelines should help you avoid most fraudulent encryption claims:

“Unbreakable”: Anyone with any experience in cryptography knows that there is no such thing as an unbreakable code. Codes exist that have not yet been broken. Some codes are very hard to break. However, when someone claims that his method is completely unbreakable, you should be suspicious.

“Certified”: No recognized certification process for encryption methods exists, so any “certification” the company has is totally worthless.

Inexperienced vendors: Find out about the experience of any company marketing a new encryption method. What is the experience of the people working with it? Do they have a background in math, encryption, or algorithms? If not, have they submitted their method to experts in peer-reviewed journals? Are they at least willing to disclose how their method works so that it can be fairly judged?

Some experts claim you should only use widely known methods such as Blowfish. I disagree. Having a secure system using less well-known or even new encryption methods is certainly possible. All the widely used methods of today were once new and untested. However, taking extra precautions to ensure that you are not being misled when using a less well-known method is necessary. To be clear, I am not in any way suggesting untested algorithms. For example, when the NIST had the contest that ended with selecting the Rijndael cipher to be AES, there were four other finalist algorithms that had been rigorously tested, but were rejected, some for performance issues. Those might be good algorithms to consider.

X.509 is an international standard for the format and information contained in a digital certificate. X.509 is the most used type of digital certificate in the world. It is a digital document that contains a public key signed by the trusted third party, which is known as a certificate authority (CA). The contents of an X.509 certificate are

Version

Certificate holder’s public key

Serial number

Certificate holder’s distinguished name

Certificate’s validity period

Unique name of certificate issuer

Digital signature of issuer

Signature algorithm identifier

A certificate authority issues digital certificates. The primary role of the CA is to digitally sign and publish the public key bound to a given user. It is an entity trusted by one or more users to manage certificates.

A registration authority (RA) is often used to take the burden off of a CA by handling verification prior to certificates being issued. RAs act as a proxy between users and CAs. RAs receive a request, authenticate it, and forward it to the CA.

A public key infrastructure (PKI) distributes digital certificates. This is a network of trusted CA servers that serves as the infrastructure for distributing digital certificates that contain public keys. A PKI is an arrangement that binds public keys with respective user identities by means of a CA.

What if a certificate is expired, or revoked? A certificate revocation list (CRL) is a list of certificates that have been revoked for one reason or another. Certificate authorities publish their own certificate revocation lists. A newer method for verifying certificates is Online Certificate Status Protocol (OSCP), a real-time protocol for verifying certificates.

There are several different types of X.509 certificates. They each have at least the elements listed at the beginning of this section, but are for different purposes. The most common certificate types are listed here.

Domain validation certificates are among the most common. These are used to secure communication with a specific domain. This is a low-cost certificate that website administrators use to provide TLS for a given domain.

Wildcard certificates, as the name suggests, can be used more widely, usually with multiple sub-domains of a given domain. So rather than have a different X.509 certificate for each sub-domain, you would use a wildcard certificate for all sub-domains.

Code-signing certificates are X.509 certificates used to digitally sign some type of computer code. These usually require more validation of the person requesting the certificate, before they can be issued.

Machine/computer certificates are X.509 certificates assigned to a specific machine. These are often used in authentication protocols. For example, in order for the machine to sign into the network, it must authenticate using its machine certificate.

User certificates are used for individual users. Like machine/computer certificates, these are often used for authentication. The user must present his or her certificate to authenticate prior to accessing some resource.

E-mail certificates are used for securing e-mail. Secure Multipurpose Internet Mail Extensions (S/MIME) uses X.509 certificates to secure e-mail communications. PGP, of course, uses PGP certificates.

A Subject Alternative Name (SAN) is not so much a type of certificate as a special field in X.509. It allows you to specify additional items to be protected by this single certificate. These could be additional domains or IP addresses.

Root certificates are used for root authorities. These are usually self-signed by that authority.

PGP uses its own certificate format. The main difference, however, is that PGP certificates are self-generated. They are not generated by any certificate authority.

Variable length input with fixed length output. In other words, no matter what you put into the hashing algorithm, the same sized output is produced.

H(x) is one-way; you cannot “un-hash” something.

H(x) is collision-free. Two different input values do not produce the same output. A collision refers to a situation where two different inputs yield the same output. A hash function should not have collisions.

Hashing is how Windows stores passwords. For example, if your password is “password,” then Windows will first hash it, producing something like:

Click here to view code image

0BD181063899C9239016320B50D3E896693A96DF

It then stores that hash in the SAM (Security Accounts Manager) file in the Windows System directory. When you log on, Windows cannot “un-hash” your password, so 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.

Storing Windows passwords is just one application of hashing. There are others. For example, in computer forensics, hashing a drive before starting a forensic examination is common practice. Then later you can always hash it again to see whether anything was changed (accidently or intentionally). If the second hash matches the first, then nothing has been changed.

In relationship to hashing, the term salt refers to random bits that are used as one of the inputs to the hash. Essentially, the salt is intermixed with the message that is to be hashed. Salt data complicates dictionary attacks that use pre-encryption of dictionary entries. It also is effective against rainbow table attacks. For best security, the salt value is kept secret, separate from the password database/file.

SHA-1: This 160-bit hash function resembles the MD5 algorithm. This was designed by the National Security Agency (NSA) to be part of the Digital Signature Algorithm.

SHA-2: This is actually two similar hash functions, with different block sizes, known as SHA-256 and SHA-512. They differ in the word size; SHA-256 uses 32-byte (256 bits) words whereas SHA-512 uses 64-byte (512 bits) words. There are also truncated versions of each standard, known as SHA-224 and SHA-384. These were also designed by the NSA.

SHA-3: This is the latest version of SHA. It was adopted in October of 2012.

RIPEMD-160 was developed in Europe as part of RIPE project and is recommended by the German Security Agency. The authors of the algorithm describe RIPEMD as follows: “RIPEMD-160 is a fast cryptographic hash function that is tuned towards software implementations on 32-bit architectures. It has evolved from the 256-bit extension of MD4, which was introduced in 1990 by Ron Rivest. Its main design features are two different and independent parallel chains, the result of which are combined at the end of every application of the compression function.” To read the authors’ full explanation of RIPEMD-160, see www.esat.kuleuven.be/cosic/publications/article-317.pdf.

Decryption is a science much like encryption. It employs various mathematical methods to crack encryption. You can find a number of utilities on the web that will actually crack encryption for you. As discussed earlier, no such thing exists as unbreakable encryption. However, the more secure an encryption technique is, the longer it will take to crack. If it takes months or years of dedicated effort to crack, then your data is secure. By the time someone cracks it, the information will likely no longer be relevant or useful to them.

Security professionals and security-savvy network administrators frequently use the same tools to inspect their systems that hackers use to try to break into them. Using the tools of hackers to try to crack an encryption method is a practical and straightforward way of testing data security.

This product is completely command line–based and has no Windows interface. It enables the user to select text files for word lists to attempt cracking a password. Although John the Ripper is less convenient to use because of its command-line interface, it has been around for a long time and is well regarded by both the security and hacking communities. Interestingly, a tool is available at www.openwall.com/passwdqc/ that ensures your passwords cannot easily be cracked by John the Ripper.

John the Ripper works with password files rather than attempting to crack live passwords on a given system. Passwords are usually encrypted and in a file on the operating system. Hackers frequently try to get that file off of a machine and download it to their own system so they can crack it at will. They might also look for discarded media in your dumpster in order to find old backup tapes that might contain password files. Each operating system stores that file in a different place:

In Linux, it is /etc/passwd.

In Windows 95, it is in a .pwl file.

In Windows 2000 and beyond, it is in a hidden .sam file.

After you have downloaded John the Ripper, you can run it by typing in (at a command line) the word john followed by the file you want it to try to crack:

john passwd

To make it use a wordlist with rules only, type:

Click here to view code image

john -wordfile:/usr/dict/words -rules passwd

Cracked passwords will be printed to the terminal and saved in a file called john.pot, found in the directory into which you installed John the Ripper.

Russian password crackers: www.password-crackers.com/crack.html

Password recovery: www.elcomsoft.com/prs.html

LastBit password recovery: http://lastbit.com/mso/Default.asp

Password crackers should be used only by administrators to test their own systems’ defenses. Attempting to crack another person’s password and infiltrate her system has both ethical and legal ramifications.

A determined cryptanalyst looks for these types of patterns and, over time, may be able to deduce the method used to encrypt the data. This process can sometimes be simple, or it may take a lot of effort. This method works only on the historical ciphers we discussed at the beginning of this chapter. It does not work on modern algorithms.

Obviously, if you put 367 people in a room, at least 2 of them must have the same birthday, since there are only 365 days in a year, plus one more in a leap year.

The paradox is not asking how many people you need to guarantee a match, just how many you need to have a strong probability.

Even with 23 people in the room, you have a 50 percent chance that 2 will have the same birthday.

The probability that the first person does not share a birthday with any previous person is 100 percent, because there are no previous people in the set. That can be written as 365/365.

The second person has only one preceding person, and the odds that the second person has a birthday different from the first are 364/365.

The third person might share a birthday with two preceding people, so the odds of having a birthday from either of the two preceding people are 363/365. Because each of these are independent, we can compute the probability as follows:

365/365 × 364/365 × 363/365 * 362/365 … × 342/365

(342 is the probability the 23rd person shares a birthday with a preceding person.) When we convert these to decimal values, it yields (truncating at the third decimal point):

1 × 0.997 × 0.994 × 0.991 × 0.989 × 0.986 × … 0.936 = 0.49, or 49 percent

This 49 percent is the probability that 23 people will not have any birthdays in common; thus, there is a 51 percent (better than even odds) chance that 2 of the 23 will have a birthday in common.

The math works out to about 1.7 √n to get a collision. Remember a collision is when two inputs produce the same output. So for an MD5 hash, you might think you need 2¹²⁸ + 1 different inputs to get a collision. And for a guaranteed collision you do. That is an exceedingly large number: 3.4028236692093846346337460743177e+38. But the birthday paradox tells us that to just have a 51 percent chance of there being a hash, you only need 1.7 √n (n being 2¹²⁸) inputs. That number is still very large: 31,359,464,925,306,237,747.2. But it is much smaller than the effort of trying every single input!

The attack is based on seeing pairs of plaintext inputs that are related by some constant difference. The usual way to define the differences is via XOR operation, but other methods can be used. The attacker computes the differences in the resulting ciphertexts and is looking for some statistical pattern. The resulting differences are called the differential. Put another way, differential cryptanalysis focuses on finding a relationship between the changes that occur in the output bits as a result of changing some of the input bits.

Remember cryptanalysis is an attempt to crack cryptography. For example, with the 56-bit DES key, brute force could take up to 2⁵⁶ attempts. Linear cryptanalysis will take 2⁴⁷ known plaintexts.¹ This is better than brute force, but still impractical for most situations.

The advantage of steganography, over cryptography alone, is that messages do not attract attention to themselves. If no one is aware the message is even there, then they won’t even try to decipher it. In many cases messages are encrypted and hidden via steganography.

The most common implementation of steganography utilizes the least significant bits in a file in order to store data. By altering the least significant bit, one can hide additional data without altering the original file in any noticeable way.

Here are some basic steganography terms you should know:

Payload is the data to be covertly communicated. In other words, it is the message you want to hide.

The carrier is the signal, stream, or data file into which the payload is hidden.

The channel is the type of medium used. This might be still photos, video, or sound files.

Although the use of digital steganography is obviously rather recent, the concept of hiding messages is not. Here are some instances of historical hidden messages:

The ancient Chinese wrapped notes in wax and swallowed them for transport.

In ancient Greece a messenger’s head might be shaved, a message written on his head, then his hair was allowed to grow back.

In the early 1500s Johannes Trithemius wrote a book on cryptography and described a technique where a message was hidden by having each letter taken as a word from a specific column.

In more recent times, but before the advent of computers, other methods were used to hide messages:

During WWII the French Resistance sent messages written on the backs of couriers using invisible ink.

Microdots are images/undeveloped film the size of a typewriter period, embedded on innocuous documents. These were said to be used by spies during the Cold War.

The most common way steganography is accomplished today is via least significant bits. Every file has a certain number of bits per unit of the file. For example, an image file in Windows is 24 bits per pixel. If you change the least significant of those bits, then the change is not noticeable with the naked eye. For example, one can hide information in the least significant bits of an image file. With least significant bit (LSB) replacement, certain bits in the carrier file are replaced.

Steganophony is a term for hiding messages in sound files. This can be done with the LSB method or other methods, such as echo hiding, which adds extra sound to an echo inside an audio file—that extra sound conceals information.

Information can also be hidden in video files. Various methods to accomplish this exist. Discrete Cosine Transform is often used for video steganography. This method alters values of certain parts of the individual frames. The usual method is to round up the values.

A number of tools are available for implementing steganography. Many are free or at least have a free trial version. A few of these tools are listed here:

QuickStego: Easy to use but very limited

Invisible Secrets: Much more robust with both a free and commercial version

MP3Stego: Specifically for hiding payload in MP3 files

Stealth Files 4: Works with sound files, video files, and image files

SNOW: Hides data in whitespace

Several methods exist for analyzing an image to detect hidden messages, one of which is the Raw Quick Pair (RQP) method. This is based on statistics of the numbers of unique colors and close-color pairs in a 24-bit image. RQP analyzes the pairs of colors created by LSB embedding.

Another option uses the chi-squared method from statistics. Chi-square analysis calculates the average LSB and builds a table of frequencies and pair of values. It then performs a chi-square test on these two tables. Essentially, it measures the theoretical versus the calculated population difference.

Steganalysis of audio files involves examining noise distortion in the carrier file. Noise distortion could indicate the presence of a hidden signal.

The essential issue with quantum computing is the ability to represent more than two states. Current computing technology, using classical bits, can only represent binary values. Qubits, or quantum bits, store data via the polarization of a single photon. The two basic states are horizontal or vertical polarization. However, quantum mechanics allows for a superposition of the two states at the same time. This is something simply not possible in a classical bit. The two states of a qubit are represented with quantum notation as |0> or |1>. These represent horizontal or vertical polarization. A qubit is the superposition of these two basis states. This superposition is represented as | ψ > = α|0> + β|1>.

Essentially a classical bit can represent a one or a zero. A qubit can represent a one, a zero, or any quantum superposition of those two qubit states. This superposition allows for much more powerful computing. The superposition allows the qubit to store a one, a zero, both a one and a zero, or an range of values between one and zero. This significantly increases data storage and data processing power.

There are already quantum based algorithms that are far superior at factoring large numbers than are classical algorithms. That is a critical issue because the widely used RSA algorithm is based on the difficulty of factoring a large number into its prime factors. When quantum computers become a reality, that factoring problem will no longer be difficult, and RSA will be obsolete. Various key exchange algorithms such as Diffie-Hellman depend on the difficulty in solving the discrete logarithm problem. The two most significant improvements to Diffie-Hellman, ElGamal, and MQV (Menezes-Qu-Vanstone) also depend on the discrete logarithm problem. Elliptic curve cryptography is based on the difficulty of solving the discrete logarithm problem with respect to an elliptic curve. Quantum algorithms will also make the discrete logarithm problem quite solvable, thus rendering these algorithms obsolete as well.

Essentially all current asymmetric cryptography is based on one of these two general classes of number theoretic problems: factoring or solving the discrete logarithm problem. Essentially, when quantum computers become a practical reality, rather than just a research interest, all modern asymmetric algorithms will become obsolete. This is a significant concern for cyber security because all modern e-commerce, encrypted e-mail, and secure communications over a network depend on these algorithms. Currently, the NIST is working on a multi-year study to determine standards for post-quantum cryptography. And there are several promising cryptographic systems. It is beyond the scope of this chapter to explore quantum cryptography in depth; however, lattice based cryptography and multi-variate cryptography look to be good candidates for post quantum computing cryptographic systems.