Symmetric key cryptography: DES and AES notes — Unit 3

Modern symmetric encryption is categorized into two types based on how they process the plaintext.

⇒1.1 Stream Ciphers

A stream cipher encrypts a digital data stream one bit or one byte at a time (like the One-Time Pad, or the RC4 algorithm). It uses a key to generate an infinite pseudorandom keystream, which is XORed with the plaintext.

⇒1.2 Block Ciphers

A block cipher processes the plaintext in fixed-size blocks (e.g., 64 bits or 128 bits) and produces a block of ciphertext of equal length for each input block. DES and AES are block ciphers.

Invented by Horst Feistel at IBM, this is the architectural blueprint for many block ciphers, including DES. It ensures that encryption and decryption are practically the exact same process, even if the underlying math function is not reversible.

⇒2.1 The Mechanism

• 1. The input block is split into a Left half (L) and a Right half (R).
• 2. A mathematical function `F` is applied to the Right half using a Subkey.
• 3. The output of `F` is XORed with the Left half.
• 4. The Left and Right halves are swapped.
• 5. This process is repeated for a set number of 'Rounds' (e.g., 16 rounds).

Adopted in 1977 by the US government, DES was the standard symmetric encryption algorithm for decades. It is a Feistel network.

⇒3.1 Specifications

• Block Size: 64 bits of plaintext are processed at a time.
• Key Size: The nominal key size is 64 bits, but 8 bits are used for parity checking, making the effective key length exactly 56 bits.
• Rounds: 16 rounds of processing.

Inside the Feistel structure, DES performs specific operations during the `F` function on the 32-bit Right half.

• Expansion: The 32-bit Right half is expanded to 48 bits using an expansion permutation table.
• Key Mixing: The 48-bit expanded right half is XORed with a 48-bit subkey generated for that specific round.
• Substitution (S-Boxes): The 48-bit result is divided into eight 6-bit blocks. Each 6-bit block is fed into a unique Substitution Box (S-Box) that outputs a non-linear 4-bit block. This compresses the 48 bits back down to 32 bits. The S-Boxes are the only non-linear part of DES and provide its core security.
• Permutation: The resulting 32 bits are rearranged using a Permutation Box (P-Box).

By the late 1990s, the 56-bit key size of DES became a fatal flaw. 2^56 keys is about 72 quadrillion. While massive in 1977, custom hardware built by the Electronic Frontier Foundation (EFF) cracked a DES key via brute force in just 56 hours in 1998.

⇒5.1 Triple-DES (3DES)

To fix the vulnerability without designing a new algorithm, 3DES was adopted. It runs the DES algorithm three times on the data block using two or three different keys.

`Ciphertext = Encrypt_K3( Decrypt_K2( Encrypt_K1(Plaintext) ) )`

This effectively expands the key length to 112 or 168 bits. However, running DES three times in software is incredibly slow.

Because 3DES was too slow, NIST ran a global competition for a new standard. In 2001, the Rijndael algorithm was chosen and named AES.

⇒6.1 Specifications

• Block Size: 128 bits.
• Key Sizes: Can be 128, 192, or 256 bits.
• Rounds: 10 rounds for 128-bit keys, 12 for 192-bit, and 14 for 256-bit.
• Structure: It is NOT a Feistel network. It is a substitution-permutation network. Every bit of the 128-bit block is processed in every round.

⇒7.1 The State Array

AES treats the 128-bit block as 16 bytes. These 16 bytes are arranged into a 4x4 grid (matrix) called the 'State'. Every operation in AES transforms this state matrix.

⇒7.2 Galois Field Math

Unlike DES which uses bit-level permutations, the math inside AES operates on entire bytes using polynomial arithmetic in the Galois Field `GF(2^8)`. This makes AES highly optimized for modern 8/32/64-bit processors, leading to incredible software speeds.

Except for the last round, each AES round consists of exactly four transformations applied to the state matrix.

• 1. SubBytes: A non-linear byte substitution. Every single byte in the state is replaced with a different byte using a lookup table (the AES S-Box). This provides confusion.
• 2. ShiftRows: A transposition step. Row 0 is not shifted. Row 1 is shifted left by 1 byte. Row 2 by 2 bytes. Row 3 by 3 bytes. This scrambles the column alignment.
• 3. MixColumns: A mixing operation that operates on the columns of the state. It multiplies each column by a fixed matrix in GF(2^8) arithmetic. This provides massive diffusion (a change in one byte affects all 4 bytes in the column).
• 4. AddRoundKey: The state is bitwise XORed with the 128-bit subkey generated for that round.

A block cipher like AES only encrypts 128 bits. If you have a 1GB file, you must break it into 128-bit chunks. How you encrypt these multiple chunks is defined by the Mode of Operation.

⇒9.1 Electronic Codebook (ECB)

The most naive method. Every 128-bit plaintext block is encrypted entirely independently using the same key. `C_i = Encrypt(P_i)`

Fatal Flaw: If two plaintext blocks are identical, they will produce identical ciphertext blocks. If you encrypt a bitmap image of a penguin using ECB, you can still see the outline of the penguin in the encrypted data. ECB should never be used for files.

To fix ECB's flaw, we must ensure identical plaintext blocks encrypt differently.

⇒10.1 The Mechanism

Before encrypting the current plaintext block, it is XORed with the previous ciphertext block.

`C_i = Encrypt(P_i ⊕ C_{i-1})`

Because the first block `P_1` doesn't have a previous ciphertext block, we use a random dummy block called the Initialization Vector (IV). A completely random IV ensures that encrypting the same file twice yields completely different ciphertexts.

A completely different approach. Instead of encrypting the data directly, CTR mode encrypts a sequential counter to create a pseudorandom keystream, effectively turning a block cipher (AES) into a stream cipher.

⇒11.1 The Mechanism

Counter 1 is encrypted. The resulting 128 bits are XORed with Plaintext Block 1 to create Ciphertext Block 1. Counter 2 is encrypted and XORed with Block 2, etc.

Advantage: Because you are encrypting counters, you don't need to wait for block 1 to finish before encrypting block 2. CTR mode is highly parallelizable, making it significantly faster than CBC on modern multi-core hardware.

Cryptography relies entirely on unpredictability. If an attacker can guess the IV or the generated AES key, the math is useless.

⇒12.1 True Random vs Pseudorandom

• TRNG (True Random Number Generator): Derives randomness from physical, unpredictable phenomena (thermal noise in a CPU, radioactive decay, user mouse movements).
• PRNG (Pseudorandom Number Generator): An algorithm that takes a 'seed' (preferably from a TRNG) and outputs a stream of bits that appears statistically random. If the seed is known, the entire stream can be recreated.

AES is mathematically solid. But if Alice and Bob want to communicate using AES, they must both possess the exact same 256-bit secret key.

⇒13.1 The Paradox

How do Alice and Bob agree on a secret key if they are communicating over the internet where hackers are listening? If they send the key unencrypted, the hacker gets the key. If they encrypt the key to send it, they need another key. This chicken-and-egg problem plagued cryptography for centuries.

Historically, the solution was a trusted third party, a Key Distribution Center.

⇒14.1 The Mechanism

Every user shares a unique, pre-arranged master key with the KDC. When Alice wants to talk to Bob, she asks the KDC. The KDC generates a temporary 'session key' for them. The KDC encrypts one copy of the session key with Alice's master key, and another copy with Bob's master key, and sends them out.

The Flaw: The KDC becomes a massive single point of failure and a high-value target. If the KDC is hacked, the entire system falls. This led to the invention of Public Key Cryptography.