RE: Why are the hash values sorted?

["Tobias Gondrom" <tgondrom@xxxxxxxxxxxx>]

Hello Tilo,

at first I fully agree with the technical reasons of Robert so far. 
(The performance and tree parsing is an important reason I forgot.)


And I must disagree with your reasons:
1. you are right, SHA-256 seems pretty secure at the moment (at least
today - let's see what the next Workshops at NIST and Crypto-conferences
turns up) and other Hash algs are also good for this spec - but the
freedom of reordering all hash-values in the tree is an absolutely
unnecessary security risk and might increase future potential collision
attacks. For the best security of the system the specification should be
clear and unambiguous as good as possible. 


2. The thought of IBM to insist that the order of the tree should
reflect the order in which the documents have been signed is - to say it
blunt - silly. 

A. you can NOT use this ordering as "proof" of order of signing time:
you can never rely on the ordering you receive from ERS-system, so you
could never rely on that it is not otherwise received or ordered. 
A-a) any user can send data in any order to the ERS-system.
A-b) to fulfil your idea the ERS system would need to inspect the data
it preserves which can not be possible in all cases (thinking of formats
the ERS-system does not know, or content that is encrypted) - What would
you do if this ordering would be in conflict with the times in the
timestamps of the signatures.
A-c) and in case you really would want to do this, you might also have
to certify such a server as trusted and the sorting mechanism according
to your proposal by a government agency to be able to rely on this
information.

B. the information about the signing time (and order) should definitely
be in the signature and NOT be deducted from the order of the tree - as
you know there is a very good mechanism called timestamp which gives
absolutely clear information about the order of the signing times.

C. small remark: your proposal is absolutely NOT required by the German
ArchiSig project (and as one of the key project members I must know it).

D. to me your proposal looks like a cheap "hack" for a proprietary not
though-out/figured out system - your business goal SHOULD definitely be
achieved otherwise. This is definitely NOT worth taking any risk (and be
it even the slightest) of easier collision attacks against the hash tree
in the future. 

E. and as a last remark: all my talks with government agencies (and
there were quite some German included) did explicitly NEVER show this
idea or strange requirement. (of course all of them need ERS and
solutions conform to ERS)


So I strongly recommend that you use a different and more mature
approach for your idea - as Robert already explained there are many
possible approaches not in conflict with ERS and a lot better than your
proposal.

Tobias



> -----Original Message-----
> From: owner-ietf-ltans@xxxxxxxxxxxx
[mailto:owner-ietf-ltans@xxxxxxxxxxxx]
> On Behalf Of Robert Eiglmaier
> Sent: Tuesday, May 02, 2006 9:07 AM
> To: Tilo Kienitz; ietf-ltans@xxxxxxx
> Subject: RE: Why are the hash values sorted?
> 
> 
> Hi Tilo,
> 
> 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.
> 
> 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.
> 
> 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.
> 
> 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.
> 
> Robert
> 
> 
> 
> -----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
>