[prev in list] [next in list] [prev in thread] [next in thread] 

List:       cfrg
Subject:    RE: [Cfrg] Any other tree hash feedback?
From:       Helger Lipmaa <helger () tcs ! hut ! fi>
Date:       2002-12-12 22:02:56
Message-ID: Pine.LNX.4.44.0212130002270.30410-100000 () rhea ! tcs ! hut ! fi
[Download RAW message or body]

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

H.


On Thu, 12 Dec 2002, Helger Lipmaa wrote:

> 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
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@ietf.org
> https://www1.ietf.org/mailman/listinfo/cfrg
>

_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg



[prev in list] [next in list] [prev in thread] [next in thread]