I want to find any two strings with same hash in any hash algorithm ( at least try to find depends on its collision resistance). What kind of algorithm should I follow? Should I constantly produce two random strings and compare them until I find a collision? Or I also think to produce a large rainbow table and check if there is duplicate element. How can I find the collusion as fast as possible?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The currently best algorithm to finding collisions of generic hash functions is the parallel pollard-rho algorithm due to van Oorschot and Wiener (1994, PDF). A nice summary with an updated communications cost model can be found in Bernstein's "Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?" (2009, PDF). For an in-depth discussion, please refer to these two papers.
I shall now sketch the parallel pollard-rho algorithm. Let $b$ be the the length of the hash function $H$'s output in bits, let $c$ be a positive constant and let $\pi:\{0,1\}^b\to\{0,1\}^{b+c}$ be an injective padding function (in practice appending $c$ zero bits works). Furthermore let $M$ be the number of parallel processing units you have. Define the sequence $x_{n+1}:=\pi(H(x_n))$ with $x_0$ being arbitrary (but different for each processor).
Compute $x_i$ until the first $b/2-\lceil\lg M\rceil$ bits of $x_i$ are $0$ and call this a "distinguished point". We expect to have found a distinguished point after $2^{b/2}/M$ after time $2^{b/2}/M$ on all $M$ processors. Note that we have considered $2^{b/2}$ inputs for $H$ at this point across all processors.
Now we only need to look through our list of $M$ distinguished points and find two which are equal, this can be done using e.g. distributed sorting algorithms in time aboutt $O(\sqrt M)$. As the starting values for the sequences were different, but the end values are the same, there must must be a collision in them.
Let's call the matching distinguished points $y_j$ and $z_k$, now compute $|j-k|$, i.e. the difference in the sequence lengths. Go back to their respective starting values and apply the iteration $|j-k|$ times on the starting value which had the larger index for the distinguished point. Now iterate the sequences in parallel until you find the collision.
All in all this algorithm will take about $O(2^{b/2}/M)$ time and a negligible amount of memory per processor.
Should I constantly produce two random strings and compare them until I find a collision?
No, this will likely take time $2^b$, because you only consider two strings at a time and not all strings you have evaluated so far.
-
$\begingroup$ Thank you, do you know if there is any example implementation of this algorithm? $\endgroup$ Oct 14, 2017 at 8:19
-
1$\begingroup$ It might be good to mention that in practice, nobody actually cares about the kind of random collisions this algorithm produces. However, it is easy to amend the algorithm so that it produces meaningful collisions, by modifying $\pi$ appropriately. The analysis becomes slightly more complicated too, since not all collisions will help the adversary. $\endgroup$– K.G.Oct 14, 2017 at 9:29
-
$\begingroup$ @venturemoo I'm not aware of any implementation for hash-collision search, however I found the related implementation for solving the ECDLP. But implementing it yourself shouldn't be too hard, especially if you use centralized instead of distributed sorting. $\endgroup$– SEJPMOct 14, 2017 at 11:07
-
$\begingroup$ @venturemoo did you manage to find or implement the algorithm? I was also looking for an implemetation $\endgroup$– icyfireSep 25, 2022 at 1:37