Cryptography Reference
In-Depth Information
A distinguisher between
r
=
1 rounds and a random permutation can be
transformed into a key recovery attack against
r
rounds. For instance, here is an attack
on
r
r
−
=
6 rounds.
1: pick
c
1
,...,
c
32
2: pick an affine space
{
X
j
=
(
A
1
,
j
,...,
A
32
,
j
,
c
1
,
j
,...,
c
32
,
j
)
}
of dimension
2
r
−
2
+
1
=
9
(
Y
j
,
Y
j
3: get
Y
j
=
C
(
X
j
)
=
)
4: find
K
r
such that
j
Y
j
=
j
f
(
Y
j
⊕
K
r
)
We notice that the affine space consists of 2
9
512 elements. The worst number of
operations in Step 4 is thus 512 times the number of possible round keys which is 2
33
.
We thus have an attack of complexity 2
42
. More generally, an attack against
r
rounds
would have led to a complexity of 2
33
=
2
2
r
−
3
+
1
×
elementary operations. When
r
<
8,
this is better than the codebook attack.
Another way to use the Nyberg-Knudsen Theorem consists of having an iterative
construction. This was the idea of Mitsuru Matsui who invented the MISTY cipher
(see Refs. [126, 127]). A variant of MISTY (KASUMI) is used in the UMTS mobile
telephone network (see Ref. [9]).
4.4
Modern Security Analysis
Although the design of modern block ciphers started in the seventies, all approaches we
have seen so far are essentially empirical or heuristic. We cannot formally guarantee
the security against any attack. Even when we restrict ourselves to differential and
linear attacks, we always need to rely on some heuristic hypothesis in order to estimate
the best characteristics. One exception though: the ad hoc construction based on the
Nyberg-Knudsen result we have seen in Section 4.3.4. This construction however does
not provide so much flexibility for the design, and even introduces other potential
weaknesses. For this reason conventional cryptography seems to be bound to remain
an art which is only accessible to experts. In this section we investigate new ways to
formally address the problem. These results are an attempt to build up a theory for
block ciphers in order to move from an artistic status to a scientific status.
4.4.1
Distinguishability Security Model
Indistinguishability
is a strong notion of security for block ciphers. Formally, a
distin-
guisher
is a machine which plays with an oracle and ultimately outputs 0 or 1. (The
notion of “machine” depends on the computational model. In Chapter 8, we will define
the notion of
Turing machine
.) We measure the ability to distinguish a random oracle
from another by the
advantage
, which is the difference between the expected output
with both random oracles. The actual power of the machine depends on the security
Search WWH ::
Custom Search