4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Thomas
    Apr 7, 2014 at 0:35
  • $\begingroup$ Yes, both poncho's hints helped me, how do I "accept" his answer? I wanted to vote up but because of low reputation... $\endgroup$
    – nvbach91
    Apr 8, 2014 at 2:13
  • $\begingroup$ Also see Marc Stevens' Hash Clash. I'm not sure if Stevens is doing anything with SHA-2 at the moment. $\endgroup$
    – user10496
    Oct 12, 2019 at 16:10

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Both methods worked for me. It's a shame I didn't think of those sooner. Thanks poncho! $\endgroup$
    – nvbach91
    Mar 10, 2014 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.