User:Ghefchob/sandbox

Differential-linear cryptanalysis is a general form of chosen plaintext cryptanalysis, that combines the ideas from both differential cryptanalysis and linear cryptanalysis. The technique allows an attacker to reduce the number of rounds that a linear characteristic must cover, resulting in a reduction (for vulnerable ciphers) in the data complexity of linear cryptanalysis attacks. It works by comparing the parity of linear approximations, for a pair of ciphertexts with a known plaintext difference (see #Technique in detail).

It was introduced by Martin Hellman and Susan K. Langford in 1994 , as an attack on 8 rounds of DES. The attack recovers 10 bits of key with an 80% success probability, given 512 chosen plaintexts . This was an improvement of more than an order of magnitude compared to the earlier results for 8-round DES . Later the technique has been used to successfully analyze, among others, the block ciphers Camellia, IDEA and Serpent , but it is also applicable to stream ciphers. Preneel and Wu used differential-linear cryptanalysis to break the stream cipher Phelix with significantly fewer operations than exhaustive key search , given attacker controlled nonces.

Technique in detail

To illustrate the idea we consider an application of the technique to a modified example cipher, which was adopted from a tutorial by Knudsen and Robshaw. This cipher can be distinguished from a random oracle (following the explanation of differential-linear cryptanalysis given by Biham et al.). The following figure illustrates the operation of the block cipher (block- and key sizes are omitted, as they are not needed for the explanation):

FIGURE MISSING

Chaining characteristics

Let there be a truncated characteristic, $\Gamma \to \Delta$, which holds for $S_{1}$ with probability 1, and a linear characteristic, $\alpha \to \beta$, which holds for $S_{2}$ with probability $1/2+q$. Then if we have two messages, $m_{0}$ and $m_{1}$, with a difference of $m_{0}\oplus m_{1}=\Gamma$, we know that the difference after $S_{1}$ is $x_{0}\oplus x_{1}=\Delta$. If the linear characteristic for $S_{2}$ uses only the bits from the output difference that are constant, and the dot product between the output difference and the input mask is $\Delta \cdot \alpha =0$, then then we know that $\alpha \cdot x_{0}=\alpha \cdot x_{1}$. In other words, the input bits to the linear approximation is the same for the two messages.

The linear characteristic for $S_{2}$ gives us a probability of $1/2+q$ for the relation $\alpha \cdot x_{0}=\beta \cdot S_{2}[x_{0}]$ to hold (and likewise for $x_{1}$). For the output parity of the two encrypted messages to be equal, the linear approximation must then either hold or fail for both messages. The probability of this happening is $(1/2+q)^{2}+(1/2-q)^{2}=1/2+2q^{2}$, which gives a bias that can be used to distinguish the cipher from a random oracle.

Distinguishing attack

The distinguishing attack on the cipher is performed by requesting the encryption of several message pairs with an input difference of $\Gamma$. For each resulting ciphertext pair, $c_{0}$ and $c_{1}$, we test if the output parity of the ciphertexts is the same ($\beta \cdot c_{0}{\text{ }}{\stackrel {?}{=}}{\text{ }}\beta \cdot c_{1}$). If the cipher was implemented as a random oracle, we would expect this relation to hold with probability $1/2$. But the differential-linear property described above tells us that the relation holds with probability $1/2+2q^{2}$ for the cipher. Given enough chosen plaintexts (on the order of $O(q^{-4})$), we may therefore distinguish it from a random oracle.

If we add another round to the example cipher, we may use this distinguisher to recover the last subkey. Given several pairs of ciphertexts, created from plaintexts with a difference of $\Gamma$, we try every possible value for the last subkey. For every guess we calculate our way back from the ciphertexts, through the last S-Box. We may then consider the values we get to be outputs from the cipher above, and apply our distinguisher. For an incorrect guess we expect the ciphertexts to act as if they came from a random oracle, but a correct guess will exhibit the bias described above. This allows us to identify the correct value for the last subkey.

Further extensions

Biham, Dunkelman and Keller extended the technique to use differential charactersitics with a probability of less than 1. Using this generalization they were able to attack 9 rounds of DES , and 11 rounds of Serpent. It is also possible to use a combination of characteristics where $\Delta \cdot \alpha =1$, with the change that one then looks for output parities that are different . Extending differential-linear cryptanalysis with higher-order differentials and bilinear cryptanalysis has also been explored to create new attacks

References

Category:Cryptographic attacks