<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Oct 8, 2014 at 9:24 PM, Bill Cox <span dir="ltr"><<a href="mailto:waywardgeek@gmail.com" target="_blank">waywardgeek@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div>This was Creating a Parallelizeable Cryptographic Hash Function, started by Jason Resch.  His XORing hashes together is not secure, but doing the same thing with multiplication modulo a prime appears to be.<br><br></div>The hash function is:<br><br></div>    Digest y = H(1 || B1) * H(2 || B2) * ... * H(n || Bn) mod p<br><br></div>The prime p should be large, such as 2048 bits, because if an attacker can compute the discrete log of the H values mod p, he can easily find collisions.<br></div><br><div>My security proof is simple.  Assume an attacker has found an algorithm that takes essentially random numbers ri as inputs (the H values for each i), and finds a way to multiply some of them together to equal the previous digest.  All we do is change his algorithm so that instead of picking various ri = H(i) to multiply together, compute instead si = g^ri mod p for each i used by the algorithm.  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 the attacker's algorithm, we now find the discrete log of y = g^x.  Just find s1
 ... sn such that s1 * s2 * ... * sm = x, and then the discrete log of x is trivially found as r1 + r2 +
 ... + rn mod p-1.<br><br></div>I've had a few days to noodle on this proof, and I now believe it is sound.  If the world needs a constant-time updateable parallel hash function, this should do the job.  When we add new messages to the end, we can compute the new digest in constant time.  We can also replace any existing message Bi with Bi', and compute the new hash in constant time.  We can also use this for a rolling-window hash, similar to what rsync uses, but more secure.<br><br></div><div>Jason, is this what you were looking for?  I would love to know what use case you have in mind.<span class="HOEnZb"><font color="#888888"><br></font></span></div><span class="HOEnZb"><font color="#888888"><div><br></div><div>Bill<br></div></font></span></div>
</blockquote></div><br></div><div class="gmail_extra">Can I take it as a good sign than no one offered any attacks or found any weaknesses so far? :-)<br><br></div><div class="gmail_extra">While I am often wrong, I claim it is secure based on the difficulty of the discrete log problem.  What would be the next natural step for this algorithm?  It seems the usual way is to write a paper...<br></div><div class="gmail_extra"><br>Bill<br></div></div>