Malleability and the Block Cipher: Why Encryption Isn't Enough

14 min read
computer-science security mathematics

Learn why encrypted data can still be tampered with and how block ciphers attempt to solve the fundamental problems of encryption.

Malleability and the Block Cipher: Why Encryption Isn’t Enough

We’ve established that the One-Time Pad provides perfect confidentiality. But there’s a dangerous flaw that even perfect encryption cannot solve: malleability.

The Malleability Problem

The OTP is malleable, meaning an attacker can XOR a “mask” (delta) onto the cipher text to produce a controlled change in the decrypted message:

C⊕delta=(M⊕K)⊕delta=M⊕deltaC \oplus \text{delta} = (M \oplus K) \oplus \text{delta} = M \oplus \text{delta}

The attacker doesn’t know the original message, but they can modify it. If a bank transaction is being sent, an attacker could change the amount from $100 to $1000—without ever knowing the original key or message!

This is why integrity verification is essential before acting on decrypted data. Encryption alone doesn’t guarantee that the message hasn’t been tampered with.

Introducing Block Ciphers

Unlike OTP, which operates on messages of any length, block ciphers work on fixed-size blocks (e.g., 128 bits). They must be reversible for decryption using a shared key.

The Ideal Block Cipher

The ideal block cipher is a theoretical structure where every possible plain text maps to a unique cipher text based on a key. For an n-bit block, the key would need to specify this entire mapping.

The problem? The required key size is:

n⋅2n bitsn \cdot 2^n \text{ bits}

For a 128-bit block, this would require terabytes of key material—completely impractical.

The Key Size Problem

This reveals a fundamental tension in cryptography:

  • We want a cipher that behaves like a random permutation
  • But we can’t afford to specify the entire permutation with a key
  • We need a “compact” key that still provides strong security

This is where practical block cipher designs come in. Instead of describing the entire mapping, we use mathematical structures that approximate a random permutation using much smaller keys.

Diffusion and Confusion

Modern ciphers achieve security through two key properties:

  1. Diffusion: Spreading the influence of plain text bits across the entire cipher text
  2. Confusion: Obscuring the relationship between the key and cipher text

By applying multiple rounds of simple operations, ciphers can achieve both properties despite using compact keys.

Conclusion

Malleability shows us that encryption alone is insufficient. We need integrity verification. And the key size problem shows us why we can’t simply use “ideal” ciphers. Next, we’ll explore how DES and AES solve these problems in practice.

Related Posts