[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Ben Laurie benl at google.com
Sat Oct 4 13:21:19 EDT 2014


On 3 October 2014 19:16, Jason Resch <jresch at cleversafe.com> wrote:
> 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?
>>>
>>> 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?

Of course ... I get you to sign the first three, now I can sign the
fourth one for you...

You could fix it by adding an IV. :-)

However, this is not a good way to go about designing crypto primitives.


More information about the cryptography mailing list