<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Sat, Oct 4, 2014 at 1:21 PM, Ben Laurie <span dir="ltr"><<a href="mailto:benl@google.com" target="_blank">benl@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">However, this is not a good way to go about designing crypto primitives.<br>
<div><div><br></div></div></blockquote><div><br></div><div>I disagree with this point.  This thread is an excellent way for people to *avoid* mistakes like this hash function.  People should be *encouraged* to post their latest dumb idea about hashing here, so it can be reviewed before harming anyone.<br><br></div><div>Furthermore, this thread introduces a valuable concept I was not aware of before, and it's fun :-)  The uses for such a hash function are I think quite broad.  For example, we could incrementally update a cryptographically strong hash of a huge database in constant time.  So... here's *my* dumb hashing solution for this problem:<br><br></div><div>Simply compute:<br><br></div><div>Digest = H(N || H(H(1 || B1) * H(2 || B2) * ... * H(n || Bn) mod p))<br><br></div><div>While I am often wrong, I have managed in my head to prove to myself that finding collisions in the generalized birthday problem over a multiplicative group modulo a prime is equivalent to solving the discrete log problem.  If this proof holds up, then this should be a secure hash, so long as p is large enough, such as 2048 bits.  Also, I assume that H is effectively a random oracle with no possible analysis of it's function that could help us find collisions.  Some hash functions, such as H(x) = g^x mod p clearly fail here.  However, any respected ARX based hash should work out, as should Wolfram's Rule-30-like hashes such as Keccak.<br><br></div><div>My proposed proof is simple.  Instead of picking true random numbers ri < p to multiply together, looking for a collision in the usual way, compute si = g^ri mod p for i in 1 .. n.  If g is a group generator, then si is just as random as ri, but we know something about si (it's discrete log).  Using a supposed algorithm faster than solving the discrete log, we now find the discrete log of y = g^x.  Just find r1 ... rn such that g^r1 * g^r2 * ... * g^rn = x, using our fast algorithm, and then the discrete log of x is trivially found as r1 + r2 + ... + rn mod p-1.<br><br></div><div>Surely, any algorithm that can find such solutions multiplying r1 * r2 * ... * rn will work just as well using ri = g^H(i) mod p as it would using the H(i) values as random numbers instead, so this step of replacing ri with si is sound.<br></div><div><br></div><div>Therefore, this hash function is secure, based on the security of the discrete log problem.<br><br></div><div>Does this work out?  If it is secure, as I currently believe, then it should have a number of good uses in cryptography.<br></div><div><br>Bill<br></div></div></div></div>