[Cryptography] Secure parallel hash, with constant time update

Bill Cox waywardgeek at gmail.com
Wed Oct 8 21:24:36 EDT 2014


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141008/e68119e5/attachment.html>


More information about the cryptography mailing list