Graphics Programs Reference
In-Depth Information
possible hashes for a single plaintext password, necessitating 4,096 different
tables. This raises the needed storage space up to about 4.6 terabytes, which
greatly dissuades such an attack.
0x764
Password Probability Matrix
There is a trade-off between computational power and storage space that
exists everywhere. This can be seen in the most elementary forms of computer
science and everyday life. MP3 files use compression to store a high-quality
sound file in a relatively small amount of space, but the demand for compu-
tational resources increases. Pocket calculators use this trade-off in the other
direction by maintaining a lookup table for functions such as sine and cosine
to save the calculator from doing heavy computations.
This trade-off can also be applied to cryptography in what has become
known as a time/space trade-off attack. While Hellman's methods for this
type of attack are probably more efficient, the following source code should
be easier to understand. The general principle is always the same, though:
Try to find the sweet spot between computational power and storage space,
so that an exhaustive brute-force attack can be completed in a reasonable
amount of time, using a reasonable amount of space. Unfortunately, the
dilemma of salts will still present itself, since this method still requires some
form of storage. However, there are only 4,096 possible salts with
crypt()
-style
password hashes, so the effect of this problem can be diminished by reducing
the needed storage space far enough to remain reasonable despite the 4,096
multiplier.
This method uses a form of lossy compression. Instead of having an
exact hash lookup table, several thousand possible plaintext values will be
returned when a password hash is entered. These values can be checked
quickly to converge on the original plaintext password, and the lossy com-
pression allows for a major space reduction. In the demonstration code that
follows, the keyspace for all possible four-character passwords (with a fixed
salt) is used. The storage space needed is reduced by 88 percent, compared
to a full hash lookup table (with a fixed salt), and the keyspace that must be
brute-forced through is reduced by about 1,018 times. Under the assumption
of 10,000 cracks per second, this method can crack any four-character pass-
word (with a fixed salt) in under eight seconds, which is a considerable
speedup when compared to the two hours needed for an exhaustive brute-
force attack of the same keyspace.
This method builds a three-dimensional binary matrix that correlates
parts of the hash values with parts of the plaintext values. On the x-axis, the
plaintext is split into two pairs: the first two characters and the second two
characters. The possible values are enumerated into a binary vector that is
95
2
, or 9,025, bits long (about 1,129 bytes). On the y-axis, the ciphertext is
split into four three-character chunks. These are enumerated the same way
down the columns, but only four bits of the third character are actually used.
This means there are 64
2
ยท 4, or 16,384, columns. The z-axis exists simply to
maintain eight different two-dimensional matrices, so four exist for each of
the plaintext pairs.
