[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

[Jonathan Katz]

On Thu, Oct 2, 2014 at 6:53 PM, Jason Resch <jresch at cleversafe.com> wrote:

> Assuming there was a secure cryptographic function H() with an output of L
> bits, what attacks or weaknesses would exist in a protocol that did the
> following:
>
>
> Digest = H(B_0 || C_0) ^ H(B_1 || C_1) ^ H(B_2 || C_2) ^ ... ^ H(B_N ||
> C_N) ^ H(N)
>
>
> Where B_0 through B_N are the blocks (of size L) constituting the message
> and C_0 through C_N are L-bit counters.
>
> One problem seems to be that if any collision can be found for a given H(X
> || C_i) and H(Y || C_i), it leads to an essentially infinite number of
> collisions (any message that contains X as a block can have that block
> replaced with Y), but what other vulnerabilities does this construction
> have that would make it unsuitable as a general purpose cryptographic hash
> function?
>
> Thanks for your expertise.
>

There are several issues. Most obvious is that your hash is homomorphic,
i.e.,
  digest(B_0, B_1) ^ digest(B'_0, B_1) ^ digest(B_0, B'_1) = digest(B'_0,
B'_1)

Also, collisions in your hash function can be found in faster than
square-root time using Wagner's generalized birthday attack.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141002/95d80ae3/attachment.html>