[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Bill Cox waywardgeek at gmail.com
Thu Oct 9 09:43:34 EDT 2014

On Wed, Oct 8, 2014 at 10:33 AM, Jerry Leichter <leichter at lrw.com> wrote:

> In the case you propose, there's another issue:  Digest(X) == 0 if and
> only if one of the constituent hashes is 0.  That breaks one of the basic
> requirements for a secure hash function:  Given H(X), it's difficult to
> find a Y != X such that H(Y) == H(X).  When H(X) == 0, it's trivial to find
> as many examples as you like.
> I challenge you to find x such that H(x) == 0.  Assuming we have a good
hash primitive, you can't.  So, this is not really a problem.  However, we
can't use just any hash function.  H has to be secure.

> Note that the cost of computing your digest is at least double that of
> simply doing a hash over the original data (as you run the hash on twice as
> much data - not to mention the cost of all those modular multiplications).
> You'd need to justify that cost.

Not true for block sizes of B where B is large.  Anything over 1MiB should
be  fine.  However, if the block size is just a KiB or so, then the modular
multiplications will dominate.  There needs to be a significant need for
constant time update in this case.

> I also see no obvious advantage to your scheme over simply adding the
> constituent hashes together (effectively mod 2^n) - a much, much cheaper
> operation which doesn't have problems with 0.  (You can make it even
> cheaper by considering each H() value as a vector of 32- or 64-bit values
> and adding them as vectors.)  Can you describe an attack on the cheaper
> approach that fails for yours?
>                                                         -- Jerry
That is much cheaper, but David Wagner broke such systems in his paper on
Generalized Birthday attacks:


He explores security using various operators and goes into some depth about
possible attacks on multiplication modulo primes.  However, his explored
directions also directly apply to attacks on discrete logs.

I'm afraid I know of no secure shortcut that avoids 2048-bit arithmetic.
That this can be done securely at all is new information, SFAIK.

Thanks for taking a crack at it.

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

More information about the cryptography mailing list