Symmetric Encryption and Block Ciphers

Course Administration and Announcements

• Class Representation: Steve is the class representative. Any comments or feedback regarding the course should be directed to the lecturer or to Steve.
• Schedule Updates:   - The Monday lecture for next week is officially canceled.   - The lecturer will be present at the usual time one week from today.
• Assignment Deadlines: There are two assignments due on the 30th of the month.

Overview of Symmetric Encryption

• Fundamental Principle: In symmetric encryption, both the sender and the receiver share the exact same key.
• Dual Requirement: The same key is used for both the encryption process and the decryption process.
• Stream Ciphers vs. Block Ciphers:   - Stream Ciphers: These utilize a shared secret key to generate an arbitrarily long sequence of random-looking bits (a key stream). Encryption is performed by applying the XOR operation (exclusive OR) to the message and the key stream bits, regardless of the message length.     - Example Reference: RC4 was discussed previously as a stream cipher outputting a stream of bytes.     - Relationship to One-Time Pad: The encryption process itself mirrors a one-time pad; however, unlike a true one-time pad, the process starts with a short key to generate a longer bit sequence.   - Block Ciphers: These schemes take a fixed amount of information—a fixed-size message block—and output a ciphertext of the same fixed size, depending on the choice of key.

Block Ciphers and the Feistel Structure

• High-Level Design: The Feistel structure (or Feistel cipher) is a design framework used to build block ciphers.
• The Encryption Process:   - Let $n$ be the total bit length of the block (e.g., $64$ or $128$ bits).   - The message is split into two halves: a left half ($L$) and a right half ($R$).   - If $n = 64$, then $L$ and $R$ are each $32$ bits.   - The Round Function ($f$): A complex, "horrible" function $f$ garbles the data based on the secret key.   - Mechanism of One Round:     - The original right half ($R$) passes through the function $f$ (incorporating the key) to output a bitstring of the same length (e.g., $32$ bits).     - This output is XORed with the original left half ($L$) to create the new right half ($R'$).     - The original right half ($R$) is carried forward unchanged to become the new left half ($L'$).     - Formally: $L_{i} = R_{i-1}$ and $R_{i} = L_{i-1} \oplus f(R_{i-1}, K_{i})$.   - Iteration: This process is repeated for several rounds (e.g., $16$ rounds). Over many rounds, all parts of the data become thoroughly scrambled.
• Key Schedule: In a real implementation, a different sub-key ($K_1$, $K_2$, etc.) is derived from the main shared secret key for each round.
• Reversibility and Decryption:   - The Feistel structure is cleverly designed to be reversible, even if the function $f$ is not itself reversible.   - One-Step Reversal Procedure: To recover the previous state from $L'$ and $R'$:     - Since $L'$ is exactly equal to the previous $R$, the receiver immediately recovers the previous right half ($R = L'$).     - To recover the previous left half ($L$), the receiver puts the recovered $R$ through the function $f$ with the key and XORs the result with $R'$.     - Logic: Since $R' = L \oplus f(R)$, then $L = R' \oplus f(R)$.

The Data Encryption Standard (DES)

• History: DES was a widely used scheme from the 1970s through the 1990s. It is now considered ancient and insecure.
• Technical Specifications:   - Block Size ($n$): $64$ bits (split into two $32$-bit halves).   - Key Size: $56$ bits.     - Note on Key Weakening: The design originally intended for a $64$-bit key, but it was deliberately weakened to $56$ bits by the US government.   - Structure: Uses the Feistel cipher design.   - Components: Function $f$ is built on "S-boxes" (substitution boxes).   - Rounds: The process is repeated for $16$ rounds.
• Modern Status: DES can be broken in seconds using special hardware today. However, the conceptual design remains sound if applied with larger block sizes, more complex key schedules, and more rounds.

Cryptanalysis and Attack Models

• Kirchhoff's Principle: The fundamental assumption that the attacker knows everything about the cryptosystem—the algorithm, the key schedule, and the functions—except for the secret key itself.
• Common Attack Scenarios:   - Ciphertext-Only Attack: The attacker sees only the encrypted messages. This is the hardest type of attack, as it is difficult to verify if a guessed key is correct without knowing the underlying plaintext.   - Known-Plaintext Attack: The attacker has access to some pairs of messages and their corresponding ciphertexts (e.g., predictable email headers or Word document metadata). This is much more powerful for finding the key.   - Chosen-Plaintext Attack: The attacker can inject a specific message into the system and receive its encryption.   - Chosen-Ciphertext Attack: The attacker can choose a specific ciphertext and somehow learn its decrypted message through leakage or other means.

Security Goals and Properties

• Brute Force (Exhaustive Search): Trying every possible key. If the attacker knows a single message-ciphertext pair, they can test every key $k$: $\text{encrypt}(m, k) = c$. If it matches, they have found the key.   - The US government chose $56$ bits for DES because a search of $2^{56}$ keys was considered viable for them, while $2^{64}$ was not.
• Varying Levels of "Breaking" a System:   - Absolute Break: Learning the secret key. This allows the attacker to read all messages and impersonate both Alice and Bob.   - Leaking Partial Information: A scheme is insecure if an attacker can learn even parts of a message without the key.   - Malleability: The ability to modify a ciphertext so that it decrypts into a specific, altered message (e.g., adding a zero to a price in an auction bid) without knowing the key.   - Distinguishability: The strongest security property. Given a ciphertext and two known possible messages ($m_0$ and $m_1$), an attacker should not be able to determine with better than $50/50$ probability which message the ciphertext represents.

Modes of Operation for Block Ciphers

• The Problem of Large Files: Block ciphers only encrypt a fixed amount (e.g., $128$ bits). Real files (emails, photos) are much larger. Files must be chopped into blocks, but the method of processing those blocks matters significantly.
• Electronic Codebook (ECB):   - Method: Chops the file into blocks ($x_1, x_2, x_3, …$) and encrypts each one independently with the same key.   - Flaw: Identical plaintext blocks result in identical ciphertext blocks.   - The Penguin Example: In an uncompressed image of a penguin, identical blocks of white space result in identical blocks of "white noise" ciphertext. The high-level structure of the penguin remains clearly visible in the encrypted image.
• Cipher Block Chaining (CBC):   - Initial Value (IV): A random bitstring chosen by the sender and sent in the clear alongside the ciphertext. It provides "freshness" so the same message encrypted twice looks different.   - Chaining Mechanism: Each message block is XORed with the ciphertext of the previous block before being encrypted.     - $C_1 = E_k(x_1 \oplus IV)$     - $C_i = E_k(x_i \oplus C_{i-1})$   - Decryption: The receiver decrypts a block and then XORs it with the previous ciphertext block (or the IV for the first block) to recover the plaintext.     - $x_i = D_k(C_i) \oplus C_{i-1}$
• Counter Mode (CTR):   - Mechanism: Turns a block cipher into a stream cipher. It encrypts a combination of an IV and a counter value to create a random key stream, which is then XORed with the message.     - Key stream block $i = E_k(IV \parallel \text{counter}_i)$     - $C_i = x_i \oplus E_k(IV \parallel \text{counter}_i)$   - Benefits: No padding required; the process can be fully parallelized.

Questions & Discussion

• Question on Packet Loss (CBC): If a block is lost in transmission in CBC mode, does that break the rest of the file?   - Answer: Yes. In CBC, because each block depends on the previous one, losing a ciphertext block prevents the decryption of everything that follows. This is usually managed at different layers of the communication stack (the transport layer) rather than the security layer.
• Question on Parallelization: Can CBC be parallelized?   - Answer: Encryption in CBC mode cannot be parallelized because you must know $C_{i-1}$ before you can compute $C_i$. However, decryption can be parallelized because all ciphertext blocks ($C_1, C_2, …$) are already available to the receiver.
• Question on IV Placement: Is the 128-bit IV part of the IP header?   - Answer: It is conceptually part of the ciphertext as it is needed for decryption, although where exactly it is placed in a packet can vary. It is not a secret value; it is independent of the message and sent openly.