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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ how many supercomputers do you have? $\endgroup$
    – Richie Frame
    Feb 17, 2016 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, 2016 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, 2016 at 6:48

2 Answers 2

Reset to default
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.

Improve this answer
$\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

Improve this answer
$\endgroup$

Your Answer

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

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