Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Introduction to Differential Cryptanalysis

Differential cryptanalysis is a statistical, chosen-plaintext attack, and one of the most important techniques for symmetric cryptanalysis. Popularised in the early 1990s, it was originally developed in the late 1980s by Eli Biham and Adi Shamir (the "S" in RSA) as a general method for attacking block ciphers. Interestingly, the designers of DES, who were in part the target of the paper, had already considered this type of attack during the 1970s, but it wasn’t widely known until years later.

At its core, differential cryptanalysis is about how differences in input can affect differences in output. If we tweak a plaintext slightly, how does that tweak propagate through the cipher, and what patterns (if any) emerge in the ciphertext?

This technique is especially useful for iterative block cipher constructions, which apply the same round function multiple times. Examples here include DES, PRESENT, and many others. If a cipher consistently transforms certain input differences into predictable output differences, it can be vulnerable to this kind of analysis.

Basic Idea

Let’s say we have two plaintexts, P and P', that differ by a known value called the input difference. We encrypt both and look at the resulting ciphertexts, C and C'. Their difference is the output difference. The idea isn't conceptually complex, and may even come as behaviour we may come to expect from a cipher. After all, it's not farfetched to assume that similar plaintexts should produce similar ciphertexts.

For a well-designed cipher, we'd expect the output differences to be effectively random, but sometimes, especially in the early rounds, patterns can emerge. Differential cryptanalysis tracks how these differences evolve round by round and looks for pairs where:

  • The input difference is fixed (e.g. one specific bit is flipped),
  • The output difference occurs with "high" probability,
  • That pattern helps narrow down the possible values of some part of the key.

By finding and exploiting these high-probability "differential trails," attackers can gradually recover key bits or reduce the cipher’s effective complexity.

Applicability

Differential cryptanalysis is a chosen-plaintext attack, meaning the attacker needs to be able to encrypt plaintexts of their choice and observe the outputs. While this may sound unrealistic in some scenarios, it’s highly relevant for embedded systems, smart cards, or network protocols where attackers can often control inputs.

This technique applies to:

  • Most block ciphers (DES, PRESENT, AES, etc.)

  • Lightweight cryptography (especially important in IoT and embedded contexts)

  • Even some stream ciphers and hash functions, when adapted creatively

In the upcoming sections, we’ll look at:

  • How to construct differential characteristics

  • How S-boxes play a key role

  • What makes a differential trail "good"

  • How to turn these observations into actual key-recovery attacks