Is it feasible to get a hash collision for CRC32, MD-5 and SHA-1 on one file?m50Nn d Eh I X L89Kk 67SYyC89A a
I'm aware that individually, each has its weaknesses (especially CRC32), but is it feasible that a file could be created to falsely match all three?
migrated from superuser.com 9 hours ago
This question came from our site for computer enthusiasts and power users.
-
$\\begingroup$ I think it would be difficult to actively intend to get a simultaneous clash on all three given that they use different algorithms. Clashes are possible in each, sure, and you can engineer a clash in each if you are determined but I would have thought it would be difficult to get a clash in all three at the same time. It feels like the sort of thing that might be possible but technically unfeasible given the amount of effort required. Personally I'd be curious to see how probable this is. $\\endgroup$ – Mokubai 9 hours ago
-
$\\begingroup$ this Q&A has the (positive) answer except for the CRC part $\\endgroup$ – SEJPM♦ 8 hours ago
1 Answer
Finding a simultaneous collision for all three would take the effort of approximately $2^{72}$ SHA-1 compression function evaluations.
The overall idea would be to take the general $2^{67}$ idea found in the answer to How hard is it to generate a simultaneous MD5 and SHA1 collision? and perform the attack 33 successive times (generating 33 places in the hash image where we can take either $X_i$ or $Y_i$ without affecting either the MD5 or SHA-1 hash).
That'll give us a total of $2^{33}$ images with all the same MD5 and SHA-1 hash; there must be a pair of images with the same CRC-32 value as well, and so that solves the problem.
Whether $2^{72}$ operations is in the realm of feasibility is another question entirely...
-
$\\begingroup$ I was brought here by the curiosity of the question and I'm a bit hung up on the feasibility side. Yes it is technically possible but 2^72 is a number that my mind just spits back as "impossibly huge". Does this mean it is within the realms of a guy sitting in a basement with an old i3 box or is it all the computers in the world running until the eventual heat death of the universe? $\\endgroup$ – Mokubai 8 hours ago
-
$\\begingroup$ @Mokubai: it's probably closer to 'if the NSA (or possibly Goggle or Amazon) decide to devote all their assets on this one problem, they could probably do it in a not-unreasonable amount of time...'. $\\endgroup$ – poncho 8 hours ago
-
$\\begingroup$ Okay, so it's within the realms of possibility of nation-state actors, but probably beyond your average malware or script-kiddie. That is unless he has a pretty large botnet... Not unreasonable to achieve, but probably costs far more than it is ever going to worth unless the target is a) incredibly paranoid (to be using/checking all three hashes) and b) extremely high value. Thank you for indulging my curiosity :) $\\endgroup$ – Mokubai 8 hours ago
-
1$\\begingroup$ The Bitcoin network has a hash rate of $2^{72}$ hashes every three days. It's more than one guy in a basement but far less than heat death of the universe. It's also probably far less than what the NSA could manage. $\\endgroup$ – djao 5 hours ago
-
1$\\begingroup$ I was half expecting to see an answer of "Yeah, these two files." $\\endgroup$ – Joshua 1 hour ago