Symmetric Encryption

Symmetric encryption uses the same secret key to encrypt plaintext and decrypt ciphertext. The sender and recipient must know this key while keeping it secret from everyone else.

Symmetric encryption provides confidentiality, but encryption alone does not necessarily provide integrity or authenticity. It is generally efficient and well suited to encrypting large amounts of data.

Keys and Encryption Algorithms

Modern encryption relies on a public, standardized algorithm and a separate secret key. This allows cryptographers to analyze the algorithm while applications generate different random keys without having to design new encryption functions.

By contrast, an unkeyed secret function relies on hiding the algorithm itself, which is security through obscurity. Once someone discovers the function, every message protected by it can be decrypted.

Confusion and Diffusion

Secure ciphers combine confusion and diffusion to resist statistical analysis and other forms of cryptanalysis. Confusion obscures the relationship between the key and ciphertext: each ciphertext bit should depend on several parts of the key. Substitution operations primarily provide confusion by replacing input values through nonlinear mappings.

Diffusion spreads the statistical structure of the plaintext throughout the ciphertext. Changing one plaintext bit should change roughly half of the ciphertext bits, preventing patterns such as common letter frequencies from remaining visible. This behavior is an avalanche effect.

Some ciphers provide only one property: substitution ciphers and the one-time pad provide confusion without diffusion, while transposition ciphers provide diffusion without confusion. Practical ciphers combine both properties.

One-Time Pad

A one-time pad (OTP) combines plaintext with a single-use, pre-shared secret key using modular addition. The key must be at least as long as the message.

For binary data, XOR performs modular addition on individual bits. Encryption and decryption use the same operation:

$$c_i = m_i \oplus k_i \qquad m_i = c_i \oplus k_i$$

The one-time pad provides information-theoretic perfect secrecy when all of the following conditions hold:

• The key is at least as long as the plaintext.
• The key is truly random.
• The key is never reused, either wholly or partially.
• The key remains completely secret.

These requirements create practical drawbacks:

• True random values are more difficult and slower to generate than pseudorandom values.
• Generating and securely exchanging a key at least as long as the message is difficult. Key agreement can be used to establish shared secret material.
• The key must remain secret and be securely erased after use. Data remanence can make complete erasure difficult.

Block Ciphers

A block cipher transforms a fixed-size block of plaintext into a ciphertext block of the same size. AES, for example, operates on 128-bit blocks. A block cipher alone can transform only one block, so a mode of operation is needed to encrypt data larger than a block.

Internal Structures

Block ciphers can use different internal structures. Feistel networks and substitution-permutation networks are two common designs.

Feistel Networks

A Feistel cipher divides a block into two halves. During each round, a round function processes one half, its output is combined with the other half, and the halves are swapped.

A round function accepts one data half and a round subkey, then returns an output the same size as the data half. A round subkey is a key value used in one particular round. A cipher’s key schedule derives the sequence of round subkeys from its master key; the Feistel construction does not define that derivation itself.

Let $F$ be the round function, and let $K_1, K_2, \ldots, K_n$ be the round subkeys. Split a plaintext block into two equal halves, $(L_0, R_0)$. For each round $i$, compute:

$$\begin{aligned} L_i &= R_{i-1} \\ R_i &= L_{i-1} \oplus F(R_{i-1}, K_i) \end{aligned}$$

The ciphertext is $(R_n, L_n)$.

The following diagram shows this construction:

The round function is applied in only one direction, even during decryption. In fact, it does not even need to be reversible. To decrypt, the cipher reuses the same per-round operations and round-function code, but applies the round subkeys in reverse order. Reusing that implementation for encryption and decryption can halve the required code or circuitry.

Video explanation of Feistel ciphers.

Substitution-Permutation Networks

A substitution-permutation network (SPN) repeatedly applies substitution and permutation operations across the entire block. Substitution replaces input values through nonlinear mappings, while permutation rearranges or mixes their positions.

An S-box substitutes one small block of input bits with another block of output bits. In an SPN intended to support decryption, an S-box must be one-to-one so that the substitution is invertible.

A well-designed S-box has strong avalanche behavior. Designers also evaluate criteria that avoid statistically weak patterns, such as short cycles in the substitution mapping (for example, a 2-bit S-box has a three-value cycle when 00 maps to 01, 01 maps to 10, and 10 maps to 00). Established sets of S-boxes already have suitable properties.

A P-box permutes all bits from the S-box outputs in one round before feeding them into the S-boxes of the next round. It does not merely connect one S-box directly to another.

S-boxes primarily provide confusion, while P-boxes spread information across subsequent rounds to provide diffusion.

At each round, a round key is combined with the state using a group operation, typically XOR. The following diagram shows the general structure of an SPN:

An S-box alone resembles a substitution cipher, and a P-box alone resembles a transposition cipher, so neither has much cryptographic strength by itself. As the number of rounds increases, the statistical mapping from input to output becomes more difficult to discover.

Video explanation of substitution-permutation networks.

Data Encryption Standard

The Data Encryption Standard (DES) is a 64-bit block cipher with a 56-bit effective key. It uses a Feistel network consisting of 16 rounds, preceded by an initial permutation and followed by its inverse, the final permutation. These permutations have no cryptographic significance; they simplified loading blocks on mid-1970s 8-bit hardware.

Before the rounds begin, DES divides the block into two 32-bit halves. Each round applies the Feistel function to one half, combines its output with the other half using XOR, and swaps the halves. The final round also swaps the halves.

The DES Feistel function processes one 32-bit half-block in four stages:

1. Expansion: An expansion permutation duplicates selected bits to expand the half-block from 32 to 48 bits. The result contains eight 6-bit groups.
2. Key mixing: The expanded value is combined with a 48-bit round subkey using XOR. The key schedule derives one subkey for each of the 16 rounds.
3. Substitution: Eight S-boxes, each transform 6 input bits into 4 output bits through a nonlinear lookup table.
4. Permutation: A fixed P-box rearranges the 32 output bits.

Like other Feistel ciphers, DES can reuse the same per-round operations for encryption and decryption. Decryption applies the round subkeys in reverse order, avoiding the need for a separate decryption algorithm.

DES’s 56-bit key eventually became too small to resist brute-force attacks. Triple DES (3DES) extends its useful key length by applying DES three times, but this also requires three DES operations and is substantially slower.

Advanced Encryption Standard

The Advanced Encryption Standard (AES) is a symmetric block cipher based on the Rijndael algorithm and a substitution-permutation network. It has a fixed block size of 128 bits and supports secret keys of 128, 192, or 256 bits.

AES represents each block as a column-major $4 \times 4$ grid of bytes called the state. Encryption begins with an AddRoundKey operation and then repeatedly applies:

1. SubBytes substitutes every byte using a standardized lookup table.
2. ShiftRows cyclically shifts the rows of the state.
3. MixColumns combines the bytes within each column using matrix multiplication.
4. AddRoundKey combines the state with a round key using XOR.

The number of rounds depends on the key size, and the final round omits MixColumns. Each round uses a different round key expanded from the original secret key, and every operation has an inverse used during decryption.

AES is common enough that many CPUs provide instructions for a single AES round and its final round.

In September 1997, the U.S. National Institute of Standards and Technology (NIST) began a public competition to replace DES with a cipher that would provide security comparable to or better than Triple DES while being faster. Fifteen candidate algorithms were submitted and assessed at three public conferences. In August 1999, NIST narrowed the field to five finalists: Rijndael, Serpent, MARS, RC6, and Twofish. On October 2, 2000, NIST selected Rijndael, designed by Belgian cryptographers Joan Daemen and Vincent Rijmen, as the proposed AES.

For a visual explanation of AES, see this video explanation of AES.

Modes of Operation

A block cipher by itself is suitable only for the cryptographic transformation of one fixed-length block. A mode of operation describes how to repeatedly apply that single-block operation to securely transform larger amounts of data.

The common modes differ in their processing and access properties:

Mode	Encryption parallelizable	Decryption parallelizable	Random read access	Partial last block
ECB	Yes	Yes	Yes	No
CBC	No	Yes	Yes	No
CTR	Yes	Yes	Yes	Yes

Initialization Vectors and Nonces

An initialization vector (IV) is an initial value used to initialize a cryptographic construction or mode of operation. It has no interesting properties of its own.

When an IV is a nonce (a number used once), it must not repeat for the same key, even when the plaintext repeats. A counter is the simplest way to produce a nonce: as long as it never overflows, every value is different.

Some modes, such as CBC, instead require an unpredictable IV. An attacker must not be able to predict it in advance, so implementations normally choose it randomly.

Random IVs are not a good substitute when a nonce is required. Under the birthday bound, a random $n$-bit value is expected to collide after roughly $2^{n/2}$ draws. Conversely, a counter nonce is not a suitable substitute when an unpredictable IV is required because an attacker can predict its next value.

Electronic Codebook Mode

Electronic codebook (ECB) mode divides a message into blocks and encrypts each block separately. Padding is required when the final plaintext block is not full.

Because ECB encrypts identical plaintext blocks into identical ciphertext blocks, it lacks diffusion across blocks and fails to hide data patterns. The following image illustrates ECB’s pattern leakage:

Therefore, ECB is not recommended for cryptographic protocols, but is fast and parallelizable.

Cipher Block Chaining Mode

In cipher block chaining (CBC) mode, each plaintext block is XORed with the previous ciphertext block before encryption. Each ciphertext block therefore depends on all preceding plaintext blocks.

An unpredictable initialization vector (IV) is used in place of the previous ciphertext block for the first block. The IV is normally transmitted with the ciphertext and does not need to be secret.

For block index $i \geq 1$, CBC encryption and decryption are:

$$\begin{aligned} C_i &= E_K(P_i \oplus C_{i-1}), & C_0 &= IV \\ P_i &= D_K(C_i) \oplus C_{i-1}, & C_0 &= IV \end{aligned}$$

CBC requires the message to be padded to a multiple of the cipher block size and cannot parallelize encryption. It supports random reads during decryption only when the receiver has the preceding ciphertext block: to decrypt block $M$, it needs ciphertext blocks $M - 1$ and $M$.

The following diagrams show CBC encryption and decryption:

Changing a ciphertext block corrupts the corresponding plaintext block and causes predictable bit changes in the next plaintext block. CBC therefore needs a separate integrity mechanism to prevent attackers from manipulating ciphertext. Decrypting with an incorrect IV corrupts the first plaintext block but leaves later blocks correct.

Counter Mode

Counter (CTR) mode turns a block cipher into a stream cipher. It encrypts successive counter blocks to generate keystream blocks. No counter block may repeat under the same key; an increment-by-one counter is the simplest and most common choice.

The counter changes for every block in one message, while the nonce changes between messages. Together, they ensure that the block cipher never receives the same input under the same key:

$$\operatorname{AES}_K(\mathit{nonce} \mathbin\| \mathit{counter})$$

The nonce identifies the encryption or message, and the counter identifies the block within that encryption or message.

When a nonce is random, it and the counter can be combined with an invertible operation, such as concatenation, addition, or XOR, to form the unique counter block. With a nonrandom nonce, such as a packet counter, concatenate the nonce and counter instead. Simply adding or XORing a nonrandom nonce and counter can break security under a chosen-plaintext attack because an attacker may manipulate the IV-counter pair to cause a collision.

The following diagram shows CTR encryption:

Flipping ciphertext bits flips the corresponding plaintext bits, so CTR requires a MAC to provide integrity.

Encryption and decryption can use the same infrastructure because XOR cancels itself. CTR needs only the cipher’s encryption function; that function does not need to be reversible for CTR to work.

Padding

Some modes, including ECB and CBC, operate only on complete plaintext blocks. Padding extends the final plaintext block to the cipher’s block size. Extending it with zero bits alone is ambiguous because the receiver cannot distinguish messages that end with zero bits from the padding.

PKCS#7 Padding

PKCS#7 padding appends $p$ bytes, each with the value $p$, where $p$ is the number of bytes needed to fill the block.

The diagram shows a 10-byte AES plaintext block followed by six 06 bytes, and a complete block followed by sixteen 10 bytes:

Bit Padding

Bit padding appends a one bit, followed by as many zero bits as needed to complete the block.

In a byte-oriented representation, the diagram shows a 10-byte AES plaintext block followed by 80 00 00 00 00 00, and a complete block followed by 80 and fifteen 00 bytes:

Padding-Oracle Attacks

A padding oracle attack is possible when a CBC implementation reveals whether a modified ciphertext decrypts to valid PKCS#7 padding. The attack requires that an attacker can replace the block before a target block, observe a valid-or-invalid response, and reach padding validation before any authentication check rejects the ciphertext.

Let $C_n$ be the target ciphertext block, and let $C_{n-1}$ be the block before it. CBC decrypts $C_n$ by XORing its decrypted value with $C_{n-1}$:

$$P_n = D_K(C_n) \oplus C_{n-1}$$

The attacker cannot calculate $D_K(C_n)$, but can replace $C_{n-1}$ with a chosen block $C_{n-1}'$. This changes the plaintext in a predictable way:

$$P_n' = D_K(C_n) \oplus C_{n-1}'$$

For a 16-byte AES block, suppose the final byte of the captured $C_{n-1}$ is 0x40. The attacker keeps $C_n$ unchanged, and replaces the final byte of $C_{n-1}$ with every possible value, written as 0x??.

The attacker wants the final plaintext byte to be 0x01, because that is valid one-byte PKCS#7 padding. After trying possible values, the oracle returns valid for 0x43. The attacker then knows that the following equation is true:

$$D_K(C_n)[15] \oplus \mathtt{0x43} = \mathtt{0x01}$$

Therefore, the attacker can recover the hidden decrypted byte, then the original plaintext byte:

$$\begin{aligned} D_K(C_n)[15] &= \mathtt{0x43} \oplus \mathtt{0x01} = \mathtt{0x42} \\ P_n[15] &= \mathtt{0x42} \oplus \mathtt{0x40} = \mathtt{0x02} \end{aligned}$$

The same idea can recover earlier bytes by forcing longer valid padding patterns.

Stream Ciphers

A stream cipher combines plaintext units with a pseudorandom stream of cipher units, called a keystream. It encrypts each plaintext unit with the corresponding keystream unit to produce the ciphertext stream. In practice, a unit is typically a bit or byte, and the combining operation is XOR.

The pseudorandom keystream is typically generated serially from a random seed value using digital shift registers. The seed value serves as the cryptographic key for decrypting the ciphertext stream. A stream cipher generates successive keystream elements from an internal state. At a high level, a keystream generator accepts a key, nonce, and block number.

Synchronous Stream Ciphers

In a synchronous stream cipher, the keystream is generated independently of the plaintext and ciphertext, then combined with the plaintext to encrypt or the ciphertext to decrypt.

The sender and receiver must remain exactly synchronized for decryption to succeed. If units are added to or removed from the message during transmission, synchronization is lost. The receiver can try offsets systematically to recover synchronization, or the ciphertext can include periodic markers.

If a unit is corrupted during transmission rather than added or removed, only the corresponding plaintext unit is affected, and the error does not propagate. This can help where transmission errors are common, but it also makes undetected alteration more likely without additional mechanisms.

Synchronous stream ciphers are therefore susceptible to active attacks: flipping a ciphertext bit can predictably flip the corresponding plaintext bit.

Self-Synchronizing Stream Ciphers

Self-synchronizing stream ciphers, also called asynchronous stream ciphers or ciphertext autokey (CTAK) ciphers, use the previous $N$ ciphertext units to compute the keystream.

The following diagram shows encryption and decryption with ciphertext feedback into the keystream generator:

The receiver automatically synchronizes with the keystream generator after receiving $N$ ciphertext units, making recovery easier when units are added to or dropped from the message stream. A single-unit error affects at most $N$ plaintext units.

ChaCha

ChaCha is a synchronous stream cipher. It generates a pseudorandom keystream from a secret key, nonce, and block counter independently of the plaintext and ciphertext. Encryption and decryption XOR that keystream with the input.

An ARX cipher is a symmetric encryption algorithm built only from modular addition, bitwise rotation, and XOR. Modular addition uses carry bits to introduce nonlinearity, rotation rearranges bit positions without losing information, and XOR combines values. ChaCha is an ARX cipher.

ChaCha uses only ARX operations in each round, so it can be implemented in constant time without table lookups that may leak information through timing attacks. Its simple instructions are available on general-purpose CPUs, allowing it to run quickly on older or low-powered devices.

A quarter round mixes four words from ChaCha’s internal state. ChaCha uses the constant expand 32-byte k and alternates two kinds of rounds:

1. A column round applies quarter rounds to the four columns: QR(0, 4, 8, 12), QR(1, 5, 9, 13), QR(2, 6, 10, 14), and QR(3, 7, 11, 15).
2. A diagonal round applies quarter rounds to the four diagonals: QR(0, 5, 10, 15), QR(1, 6, 11, 12), QR(2, 7, 8, 13), and QR(3, 4, 9, 14).

Video explanation of ChaCha.

Authenticated Encryption

Authenticated encryption (AE) simultaneously provides confidentiality and authenticity. It encrypts the message and includes an authentication tag that only a sender with the secret key can calculate. A valid tag means the ciphertext has not been altered and was created by a party possessing the key.

Associated Data

Many, but not all, AE schemes support associated data (AD). Associated data is readable but integrity protected rather than confidential. An AE scheme that supports associated data is called authenticated encryption with associated data (AEAD).

For example, a network packet header can contain a destination address that intermediate nodes must read to route the packet, even though they do not possess the secret key. The header is not confidential, but it must still be authenticated with the encrypted payload.

Composing Encryption and MACs

AEAD can be constructed by combining an encryption scheme with a message authentication code (MAC). The MAC must authenticate the ciphertext and any associated data. The following arrangements differ in the order in which encryption and MAC generation occur:

• Encrypt-then-MAC (EtM) encrypts the plaintext, then calculates a MAC over the resulting ciphertext. The sender transmits the ciphertext and MAC together. EtM is the only composition method that can achieve the strongest definition of AE security.
• Encrypt-and-MAC (E&M) calculates a MAC over the plaintext and encrypts the plaintext without the MAC. The sender transmits the plaintext’s MAC and the ciphertext together.
• MAC-then-encrypt (MtE) calculates a MAC over the plaintext, then encrypts the plaintext and MAC together. The sender transmits the resulting ciphertext, which contains an encrypted MAC.

ChaCha20-Poly1305

ChaCha20-Poly1305 is an AEAD algorithm that combines the ChaCha20 stream cipher with the Poly1305 MAC. It has fast software performance and, without hardware acceleration, is usually faster than AES-GCM.

Integrated AEAD Algorithms

Purpose-built AEAD algorithms define encryption and authentication as one integrated construction.

Galois Counter Mode

Galois/Counter Mode (GCM) is an AEAD mode that combines Counter (CTR) encryption with an authentication mechanism that can be parallelized. It solves CTR’s malleability problem: changing a ciphertext bit would change the corresponding message bit, but an invalid authentication tag causes verification to fail.

GCM encrypts and authenticates a message in four steps:

1. The cipher derives a hash subkey, $H = E_K(0^{128})$, by encrypting an all-zero block.
2. Counter mode encrypts the plaintext with counter blocks derived from the nonce, producing the ciphertext.
3. GCM XORs the associated data and ciphertext blocks into an accumulator, multiplying by $H$ in a Galois field after each block. It also incorporates the lengths of the associated data and ciphertext.
4. The cipher encrypts the nonce-derived initial counter block and XORs it with the final accumulator to produce the tag.

The receiver repeats the computation and compares the expected tag with the received tag to validate.

Nonce reuse is especially dangerous in GCM. Its construction can allow an attacker to recover the hash subkey $H$, forge authentication tags, and forge messages.

Video explanation of GCM.

AES-GCM

AES-GCM instantiates GCM with AES as its block cipher.

AES-GCM is widely used in transport and network-security protocols, including TLS, IPsec Encapsulating Security Payload (ESP), and Secure Shell (SSH).