Article,
Cycle Finding Techniques for Hash Functions
(2011)
Abstract
Finding collision in a hash function is not a trivial task. Even if a serious leak
is found in the hash function, leading to the reduction of iterations before the detection
of the collision, enormous number of values need to be computed. Some
of the major problems are storing, indexing and searching such amount of values.
Introducing cycle finding techniques for finding the collision can be the solution
for this problem. They reduce needs for the storage size. The penalty for this
approach is an additional evaluation of the function and an increment of the time
complexity. These techniques use a property of the function defined over the finite
set. If the output value of the hash function deterministic evaluates the input value
of the next one, the trial must start cycling eventually. Various characteristics and
comparisons were investigated and proved by practical experiments and performed
on 1 bit version of RadioGatùn hash function designed by Guido Bertoni et al. 6.
All theoretical and practical observations are mostly focused on the distinguished
point as well as Nivasch, Floyd and Brent methods.
