Cryptography Reference
In-Depth Information
4
Conventional Security Analysis
Content
Attack methods:
differential cryptanalysis, linear cryptanalysis
Security analysis:
nonlinearity, Markov ciphers
Security strengthening:
indistinguishability, dedicated construction, decorrelation
Previous chapters presented brute force attacks and dedicated attacks. This chapter
investigates classical general attack methods for conventional cryptographic algorithms
(namely, differential and linear cryptanalysis), and different ways to strengthen the
security in primitive design or to estimate the resistance against attacks. For further
readings we recommend the tutorial Ref. [90] of Howard Heys on differential and linear
cryptanalysis.
4.1
Differential Cryptanalysis
The idea of differential cryptanalysis is originally due to Eli Biham and Adi Shamir
from the Weizmann Institute in Israel.
1
It assumes a
chosen plaintext attack
model:
the adversary can play with the encryption device as a black box, submitting chosen
plaintexts and getting ciphertexts in return (see Fig. 4.1). The aim of the attack is to
recover the secret key.
The basic idea of differential cryptanalysis is to investigate differential behaviors:
we submit pairs of random plaintext blocks the difference of which is a fixed value
a
.
We then look at the corresponding ciphertext difference until it is a fixed value
b
.A
first analysis phase consists of looking for good
a
and
b
values in a heuristic way. A
crucial quantity is the differential probability defined by
DP
f
(
a
,
=
+
=
+
b
)
Pr[
f
(
X
a
)
f
(
X
)
b
]
where
f
is the encryption function and
X
is a uniformly distributed random variable.
The higher this probability is, the more efficient the attack is. Additional dedicated
tricks enable the analysis of complicated ciphers by using differentials on simplified
variants.
We illustrate the differential cryptanalysis paradigm by the example of DES re-
duced to eight rounds instead of sixteen.
1
See Refs. [28-31].
Search WWH ::
Custom Search