<div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Thu, Nov 1, 2018 at 3:57 PM Kristian Gjøsteen <<a href="mailto:kristian.gjosteen@ntnu.no">kristian.gjosteen@ntnu.no</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">31. okt. 2018 kl. 23:03 skrev <a href="mailto:jamesd@echeque.com" target="_blank">jamesd@echeque.com</a>:<br>
> Launching a birthday attack on a 128 bit hash would involve generating 2^64 hashes and sorting them.<br>
<br>
Does it? Pollard’s lambda certainly does not. I believe it can be made parallel with the usual techniques. That is, you can find collisions with little communication and insignificant storage.<br><br></blockquote><div>Parallel Pollard Rho works in ~2^64 time, and has trivial memory and communication overhead.  A recent paper about this algorithm that was invented in 1994:</div><div><a href="https://www.semanticscholar.org/paper/Parallel-hash-collision-search-by-Rho-method-with-Weber-Zhang/a953b65f6feb9dae15f5cb0d9458579836a1199e">https://www.semanticscholar.org/paper/Parallel-hash-collision-search-by-Rho-method-with-Weber-Zhang/a953b65f6feb9dae15f5cb0d9458579836a1199e</a>  </div><div><br></div><div>128-bit is simply not collision resistant for any modern efficiently computed hash.  If you don't care about collisions, sha1 still is secure.  There are <a href="https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html">already collisions for SHA1</a>.  Generating the collision took ~2^63 SHA1 computations.  Google did it for fun (well... really to make the point that SHA1 is insecure).</div><div><br></div><div>Bill</div></div></div></div>