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.