Cryptography Reference
In-Depth Information
Among the approximately 2
16
key candidates
k
(
i
)
is the correct one that was used
by to perform the encryption. Let's call this one the target key. In order to identify
the target key we need a second plaintext-ciphertext pair (
x
2
,
y
2
). Again, there are
about 2
16
key candidates that map
x
2
to
y
2
. One of them is the target key. The other
keys can be viewed as randomly drawn from the 2
80
possible ones. It is crucial to
note that the target key must be present in
both
sets of key candidates. To determine
the effectiveness of a brute-force attack, the crucial question is now: What is the
likelihood that another (false!) key is contained in both sets? The answer is given by
the following theorem:
Theorem 5.2.1
Given 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 number of false keys which en-
crypt all plaintexts to the corresponding ciphertexts is:
κ
2
κ
−
tn
Returning to our example and assuming two plaintext-ciphertext pairs, the likeli-
hood of a false key
k
f
that performs both encryptions
e
k
f
(
x
1
)=
y
1
and
e
k
f
(
x
2
)=
y
2
is:
2
80
−
2
·
64
= 2
−
48
This value is so small that for almost all practical purposes it is sufficient to test two
plaintext-ciphertext pairs. If the attacker chooses to test three pairs, the likelihood
of a false key decreases to 2
80
−
3
·
64
= 2
−
112
. As we saw from this example, the like-
lihood of a false alarm decreases rapidly with the number
t
of plaintext-ciphertext
pairs. In practice, typically we only need a few pairs.
The theorem above is not only important if we consider an individual block ci-
pher but also if we perform multiple encryptions with a cipher. This issue is ad-
dressed in the following section.
5.3 Increasing the Security of Block Ciphers
In some situations we wish to increase the security of block ciphers, e.g., if a ci-
pher such as DES is available in hardware or software for legacy reasons in a given
application. We discuss two general approaches to strengthen a cipher, multiple en-
cryption and key whitening. Multiple encryption, i.e., encrypting a plaintext more
than once, is already a fundamental design principle of block ciphers, since the
round function is applied many times to the cipher. Our intuition tells us that the
security of a block cipher against both brute-force and analytical attacks increases
by performing multiple encryptions in a row. Even though this is true in principle,
there are a few surprising facts. For instance, doing double encryption does very
little to increase the brute-force resistance over a single encryption. We study this
