Modes of Operation MyNotes

Outline

• Overview of Modes of Operation
• Security Pitfalls/Advantages of each Mode of Operation

Introduction

• Block Ciphers: Typical block ciphers encrypt fixed-size blocks of data.
  • Example: DES encrypts $64$-bit blocks.
  • Example: AES encrypts $128$-bit blocks.
• Message Size: In practice, messages are often larger than the standard block size.
• Processing Large Messages: To handle larger messages:
  • Divide the message into a number of blocks.
  • Cipher each block one by one.
• Mode of Operation: A mode of operation describes the specific process of encrypting each block of a message using a single key.

Modes of Operation Overview

Current well-known modes of operation include:

• Electronic Code Book mode (ECB)
• Cipher Block Chaining mode (CBC)
• Cipher Feedback mode (CFB)
• Output Feedback mode (OFB)
• Counter mode (CTR)
• Galois Counter mode (GCM)

Terminology

• Initialize Vector (IV):
  • A block of bits used to randomize the encryption process.
  • Purpose: To produce distinct ciphertexts even for identical plaintext blocks or messages.
  • Must be non-repeating for certain modes, often required to be unpredictable.
• Nonce (Number used Once):
  • A random or pseudo-random number.
  • Purpose: To ensure that past communications cannot be reused in replay attacks. The nonce should be unique for each message encrypted with the same key.
  • Note: Sometimes the term “nonce” is used interchangeably with “initialize vector (IV)”, especially when the primary requirement is uniqueness.
• Padding:
  • The process of adding extra bits to the final block of plaintext to ensure it meets the required block size for the cipher.
  • Necessary for modes like ECB and CBC if the message length is not an exact multiple of the block size.

Electronic Codebook Mode (ECB)

Operation

• Encryption: Each plaintext block $P_i$ is encrypted independently using the secret key $K$.

  • Formula: $C_i=E_K(P_i)$

• Decryption: Each ciphertext block $C_i$ is decrypted independently using the secret key $K$.

  • Formula: $P_i=D_K(C_i)$

• Definitions:

  • $E$: Encryption function
  • $D$: Decryption function
  • $P_i$: Plaintext block $i$
  • $C_i$: Ciphertext block $i$
  • $K$: Secret key
  • $n$: Block size in bits

Diagram Description (Based on Slide 6)

• Encryption:
  • The message is divided into $n$-bit blocks: $P_1,P_2,...,P_N$.
  • Each block $P_i$ is fed into the encryption algorithm $E$ with the key $K$.
  • The output is the corresponding $n$-bit ciphertext block $C_i$.
  • All encryptions are independent.
• Decryption:
  • The ciphertext is divided into $n$-bit blocks: $C_1,C_2,...,C_N$.
  • Each block $C_i$ is fed into the decryption algorithm $D$ with the key $K$.
  • The output is the corresponding $n$-bit plaintext block $P_i$.
  • All decryptions are independent.

Ciphertext Stealing (CTS) for ECB

• Problem: Padding is required in ECB if the last block is not $n$ bits long. Padding isn’t always feasible (e.g., when ciphertext must occupy the exact same buffer as the plaintext).
• Solution: Ciphertext Stealing (CTS) allows ECB use without padding.
• Process (for last two blocks $P_{N-1}$ and $P_N$):
  • Assume $P_{N-1}$ has $n$ bits and $P_N$ has $m$ bits, where $m\le n$.
  • Step 1: Encrypt the second-to-last plaintext block: $X=E_K(P_{N-1})$
  • Step 2: Construct an intermediate block $Y$ by concatenating the last (partial) plaintext block $P_N$ with the trailing bits of $X$: $Y=P_N|tai{l}_{n-m}(X)$ (where $tai{l}_{n-m}(X)$ selects the rightmost $n-m$ bits of $X$)
  • Step 3: The final ciphertext block $C_N$ consists of the leading bits of $X$: $C_N=hea{d}_m(X)$ (where $hea{d}_m(X)$ selects the leftmost $m$ bits of $X$)
  • Step 4: The second-to-last ciphertext block $C_{N-1}$ is the encryption of $Y$: $C_{N-1}=E_K(Y)$
• Note: Decryption involves reversing these steps. Detailed diagrams/procedures are often left as exercises.

Security Issues

1. Pattern Preservation: Identical plaintext blocks always encrypt to identical ciphertext blocks (given the same key).
   • Leakage: If an attacker (Eve) observes that $C_1$, $C_5$, and $C_{10}$ are the same, she knows $P_1$, $P_5$, and $P_{10}$ are also the same.
   • Attack Vector: Eve could perform an exhaustive search to decrypt just one repeated block and learn the content of all identical blocks.
2. Block Independence & Substitution: Since blocks are independent, Eve can manipulate the ciphertext without knowing the key.
   • Attack: Eve can capture messages, identify blocks with specific meanings (e.g., block 8 always contains salary info), and substitute blocks from previous messages or rearrange blocks within a message.
   • Example (Slide 9): Eve works part-time (low pay). The company sends payment info to the bank; block 7 contains the payment amount. Eve intercepts the ciphertext for her payment. She replaces block 7 with a copy of block 7 from a previous message containing the payment for a full-time colleague. She receives higher pay. This is a substitution attack.

Error Propagation

• A single-bit error in a transmitted ciphertext block $C_i$ will cause errors within the corresponding decrypted plaintext block $P_i$.
• The error affects only the corresponding block. Decryption of other blocks ($P_j$ where $j\ne i$) remains unaffected.
• Effect within the block: Typically, about half of the bits in the decrypted block $P_i$ will be incorrect due to the properties of block ciphers.

Advantages of ECB Mode

• No Synchronization Needed: Block encryption/decryption for $P_i$/$C_i$ doesn’t depend on other blocks, so synchronization between sender and receiver for block processing isn’t required beyond agreeing on the key.
• Error Isolation: Transmission errors (bit flips) in one ciphertext block $C_i$ only affect the decryption of that specific block $P_i$. Errors do not propagate to subsequent blocks.
• Parallelizable: Encryption and decryption of multiple blocks can be performed in parallel, potentially increasing throughput.

Limitations of ECB Mode

• Deterministic Encryption: Identical plaintext blocks produce identical ciphertext blocks (with the same key). This is the primary weakness.
• Susceptibility to Substitution Attacks: Due to block independence and deterministic encryption, attackers can rearrange, repeat, or substitute ciphertext blocks to manipulate the decrypted message without needing the key. (See Security Issues and Slide 12 example table).

Applications

• Not Recommended for Messages: Generally not recommended for encrypting messages longer than one block, especially over insecure channels, due to the security weaknesses (pattern preservation, substitution).
• Single Block Encryption: Tolerable if the message fits within a single block.
• Encrypted Databases (with caution): Sometimes used where random access to encrypted records is needed. Since blocks are independent, a specific record (if aligned with block boundaries) can be decrypted or re-encrypted without affecting others. However, the pattern preservation weakness can still be a concern depending on the data structure.

Visual Example (Slide 14)

• An image encrypted using AES-256 in ECB mode.
• Observation: Although encrypted, the outline and major features of the original image (“CRYPTOGRAPHY AND DATA SECURITY”) are still clearly visible in the encrypted version. This is because identical blocks of color/pixels in the original image encrypt to identical blocks in the ciphertext image, preserving patterns. This visually demonstrates the primary weakness of ECB.

Cipher Block Chaining (CBC) Mode

Operation

• Goal: To make each ciphertext block dependent on all preceding plaintext blocks.

• Initialization Vector (IV): Uses an IV ($C_0$) to start the process. The IV must be known by both sender and receiver. It should ideally be random and unpredictable for each message encryption session.

• Encryption: Before encrypting plaintext block $P_i$, it is XORed with the previous ciphertext block $C_{i-1}$.

  • Formula: $C_i=E_K(P_i\oplus C_{i-1})$
  • Initial step: $C_1=E_K(P_1\oplus IV)$

• Decryption: Each ciphertext block $C_i$ is first decrypted, and then the result is XORed with the previous ciphertext block $C_{i-1}$ to recover the plaintext $P_i$.

  • Formula: $P_i=D_K(C_i)\oplus C_{i-1}$
  • Initial step: $P_1=D_K(C_1)\oplus IV$

• Derivation Proof (Decryption): $P_i=D_K(C_i)\oplus C_{i-1}$ $P_i=D_K(E_K(P_i\oplus C_{i-1}))\oplus C_{i-1}$ $P_i=(P_i\oplus C_{i-1})\oplus C_{i-1}$ $P_i=P_i\oplus (C_{i-1}\oplus C_{i-1})$ $P_i=P_i\oplus 0$ $P_i=P_i$

• Definitions:

  • $E$: Encryption function
  • $D$: Decryption function
  • $P_i$: Plaintext block $i$
  • $C_i$: Ciphertext block $i$
  • $K$: Secret key
  • $n$: Block size in bits
  • $IV$: Initialization Vector (acts as $C_0$)
  • $\oplus$: Bitwise XOR operation

Diagram Description (Based on Slide 15)

• Encryption:
  • An $n$-bit IV ($C_0$) is used.
  • For block 1: $P_1$ is XORed with $IV$, then encrypted with $K$ to get $C_1$.
  • For block $i$ ($i>1$): $P_i$ is XORed with the previous ciphertext block $C_{i-1}$, then encrypted with $K$ to get $C_i$.
  • The process chains blocks together.
• Decryption:
  • The same $n$-bit IV ($C_0$) is used.
  • For block 1: $C_1$ is decrypted with $K$, then XORed with $IV$ to get $P_1$.
  • For block $i$ ($i>1$): $C_i$ is decrypted with $K$, then XORed with the previous ciphertext block $C_{i-1}$ to get $P_i$.

Discussion

• Dependency: Encryption of a block $P_i$ depends on $P_i$ and all preceding plaintext blocks ($P_1,...,P_{i-1}$) due to the chaining mechanism ($C_{i-1}$ depends on $P_{i-1}$ and $C_{i-2}$, etc.).
• Identical Plaintext Blocks: Repeated plaintext blocks within the same message will (almost always) encrypt to different ciphertext blocks because the input to the encryption function ($P_i\oplus C_{i-1}$) changes.
• Initialization Vector (IV):
  • Must be known by both sender and receiver.
  • Typically, the IV is generated by the sender and sent in the clear (unencrypted) along with the ciphertext, often prepended to the first ciphertext block. It does not need to be secret, but it must be unique (preferably random/unpredictable) for each message encrypted with the same key.
• Decryption Dependency: Decryption of $P_i$ depends on $C_i$ and $C_{i-1}$. It is not dependent on the entire message decryption process before it, only the immediately preceding ciphertext block.
• Error Propagation: Occurs (see details below).

CBC Encryption Algorithm (Pseudocode - Slide 17)

CBC_Encryption (IV, K, Plaintext blocks P[1...N])
{
  C[0] = IV // Use IV as the "zeroth" ciphertext block
  for (i = 1 to N)
  {
    Temp = P[i] XOR C[i-1]
    C[i] = E_K(Temp)
  }
  return Ciphertext blocks C[1...N]
}

(Note: MathJax formatting applied conceptually here) $C_0\leftarrow IV$ for ($i=1$ to $N$) { $Temp\leftarrow P_i\oplus C_{i-1}$ $C_i\leftarrow E_K(Temp)$ } return $C_1,C_2,...,C_N$

Security Issues

1. Pattern Hiding (Within a Message): CBC hides patterns within a single message. Identical plaintext blocks usually yield different ciphertext blocks.
2. Identical Messages & IV Reuse: If two identical messages are encrypted with the same key and the same IV, they will produce the exact same ciphertext.
   • Problem: If an attacker sees the same ciphertext twice, they know the same message was sent.
   • Partial Leakage: If the first $M$ blocks of two different messages are identical, and the same IV is used, the first $M$ ciphertext blocks will also be identical.
   • Mitigation: Always use a unique, unpredictable IV for each message. Using a timestamp as an IV is sometimes suggested but may not provide sufficient unpredictability. Random IVs are generally preferred.
3. Ciphertext Manipulation (End of Stream): An attacker can potentially append blocks to the end of a ciphertext stream without being detected immediately if integrity is not checked separately. (The effect on the final plaintext block might be predictable if the attacker can guess the plaintext). More sophisticated attacks like padding oracle attacks exist if padding is handled improperly during decryption.

Error Propagation

• Effect of Error in $C_j$: A single-bit error in ciphertext block $C_j$ during transmission has the following effects during decryption:
  • On $P_j$: The error completely corrupts the decryption of the corresponding plaintext block $P_j$. Due to block cipher properties, typically ~50% of the bits in $P_j$ will be flipped.
  • On $P_{j+1}$: The same single-bit error appears in the same bit position in the next plaintext block $P_{j+1}$. This is because $P_{j+1}=D_K(C_{j+1})\oplus C_j$. The error in $C_j$ directly flips the corresponding bit in $P_{j+1}$ after the XOR operation.
  • On Subsequent Blocks ($P_{j+2}$ onwards): Plaintext blocks $P_{j+2}$ to $P_N$ are not affected by the error in $C_j$, as their decryption only depends on $C_{j+1},C_{j+2},...$.
• Self-Recovery: The effect of a ciphertext bit error is limited. The decryption process automatically recovers (resynchronizes) after two blocks ($P_j$ and $P_{j+1}$).

Ciphertext Stealing (CTS) for CBC

• Similar to ECB CTS, it can be applied to CBC to avoid padding.
• Process (Conceptual - Slide 20): Involves manipulating the last two blocks ($P_{N-1},P_N$) and the preceding ciphertext block ($C_{N-2}$) differently.
  • $U=P_{N-1}\oplus C_{N-2}$
  • $X=E_K(U)$
  • $V=P_N|pa{d}_{n-m}(0)$ (Pad the last partial block $P_N$ with zeros to full block size $n$)
  • $Y=X\oplus V$
  • $C_N=hea{d}_m(X)$ (Final ciphertext block is partial)
  • $C_{N-1}=E_K(Y)$ (Second-to-last ciphertext block)
• Note: The pad function here inserts $0$s. Decryption reverses this.

Applications

• General Message Encryption: CBC is widely used for encrypting messages and data streams where confidentiality is required and patterns need to be obscured.
• Not Ideal for Random Access: Because decryption of block $P_i$ requires $C_{i-1}$, CBC is generally not suitable for applications requiring efficient random access to encrypted data (like databases where individual records need frequent decryption/re-encryption). Accessing $P_i$ requires accessing $C_i$ and $C_{i-1}$.
• Authentication: CBC is also used as a basis for authentication mechanisms, such as CBC-MAC (Cipher Block Chaining Message Authentication Code).

Cipher Feedback Mode (CFB)

Operation

• Stream Cipher Emulation: CFB uses a block cipher to generate a pseudorandom keystream that is XORed with plaintext, effectively turning the block cipher into a self-synchronizing stream cipher.

• Shift Register: Uses an $n$-bit shift register (initially containing the IV).

• Parameter $r$: Operates on segments of $r$ bits at a time, where $1\le r\le n$. Often $r=8$ (byte) or $r=n$.

• Encryption:

  1. Encrypt the current content of the shift register ($S_{i-1}$) using key $K$: $Temp=E_K(S_{i-1})$.
  2. Select the leftmost $r$ bits of $Temp$: $k_i=SelectLef{t}_r(Temp)$.
  3. XOR $k_i$ with the $r$-bit plaintext segment $P_i$: $C_i=P_i\oplus k_i$.
  4. Update the shift register: Shift $S_{i-1}$ left by $r$ bits, discard the old leftmost $r$ bits, and place the $r$-bit ciphertext segment $C_i$ into the rightmost $r$ positions. $S_i=[ShiftLef{t}_r(S_{i-1})|C_i]$.

• Decryption:

  1. Encrypt the current content of the shift register ($S_{i-1}$) using key $K$: $Temp=E_K(S_{i-1})$.
  2. Select the leftmost $r$ bits of $Temp$: $k_i=SelectLef{t}_r(Temp)$.
  3. XOR $k_i$ with the $r$-bit ciphertext segment $C_i$: $P_i=C_i\oplus k_i$.
  4. Update the shift register: Shift $S_{i-1}$ left by $r$ bits, discard the old leftmost $r$ bits, and place the received $r$-bit ciphertext segment $C_i$ into the rightmost $r$ positions. $S_i=[ShiftLef{t}_r(S_{i-1})|C_i]$. (Shift register update is identical for encryption and decryption).

• Formulas (Summarized):

  • Keystream generation: $k_i=SelectLef{t}_r(E_K(S_{i-1}))$
  • Encryption: $C_i=P_i\oplus k_i$
  • Decryption: $P_i=C_i\oplus k_i$
  • Register Update: $S_i=(S_{i-1}\ll r)|C_i$ (Conceptual: shift left by $r$, append $C_i$)

• Definitions:

  • $E$: Encryption function (Decryption function $D$ is not used)
  • $P_i$: $r$-bit Plaintext segment $i$
  • $C_i$: $r$-bit Ciphertext segment $i$
  • $K$: Secret key
  • $IV$: Initialization Vector (initial state $S_1$ of the shift register)
  • $S_i$: State of the $n$-bit shift register after step $i$
  • $T_i$: Temporary $n$-bit register holding $E_K(S_{i-1})$
  • $k_i$: $r$-bit keystream segment for step $i$
  • $n$: Block size of the underlying cipher
  • $r$: Feedback size (number of bits processed per step)
  • $SelectLef{t}_r$: Function selecting the leftmost $r$ bits
  • $ShiftLef{t}_r$: Function shifting register left by $r$ bits
  • $|$ : Concatenation

Diagram Description (Based on Slide 22 - Encryption)

• Starts with IV in shift register $S_1$.
• For step $i$:
  • $S_{i-1}$ (content of register before step $i$) is encrypted using $E$ with key $K$, result stored in $T_i$.
  • The leftmost $r$ bits of $T_i$ are selected ($k_i$).
  • $k_i$ is XORed with the $r$-bit plaintext $P_i$ to produce $r$-bit ciphertext $C_i$.
  • $S_{i-1}$ is shifted left by $r$ bits.
  • The ciphertext $C_i$ is placed in the newly vacated rightmost $r$ bits of the register to form $S_i$.
  • This $C_i$ is transmitted.

CFB as a Stream Cipher

• Although CFB uses a block cipher internally, its operation mimics a stream cipher.
• It generates a keystream ($k_1,k_2,...$) which is XORed with the plaintext.
• It’s a nonsynchronous (or self-synchronizing) stream cipher because the keystream generation depends on the ciphertext that has been previously generated (and transmitted). If synchronization is lost, it can resynchronize after $n/r$ steps once correct ciphertext segments are received.

CFB Encryption Algorithm (Pseudocode - Slide 24)

CFB_Encryption (IV, K, r, Plaintext P) // P is sequence of r-bit blocks
{
  Initialize shift register S with IV
  i = 1
  while (more r-bit blocks P_i in P)
  {
    // Keystream Generation
    Temp_Encrypted = E_K(S)
    k_i = selectLeft_r(Temp_Encrypted)

    // Encryption
    C_i = P_i XOR k_i
    output(C_i)

    // Shift Register Update
    S = shiftLeft_r(S)
    S = concatenate(S_shifted, C_i) // Append C_i to the right

    i = i + 1
  }
}

(Note: MathJax applied conceptually. Slide 24 has slightly different pseudocode structure but equivalent logic) Initialize $S\leftarrow IV$ $i\leftarrow 1$ while (more blocks to encrypt) { input ($P_i$) // $r$-bit plaintext block $T\leftarrow E_K(S)$ $k_i\leftarrow selectLef{t}_r(T)$ $C_i\leftarrow P_i\oplus k_i$ output ($C_i$) $S\leftarrow shiftLef{t}_r(S)$ $S\leftarrow concatenate(S,C_i)$ // Simplified notation for shifting and inserting $i\leftarrow i+1$ }

Security Issues

1. Pattern Hiding: Like CBC, CFB generally hides patterns within the message, as the keystream depends on previous ciphertext.
2. IV Requirement: More than one message can be encrypted with the same key, but the IV must be unique for each message to ensure the keystreams are different. Reusing an IV with the same key compromises security (e.g., allows recovery of XOR of plaintexts).
3. Ciphertext Manipulation: Similar to CBC, an attacker might append blocks to the ciphertext stream. Also, manipulating ciphertext bits will affect decryption (see Error Propagation). Requires integrity protection.

Error Propagation

• Effect of Error in $C_j$: A single-bit error in an $r$-bit ciphertext segment $C_j$ has the following effects:
  • On $P_j$: It causes a single-bit error (in the same position) in the corresponding plaintext segment $P_j$, because $P_j=C_j\oplus k_j$.
  • On Subsequent Plaintext ($P_{j+1}$ to $P_{j+n/r}$): The incorrect $C_j$ enters the shift register. It will remain in the register and affect the generation of the next $n/r$ keystream segments ($k_{j+1},...,k_{j+n/r}$). This will corrupt the decryption of the corresponding plaintext segments ($P_{j+1},...,P_{j+n/r}$). The corruption is typically widespread within these segments (approx. 50% bit errors).
  • Recovery: After the erroneous bits from $C_j$ have been completely shifted out of the register (which takes $n/r$ steps), the system recovers and subsequent plaintext segments are decrypted correctly, assuming no further ciphertext errors occur. This is the self-synchronizing property.

Applications

• Stream-oriented Encryption: Useful for encrypting data streams where processing must happen in smaller units (e.g., characters, single bytes, or even bits if $r=1$) without waiting for a full block.
• No Padding Needed: Since it operates on $r$-bit segments, there’s no need for message padding, as the last segment can be processed regardless of its size (up to $r$ bits, though typically used with fixed $r$). Common values for $r$ are $8$ (byte-oriented) or $n$ (full block feedback).

CFB as a Stream Cipher (Diagram - Slide 28)

• Shows sender (Encryption) and receiver (Decryption).
• Both use the same Key Generator logic (Shift Register + Block Cipher Encryption $E$).
• Encryption: Generates keystream $k_i$, XORs with $P_i$ to get $C_i$. $C_i$ is sent over insecure channel AND fed back into the shift register.
• Decryption: Generates the same keystream $k_i$ (using the received $C_{i-1}$ in its shift register), XORs with received $C_i$ to recover $P_i$. The received $C_i$ is also fed back into the shift register.
• Highlights that only the encryption function $E$ of the block cipher is needed for both encryption and decryption.

Discussion on CFB (Slide 29)

• Decryption using Encryption: A key feature is that the decryption process uses only the encryption function ($E_K$) of the underlying block cipher. The decryption function ($D_K$) is never needed.
• Role of Encryption Algorithm: The block cipher encryption $E_K$ is not used directly on plaintext but acts as a keystream generator. The generated keystream ($k_i$) is then XORed with the plaintext/ciphertext.

Advantage (Slide 30)

• Hides Patterns: Same plaintext block/segment will likely produce different ciphertext segments due to the changing state of the shift register.
• No Padding Essential: Can process data in smaller units ($r$ bits), avoiding the need for padding the message to a multiple of the block size $n$. Example: Encrypting 400 bits with AES (128-bit block, $n=128$). If using CFB-16 ($r=16$), the last 16 bits ($400=25\times 16$) can be encrypted directly. (Example needs clarification: $400=3\times 128+16$. If using CFB-128, padding might still be considered conceptually, but CFB allows operating on the final partial block, effectively generating only 16 bits of keystream for the last step if $r$ is flexible or handled appropriately.) The key point is CFB can naturally handle streams that don’t end on a block boundary.

Limitation (Slide 31)

• Decryption Dependency: Decryption of $P_i$ depends on $E_K(S_{i-1})$. Since $S_{i-1}$ depends on $C_{i-1},C_{i-2},...,C_{i-n/r}$, decryption has a dependency on several preceding ciphertext segments. (Note: Slide 16 said CBC decryption is message dependent, Slide 31 seems to imply CFB encryption process dependence affects decryption. Let’s stick to the mechanism: $P_i$ depends on $C_i$ and $k_i$. $k_i$ depends on $S_{i-1}$, which depends on previous $C$‘s. So correct.)
• Error Propagation: Errors in ciphertext propagate to multiple subsequent plaintext segments, as described previously.

Output Feedback Mode (OFB)

Operation

• Stream Cipher Emulation: Similar to CFB, OFB turns a block cipher into a stream cipher by generating a keystream that is XORed with plaintext.

• Key Difference from CFB: The output of the block cipher encryption ($T_i$) is fed back into the shift register, not the ciphertext ($C_i$).

• Shift Register: Uses an $n$-bit shift register (initially containing the IV).

• Parameter $r$: Can conceptually operate on $r$-bit segments ($1\le r\le n$), but typically used with $r=n$ (full block feedback). The diagram implies $r$ bits of keystream are used, but the feedback loop uses the full $n$-bit output $T_i$. We’ll assume $r=n$ for simplicity based on common usage and the diagram’s implication for feedback, though $r$ bits are XORed. Slide 40 implies $r\le n$. Let’s assume the keystream generation uses full block output feedback, but $r$ bits are selected for XOR.

• Encryption:

  1. Encrypt the current content of the shift register ($S_{i-1}$) using key $K$: $T_i=E_K(S_{i-1})$.
  2. Select the leftmost $r$ bits of $T_i$: $k_i=SelectLef{t}_r(T_i)$.
  3. XOR $k_i$ with the $r$-bit plaintext segment $P_i$: $C_i=P_i\oplus k_i$.
  4. Update the shift register with the output of the encryption: $S_i=T_i$. (If $r=n$, $S_i=T_i$. If $r<n$, the update rule needs clarification, but standard OFB uses full block feedback: $S_i=T_i=E_K(S_{i-1})$). Let’s assume standard full-block feedback OFB ($r=n$).

• Decryption:

  1. Generate the keystream exactly as in encryption (it’s independent of ciphertext). $T_i=E_K(S_{i-1})$, $k_i=SelectLef{t}_r(T_i)$, $S_i=T_i$.
  2. XOR $k_i$ with the $r$-bit ciphertext segment $C_i$: $P_i=C_i\oplus k_i$.

• Formulas (Assuming $r=n$, Full Block Feedback):

  • Register Update: $S_i=E_K(S_{i-1})$ (Starting with $S_0=IV$)
  • Keystream generation: $k_i=S_i$ (The entire output is the keystream block)
  • Encryption: $C_i=P_i\oplus k_i$
  • Decryption: $P_i=C_i\oplus k_i$

• Definitions: (Similar to CFB, but $S_i$ update differs)

  • $S_i$: State of the $n$-bit register (or input block) for step $i$. $S_0=IV$.
  • $k_i$: $n$-bit Keystream block $i$.

Diagram Description (Based on Slide 32 - Encryption, assuming r=n)

• Starts with IV in the position of $S_0$.
• For step $i$ (generating block $k_i$):
  • $S_{i-1}$ (output from previous encryption, or IV for $i=1$) is encrypted using $E$ with key $K$ to produce $T_i$ (which is also $k_i$ and $S_i$).
  • $k_i$ is XORed with plaintext block $P_i$ to produce ciphertext block $C_i$.
  • The output $T_i$ (which is $k_i$) becomes the input $S_i$ for the next encryption step. The ciphertext $C_i$ is not part of the feedback loop.

OFB as a Stream Cipher (Diagram - Slide 33)

• Shows sender and receiver generating the exact same keystream ($k_i$) independently of the data being transmitted (once initialized with the same IV).
• The keystream generator involves the register ($S_i$) and the block cipher encryption ($E$).
• The generated keystream $k_i$ is XORed with $P_i$ for encryption and with $C_i$ for decryption.
• The process is identical to a synchronous stream cipher where the keystream is pre-computable.

OFB Encryption Algorithm (Pseudocode - Slide 34, assuming r=n)

OFB_Encryption (IV, K, Plaintext P) // P is sequence of n-bit blocks
{
  S = IV // Current input to encryption
  i = 1
  while (more n-bit blocks P_i in P)
  {
    // Keystream Generation & Register Update
    k_i = E_K(S) // Keystream block is the output
    S = k_i      // Output is the next input

    // Encryption
    C_i = P_i XOR k_i
    output(C_i)

    i = i + 1
  }
}

(Note: MathJax applied conceptually. Slide 34 pseudocode uses slightly different variable names and logic flow, including concatenation with $k_{i-1}$ which seems incorrect for standard OFB. Standard OFB uses the full block output $E_K(S_{i-1})$ as the next state $S_i$. Let’s stick to the standard definition as described above and matching slide 32/33 diagrams)

OFB Scheme Explanation (Slide 35)

• Similarity to CFB: Generates a keystream using the block cipher.
• Key Difference: In OFB, the input to the encryption function at each step is the output from the previous step’s encryption. In CFB, the input includes the ciphertext from the previous step.
• Independence from Ciphertext: The keystream generation in OFB is independent of both the plaintext and the ciphertext.
• No Error Propagation: This is the main advantage. A bit error in the ciphertext $C_i$ only affects the corresponding bit in the decrypted plaintext $P_i$. It does not affect the decryption of any other blocks because the keystream generation is independent of the ciphertext.

Advantages of OFB

• No Error Propagation: Bit errors in ciphertext do not propagate.
• Pre-computation: The keystream can be pre-computed independently of the plaintext, which can be useful if the plaintext arrives later or if high speed is needed.
• No Padding: Like CFB, operates as a stream cipher, naturally handling messages of any length.

Disadvantages of OFB

• Synchronous Stream Cipher Issues: More susceptible to attacks involving modification or replay if IVs are reused or if the stream synchronization is lost. If a ciphertext block is lost or inserted, synchronization is lost permanently for the rest of the message (unlike CFB which can resynchronize).
• IV Uniqueness Critical: Reusing the same IV with the same key is catastrophic, as it reproduces the exact same keystream, allowing attackers to obtain the XOR of two plaintexts ($C_1\oplus C_2=(P_1\oplus k)\oplus (P_2\oplus k)=P_1\oplus P_2$).

Counter Mode (CTR)

Operation

• Stream Cipher Emulation: Like OFB, CTR mode turns a block cipher into a synchronous stream cipher.

• Counter: Uses a “counter” block for each plaintext block. The counter value must be unique for each block encrypted with the same key.

• Process:

  1. Initialize a counter (often derived from a nonce or IV).
  2. For each block $i$, encrypt the current counter value: $k_i=E_K(Counte{r}_i)$.
  3. XOR the result ($k_i$, the keystream block) with the plaintext block $P_i$: $C_i=P_i\oplus k_i$.
  4. Increment the counter for the next block ($Counte{r}_{i+1}=Counte{r}_i+1$, or some other deterministic sequence).

• Decryption: Identical to encryption, except XOR the keystream $k_i$ with the ciphertext block $C_i$: $P_i=C_i\oplus k_i$. The keystream is generated the same way using the counter sequence.

• Formulas:

  • Keystream generation: $k_i=E_K(Counte{r}_i)$
  • Encryption: $C_i=P_i\oplus k_i$
  • Decryption: $P_i=C_i\oplus k_i$
  • Counter Update: $Counte{r}_{i+1}=f(Counte{r}_i)$ (e.g., $f(x)=x+1$)

• Definitions:

  • $E$: Encryption function (Decryption $D$ not used)
  • $P_i$: Plaintext block $i$
  • $C_i$: Ciphertext block $i$
  • $K$: Secret key
  • $k_i$: Keystream block $i$
  • $Counte{r}_i$: Value of the counter for block $i$. Often formed by combining a nonce and a block index $i$. Must be unique per block per key.
  • $IV$/Nonce: Used to initialize the counter sequence, ensuring uniqueness across messages.

Diagram Description (Based on Slide 36 - Encryption)

• An initial counter value is established (e.g., from an IV/Nonce).
• For each block $i$:
  • The current counter value ($Counte{r}_i$) is encrypted using $E$ with key $K$ to produce keystream block $k_i$.
  • $k_i$ is XORed with plaintext block $P_i$ to produce ciphertext block $C_i$.
  • The counter is incremented (or updated deterministically) for the next block.
  • The diagram shows separate counters for each block, implying $Counte{r}_i$ is typically $Nonce||i$.

Discussion (Slide 37)

• No Message Dependency: Keystream generation depends only on the key and the unique counter value for that block, not on plaintext or ciphertext.
• Parallelizable: Encryption (and decryption) of blocks can be done in parallel because the keystream generation for block $i$ ($E_K(Counte{r}_i)$) does not depend on the results from block $i-1$. This is a significant advantage for performance.
• Encryption Only: Only the encryption function $E_K$ of the block cipher is needed for both CTR encryption and decryption.

CTR Encryption and Decryption Diagram (Slide 38)

• Shows parallel structures.
• Encryption: $Counter$, $Counter+1$, …, $Counter+N-1$ are each encrypted with $K$ to produce $k_1,k_2,...,k_N$. Each $k_i$ is XORed with $P_i$ to get $C_i$.
• Decryption: $Counter$, $Counter+1$, …, $Counter+N-1$ are each encrypted with $K$ to produce the same $k_1,k_2,...,k_N$. Each $k_i$ is XORed with $C_i$ to get $P_i$.

Advantages of CTR

• Efficiency: Can be highly parallelized for high throughput.
• Random Access: Encryption/Decryption of any block $i$ can be done independently if the counter value $Counte{r}_i$ is known/calculable.
• Simplicity: Requires only the encryption function. No padding needed (operates as stream cipher).
• Provable Security: Strong security properties (if block cipher is secure and counters are unique).
• No Error Propagation: Like OFB, ciphertext errors don’t propagate.

Disadvantages of CTR

• Nonce/Counter Uniqueness is Critical: Reusing a counter value for two different blocks with the same key is catastrophic (allows recovery of $P_1\oplus P_2$). The nonce/IV part of the counter must be unique for each message.
• Synchronous Stream Cipher Issues: Susceptible to ciphertext manipulation (bit-flipping attacks) if integrity is not separately ensured. Loss of synchronization requires re-initialization.

CBC and CTR Comparison (Slide 39)

Feature	CBC	CTR
Padding	Needed if message not multiple of $n$	No padding needed
Parallel Processing	No (Encryption is sequential)	Yes (Encryption/Decryption)
Block Cipher Functions	Requires both Encryption ($E$) & Decryption ($D$)	Requires only Encryption ($E$)
Initialization	Random IV or Nonce	Unique Nonce (forms part of counter)
Nonce/IV Reuse Impact	Leaks if messages are identical	Leaks XOR of plaintexts ($P_i\oplus P_i^{\prime }$)
Error Propagation (Ciphertext)	Affects $P_i$ (fully) and $P_{i+1}$ (single bit)	Affects only $P_i$ (single bit)
Random Access	No (Decryption needs $C_{i-1}$)	Yes (If counter value is known)

Comparison of Different Modes (Summary Table - Slide 40)

Operation Mode	Description	Type of Result	Data Unit Size	Parallelizable (Encrypt)	Error Propagation (Ciphertext)	Function(s) Needed	Padding Needed
ECB	Each $n$-bit block encrypted independently with same key.	Block cipher	$n$	Yes	Affects $P_i$ only	$E,D$	Yes
CBC	Block $i$ is $P_i\oplus C_{i-1}$ encrypted.	Block cipher	$n$	No	Affects $P_i,P_{i+1}$	$E,D$	Yes
CFB	$r$-bit $P_i$ XORed with $r$ bits from $E_K(S_{i-1})$; $C_i$ fed back.	Stream cipher	$r\le n$	No	Affects $P_i$ & next $n/r$ P’s	$E$ only	No
OFB	$r$-bit $P_i$ XORed with $r$ bits from $E_K(S_{i-1})$; $E_K$ output fed back.	Stream cipher	$r\le n$	No	Affects $P_i$ only	$E$ only	No
CTR	$P_i$ XORed with $E_K(Counte{r}_i)$.	Stream cipher	$n$ (or $r\le n$)	Yes	Affects $P_i$ only	$E$ only	No

(Note: Parallelizability & Data Unit Size for CTR adjusted based on common usage & potential for partial blocks)

Galois Counter Mode (GCM)

Introduction

• Goal beyond Confidentiality: While ECB, CBC, CFB, OFB, CTR provide confidentiality (encrypt data), GCM provides both confidentiality and data authenticity (integrity).
• Authentication: Ensures the receiver (Bob) that the message genuinely originated from the sender (Alice) who shares the key, and that it hasn’t been tampered with in transit.
• AEAD: GCM is an Authenticated Encryption with Associated Data (AEAD) scheme.

GCM Components (Slides 41-43)

• Encryption: Uses Counter (CTR) mode for encryption, providing confidentiality.
• Authentication: Computes a Message Authentication Code (MAC) called an “authentication tag”.
  • Uses chained Galois Field multiplication ($GF(2^{128})$) for efficient MAC computation.
  • The specific field uses the irreducible polynomial: $P(x)=x^{128}+x^7+x^2+x+1$.
• Associated Data (AAD): Allows authentication of additional data (like headers) that is not encrypted but needs integrity protection.
• MAC (Tag): A cryptographic checksum computed by the sender (Alice) based on the key, nonce, plaintext (via ciphertext), and AAD. It’s appended to the message. The receiver (Bob) recomputes the MAC based on the received data and compares it with the received tag. A match confirms authenticity and integrity.

GCM High-Level Process (Diagram Slide 44)

• Inputs: Plaintext ($x_1,...,x_n$), Key ($K$), Nonce (IV), Additional Authenticated Data (AAD).
• Encryption Path (Top):
  • Generates keystream blocks ($e_k=E_K(CT{R}_i)$) using CTR mode based on the nonce/IV.
  • XORs keystream with plaintext blocks ($y_i=x_i\oplus e_k(CT{R}_i)$) to produce ciphertext blocks ($y_1,...,y_n$).
• Authentication Path (Bottom/Chaining):
  • Generates an authentication subkey $H=E_K(0^{128})$ (encrypting the all-zero block).
  • Initializes accumulator $g_0=AAD\times H$ (multiplication in $GF(2^{128})$).
  • For each ciphertext block $y_i$: $g_i=(g_{i-1}\oplus y_i)\times H$.
  • Computes final tag $T$ based on the final accumulator value ($g_n$), the lengths of AAD and ciphertext, and the encrypted initial counter value $E_K(CT{R}_0)$. The formula is $T=(g_n\times H)\oplus E_K(CT{R}_0)$ (simplified view, actual GHASH involves lengths).
• Output: Ciphertext ($y_1,...,y_n$) and Authentication Tag ($T$).

GCM Definition and Algorithm Steps (Slide 45)

• Let $e()$ be the block cipher (e.g., AES) with block size $n=128$ bits.
• Let plaintext $x$ be blocks $x_1,...,x_n$.
• Let AAD be the additional authenticated data.
• Let $IV$ be the initialization vector (nonce).

1. Encryption (CTR part):

   • a. Derive initial counter $CT{R}_0$ from $IV$. Compute subsequent counters $CT{R}_i=CT{R}_0+i$ (typically).
   • b. Compute ciphertext blocks: $y_i=e_K(CT{R}_i)\oplus x_i$, for $i\ge 1$.

2. Authentication (GMAC/GHASH part):

   • a. Generate authentication subkey: $H=e_K(0^n)$.
   • b. Compute initial hash value from AAD: $g_0=AAD\times H$ (Galois field multiplication). Pad AAD if necessary.
   • c. Compute intermediate hash values: $g_i=(g_{i-1}\oplus y_i)\times H$, for $1\le i\le n$. Pad last $y_n$ if partial. (This forms the GHASH function).
   • d. Compute final authentication tag: $T=GHASH(H,AAD,y_1..y_n)\oplus e_K(CT{R}_0)$. (Slide formula: $T=(g_n\times H)\oplus e_K(CT{R}_0)$ is a slight simplification, GHASH includes length block).

Receiver Steps (Slide 46)

1. Receive Packet: Gets $[(y_1,...,y_n),T,AAD]$.
2. Decrypt: Uses CTR mode with the shared key $K$ and the IV (to reconstruct $CT{R}_i$) to decrypt $y_i$ back to potential plaintext $x_i$. ($x_i=e_K(CT{R}_i)\oplus y_i$).
3. Verify Authenticity:
   • Recomputes the authentication tag $T^{\prime }$ using the received ciphertext $y_1..y_n$, the received $AAD$, the shared key $K$, and the IV (nonce). This uses the same authentication steps (GHASH) as the sender.
   • Compares the computed tag $T^{\prime }$ with the received tag $T$.
4. Validation: If $T^{\prime }==T$, the receiver is assured:
   • The message came from the legitimate sender (who knows $K$).
   • The ciphertext $y_i$ and the AAD were not tampered with during transit.
   • If the tags do not match, the decryption should be discarded, and the message rejected as invalid/tampered.

Conclusions (Slide 47)

• Variety: Many modes exist for using block ciphers, each with pros and cons.
• Stream Ciphers: Several modes (CFB, OFB, CTR, GCM via CTR) effectively turn block ciphers into stream ciphers.
• ECB Weakness: Straightforward ECB mode is insecure due to pattern preservation, regardless of the underlying block cipher’s strength.
• CTR Parallelism: Counter mode allows high-speed implementation due to parallelizable encryption/decryption.
• Double Encryption: Generally, applying the same block cipher twice (e.g., double DES with the same key) provides only marginal improvement against brute-force attacks (related to meet-in-the-middle attacks). Proper modes or longer keys are better solutions. GCM provides a standardized way to achieve both confidentiality and integrity.

---