[Cryptography] Secure parallel hash, with constant time update

Bill Cox waywardgeek at gmail.com
Mon Oct 13 16:53:42 EDT 2014

On Wed, Oct 8, 2014 at 9:24 PM, Bill Cox <waywardgeek at gmail.com> wrote:

> 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.
> The hash function is:
>     Digest y = H(1 || B1) * H(2 || B2) * ... * H(n || Bn) mod p
> 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.
> 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.
> 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.
> Jason, is this what you were looking for?  I would love to know what use
> case you have in mind.
> Bill

Can I take it as a good sign than no one offered any attacks or found any
weaknesses so far? :-)

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...

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141013/986a3758/attachment.html>

More information about the cryptography mailing list