哈希生日悖论

Question

So I am working on a piece of code that computes the hashes of 2^4 sets of 3 random prime numbers (less than 2^8). Then keep selecting sets of 3 composite numbers (less than 2^8) until there is a set of {c1, c2, c3} with a hash value that matches one of the previous hashes (the prime ones), that set would be known as {p1,p2,p3}.

From my understanding the birthday attack is basically finding two functions that provide the same result. So I would create 2 functions? One for the prime numbers and then another for composite? What would the best way of doing this be? I am thinking PHP as the language.

Any help would be greatly appreciated.

Answer 1

I think the premise is looking for a set of any 3 numbers < 2^8 that produces the same hash value as a set of 3 prime numbers using the same hash function.

Not stated is the range of the hash value.

The birthday attack is based on the fact that since the range of the hash value is limited, a brute force method that tries hashing all combinations of 3 numbers < 2^8 is likely to produce some collisions with valid hash values well before actually trying all possible combinations. However, in this case, trying all combinations of 3 numbers < 2^8 only takes 16777216 loops, so a complete brute force approach can be used.

The program could create a histogram of all the possible hash values . Since there are only 54 primes < 2^8, generating the histogram for all valid inputs (3 primes) would take 54^3 = 157464 loops.

Checking for collisions using all sets of 3 numbers < 2^8 would take 2^24 = 16777216 loops, which shouldn't take too long depending on the hash algorithm.