SHA-256 Partial Collision of initial 36 bits and more

Question

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.

Answer 1

Actually, this sort of programming question is more suited for stackexchange.

However, to answer your question, there are two obvious approaches to speed up a collision search:

• Use a Hash table; that is, instead of keeping everything on one big list, divide them onto (say) 1024 different lists (in such a way that you know that items on two different lists aren't "matches"). And, given that you know that the SHA256 is already wonderfully distributed, you can (for example) select the hash table entry that a specific hash is placed on by using the first 10 bits of the SHA256 hash value; that way, you'll never have to explicitly compare two hashes that differ in the first 10 bits. That reduces the number of comparisons you'll need to do by 99.9%. Of course, you'll adjust the size of the hash table (that is, how many entries it contains) according to the resources you have.

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

I don't know which would be better in your situation; however it ought to give you something to think about.