Encryption: Most Common Algorithms

In Encryption: What Is It and How Does it Work? we promised the solution to the monoalphabetic substitution cipher. See below:

In this blog, we'll introduce some well-known symmetric encryption algorithms. The class of symmetric algorithms refers to the fact that each party involved must have access to the same key, and thus their information about the key is the same or symmetric. In our next blog, we will introduce asymmetric algorithms where the information about keys is not the same between all participants. Let's begin by examining a well-known, but now mostly retired, symmetric algorithm: DES.

The Data Encryption Standard (DES) is a symmetric encryption algorithm developed by IBM and standardized in 1977. Although it has been superseded by AES (which we examine next), the design choices of DES provide an excellent real-world example of key space issues. While a complete description of how these algorithms work is well outside of the scope of this article, let’s take a look at portions of their designs that exemplify important properties of symmetric encryption algorithms.

The DES algorithm operates on 64-bit blocks of input data and processes each block through a structure called a Feistel network (illustrated at right). As the algorithm operates on a fixed size input of 64-bit blocks, we will later need to introduce different modes of operation: methods for splitting larger inputs into blocks and combining the outputs to form the final ciphertext. As we will see, it is not as straightforward as simply concatenating the 64-bit ciphertexts corresponding to each block!

The plaintext input is first permuted, but since the permutation is fixed and publicly known it adds no security to the design – it was included only to slow down adversaries that lacked a hardware implementation of the algorithm.  It’s important to note that the security of modern encryption algorithms does not depend on the secrecy of any part of the algorithm. Instead, only the key is assumed to be unknown to the adversary. This important concept in modern cryptographic design is known as Kerckhoffs’ Principle.

The data is then split into a left (L0) and right (R0) half, with the right half being combined with a subkey K1 (derived from the main key by the algorithm). The right half and subkey are combined through a function “f”, highlighted in red.

Referred to as the Feistel function, f is an important component of what makes breaking DES a hard problem. Interestingly, we will see that unlike the general hard problem example f(x) from the start of the article, the Feistel function f in DES is actually not invertible! Instead, the invertibility property (the ability to decrypt with DES) comes from the Feistel network structure: running the network with the ciphertext blocks and subkeys in reverse order results in the original plaintext.

The structure of the Feistel function f (illustrated below) operates by combining the right 32 bits of data with the subkey K through an expansion and exclusive-or operator. This combined result is then divided into 8 blocks of 6 bits, each of which passes through a Substitution Box, or “S-box”. Each of these S-boxes implements a publicly known non-linear transformation, mapping 6-bit inputs to 4-bit outputs. The selection of each of these mappings is critical to the security of DES, and prior to standardization the NSA replaced the original mappings with their own. Widely believed to be malicious at the time, it was later revealed that the NSA’s mappings were resistant to an (at the time, publicly unknown) attack called differential cryptanalysis.

Unfortunately, not all of the NSA’s contributions to DES were as altruistic. The original design called for a 64-bit key, which was more than ample security in the 1970s. However, the NSA argued heavily for a much weaker 48-bit key, with the standard eventually settling on 56-bits. The public justification at the time was to use one bit of each byte as a parity bit (resulting in a "64-bit" key with only 56 meaningful bits) to validate whether or not the DES key was “valid”. Of course, attempting decryption with the wrong key would have accomplished the same goal. Today, 56-bit DES keys provide no security, and the DES algorithm should not be used. Instead, symmetric encryption algorithms should use at least 128-bit keys, a property satisfied by the next algorithm we examine: the Advanced Encryption Standard, AES.

AES

In 1997, the National Institute of Standards and Technology (NIST) announced a competition to develop the Advanced Encryption Standard (AES), a symmetric encryption algorithm that would supersede DES. In 2001, the Rijndael algorithm (a combination of the last names of its Belgian designers, Vincent Rijmen and Joan Daemen) was selected as the winner, and was standardized as AES. It is defined for key sizes of 128, 192, and 256 bits, much larger than the 56-bit key used by DES.

The AES algorithm uses a substitution-permutation network, which is similar to the Feistel network used by DES but differs in that the Substitution Boxes (S-boxes) are invertible. AES performs four basic operations:

AddRoundKey

To mix in key material, a subkey is derived from the main key to form an AES round key. The state array s is initialized to the 128-bit block of plaintext input and is combined with a word w of the round key through exclusive-or to form the updated state.

SubBytes

Similar to DES, the state is then transformed through a non-linear S-box, which in AES maps bytes-to-bytes in an invertible manner. Following Kerckhoffs’ Principle, this transformation and the entire description of the AES algorithm is publicly known.

ShiftRows

This step cyclically shifts the last three rows in the current state. This operation, along with the MixColumns operation, provide diffusion: propagating small changes in the plaintext input throughout the entire resulting ciphertext output. This “avalanche effect” protects against attacks where an adversary knows a plaintext-ciphertext pair: multiple diffusion operations, combined with the confusion from adding in round keys in each iteration, makes it difficult to recover the key even with knowledge of the plaintext and ciphertext.

MixColumns

The final operation mixes the information within a single column, providing a further diffusion effect. 

These groups of operations are then iterated a number of times, depending on the key size selected.

We've seen that DES and AES are both symmetric encryption algorithms that process, respectively, 64-bit and 128-bit plaintext blocks. But how do asymmetric ciphers differ from symmetric ciphers, and how do we encrypt messages that are longer than the block size (it's not as simple as concatenating the output!)? We'll cover these topics in our next blog post.