CRYPTOLOGY - Hacking: The Art of Exploitation - page 425

The basic idea is to split the plaintext into two paired values that are
enumerated along a vector. Every possible plaintext is hashed into ciphertext,
and the ciphertext is used to find the appropriate column of the matrix.
Then the plaintext enumeration bit across the row of the matrix is turned
on. When the ciphertext values are reduced into smaller chunks, collisions
are inevitable.

Plaintext Hash

test je HEA X1m66RV.

!J)h je HEA 38vqlkkQ

".F+ je HEA 1Tbde5FE

"8,J je HEA nX8kQK3I

In this case, the column for HEA would have the bits corresponding to the
plaintext pairs te , !J , ". , and "8 turned on, as these plaintext/hash pairs are
added to the matrix.
After the matrix is completely filled out, when a hash such as jeHEA38vqlkkQ
is entered, the column for HEA will be looked up, and the two-dimensional
matrix will return the values te , !J , ". , and "8 for the first two characters of
the plaintext. There are four matrices like this for the first two characters,
using ciphertext substring from characters 2 through 4, 4 through 6, 6 though
8, and 8 though 10, each with a different vector of possible first two-character
plaintext values. Each vector is pulled, and they are combined with a bitwise
AND. This will leave only those bits turned on that correspond to the plaintext
pairs listed as possibilities for each substring of ciphertext. There are also
four matrices like this for the last two characters of plaintext.
The sizes of the matrices were determined by the pigeonhole principle.
This is a simple principle that states: If k + 1 objects are put into k boxes, at
least one of the boxes will contain two objects. So, to get the best results, the
goal is for each vector to be a little bit less than half full of 1s. Since 95 4 , or
81,450,625, entries will be put in the matrices, there need to be about twice
as many holes to achieve 50 percent saturation. Since each vector has 9,025
entries, there should be about (95 4 · 2) / 9025 columns. This works out to be
about 18,000 columns. Since ciphertext substrings of three characters are
being used for the columns, the first two characters and four bits from the
third character are used to provide 64 2 · 4, or about 16 thousand columns
(there are only 64 possible values for each character of ciphertext hash).
This should be close enough, because when a bit is added twice, the overlap
is ignored. In practice, each vector turns out to be about 42 percent saturated
with 1s.
Since there are four vectors that are pulled for a single ciphertext, the
probability of any one enumeration position having a 1 value in each vector
is about 0.42 4 , or about 3.11 percent. This means that, on average, the 9,025
possibilities for the first two characters of plaintext are reduced by about 97
percent to 280 possibilities. This is also done for the last two characters, pro-
viding about 280 2 , or 78,400, possible plaintext values. Under the assumption
of 10,000 cracks per second, this reduced keyspace would take under 8 seconds
to check.