[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?
>
> 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()?
>
> 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>
More information about the cryptography
mailing list