[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Jerry Leichter leichter at lrw.com
Fri Oct 3 15:56:46 EDT 2014

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141003/a5e18b6b/attachment.bin>

More information about the cryptography mailing list