<p dir="ltr"><br>
Den 17 okt 2015 11:22 skrev "Natanael" <<a href="mailto:natanael.l@gmail.com">natanael.l@gmail.com</a>>:<br>
> 128 bit hashes can be attacked the same way with standard birthday collisions at 2^64 operations. Also note that a larger target set reduces the work of takes almost linearly IIRC, as 2^64 applies for one single target hash to match. 2^16 hashes in the set to match thus reduces it to 2^40, I think.<br>
><br>
> Just stick with strong 196 bit hashes or longer. SHA256 is good enough, but SHA3 ought to be a good choice too if you're starting from scratch.</p>
<p dir="ltr">I misremembered things here, sorry.</p>
<p dir="ltr">The pre-existing set of files can be considered to be precomputation done for you, on average 2^(128/2) = 2^64 total hashes still need to be computed to find a collision. With for example 2^32 existing hashes for 4 billion files, the effect isn't really noticeable:</p>
<p dir="ltr">2^(Log2(2^64-2^32)) = 2^63.9999999996641 work factor</p>
<p dir="ltr">However you get collisions more often once you finally got to this number of computed hashes, so at 2^65 work you likely will have 2 collisions already, and so on.</p>
<p dir="ltr">Since 2^(192/2) = 2^96 which will likely remain out of reach for decades, that recommendation still stands. Don't go below that number. </p>
<p dir="ltr">Also, I just remembered the Flame MD5 certificate collision attack. That's yet another attack algorithm faster than bruteforce.</p>