SHA-256 : Finding two strings that the first n bits of hash value are same 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:


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?

Hash the two random string and store in a dictionary 


import hashlib in python
{random string : hash value}

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.
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.


  
  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. 


  
  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. 


  
  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