Cryptography Reference
In-Depth Information
corresponding message number (which allows the retrieval of the message) in the
entry whose index is the obtained hash value (storing database entries this way is
one important—noncryptographic—application of hash functions). Then she would
start computing the hash values of variants of
m2
and, for each of them, she would
check whether the array entry corresponding to that index is filled and, if this is the
case, she would obtain the required collision without having to search the array. The
problem is that this method requires the use of a one-dimensional array of size 2
40
and Maple cannot handle arrays so large (and much less in Eve's world). This is an
extreme example of a “time-memory trade-off” in which using a very large array—
which means using a lot of memory—reduces searching, and hence computing time,
to a minimum.
Exercise 5.17
Use Maple to implement the attack just mentioned when the hash
function used is MD5 truncated to its first 24 bits. Use a 2
24
-sized Maple
Array
to store 2
14
message numbers, corresponding to variants of
m1
, in the array entries
whose indices are the corresponding hash values and then search for a collision with
one of the variants of
m2
.
Eve regrets that she does not have enough memory to carry out this attack against
Hash40
but, things being as they are, she thinks of another way to do it. The problem
with the preceding method is that using hash values as indices requires a 2
40
-sized
Array
but what if she instead uses the message numbers as indices? Eve soon
realizes that, as she only is going to use 2
21
values for the variants of
m1
, she can
store them in a one-dimensional
Array
of size 2
21
indexed this way. Then she can
compute the hashes of variants of
m2
until finding a collision. The problem now is
that, in exchange for the much lower memory requirements, this method requires
searching the array for each computed hash value of a variant of
m2
. Eve knows
that searching an unordered array (or list) is very inefficient (the naive algorithm
that scans the array elements one by one has linear complexity
O
, where
n
is the
array length) and so this method would require close to 2
40
comparisons. But, finally,
Eve realizes that there is a much better way that still allows a form of time-memory
trade-off. She is going to build a table indexed by the hash values of the 2
21
variants
of
m1
whose entries are the corresponding message numbers. Afterwards, she will
sort the list of indices of this table (i.e., the list of hash values of variants of
m1
)
using Maple's built-in implementation of merge sort (with complexity
O
(
n
)
),
which will require on average less than 2
26
comparisons and will be feasible with
her computing resources. Finally, she will generate the hashes of variants of
m2
and,
using the binary search algorithm, search for each of them on the sorted list of table
indices. When she finds one of these values in the indices list she has found the
required collision. The binary search algorithm has complexity
O
(
n
ln
n
)
(
)
, which is
much faster than the linear complexity of the naive algorithm mentioned above (see
[116] for details on sorting and searching algorithms).
This attack is implemented in Maple's function
FindCollision
below. The
inputs are two text strings, the name of the hash function used, and the output length
(in bits) of this function. The output is a list containing two text strings which are vari-
ln
n
