Using Random Error Correcting Codes in Near-Collision Attacks on Generic Hash-Functions
Inna Polak and Adi Shamir
Abstract
In this paper we consider the problem of finding a near-collision
with Hamming distance bounded by in a generic cryptographic hash
function whose outputs can be modeled as random -bit strings.
In 2011, Lamberger suggested a modified version of Pollard's rho method
which computes a chain of values by alternately applying the hash
function and an error correcting code to a random starting
value until it cycles. This turns some (but not all) of the
near-collisions in into full collisions in , which
are easy to find. In 2012, Leurent improved Lamberger's memoryless
algorithm by using any available amount of memory to store the endpoints
of multiple chains of values, and using Van Oorschot and Wiener's
algorithm to find many full collisions in , hoping that one of
them will be an -near-collision in . This is currently the
best known time/memory tradeoff algorithm for the problem.
The efficiency of both Lamberger's and Leurent's algorithms depend
on the quality of their error correction code. Since they have to
apply error correction to \emph{any} bit string, they want to use
perfect codes, but all the known constructions of such codes can correct
only or errors. To deal with a larger number of errors,
they recommend using a concatenation of many Hamming codes, each capable
of correcting a single error in a particular subset of the bits, along
with some projections. As we show in this paper, this is a suboptimal
choice, which can be considerably improved by using randomly chosen
linear codes instead of Hamming codes and storing a precomputed lookup
table to make the error correction process efficient. We show both
theoretically and experimentally that this is a better way to utilize
the available memory, instead of devoting all the memory to the storage
of chain endpoints. Compared to Leurent's algorithm, we demonstrate
an improvement ratio which grows with the size of the problem. In
particular, we experimentally verified an improvement ratio of about
in a small example with and which we implemented
on a single PC, and mathematically predicted an improvement ratio
of about in a large example with and , using
memory.
@misc{cryptoeprint:2014/417,
author = {Inna Polak and Adi Shamir},
title = {Using Random Error Correcting Codes in Near-Collision Attacks on Generic Hash-Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2014/417},
year = {2014},
url = {https://eprint.iacr.org/2014/417}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.
PDF
