1
$\begingroup$

How can I find two strings that have the same hash value for first $n$ bits in SHA-256? I'm implementing it by Python and I have the following ideas and problems:

  1. Keep generating two random string

    • What is the length of the string that I need to generate?
    • How to avoid generating the existing string again?
    • How many string should I generate in total?
  2. Hash the two random string and store in a dictionary

    • import hashlib in python
    • {random string : hash value}
  3. Loop the dictionary to check if there is two hash value share the same first n bits and return the two strings as a result

Please give me some advice on it.

$\endgroup$
  • $\begingroup$ Also see Kelsey's work at NIST on Truncated SHA hashes and Marc Stevens' Hash Clash. Kelsey's work is more theoretical, while Stevens' work is more practical. I'm not sure if Stevens is doing anything with SHA-2 at the moment. $\endgroup$ – user10496 Oct 12 at 16:08
1
$\begingroup$

If you use the same size input, there may no be a collision at all. It is better to increase the input size like double of $n$. Note that the input is padded so that the input to $\operatorname{SHA256}$ it is multiple of 512-bit.

  1. Keep generating two random string

You need to store all the hashes to see that there is a collision. If you don't store you may miss it. Since you are not storing, you can use an LFSR to generate uniquely, if you want.

Actually you should use Rho Method for this one, which is a low memory collision search.

  • Pick a random hash value $h_1=h_1'$
  • and compute $h_2 =\operatorname{SHA256}(h_1)$ and $h_2' = \operatorname{SHA256}(\operatorname{SHA256}(h_1'))$.
  • Continue to iterate $h_{i} = \operatorname{SHA256}(h_{i-1})$ and $h_{i}' = \operatorname{SHA256}(\operatorname{SHA256}(h_{i-1}'))$

These two sequences will eventually enter into a cycle, and there will be a tail (rho-shape $\rho$). The cycle start is the collision point.

Note: this algorithm is also known as Robert W. Floyd's Tortoise and Hare which is used for cycle detection.

  1. Hash the two random string and store in a dictionary

This can be better since hash tables can effectively search, up to amortized $\mathcal{O}(1)$-time Generate the hashes and look upon the hash table - if exist you have found, not exist then insert the new hash.

The performance is really depending on the value of $n$. If the value of $n$ is too big, you may choose the Rho method. Since when the needed memory becomes larger than your system memory, you will be slowed.

  1. Loop the dictionary to check if there is two hash value share the same first n bits and return the two strings as a result

In this case, you already store the data in the Python dictionary. Python dictionary is already implemented by hash tables. Therefore, you only need to use Python's existing dictionary functionalities.

If you want to use a double dimensional array (or similar structure) to store the value and hash you You first calculate all of the hashes up to a predetermined amount $n$, then sort the array with an $\mathcal{O}(n \log n)$-time sorting algorithm. After the sort, all you need to iterate and see that are there any adjacent elements is the same. This can be done in $\mathcal{O}(n)$-time

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.