Cryptography Reference
In-Depth Information
4b 47 53 21 40 23 24 25
Assuming that we have the final hash, we wish to find a password that gives this hash. With 26 letters and
10 numbers, we have 36 different characters possible in the password. With seven positions, we then have 36
7
= 78,364,164, 096 different possible ciphertexts corresponding to the original plaintext. With each ciphertext
occupying 64 bits, it would require 626,913,312,768 bytes (about 583 GB
2
)
to store a table of every possible
password. Only in the past couple of years has this kind of storage been available. Even so, it may not be prac-
tical to store quite so much. We also would not want to perform 36
7
encryptions for every key.
Luckily, we could use rainbow tables that will allow us to easily break this in far less time and space.
Oechslin even used this problem as one of the first demonstrations of rainbow tables [10]. The rainbow table
attack demonstrated used five tables, each having 35,000,000 rows (chains) with 4,666 columns (elements in
the chain). Using such a table, the passwords were cracked in a matter of seconds.
5.4 Slide Attacks
A generally held belief among cryptographers is that merely increasing the number of rounds of even a weak
cipher will increase the strength of the cipher. Although this may be true against certain attacks, such as those
that rely on probabilities of each individual round (where the number of rounds can dictate how effective the
attack is), it cannot be taken for granted.
Oneattack inparticular canworkonanynumberofrounds,sinceittakesadvantage ofthekeyschedule. This
attack is called the
slideattack
[2] (name chosen by Bruce Schneier). It can be used as either a known-plaintext
or chosen-plaintext attack.
The basic attack, as described in Reference [2], requires two properties. First, the attack requires that the
cryptographic algorithm have a
weak
round function — “weak” is used to mean that, if given two blocks,
A
and
B
, and a found function,
F,
it is computationally “easy” to tell if
B
=
F(A),
regardless of the key used. Although
this requirement seems strong, many ciphers are built around weak round functions.
The second requirement is less reasonable. The attack works only with fairly weak key-scheduling al-
gorithms, such as using the same key every round, or alternating between two keys every round.
Although these requirements may not be practical for most ciphers, slide attacks have been used successfully
on several ciphers, including variants of Blowfish and DES (some of which were meant to strengthen their se-
curity) [1,2].
At this point, we will also assume that each round function is identical. (For most ciphers, this will not be
quite true, since each round will depend on a different portion of the key schedule.) Hence, we will refer to them
both as
F.
Theknown-plaintextstrategyistocollectalargenumberofknownplaintextsandtheircorrespondingcipher-
texts. The goal is to find two plaintext-ciphertext pairs, say,
(P,C)
and
(Q,D),
such that
Q = F(P).
As we can
see from
Figure 5-1
,
if
Q = F(P),
then we also know that
D = F(C),
since they are only off by 1.
Search WWH ::
Custom Search