[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Jason Resch jresch at cleversafe.com
Fri Oct 3 18:30:33 EDT 2014

On 10/03/2014 02:56 PM, Jerry Leichter wrote:
> On 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.
> This construction is insecure.  Call your function J.  Let A and B be any L-bit values.  Then:
> J(A || B) = H(A || 0) ^ H(B || 1) ^ H(1)
>            = (H(A || 0) ^ H(0)) ^ H(0) ^ H(B || 1) ^ H(1)
>            = J(A) ^ (H(0) ^ H(1) ^ H(B || 1))
> (Your use of N is a bit odd - it "feels" like it's the number of blocks, but in fact it's one less than that.  This becomes obvious here when you have to add the constant length-dependent terms - with one block, I expected to add H(1)!)
> So if I'm given J(A) for an unknown A, I can compute J(A || B) for any B.  This is a form of length extension attack.  In this case, I don't think the usual tricks for preventing length extension attacks, like replacing H by an HMAC based on H or just wrapping an additional H around the whole thing, will help you - they are meant for cases where there is a secret key that the attacker doesn't have access to, but here everything but the original message hashed is assumed to be available.
>                                                          -- Jerry


Very clever. I see now that this is clearly vulnerable to a length 
extension attack.  However, it isn't clear to me why throwing the final 
result through H() as a final post-processing step wouldn't serve to 
address it.


More information about the cryptography mailing list