Differential Cryptanalysis - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 158

Chapter 7
Differential Cryptanalysis
In the previous chapter, I introduced the concept of linear cryptanalysis, based on exploiting linear relationships
between bits in the ciphers. In this chapter, we explore the use of differential relationships between various bits
in the cipher.
Although the concept of exploiting differences is not necessarily new, the way it is approached for sophistic-
ated ciphers, such as DES, was not well understood until fairly recently.
The standard differential cryptanalysis method is a chosen-plaintext attack (whereas linear cryptanalysis is a
known-plaintext attack, thus is considered more feasible in the real world). Differential cryptanalysis was first
made public in 1990 by Eli Biham and Adi Shamir Biham and Shamir [2]. In the years following, it has proven
to be one of the most important discoveries in cryptanalysis.
In this chapter, we explore the technique of differential cryptanalysis. I then show how this method can be
used on several different ciphers. Finally, I show some of the more advanced techniques that have evolved from
differential cryptanalysis.
7.1 Overview
Although differential cryptanalysis predates linear cryptanalysis, both attacks are structured in a similar fashion
— a simple model of individual cipher components and a predictive model of the entire cipher. Instead of analyz-
ing linear relationships between input and output bits of S-boxes, as in linear cryptanalysis, differential crypt-
analysis focusesonfindingarelationship betweenthechangesthatoccurintheoutputbitsasaresultofchanging
some of the input bits.
Like linear cryptanalysis, differential cryptanalysis is a probabilistic attack: In this case, we will be measuring
how changes in the plaintext affect the output, but since we do not know the key, the measurements will be ran-
dom, but guided, in nature. How close the measurements are to what we desire will tell us information about the
key.
7.2 Notation
First, a few definitions and conventions. There are a few conventions used in cryptanalysis literature, and I'll use
these as much as possible, but the notation used can sometimes sacrifice conciseness for clarity.