1
$\begingroup$

I'm currently implementing the "distinguished points" collision finding algorithm on SHA-3 reduced to a lower number of bits. Let's say I'm going to find one collision on SHA-3-256bits reduced to first n=72 bits (meaning the higher 72 bits should be same). I'm choosing the number of bits d=14 for distinguished points, meaning if the lower 14 bits in those 72 bits are all 0, then this will be considered as a distinguished point(DP). My understanding and implementation can be divided by these steps:

  1. Create a number of threads. For each thread, random generate a starting point $x_0$. Create an empty global look-up table (unordered_map in C++) to store DPs.
  2. Define the iteration function f(x)=SHA3_256(x). Every thread keeps iterating with $x_{i+1}=f(x_i)$ until a DP $x_e$ is found. Then generate another random starting point, repeat.
  3. Check if it is a duplicated DP by querying the global look-up table. If not, store $(x_0,x_e)$ into the table. Else, find the actual collision if it isn't a "Robin Hood". A pair of DPs is considered duplicated only if both shares the same higher 72 bits. This means that if two hash values share a same higher 72 bits, ignoring the lower 256-72=184 bits, we consider it as a pair of valid DP duplication. Then we can find the actual hash collision in these two paths, as long as it isn't a "Robin Hood".

I'm currently doubting if I made some mistakes on my implementation. Specifically, my questions are:

  1. Is there any difference between my understanding and the algorithm illustrated originally in the paper? Am I correct?
  2. If correct, what should be the expected number of iterations performed and the expected number of DPs stored before finding a collision? From the paper I calculated the estimated number: $\sqrt{πn/2}+2.5/θ=1.25*2^{36}=8.5e^{10}$ iterations and divided by $2^d=2^{14}$ to be $5.2e^6$ DPs. Am I calculating it correct?
  3. If correct, I've produced $2.5e^7$ DPs and $4.1e^{11}$ iterations without finding a collision with my own implementation. To a smaller range, I tested my implementation on SHA3-256 reduced to 32 bits and chose d=10 as distinguished characteristic. The expected number of DPs should be 80, according to the calculation above, but by repeating the experiment for 20 times, I have to produce 2000 DPs and perform 3e6 iterations on average before finding a collision, which is far more than the estimated number by formula. Moreover, I switched the iteration function from SHA3 to a random number generator by using seed as input, and it gives me the same result. I have no idea if I'm just unlucky or if I actually made some mistakes in my implementation.
$\endgroup$
2
  • 1
    $\begingroup$ @kodlu It means if two hash values share a same higher 72 bits, ignoring the lower 256-72=184 bits, we consider it as a pair of valid DP duplication. e.g. Consider choosing d=16 as number of characteristic bits for DP. abcde0000123456789abcdef01234567 and abcde000022222222222222222222222 are considered duplicated. Then we can find the actual hash collision in these two paths, as long as it isn't a "Robin Hood". The overall idea is to reduce the overall complexity from attacking the whole 256 bits, in order to verify the correctness of my implementation with limited amount of resources. $\endgroup$
    – Froest
    Commented Apr 25 at 14:08
  • $\begingroup$ could you link the source where you get the formula? One has to run many independent events to verify the formula not just working with one. $\endgroup$
    – kelalaka
    Commented Apr 26 at 7:11

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.