Cryptography basics: Symmetric key encryption algorithms

Single-Key (Symmetric) Encryption

Basically, single-key encryption means that the same key is used to both encrypt and decrypt a message. This is also referred to as symmetric key encryption. There are two types of symmetric algorithms (or ciphers): stream and block. A block cipher divides the data into blocks (often 64-bit blocks, but newer algorithms sometimes use 128-bit blocks) and encrypts the data one block at a time. Stream ciphers encrypt the data as a stream of bits, one bit at a time.

Data Encryption Standard

Click to learn more about
Computer Security Fundamentals
by Chuck Easttom.

Data Encryption Standard, or DES, was developed by IBM in the early 1970s and published in 1976. Yes, it is old, and it is no longer considered secure; however, it is worthy of study for two reasons. The first reason is that DES was the first modern symmetric cipher. The second reason is that the general structure, often called a Feistel function or Feistel cipher, is still used in many modern algorithms. DES is a block cipher, which divides the plain text into 64-bit blocks and encrypts each block. The basic concept is as follows:

At the time DES was released, it was a marvelous invention. Even today the algorithm is still sound. However, the small key size, 56 bits, is not good enough to defend against brute-force attacks with modern computers. Many cryptography textbooks and university courses use DES as the basic template for studying all block ciphers. We will do the same and give this algorithm more attention than most of the others in this chapter.

For those new to security and cryptography, the brief facts listed earlier are enough. However, for those who want to delve a bit deeper, let's examine the details of the DES algorithm. DES uses a 56-bit cipher key applied to a 64-bit block. There is actually a 64-bit key, but 1 bit of every byte is used for error correction, 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. They are called Feistel ciphers (also Feistel functions) after Horst Feistel, the inventor of the concept, and the primary inventor of DES. All Feistel ciphers work in the same way: They divide the block into two halves, apply a round function to one of those halves, and then swap the halves. This is done each round. The primary difference between different Feistel ciphers is what exactly occurs within the round function.

The first issue to address is the key schedule. A key schedule, which all block ciphers use, is a simple algorithm that will take the initial key the two parties derived and generate from that a slightly different key each round. DES does this by taking the original 56-bit key and slightly permuting 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 1 or 2 bits to provide a different subkey 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 that the two endpoints of encryption must exchange) are shifted a specific amount. The end result is that for each of the 16 rounds of DES, the key is actually a little different from the key used in the previous round. All modern symmetric ciphers do something like this to improve the security of the cipher.

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. This 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 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 are to be expanded are 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 8 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 understand what is occurring at this point. Let us assume 32 bits, as shown here:

11110011010111111111000101011001

Now divide this into 8 sections of 4 bits each, 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 resulting 48-bit string is now XORed with the 48-bit round key. Now you are done with the round key. Its only purpose was to XOR with the 32-bit half. It is now discarded, 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, using the key schedule we previously described.

Now we have the 48-bit output of the XOR operation. But this still does not seem to work. Don't we need 32 bits rather than 48? That 48 bits is now split into 8 sections of 6 bits each. Each of those 6-bit sections is going to be input into an s-box (substitution box), and only 4 bits will be output.

The 6-bit section is used as the input to an s-box, which 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. There are eight different s-boxes for DES, but below you can see one of them:

An s-box is really just a hard-coded lookup table. The 2 bits on either end are shown in the left 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 3 in decimal, or 0011 in binary.

Recall that during the expansion phase we simply duplicated the outermost bits, so when we come to the s-box phase and drop the outermost bits, no data is lost.

Since each s-box outputs 4 bits and there are 8 s-boxes, the result is 32 bits. That 32 bits is now exclusively ORed with the other half of the original block. Recall that we did nothing with that half originally. Now the two halves are swapped.

If you are new to cryptography, all of this might seem a bit confusing, even with the explanations provided. Many readers will need to reread this section a few times for it to become totally clear.

3DES

Triple DES (3DES) was created as a replacement for DES. At the time, the cryptography community was searching for a viable alternative. While that was still being worked on, 3DES was created as a stop-gap measure. It essentially applies DES three times with three different keys, thus the name 3DES.

There were variations of 3DES that used only two keys. The text was first encrypted with key A. The cipher text from that operation was then encrypted with key B. Then the cipher text from that operation was encrypted, this time reusing key A. The reason for this reuse is that creating good cryptographic keys is computationally intensive.

AES

Advanced Encryption Standard (AES) was the algorithm eventually chosen to replace DES. It is a block cipher that works on 128-bit blocks. It can have one of three key sizes: 128, 192, or 256 bits. The U.S. government selected AES to be the replacement for DES, and it is now the most widely used symmetric key algorithm.

AES, also known as Rijndael block cipher, was officially designated as a replacement for DES in 2001 after a 5-year process involving 15 competing algorithms. AES is designated as FIPS 197. Other algorithms that did not win that competition include such well-known algorithms as Twofish. The importance of AES cannot be overstated. It is widely used around the world and is perhaps the most widely used symmetric cipher. Of all the algorithms in this chapter, AES is the one you should give the most attention to.

As mentioned earlier, AES can have three different key sizes: 128, 192, and 256 bits. The three different implementations of AES are referred to as AES 128, AES 192, and AES 256. The block size can also be 128, 192, or 256 bit. It should be noted that the original Rijndael cipher allowed for variable block and key sizes in 32-bit increments. However, the U.S. government uses these three key sizes with a 128-bit block as the standard for AES.

This algorithm was developed by two Belgian cryptographers, John Daemen and Vincent Rijmen. John Daeman is a Belgian cryptographer who has worked extensively on the cryptanalysis of block ciphers, stream ciphers, and cryptographic hash functions. For those new to security, the brief description given so far is sufficient. However, we will explore the AES algorithm in more detail. Just as with the details of DES, this may be a bit confusing to some readers at first glance and may require a few rereads.

Rijndael uses a substitution-permutation matrix rather than a Feistel network. The Rijndael cipher works by first putting the 128-bit block of plain text into a 4-byte-by-4-byte matrix, termed the state, that changes as the algorithm proceeds through its steps. The first step is to convert the plain text block into binary and then put it into a matrix, as shown in Figure 8.3.

Once you have the original plain text in binary, placed in the 4-byte-by-4-byte matrix, the algorithm consists of a few relatively simple processes that are used during various rounds. The processes are described here:

• AddRoundKey: In this process, each byte of the state is exclusively ORed with the round key. Just as with DES, there is a key schedule algorithm that slightly changes the key each round.
• SubBytes: This involves substitutions of the input bytes (which are the output from the AddRoundKey phase). This is where the contents of the matrix are put through the s-boxes. Each of the s-boxes is 8 bits.
• ShiftRows: This is a transposition step where each row of the state is shifted cyclically a certain number of steps. In this process, the first row is left unchanged. Every byte in the second row is shifted 1 byte to the left (and the far left wraps around). Every byte of the third row is shifted 2 to the left, and every byte of the fourth row is shifted 3 to the left (again with the far left wrapping around). This is shown in Figure 8.4. Notice that in this figure that the bytes are simply labeled by their row and then a letter, such as 1a, 1b, 1c, 1d.

• MixColumns: This is a mixing operation that operates on the columns of the state, combining the 4 bytes in each column. In the MixColumns process, each column of the state is multiplied with a fixed polynomial. Each column in the state (remember the matrix we are working with) is treated as a polynomial within the Galois field (2⁸). The result is multiplied with a fixed polynomial c(x) = 3x³ + x² + x +2 modulo x⁴ + 1. The MixColumns process can also be viewed as a multiplication by the shown particular MDS matrix in the finite field GF(2⁸).

These processes are executed multiple times 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.

These last few steps may be leaving you a bit confused if you don't have a background in number theory. You may be asking questions like "What is a Galois field?" and "What is a fixed polynomial?" A general overview of the math needed to understand this is provided in the next section.

AES Math

A group is an algebraic system consisting of a set, an identity element, one operation, and its inverse operation. Basically, groups are ways to limit math operations, such as addition, to specific sets of numbers. There are several specialized types of groups, briefly described here:

• An abelian group, or commutative group, has an additional axiom a + b = b + a if the operation is addition or ab = ba if the operation is multiplication.
• A cyclic group has elements that are all powers of one of its elements.
• A ring is an algebraic system consisting of a set, an identity element, two operations, and the inverse operation of the first operation.
• A field is an algebraic system consisting of a set, an identity element for each operation, two operations, and their respective inverse operations.

This brings us to the Galois group, or Galois field. GF(p) for any prime, p, this Galois field has p elements that are the residue classes of integers modulo p. That prime number p is the defining element for the field. Now, this is obviously a brief description and does not attempt to get into details. A thorough study of group theory would be needed to get into more detail.

Blowfish

Blowfish is a symmetric block cipher. It uses a variable-length key ranging from 32 to 448 bits. Blowfish was designed in 1993 by Bruce Schneier. It has been analyzed extensively by the cryptography community and has gained wide acceptance. It is also a noncommercial (free of charge) product, thus making it attractive to budget-conscious organizations.

RC4

All the other symmetric algorithms we have discussed have been block ciphers. RC4 is a stream cipher developed by Ron Rivest. RC is an acronym for Ron's Cipher, or sometimes Rivest's Cipher. There are other RC versions, such as RC5 and RC6.

Serpent

Serpent has a block size of 128 bits and can have a key size of 128, 192, or 256 bits, much like AES. The algorithm is also a substitution-permutation network (like AES). It uses 32 rounds working with a block of four 32-bit words. Each round applies one of eight 4-bit to 4-bit s-boxes 32 times in parallel. Serpent was designed so that all operations can be executed in parallel. This is one reason it was not selected as a replacement for DES. At the time it was created, many computers had difficulty with parallel processing. However, modern computers have no problem with parallel processing, so Serpent is once again an attractive choice.

Skipjack

Originally classified, the Skipjack algorithm was developed by the National Security Agency (NSA) for the clipper chip. The clipper chip was a chip with built-in encryption; however, the decryption key would be kept in a key escrow in case law enforcement needed to decrypt data without the computer owner's cooperation. This feature made the process highly controversial. Skipjack uses an 80-bit key to encrypt or decrypt 64-bit data blocks. It is an unbalanced Feistel network with 32 rounds. Unbalanced Feistel simply means a Feistel cipher wherein the two halves of plain text for each block are not the same size. For example, a 64-bit block might be divided into a 48-bit half and a 16-bit half rather than two 32-bit halves.

Modification of Symmetric Methods

Just as important as understanding symmetric ciphers is understanding how they are implemented. There are some common modes that can affect how a symmetric cipher functions.

Electronic Codebook

The most basic encryption mode is the electronic codebook (ECB) mode. With ECB, a message is divided into blocks, and each block is encrypted separately. The problem is that if you submit the same plain text more than once, you always get the same cipher text. This gives attackers a place to begin analyzing the cipher to attempt to derive the key. Put another way, ECB is simply using the cipher exactly as it is described, without attempting to improve its security.

Cipher Block Chaining

When using cipher block chaining (CBC) mode, each block of plain text is XORed with the previous cipher text block before being encrypted. This means there is significantly more randomness in the final cipher text, making it much more secure than electronic codebook mode. It is the most common mode.

There really is no good reason to use ECB over CBC if both ends of communication can support CBC. CBC is a strong deterrent to known plain text attacks, a cryptanalysis method we will examine later in this chapter.

The only issue with CBC is the first block. There is no preceding block of cipher text to XOR the first plain text block with. It is common to add an initialization vector (IV) to the first block so that it has something to be XORed with. The initialization vector is basically a pseudo-random number, much like the cipher key. Usually an IV is only used once, and it is thus called a nonce (for "number used only once"). The CBC mode is actually fairly old. It was introduced by IBM in 1976.

About the author

Chuck Easttom

Dr. Chuck Easttom is the author of 26 books, including several on computer security, forensics and cryptography. He has also authored scientific papers on digital forensics, cyberwarfare, cryptography and applied mathematics. He is an inventor with 16 computer science patents. He holds a doctorate of science in cybersecurity (dissertation topic: a study of lattice-based algorithms for post-quantum cryptography) and three master's degrees (one in applied computer science, one in education and one in systems engineering). He also holds 44 industry certifications (CISSP, CEH, etc.) He is a frequent speaker at cybersecurity, computer science and engineering conferences. He is a distinguished speaker and senior member of the Association for Computing Machinery and a senior member of the Institute of Electrical and Electronics Engineers. Dr. Easttom is also a reviewer for five scientific journals and editor in chief for the American Journal of Science & Engineering. You can find out more about Dr. Easttom and his research at his website.

http://www.pearsonitcertification.com/store/computer-security-fundamentals-9780135774779