[Cryptography] Creating a Parallelizeable Cryptographic Hash Function
jresch at cleversafe.com
Fri Oct 3 14:16:43 EDT 2014
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
>> 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)?
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the cryptography