Subject: [Cfrg] Merkle Hash Tree Weakness - Request for Advice

From: Justin Chapweske <[email-masked]>
Date: Wed, 04 Dec 2002 23:36:05 -0600

Hello All,

We have authored what we hope to become an Internet Draft for using 
Merkle Hash Trees for file integrity verification in distributed 
systems.  The first draft of our paper is available at 
(http://open-content.net/specs/draft-jchapweske-thex-01.html).

There is a weakness in this draft where by the hash tree is vulnerable 
to attacks on its 2nd-preimage resistance.  Several suggestions have 
been made as to what the appropriate fix would be, but I wanted to run 
this problem by the CFRG to hopefully receive a somewhat authoritative 
answer.

The simple exploit follows:

Let F1 be a string 2048 bytes long, composed of two equal length
substrings s1
and s2.  Let F2 be a string 48 bytes long, composed of two equal
length
substrings s3 and s4.  Now let s3 equal H(s1) and S4 equal H(s2).

These two strings will create the same root value using the proceedure
defined in the above document.  This is not good.

The first suggestion, from Richard Parker, is to strengthen each 
internal hash by adding a sort of "aggregate" MD-strengthening whereby a 
   one-and-zeros padding is added followed by a fixed-length field that 
specifies the total bit length of data that this hash covers.  So if the 
leaf nodes each cover 1k of data, their parents would each cover 2k of 
data, and so on...

Here is the quote from Richard Parker:

"The problem appears to be that your hash is not
adequately "capturing" the size of substrings.  Fortunately there is a
simple fix, when computing the hash for each vertex append to the hash input
string the total length of the substrings rooted by that vertex (after
padding to the size of the hash function's block size, i.e. 512 bits for
SHA-1 and MD5).  Appending the size to the input of a hash is called
"MD-strengthening" after Merkle and Damgard who independently proposed this
idea.

For example, ignoring optimizations, such such a hash tree might look as
follows:

            V_0
         /       \
        /         \
      V_1         V_2
     /  \        /  \
    /    \      /    \
   V_3   V_4   V_5   V_6

   H()   hash function
   l()   length
   ||    concatenation
   V_i   vertex i
   S_j   substring j
   r     block size of H
   n     output size of H
   p_i   number of bits needed to pad to multiple of r
   w     number of bits used to represent substring length

   V_0 = H(V_1 || V_2 || 0^p_0 || 0^(r-w) || l(S_1)+l(S_2)+l(S_3)+l(S_4))
   V_1 = H(V_3 || V_4 || 0^p_1 || 0^(r-w) || l(S_1)+l(S_2))
   V_2 = H(V_5 || V_6 || 0^p_2 || 0^(r-w) || l(S_3)+l(S_4))
   V_3 = H(S_1 || l(S_1))
   V_4 = H(S_2 || l(S_2))
   V_5 = H(S_3 || l(S_3))
   V_6 = H(S_4 || l(S_4))
"

Note that the padding for the leaf nodes was accidentally left out...

The second suggestion is from David Wagner, where he recommends 
prepending a fixed length "depth counter" to each hash input.  We would 
probably do an "inverse depth counter" with the leaves starting at 0 and 
incrementing the value towards the root.  This allows the tree to be 
generated incrementally w/o knowing the entire tree size ahead of time. 
A 1 byte field should be safe for files up to 2^256 bits in size.

The quote from Dr. Wagner follows:

"
The standard fix is to do one or the other of the following.
   (1) Include a depth, i.e., we compute the hash value at a
       node of depth d as Hash(d,l,r) where l represents the
       hash value at the left child and r the right child's hash.
   (2) Use a different hash function at the leaves than at
       internal nodes.  In other words, we compute the hash value
       at a leaf node as Hash("leaf",x) where x is the data
       associated at that leaf; we compute the hash value at
       an internal node as Hash("internal",l,r) where l,r are
       as above.
If I recall correctly, both of these can be proven secure if
the underlying hash is modelled as a random oracle.  However,
I haven't checked this, so I could be wrong.
"

Personally I prefer Dr. Wagner's depth counter suggestion, but I 
encourage the members of this group to read our proposal and come up 
with your own recommendation.

Thank you so much for your time and thanks for helping deliver a more 
secure future internet.

-Justin

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Justin Chapweske <[email-masked]>
Date: Thu, 05 Dec 2002 00:12:52 -0600

> A 1 byte field should be safe for files up to 2^256 bits in size.

I'm sorry, one correction:  a 1 byte depth counter field will allow for 
files up to 2^256 * leaf segment size.  Currently we recommend a default 
leaf segment size of 1024 bytes.

So as an aside question, what is a reasonable expectation of maximum 
file sizes that modern cryptographic systems should safely support?

-- 
Justin Chapweske, Onion Networks
http://onionnetworks.com/

---

From: Helger Lipmaa <[email-masked]>
Date: Thu, 5 Dec 2002 14:29:45 +0200 (EET)

> A 1 byte field should be safe for files up to 2^256 bits in size.

Depth counter might cause problems in several setting. For example, if
your tree is not complete, you cannot assign the same counter to every
leave. If your tree is dynamic, adding new leaves might force you to
recompute a significant part of the tree. The second suggestion of David
Wagner (which corresponds more to - as far as I know - to the standard
practices) is a special case of suggestion (1) where all leaves have
counter (say) 1 and non-leaves counter (say) 0. 

The standard way of implementing (2) is to prepend this one-bit counter
(or a byte, or a block) to the l and r. This should be secure if the hash
function is collision-resistant; but at least the security of the 'block'
version should be studied when a concrete hash function like SHA-1 is
used.

Helger

---

From: Justin Chapweske <[email-masked]>
Date: Thu, 05 Dec 2002 09:40:44 -0600

> counter (say) 1 and non-leaves counter (say) 0. 

If you read through our paper and look at the orphan node promotion 
semantics, then I think you'll find that there is no problem with the 
depth counter.

Are you aware of any public references which discuss David Wagner's 
second suggestion?

Also, any feedback on the overall document, beyond this specific problem 
we are working to fix, would be greatly appreciated.

Thanks,

-Justin

---

From: Helger Lipmaa <[email-masked]>
Date: Thu, 12 Dec 2002 01:50:12 +0200 (EET)

> Are you aware of any public references which discuss David Wagner's

Not, but this does not say anything. I'd say it's a part of folklore that
is very well known, something that gets now and then reinvented. May be
somebody else has better information.

[I have no time to read your document, unfortunately]

H.