[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Jason Resch jresch at cleversafe.com
Fri Oct 3 13:18:12 EDT 2014

```On 10/02/2014 06:50 PM, Jonathan Katz wrote:
> On Thu, Oct 2, 2014 at 6:53 PM, Jason Resch <jresch at cleversafe.com
> <mailto: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?
>
>
>
> 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)

But here you are not using counter values in the digest calculation. Is
there a way to determine any kind of homomorphism when no collisions can
be found in H()?

>
> Also, collisions in your hash function can be found in faster than
> square-root time using Wagner's generalized birthday attack.

Interesting, thanks for pointing this out. If I interpret the
improvement of the GBA correctly, does that mean the time complexity to
find a collision is N^(L/2) / L vs. N^(L/2)?

Thanks,

Jason
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141003/72654d0b/attachment.html>
```