Ciphertext Stealing (CTS) - Detailed Explanation

Overview

• A technique for encrypting plaintext using a block cipher without padding the message to a multiple of the block size
• The ciphertext is the same size as the plaintext
• Works by altering processing of the last two blocks of the message

How It Works

Key Concept

• The processing of all but the last two blocks is unchanged
• A portion of the second-last block's ciphertext is "stolen" to pad the last plaintext block
• The padded final block is then encrypted as usual

Final Ciphertext Composition

The final ciphertext, for the last two blocks, consists of:

1. The partial penultimate block (with the "stolen" portion omitted)
2. Plus the full final block
3. These are the same size as the original plaintext

Decryption Process

• Requires decrypting the final block first
• Then restoring the stolen ciphertext to the penultimate block
• Which can then be decrypted as usual

Analogy: CTS is like borrowing (stealing) the last few pages from the second-to-last chapter to complete the final chapter - no extra padding needed, but you need to return those pages to the right place when reading (decrypting).

CBC Ciphertext Stealing Encryption

Encryption Steps

1. Pad the last partial plaintext block with 0

2. Encrypt the whole padded plaintext using the standard CBC mode

3. Swap the last two ciphertext blocks

4. Truncate the ciphertext to the length of the original plaintext

Visual Process

Step 1-2: Standard CBC Encryption with Zero Padding
┌────────────────┐  ┌────────────────┐  ┌────────────────┐
│ Plaintext      │  │ Plaintext      │  │ Plaintext||0000│
│ block (full)   │  │ block (full)   │  │ (partial+zeros)│
└────────────────┘  └────────────────┘  └────────────────┘
        ↓                   ↓                   ↓
   IV → ⊕              ⊕                   ⊕
        ↓                   ↓                   ↓
    [Encrypt]          [Encrypt]          [Encrypt]
      Key                 Key                 Key
        ↓                   ↓                   ↓
┌────────────────┐  ┌────────────────┐  ┌────────────────┐
│ Ciphertext     │  │ Ciphertext     │  │ Full encrypted │
│ block          │  │ block (used 2x)│  │ block          │
└────────────────┘  └────────────────┘  └────────────────┘
                         ↓                   ↓
                         └─────────┬─────────┘
                                   ↓
Step 3: Swap last two blocks + Step 4: Truncate

┌────────────────┐  ┌────────────────┐  ┌──────────┐
│ Ciphertext     │  │ Full encrypted │  │ Partial  │
│ block          │  │ block          │  │ CT block │
└────────────────┘  └────────────────┘  └──────────┘
                     (now 2nd-last)      (truncated)

Key Points

• The second-to-last ciphertext block is used twice in the process
• The final output is truncated to match original plaintext length
• No padding visible in the final ciphertext

CBC Ciphertext Stealing Decryption

Decryption Steps

1. $D_n = \text{Decrypt}(K, C_{n-1})$

   • Decrypt the second-to-last ciphertext block using ECB mode

2. $C_n = C_n \,||\, \text{Tail}(D_n, B-M)$

   • Pad the ciphertext to the nearest multiple of the block size
   • Use the last $B-M$ bits of block cipher decryption of the second-to-last ciphertext block
   • Where: $B$ = block size, $M$ = length of last block

3. Swap the last two ciphertext blocks

4. Decrypt the (modified) ciphertext using the standard CBC mode

5. Truncate the plaintext to the length of the original ciphertext

Visual Process

Input: Truncated Ciphertext
┌────────────────┐  ┌────────────────┐  ┌──────────┐
│ Ciphertext     │  │ Ciphertext     │  │ Last CT  │
│ block          │  │ (2nd-to-last)  │  │ (partial)│
└────────────────┘  └────────────────┘  └──────────┘

Step 1: Decrypt second-to-last to get padding material
                     ┌────────────────┐
                     │ Ciphertext     │
                     │ (2nd-to-last)  │
                     └────────────────┘
                            ↓
                        [Decrypt]
                          Key
                            ↓
                     ┌────────────────┐
                     │ Use tail bits  │ ← Steal these
                     │ to pad last    │
                     └────────────────┘

Step 2-3: Pad and swap, then decrypt normally

┌────────────────┐  ┌────────────────┐  ┌────────────────┐
│ Ciphertext     │  │ Padded last    │  │ Second-to-last │
│ block          │  │ block (full)   │  │ (restored)     │
└────────────────┘  └────────────────┘  └────────────────┘
        ↓                   ↓                   ↓
     [Decrypt]          [Decrypt]          [Decrypt]
       Key                 Key                 Key
        ↓                   ↓                   ↓
        ⊕                   ⊕                   ⊕
        ↓                   ↓                   ↓
┌────────────────┐  ┌────────────────┐  ┌────────────────┐
│ Plaintext      │  │ Plaintext      │  │ Plaintext||0000│
│ block          │  │ block          │  │                │
└────────────────┘  └────────────────┘  └────────────────┘

Step 5: Truncate to remove padding
                                        ┌──────────┐
                                        │ Plaintext│
                                        │ (partial)│
                                        └──────────┘

Important Notes

• The second-to-last block must be decrypted first to obtain padding material
• This is more complex than standard CBC
• Order matters - must follow the exact sequence