Cryptography Reference
In-Depth Information
where and respectively, represent subsets of the differentials Ω
X
and Ω
Y
. The term
subsets
here means
that just some (or possibly all) of the bits that are different in characteristics will be different in the truncated
differential.
For example, DES itself has known truncated round characteristics of probability 1.
Knudsen in Reference [9] gives a simple attack on a five-round Feistel cipher with an
n
-bit round function
(and, therefore, a 2
n
-bit block size). Let the Feistel round function be
F
. Assume we have a non-zero input trun-
cated differential Ω
a
, using only some of the bits:
1. Let
T
be a table, potentially up to size 2
n
, of all zeros.
2. For every input value of
x
(all 2
n
of them), calculate
x
+ Ω
a
, and set the entry corresponding to the
output differential equal to 1, that is, set
This way, all possible output differentials corresponding to the truncated differential are marked and
known.
3. Choose a plaintext at random,
P
1
. Calculate
P
2
=
P
1
⊕
(Ω
a
|| 0), that is, the right half of the difference
is 0, and the left half is Ω
a
.
4. Calculate the encryptions of
P
1
and
P
2
, setting them to
C
1
and
C
2
, respectively.
5. For every value of the fifth round key,
k
5
, do the following:
(a) Decrypt one round of
C
1
and
C
2
using
k
5
, and save these intermediate ciphertexts as
D
1
and
D
2
.
(b) For every value of the fourth round key,
k
4
, do the following:
i.Calculate
t
1
= and
t
2
= ,wherethe
R
representstherighthalfofthe
D
-values.
ii. If is greater than 0, then output the values of
k
4
and
k
5
(where the
L
repres-
ents the left half of the
D
-values). Here, we are measuring if the truncated differential was seen.
This will generate a list of keys proportional to the number of key bits in the truncated differential. Repeating
this a sufficient number of times, we will have only a single set of keys come out each time.
We can use this same attack on any number of rounds by doing the exact same analysis, except for the first
three rounds. Naturally, with each application, we have to do more work and will have less precision.
Truncated differential analysis is a potentially powerful technique. It has been done on the Twofish Al-
gorithm [17] in Reference [14], although it has not been used in a successful attack as yet [16].
7.13 Impossible Differentials
Impossibledifferentials
were used successfully to cryptanalyze most of Skipjack [19] (31 out of 32 rounds) by
Biham, Biryukov, and Shamir [4].
The idea is fairly simple: Instead of looking for outcomes that are as highly probable as possible, we look
for events that cannot occur in the ciphertext. This means that, if we have a candidate key (or set of key bits)
that produces a differential with a probability of 0, then that candidate is invalid. If we invalidate enough of the
keys, then we will be left with a number reasonable enough to work with.
AsBiham etal.[4]pointout,events that shouldbeimpossible havebeenhistorically usedinotherevents [5].
For example, with a German Enigma machine, it was not possible for any plaintext character to be encrypted to
Search WWH ::
Custom Search