# SHA-256 Partial Collision of initial 36 bits and more

I was lucky enough to, by brute force, have found two different messages, whose SHA-256 hashes collide in the first 9 hexadecimal characters, which are 36 bits, let's call this hash-prefix.

Given the Birthday Problem, I had to put together 2^18 or rather 2^(36/2) hashes so the chance of success at finding the two messages that have hash-prefix collision would increase to about 50%. I did find them by just gradually comparing the prefixes of each hash with another. The process didn't take too long, but that's why I was lucky.

I want to find 2 different messages that, after hashing, collide in more than 36 initial bits. Can you please help me to come up with a better strategy when comparing hashes?

Here is my method for comparing the hash-prefixes:

class FindPartialCollision {
private:
...

public:
...

bool compare(vector<string> sv, int n_Hashes) {
for (int i = 0; i < n_Hashes; i++) {
for (int j = i + 1; j < n_Hashes; j++) {
if (sv.at(i) == sv.at(j)) {
cout << "COLLISION FOUND." << endl;
return true;
}
}
}
cout << "No collision found." << endl;
return false;
}

...
}


Note that vector<string> sv only contains the initial x-character string taken from each SHA-256 hash of each messages, where x is the desired length to compare.

For example, if I were to look for a pair of messages, whose hashes collide in the first 10 hexadecimal characters, the n_Hashes value passed into this method would be 16^(10/2) = 2^(40/2) = 2^20 = 1 048 576, which is already too big and would result in a huge time complexity.

Any help is much appreciated and I'm sorry for the amateurish question.

• Just keep in mind that you're not going to be able to get more than 80 or maybe 90 bits colliding, so don't be disappointed if it becomes prohibitively slow - it's supposed to! But poncho's optimizations should get you most of the way there. Would you care to accept poncho's answer if it helped you, by the way? Apr 7, 2014 at 0:35
• Yes, both poncho's hints helped me, how do I "accept" his answer? I wanted to vote up but because of low reputation... Apr 8, 2014 at 2:13
• Also see Marc Stevens' Hash Clash. I'm not sure if Stevens is doing anything with SHA-2 at the moment.
– user10496
Oct 12, 2019 at 16:10

• Use a sort algorithm; that is, use a good algorithm to sort the hashes into ascending order; that way, any 'close' matches will be adjacent, and so that's the only comparisons you'll need to make. A good sorting algorithm on $N$ elements can be done in $O(N \log N)$ time, hence this is much faster than individually comparing each element.