[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Bill Cox waywardgeek at gmail.com
Tue Oct 7 06:52:26 EDT 2014


On Mon, Oct 6, 2014 at 10:05 PM, Zooko Wilcox-OHearn <
zooko at leastauthority.com> wrote:

> Hello again, Jason Resch of cleversafe.
>
> I'd like to emphasize what Philipp Jovanovic said, in case he didn't
> express it strongly enough: just use BLAKE2!
>

Tom's idea being discussed here is a constant time updateable hash function
of very many records/messages/blocks, which Blake2 does not do.  A good
solution to this problem has many real-world use cases.  Rsync, for
example, uses a rolling hash function
<http://en.wikipedia.org/wiki/Rolling_hash> which is insecure.  Maybe we
could use:

y = H(1 || B1) * H(2 || B2) * ... * H(n | Bn) mod p

This looks secure to me, based on the difficulty of the discrete log
problem.

If you can give me an algorithm that takes random numbers and finds
combinations of them that multiply out to a specific digest y mod p, then I
can use your algorithm to find the discrete log base g of y.  I simply give
your algorithm g^rand() rather than rand(), and the algorithm finds y =
g^r1 * g^r2 * ... * g^rn mod p.  I am somewhat surprised Wagner did not see
this in his paper on the generalized birthday problem,
<http://www.di.ens.fr/~fouque/ens-rennes/gbp.eps> since significant effort
was put into framing attacks using multiplicative groups.  I just didn't
find that part very convincing :-)

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141007/3aa56e44/attachment.html>


More information about the cryptography mailing list