Cryptography Reference
In-Depth Information
Phase I: Table Computation
For a given plaintext
x
1
, compute a lookup table for
all pairs (
k
L
,
i
,
z
L
,
i
), where
e
k
L
,
i
(
x
1
)=
z
L
,
i
and
i
= 1
,
2
,...,
2
κ
. These computations
are symbolized by the left arrow in the figure. The
z
L
,
i
are the intermediate values
that occur in between the two encryptions. This list should be ordered by the values
of the
z
L
,
i
. The number of entries in the table is 2
κ
, with each entry being
n
+
bits
wide. Note that one of the keys we used for encryption must be the correct target
key, but we still do not know which one it is.
κ
Phase II: Key Matching
In order to find the key, we now decrypt
y
1
, i.e., we
perform the computations symbolized by the right arrow in the figure. We select the
first possible key
k
R
,
1
, e.g., the all-zero key, and compute:
e
−
1
k
R
,
1
(
x
1
)=
z
R
,
1
.
We now check whether
z
R
,
1
is equal to any of the
z
L
,
i
values in the table which we
computed in the first phase. If it is
not
in the table, we increment the key to
k
R
,
1
,
decrypt
y
1
again, and check whether this value is in the table. We continue until we
have a match.
We now have what is called a
collision
of two values, i.e.,
z
L
,
i
=
z
R
,
j
. This gives
us two keys: The value
z
L
,
i
is associated with the key
k
L
,
i
from the left encryption,
and
k
R
,
j
is the key we just tested from the right encryption. This means there exists
a key pair (
k
L
,
i
,
k
R
,
j
) which performs the double encryption:
e
k
R
,
j
(
e
k
L
,
i
(
x
1
)) =
y
1
(5.2)
As discussed in Sect. 5.2, there is a chance that this is not the target key pair we
are looking for since there are most likely several possible key pairs that perform
the mapping
x
1
→
y
1
. Hence, we have to verify additional key candidates by en-
crypting several plaintext-ciphertext pairs according to Eq. (5.2). If the verification
fails for any of the pairs (
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,...
, we go back to beginning of Phase II
and increment the key
k
R
again and continue with the search.
Let's briefly discuss how many plaintext-ciphertext pairs we will need to rule
out faulty keys with a high likelihood. With respect to multiple mappings between a
plaintext and a ciphertext as depicted in Fig. 5.9, double encryption can be modeled
as a cipher with 2
>
n
,
in which case we need several plaintext-ciphertext pairs. The theorem in Sect. 5.2
can easily be adopted to the case of multiple encryption, which gives us a useful
guideline about how many (
x
,
y
) pairs should be available:
κ
key bits and
n
block bits. In practice, one often has 2
κ
Theorem 5.3.1
Given are l subsequent encryptions with a block
cipher with a key length of
bits and block size of n bits, as well as
t plaintext-ciphertext pairs
(
x
1
,
y
1
)
,...,
(
x
t
,
y
t
)
. The expected num-
ber of false keys which encrypt all plaintexts to the corresponding
ciphertexts is given by:
κ
2
l
κ
−
tn
