5
$\begingroup$

I have seen a lot of different files with the same MD5s. For CRC32 is quite easy to find collision. But is is it possible to make size, and two different hashes the same?

I have seen many linux packages has only one SHA test-sum, why not to increase security with another hashing function?

(I am not asking about SHA family - answer is YES, possible, but MUCH MORE UNREALISTIC)

$\endgroup$
  • 1
    $\begingroup$ All known methods for producing MD5 and SHA1 collisions faster than brute force will produce a collision of two inputs of identical length. So including the size provides zero additional security. $\endgroup$ – kasperd Nov 1 '17 at 21:07
  • 1
    $\begingroup$ In the same paper (see below) Joux also finds that using two different hashes is not more secure than using a single hash. $\endgroup$ – OrangeDog Nov 2 '17 at 1:06
  • $\begingroup$ @OrangeDog Yes, now I understand that is better to use more difficult hashing function than many less-collision stable. $\endgroup$ – XuMuK Nov 2 '17 at 12:01
10
$\begingroup$

Is it possible to make two files with the same size and the same MD5 and CRC32?

It's straight-forward.

First off, we start with Joux's multicollision attack (PDF) to generate $2^{33}$ different same-sized files with the same MD5. Here's how that works; the MD5 collision attack works by starting with an internal MD5 state $S$, and finding two different blocks $B_0, B_1$ such that, with the MD5 compression function, $\text{MD5Compress}( S, B_0 ) = \text{MD5Compress}( S, B_1 )$. Finding such a $B_0, B_1$ is fairly easy.

What Joux's attack is ask us to do that 33 times to succesive states; and so we have $2^{33}$ different sequences (as there are $2^{33}$ different ways of selecting $B_0, B_1$ values) that all hash to the same final value.

Once we have that, we know that there exists a pair of files with the same CRC32 value (and actually, we don't need to search through them all, with CRC32, we can find such a pair with linear algebra)

$\endgroup$
  • 2
    $\begingroup$ Could you improve your question by explaining how are the files found with linear algebra? $\endgroup$ – Tomáš Zato Nov 1 '17 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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