Cryptography Reference
In-Depth Information
More interestingly, several cryptanalytical attacks have been developed in an
attempt to break the security of DES. Examples include
differential cryptanalysis
[3]
and
linear cryptanalysis
[4]. Using differential cryptanalysis to break DES requires
2
47
chosen plaintexts, whereas linear cryptanalysis requires 2
43
known plaintexts.
13
In either case, the amount of chosen or known plaintext is far too large to be
practically relevant. The results, however, are theoretically interesting and have
provided principles and criteria for the design of secure block ciphers (people have
since admitted that defending against differential cryptanalysis was one of the design
goals for DES [5]).
From a practical viewpoint, the major vulnerability and security problem of
DES is its relatively small key length (and key space). Note that a DES key is
effectively 56 bits long, and hence the key space comprises only 2
56
elements.
Consequently, a key search is successful after 2
56
trials in the worst case and
2
56
/
2=2
55
trials on the average. Furthermore, the DES encryption has the
following property:
DES
k
(
m
)=
DES
k
(
m
)
(10.3)
This property can be used in a known-plaintext attack to narrow down the key
space with another factor of two. If the adversary knows two plaintext-ciphertext
pairs (
m, c
1
) with
c
1
=
DES
k
(
m
) and (
m, c
2
) with
c
2
=
DES
k
(
m
),thenheor
she can compute for every key candidate
k
the value
c
=
DES
k
(
m
) and verify
whether this value matches
c
1
or
c
2
.
If
c
=
c
1
,then
k
is the correct key. In fact,
k
=
k
follows from
c
=
DES
k
(
m
) and
c
1
=
DES
k
(
m
).
•
If
c
=
c
2
,then
k
is the correct key. In fact,
k
=
k
•
follows from
c
=
DES
k
(
m
),
c
2
=
DES
k
(
m
), and (10.3).
So in every trial with key candidate
k
, the adversary can also verify the
complementary key candidate
k
. As mentioned earlier, this narrows down the key
space with a factor of two. Against this background, it can be concluded that an
exhaustive key search is successful after 2
54
trials on the average.
The feasibility of an exhaustive key search was first publicly discussed in 1977
[6]. Note that an exhaustive key search needs a lot of time but almost no memory.
On the other hand, if one has a lot of memory and is willing to precompute the
ciphertext
c
for any given plaintext message
m
and all possible keys
k
, then one can
store the pairs (
c, k
) and quickly find the correct key in a known-plaintext attack.
Consequently, there is a lot of room for time-memory tradeoffs (e.g.,[7]).
13
Both cryptanalytical attacks require less plaintexts if one reduces the number of rounds.
