Re: Why are the hash values sorted?

[Tilo Kienitz <tk-tlslist@xxxxxxxxxxxxxx>]

Hi Robert,

thank you for your comments.

> there are some more (technical) reasons for sorting the hashes:
>
> In an unsorted hashtree searching a certain hash value becomes
> slow whereas in a sorted tree you can look it up real quick
> with binary search.
> Sorting is done only once when creating the tree, searching
> is done everytime a document needs to be verified.

That's right. But searching something in the tree is a seldom
operation. We only need to do it when an algorithm in the
original document's signature has expired and still somebody
is interested in verifying the signature. Of course that will
happen sometimes, but the older a documents gets the less often
it will be used.
Furthermore the hash tree is the logical structure and there
may be a different physical structure in the data base. The data
base could create an index which might for example contain a
binary sorted tree.


> The format of the reduced hashtree would have to be changed
> for unsorted hashtrees because for all the middle levels of the
> tree only the neighbor hashvalue(s) are given. There is no
> information where to put the calculated hashvalue. Left or right
> or if the arity > 2 somewhere between the neighbors?
> If they are sorted, this is unambiguous.

Right. It would be necessary to put each required node completely
into the reduced hash tree. If for example a parent node on a
middle level has 1000 children, then these 1000 hashes have to be
there in the reduced hash tree and not only 999. I do not see a
problem in this change.


> And finally ArchiSig hashtrees have not been designed to prove
> the order in which the documents arrived in an archive. Even if
> the hashvalues would represent that order, this would be a hint
> but no proof.

So we will need a flag which expresses that in this hash tree the
order of the hashes represents the order in which the hashes
arrived in the archive. By order in the hash tree I mean a
depth-first-enumeration of the leafs starting with the left-most
leaf.


> You might create an additional document with references (hashes)
> of your documents and e. g. the current date & time and add it
> to the archive before creating the hashtree so that it is
> timestamped.

We thought about it and it is possible. But it makes the data
structure more complicated. Some of our customers need to know
the order in which the documents arrived in the archive. The
easiest way to achieve this is to maintain the order in the
tree. We could do it more complicated with additional documents
and time stamps, but why should we?

Kind regards
Tilo



> -----Original Message-----
> From: owner-ietf-ltans@xxxxxxxxxxxx
> [mailto:owner-ietf-ltans@xxxxxxxxxxxx] On Behalf Of Tilo Kienitz
> Sent: Freitag, 28. April 2006 19:07
> To: Tobias Gondrom
> Cc: ietf-ltans@xxxxxxx; Boris Baltzer
> Subject: Re: Why are the hash values sorted?
>
>
>
> Hello Tobias,
>
>  > We sort the hash values (binary ascending) to reduce the risk of
>  > collision attacks by resorting the hash values in another combination
>  > and by this getting another hash value for the parent node.
>
> I understand these arguments, but they do not convince me. If there
> was a realistic risk of collision attacks, a better hash algorithm
> should be used to prohibit such an attack. The draft does not demand
> a certain hash algorithm and an upgrade would be conformal. I am no
> cryptographer and maybe missing something, but it is my understanding
> that we do not have to expect collision attacks against for example
> SHA-256 within the next years.
> If your concern is that of a collision attack, you will also have
> to consider the possibility of inserting arbitrary values into the
> hash tree in order to perform such an attack. In my perception,
> inserting arbitrary values into the hash tree provides possibilities
> for collision attacks similar to those of resorting the hashes. In
> this respect, sorting the hashes to prevent collisions seems like
> installing a bigger lock on the door while the window remains open.
>
> In short: I think that collision attacks have to be prevented by the
> hash algorithm, not by the way the tree is sorted.
>
>  > And as we
>  > only secure the root hash with the time stamp we think that it is
>  > mandatory that the mapping/transformation from a given set of hash
>  > values to the root hash MUST be unambiguous.
>
> I suggest to compute the parent hash on the hashes below it in the
> exact order in which they appear in the ASN.1-sequence. This is
> an unambiguous rule.
>
>  > I understand the need for grouping of objects, but the order in the
>  > hash
>  > tree is not the right element for the information of the order of the
>  > documents in an application/document specific context.
>
> For many of our customers like IBM and major German authorities it
> is an important feature to be able to prove the order in which the
> documents have been signed. They insist that the hash tree is the
> natural place for this proof. It is important for us to have a
> solution compatible to the ArchiSig standard and therefore to
> LTANS-ERS. Therefore I suggest to make the sorting optional and
> insert a flag into the evidence record which shows whether the
> values have to be binary sorted before verification or just taken
> as they are.
>
> Kind regards
> Tilo
>
>
> --
> Tilo Kienitz
> SecCommerce Informationssysteme GmbH
> Obenhauptstr. 5
> D - 22335 Hamburg                       http://www.seccommerce.de
> Germany