2
$\begingroup$

I am trying to find two collisions in SHA1 for the 50 least significant bits. I was wondering if there was a way to efficiently do this without having to brute force all of the possible hash outputs?

It seems like trying to look for two same hash outputs is easier than trying to find a message that hashes and matches to a hash output I already have. (i.e. trying to break preimage resistance rather than second preimage resistance) But this still seems like I would need to brute force all the possibilities

$\endgroup$
  • 1
    $\begingroup$ how many supercomputers do you have? $\endgroup$ – Richie Frame Feb 17 '16 at 4:18
  • 1
    $\begingroup$ @RichieFrame: actually, I'd expect a search for a 50 bit collision to take a few seconds on a laptop... $\endgroup$ – poncho Feb 17 '16 at 4:24
  • 1
    $\begingroup$ @poncho for brute force yes, but to do it "efficiently" without brute force will probably take a crap load of memory $\endgroup$ – Richie Frame Feb 17 '16 at 6:48
2
$\begingroup$

The easiest way to find a collision in 50 bits is to hash distinct values (random, incrementing, however's convienent), and put the results in a hash table, based on the 50 bits you're interested in. When you insert a value into the hash table, and there's already an entry there, you've found a collision.

With 50 bits, you expect to have to hash around $2^{25}$ values, or about 30 million or so; if you're unlucky, you might run into 50 or 100 million before hitting a collision. That many entries easily fits into memory, and so this works out fairly well.

$\endgroup$
0
$\begingroup$

You can use the SHAttered attack which is 100,000 faster than the brute force attack as it relies on the birthday paradox.

Source: shattered.io

$\endgroup$

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.