4
$\begingroup$

File-A is hashed with CRC32, MD5 and SHA-1.

How easy is it to create a fake file-B that has the same hashes of file-A? CRC32, MD5 and SHA-1?

Can an average PC with a GPU calculate a triple hash collision of file-A? And how long would it take?

$\endgroup$

2 Answers 2

11
$\begingroup$

How easy is it to create a fake file-b that has the same hashes of file-a? crc32, md5 and sha1?

This is known in cryptographical circles as the 'second preimage' problem.

With CRC32, it's easy; just take the original message and add in (that is, xor) some shifted copies of the CRC polynomial, and that won't change the hash. If you don't have the original file-a (you only have the hash), then constructing file-b would involve solving 32 simultaneous boolean equations - only slightly harder.

With MD5 and SHA-1, there's no known practical way. In both cases, the best approach we have is to try a huge number of arbitrary file-b's until we stumble on one with the expected hash - that's an infeasible amount of work in both cases.

Now, what is known with MD5 and SHA-1 is how to construct two different files with the same hash. However, these methods require being able to specify both files, and don't apply if one of the files is already given.

Can average pc with a gpu calculate triple hash collision of file-a?

There is no known way to do so (in practical time, e.g. before the sun turns into a Red Giant...)

$\endgroup$
2
4
$\begingroup$

As poncho writes we do not know how to practically find a second preimage for SHA1 or MD5 let alone one which will match both.

However we do know how to find collisions. Due to the nature of MD construction we can easily convert collisions into multi-collisions. Which means we can create many messages which will collide so many we can construct many collisions of SHA-1 (the wider hash) and get the rest via birthday attack. as described here: How hard is it to generate a simultaneous MD5 and SHA1 collision?

So a second preimage of these 3 seems well beyond us. But a collision of SHA-1 and MD5 will cost $2^{67}$ operations. We can do this again 16 times to construct a multi collision on both. and find a collision also for CRC32 (or any 32 bit hash even a strong one). This will make the total cost $2^{71}$ to construct two messages which collide in all 3 hashes. But this will be when attacker picks both messages not when one is provided. This is well beyond what a single powerful PC can do, but not beyond the means of a nation state ot a megacorp.

$\endgroup$
0

Your Answer

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

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