For most of its life, the prime concern with DES has been its vulnerability to brute-force attack because of its relatively short (56 bits) key length.

**DIFFERENTIAL
AND LINEAR CRYPTANALYSIS**

For most of its life, the prime concern with DES
has been its vulnerability to
brute-force attack because of its relatively short (56 bits) key length. However,
there has also been interest in finding
cryptanalytic attacks on DES. With
the increasing popularity of block ciphers
with longer key lengths, including triple DES, brute-force
attacks have become increasingly impractical. Thus, there has
been increased emphasis on cryptanalytic attacks on DES and other
symmetric block ciphers. In this section, we provide a brief overview of
the two most powerful and promising
approaches: differential cryptanalysis and
linear cryptanalysis.

Differential Cryptanalysis

One of the most significant advances in
cryptanalysis in recent years is differential cryptanalysis. In this section,
we discuss the technique and its applicability to DES.

** HISTORY **Differential cryptanalysis was not reported in the open literature until 1990. The first published effort appears to have been the
cryptanalysis of a block cipher called FEAL by
Murphy [MURP90]. This was followed
by a number of papers
by Biham and Shamir, who demonstrated this form of attack on a variety
of encryption algorithms and hash
functions; their results are summarized in [BIHA93].

The most publicized results for this approach have been those
that have application to DES. Differential cryptanalysis is the first
published attack that is capable of breaking DES in less than 255 encryptions. The
scheme, as reported in [BIHA93], can successfully cryptanalyze DES with an
effort on the order of 247 encryptions, requiring 247 chosen plaintexts. Although 247 is certainly
significantly less than 255, the need for the adversary to find 247 chosen plaintexts
makes this attack of
only theoretical interest.

Although differential cryptanalysis is a powerful
tool, it does not do very well against DES. The reason, according to a member of the IBM team that
designed DES [COPP94], is that differential cryptanalysis was known to the team as early as 1974. The need to strengthen DES
against attacks using differential cryptanalysis played a large part in the design of the S-boxes
and the permutation P. As evidence of the impact of these changes,
consider these comparable results
reported in [BIHA93]. Differential cryptanalysis of an eight-round LUCIFER algorithm requires only 256 chosen plaintexts, whereas an attack on an eight-round version
of DES requires 214 chosen plaintexts.

*DIFFERENTIAL **CRYPTANALYSIS *** ATTACK **The differential
cryptanalysis attack is complex; [BIHA93]
provides a complete description. The rationale behind differential cryptanalysis is to observe the behavior of pairs of text blocks
evolving along each round of the cipher, instead
of observing the evolution of a single
text block. Here, we provide a brief overview
so that you can get the flavor
of the attack.

We begin with a change in notation for DES. Consider the original plaintext block
*m *to
consist of two halves *m*0, *m*1.
Each round of DES maps the right-hand
input into the left-hand output
and sets the right-hand output
to be a function of the
left-hand input and the subkey for this round. So, at each round,
only one new 32-bit
block is created. If we label each new block
*m**i *(2 … *i *… 17), then the intermediate
message halves are
related as follows:

In differential cryptanalysis, we start with two messages, *m** *and *m*¿, with a known XOR difference Δ*m** *= *m** *NOR *m*¿, and consider the difference between the intermediate
message halves: Δ*m**i** *= *m**i** *NOR *m*¿*i*. Then we
have

Now, suppose that many pairs of inputs to f with the same difference yield
the same output difference if the same subkey is used. To put this more precisely, let us
say that *X **may cause Y with probability **p*, if for a fraction
*p *of the pairs
in which the input XOR is *X*, the output XOR equals *Y*. We want to suppose that there are a number of values of *X *that have high probability
of causing a particular output difference.
Therefore, if we know ¢*m**i *- 1 and ¢*m**i *with high probability, then we know ¢*m**i** *+ 1 with high probability. Furthermore, if a number of such differences are determined, it is feasible to determine the subkey used in the function f.

The overall strategy
of differential cryptanalysis is based on these considerations for a single round. The procedure is to begin with two plaintext messages *m** *and *m*¿ with a given difference and trace through
a probable pattern
of differences after
each round to yield
a probable difference for the ciphertext. Actually, there
are two proba-
ble patterns of differences for
the two 32-bit
halves: (¢*m*17 || ¢*m*16). Next, we submit *m *and *m*¿ for encryption to determine the actual difference under the unknown key and
compare the result to the probable
difference. If there is a match,

then we suspect that all the probable
patterns at all the intermediate rounds are correct. With that assumption, we
can make some deductions about the key bits. This procedure must be repeated
many times to determine all the key bits.

Figure 3.8, based
on a figure in [BIHA93], illustrates the propagation of differ- ences
through three rounds of DES. The probabilities
shown on the right refer to the probability that a given
set of intermediate differences will appear as a function

of the input differences. Overall, after
three rounds, the probability that the output difference is as shown is equal
to 0.25 * 1 * 0.25 = 0.0625.

Linear Cryptanalysis

A more recent
development is linear
cryptanalysis, described in [MATS93].
This attack is based on finding
linear approximations to describe
the transformations performed
in DES. This method can find a DES key given 243 known plaintexts, as compared to 247 chosen plaintexts for differential cryptanalysis. Although this is a minor improvement,
because it may be easier to acquire
known plaintext rather than chosen plaintext, it still leaves linear cryptanalysis infeasible as an attack on DES. So far, little work has been done
by other groups to validate the linear cryptanalytic approach.

We now give a brief summary of the principle
on which linear cryptanalysis is based. For a cipher with *n*-bit plaintext and ciphertext blocks and an *m*-bit key, let

(where *x *= 0 or 1; 1 <=
*a*;
*b *<= *n*; *c *<= *m*; and where the *a*, *b*, and
*g *terms represent fixed, unique bit locations) that holds
with probability *p *!= 0.5. The further *p *is from 0.5, the more effective the equation. Once a
proposed relation is determined, the pro- cedure is to compute the results of
the left-hand side of the preceding equation for a large number of
plaintext–ciphertext pairs. If the
result is 0 more than half the time, assume K[*g*1, *g*2, …..
, *gc*] = 0. If it is 1 most of
the time, assume K[*g*1, *g*2, …..
, *gc*] = 1. This gives us a linear equation
on the key bits.Try
to get more such relations
so that we can solve for the key bits.
Because we are dealing with linear equations,
the problem can be approached one round of the cipher at a time, with the results combined.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : One Symmetric Ciphers : Block Ciphers and the Data Encryption Standard : Differential and Linear Cryptanalysis |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.