Cryptology III.5 Cryptanalysis of Bitblock Ciphers

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. The idea of linear cryptanalysis [PDF]
2. Example A: a one-round cipher [PDF]
3. Approximation table, correlation matrix, and linear spectrum of a Boolean map [PDF]
4. Example B: a two-round cipher [PDF]
5. Linear paths [PDF]
6. Parallel arrangement of S-boxes [PDF]
7. Mini-Lucifer [PDF]
8. Systematic search for linear relations [PDF]
9. The idea of differential cryptanalysis [PDF]

Here is the complete Section III.5 (with small gaps) as a PDF file.

Overview

For cryptanalyzing bitblock ciphers we know some basic approaches:

1. exhaustion = brute-force searching the complete key space
2. algebraic attack, see Chapter 2
3. Statistical attacks against hidden linearity:
   1. linear cryptanalysis (MATSUI/YAMAGISHI EUROCRYPT 92), the main subject of this section
   2. differential cryptanalysis (MURPHY, SHAMIR, BIHAM 1990)
   3. generalizations and mixtures of (a) and (b)

Differential cryptanalysis was known at IBM and NSA already in 1974 when designing DES. In contrast apparently linear cryptanalysis—though conceptually simpler—was unknown to the designers of DES. Accordingly the resistance of DES against linear cryptanalysis is suboptimal. However an important design criterion was:

• The S-boxes should be as nonlinear as possible.

In the following years many people developed generalizations and combinations of linear and differential cryptanalysis:

• related keys attack (BIHAM 1992, SCHNEIER)
• differentials of higher order (HARPES 1993, BIHAM 1994, LAI 1994)
• differential-linear cryptanalysis (LANGFORD/HELLMAN 1994)
• partial differentials (KNUDSEN 1995)
• I/O-sum analysis (HARPES/KRAMER/MASSEY 1995)
• S-box-pair analysis (DAVIES/MURPHY 1995, MIRZA 1996)
• boomerang attack (WAGNER 1999)
• slide attack against (maybe hidden) periodicity in ciphers or key schedules (BIRYUKOV/WAGNER 1999)
• impossible differentials (BIHAM/BIRYUKOV/SHAMIR 1999)

Should we take an attack with 2⁴³ known plaintext blocks seriously? For an answer see the FAQ.

Here we see cryptanalysis from the »legal« facet: It isn't used for eavesdropping, but is an important tool for the construction of strong ciphers.

Given an SP-network the analysis starts with the nonlinear components of the single rounds, in particular with the S-boxes. The next step is extending the potential attack over several rounds. This shows how the cost of the attack grows with the number of rounds. In this way we find criteria for the number of rounds for which the cipher is »secure«—at least from this special attack.

By the way we should never forget that the attack always relates to a certain algebraic structure; in most cases to the structure of the plaintext space as a vector space over F₂. Of course a similar attack could relate to another structure. A seemingly complex map could look simple if considered with the structure as cyclic group Z/2ⁿZ in mind—or even with »exotic« structures invented for the analysis of this single map. In the following however we only consider the structure as a vector space over F₂, the structure that is best understood.

Security Criteria for Bitblock Ciphers

To escape attacks bitblock ciphers, or their round maps, or their S-boxes, should fulfill some requirements.

For background theory see the mathematical appendix D.

• Balance: All preimages have the same number of elements, or in other words, the values of the map are uniformly distributed. Irregularities of the distribution would provide hooks for statistical cryptanalysis.
• Diffusion/avalanche effect: If a plaintext bit changes, about 50% of the ciphertext bits change. This effect conceals similarity of plaintexts.
• Algebraic complexity: The determination of preimages or parts thereof should lead to equations whose solution is as difficult as possible. This requirement is related to the algebraic degree of the map, but only in an indirect way. A suitable measure is »algebraic immunity«.
• Nonlinearity: We know several criteria that measure linearity, also »hidden« linearity, and are relatively easy to describe and to handle. For example they quantify how susceptible Boolean maps are for linear or differential cryptanalysis.
  • The »linear potential« should be as low as possible, the »linear spectrum« (or »linear profile«) as balanced as possible.
  • The »differential potential« should be as low as possible, the »differential spectrum« (or »differential profile«) as balanced as possible.
  • The »nonlinearity« (in a narrow sense as the Hamming distance from affine maps) should be as large as possible.
  • The »linearity distance«, the Hamming distance from maps with »linear structure«, should be as large as possible.

Some of these criteria are compatible with each other, some criteria contradict other ones. Therefore the design of a bitblock cipher requires a balance between different criteria. Instead of optimizing a map for a single criterion the designer should aim at a uniformly high level for all criteria.

Cipher designers usually decide the conflict between balance and nonlinearity in favour of balance. But there is no really convincing reason for this—the psychological reason seems to be that statistical attacks that use the nonuniform distribution of the output of non-balanced maps are easier to understand and therefore taken more seriously. The trade-off for nonlinearity is then handled by increasing the number of rounds.

In this section we freely use the notations and results from the mathematical appendices A to E—often without explicit reference.