Subject: [Cfrg] Any other tree hash feedback?

From: Justin Chapweske <[email-masked]>
Date: Wed, 11 Dec 2002 14:57:48 -0600

Hello,

I am interested in any and all feedback on our "Tree Hash EXchange" 
format defined at 
(http://open-content.net/specs/draft-jchapweske-thex-01.html).

We will be posting a new revision of this specification that 
incorporates a fix to the 2nd-preimage resistance problem in the near 
future.

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

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

---

From: "David A. Mcgrew" <[email-masked]>
Date: Thu, 12 Dec 2002 11:24:42 -0800

Justin,

I'm glad to see this work, it is interesting and looks useful.  I have some
random comments.

I agree that Wagner's depth counter fix sounds good.  I wondered for a minute if
there would be any problems combining that solution with the fact that the
serialization algorithm 'promotes' hashes up the tree, but I'm sure it's
workable.  I regret that I can't cite any reference that would help establish
the security of this method, as you'd asked in another mail.  Hopefully someone
else can. (Anyone?).

In Section 3.2 of your spec you mention that the tree description (which
contains the parameters of the tree) comes from an untrusted source, and that
only the tree-hash value comes from the trusted source.  This allows an attacker
to choose any underlying hash function and any set of parameters when attempting
a forgery, and of course the attacker will choose the weakest one available.
This is not likely to be a problem if SHA-1 is your weakest hash, but OTOH it
might be a real flaw if MD4 is an option.

IIUC, the intended use is to have the tree-hash value delivered over a secure
channel  and to have some entities verify that the computed value matches that
value.  I'd guess that TLS would be used here, since we're doing XML; is that
right?   I'm not completely familiar with the application space you have in
mind.  Is it the case that the data (and thus the hash-value) will be changing
often?  If so, would it be appropriate to introduce a way to synchronize the
hash value?  I'd guess that the secure channel which carries the true hash-value
contains a method to prevent replay attacks, so those aren't a concern.

If the data does change often, it might make sense to use an incremental MAC
(for which it's easy to compute new MAC values if the amount of data changed is
small) rather than a hash tree.  FWIW, I've spoken with some others about
putting together an incremental MAC based on universal hashing.  (The first
version of the TMMH hash could be used to support such a thing.)  Incremental
MACs may or may not be interesting in your application area, I don't really
know.

David

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On Behalf Of
> Justin Chapweske
> Sent: Wednesday, December 11, 2002 12:58 PM
> To: [email-masked]
> Subject: [Cfrg] Any other tree hash feedback?
>
>
> Hello,
>

---

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

On Thu, 12 Dec 2002, David A. Mcgrew wrote:

> I agree that Wagner's depth counter fix sounds good.  I wondered for a
> minute if there would be any problems combining that solution with the
> fact that the serialization algorithm 'promotes' hashes up the tree, but
> I'm sure it's workable.  I regret that I can't cite any reference that
> would help establish the security of this method, as you'd asked in
> another mail.  Hopefully someone else can. (Anyone?).

Security proof is easy. Assume H is a CRHF. Take the simpler version where
internal nodes are prefixed by 1 and leaves by 0. Say T is a tricky tree
if for some different tree T', their root hashes H(T) and H(T') are equal.
Let T be the tricky tree of smallest depth, and let T' be this second
tree. Let v1...vn be the children of the root in the first tree, and let
h1...hn be the curresponding hash values. (Then H(T)=H(1,h1,...hn) or
H(T)=H(0,data), if T is a singleton tree.)  Let the corresponding primed
variables be the same things in the second tree. Then either:

1. (v1,...,vn)!=(v1'...vn'), in which case we have found a collision to
   the hash function, or
2. (v1,...,vn)==(v1'...vn') but then some subtree of T is tricky,
   which is a contradiction to our choice of T.

QED

I arrived to this construction (quite a long time ago) when Ahto Buldas
pointed out that the hash tree is not good for time-stamping under the
sole assumption that H is collision-resistant, and I proposed him to use
this modification. We never published the break, and we never published
the fix just because we did not think it was novel, and I bet it is not.
(Although it seems that nobody has realized this problem in the context of
time-stamping before.) Still, I do not have any references.

Helger

---

From: Helger Lipmaa <[email-masked]>
Date: Fri, 13 Dec 2002 00:02:56 +0200 (EET)

The complete proof of course requires to look also at the special cases
when the added bit is 0 vs it is 1...

H.