[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

[Jason Resch]

On 10/03/2014 12:25 PM, Jonathan Katz wrote:
> On Fri, Oct 3, 2014 at 1:18 PM, Jason Resch <jresch at cleversafe.com 
> <mailto: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 <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?
>>
>>         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)
>
>     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.

Okay I see how that works now. That is an interesting property, but can 
it be used to undermine the security of any typical applications of hash 
functions?

Thanks,

Jason

>>
>>     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/01a93545/attachment.html>