Score:3

How easy is it to fake a file hashed with three functions, CRC32, MD5 and SHA-1?

pk flag

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?

Score:10
my flag

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

ma flag
With CRC-32, it's very easy: https://www.nayuki.io/page/forcing-a-files-crc-to-any-value
nisc avatar
it flag
@Nayuki that's what poncho is saying
Score:4
in flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.