# [Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Jonathan Katz jkatz at cs.umd.edu
Fri Oct 3 13:25:34 EDT 2014

```On Fri, Oct 3, 2014 at 1:18 PM, Jason Resch <jresch at cleversafe.com> wrote:

>  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> 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()?
>

Yes, I was. By digest(., .), I meant to apply your scheme.

>
>  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/9769c28f/attachment.html>
```