# 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? – Thomas Apr 7 '14 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... – nvbach91 Apr 8 '14 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 '19 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.