Modern Cryptanalysis: Techniques for Advanced Code Breaking

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 sophisticated 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.

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 analyzing linear relationships between input and output bits of S-boxes, as in linear cryptanalysis, differential cryptanalysis focuses on finding a relationship between ...