Cryptography Reference
In-Depth Information
assured that the cipertext (and
ADD
) were not manipulated in transit and that only
the sender could have generated the message.
5.2 Exhaustive Key Search Revisited
In Sect. 3.5.1 we saw that given a plaintext-ciphertext pair (
x
1
,
y
1
) aDESkeycan
be exhaustively searched using the simple algorithm:
?
=
y
1
,
i
= 0
,
1
,...,
2
56
DES
k
i
(
x
1
)
−
1
.
(5.1)
For most other block ciphers, however, a key search is somewhat more complicated.
Somewhat surprisingly, a brute-force attack can produce
false positive
results, i.e.,
keys
k
i
are found that are not the one used for the encryption, yet they perform a
correct encryption in Eq. (5.1). The likelihood of this occurring is related to the
relative size of the key space and the plaintext space.
A brute-force attack is still possible, but several pairs of plaintext-ciphertext are
needed. The length of the respective plaintext required to break the cipher with a
brute-force attack is referred to as
unicity distance
. After trying every possible key,
there should be just one plaintext that makes sense.
Let's first look why one pair (
x
1
,
y
1
) might not be sufficient to identify the correct
key. For illustration purposes we assume a cipher with a block width of 64 bit and a
key size of 80 bit. If we encrypt
x
1
under all possible 2
80
keys, we obtain 2
80
cipher-
texts. However, there exist only 2
64
different ones, and thus some keys must map
x
1
to the same ciphertext. If we run through all keys for a given plaintext-ciphertext
pair, we find on average 2
80
/
2
64
= 2
16
keys that perform the mapping
e
k
(
x
1
)=
y
1
.
This estimation is valid since the encryption of a plaintext for a given key can be
viewed as a random selection of a 64-bit ciphertext string. The phenomenon of mul-
tiple “paths” between a given plaintext and ciphertext is depicted in Fig. 5.9, in
which
k
(
i
)
denote the keys that map
x
1
to
y
1
. These keys can be considered key
candidates.
Fig. 5.9
Multiple keys map between one plaintext and one ciphertext
