Subject: RE: Time-Stamp: Why not use several hashes?

From: Robert Zuccherato <[email-masked]>
Date: Tue, 13 Apr 1999 13:30:55 -0400

I think that if a common hash function is broken (for example SHA-1) then no
signature created within that infrastructure, with that hash function can be
trusted, including the TSA's.  Thus, I am reluctant to include multiple
hashes within the message imprint.  It will not actually help if the hash
algorithm used to sign the token is broken.  Also, as I stated earlier, if
certain individuals really want to do this, they can do it by defining a new
OID.

> ----------
> From: 	Jose A. Manas[SMTP:[email-masked]]
> Sent: 	Monday, April 12, 1999 4:24 AM
> To: 	Denis Pinkas
> Cc: 	Manuel Heras Gilsanz; [email-masked]; [email-masked]
> Subject: 	Re: Time-Stamp: Why not use several hashes?
> 
> Denis,
> I feel uneasy with both arguments.
> 
> If a guy finds out how to provoke collisions on a hash functions,
> there is a serious temptation to exploit the hole before
> publishing it. Breaking a time-stamp infrastructure is a nice
> goal: you break it before anybody knows it can be broken,
> and then there is a difficult question about when the TSA was
> no longer to be trusted.
> 
> I have some concern as well with respect to breaking a digital
> signature. If broken but time-stamped, 
> a TSA can still prove that it was signed
> before it was breakable. But if you break the TSA itself, then
> there is no help. That about breaking the hash.
> 
> Still, if you break the TSA signature, you have audit records
> (stored evidence in the TSA) to help you (as far as there are
> no collisions in the hash).
> 
> Alltogether, I aim to say that breaking a hash does break down
> everything, and it sounds interesting to foresee the case.
> Allowing for several messageimprints sounds as a cheap end
> effective countermeasure.
> 
> pp
> 
> Denis Pinkas wrote:
> > 
> > Manuel,
> > 
> > We want to keep the protocol simple. The threat you mention can be
> countered
> > by another way: re-time-stamp later on with a new hash function. If
> SHA-1
> > gets broken one day, this will not happen in just one day. Some
> > cryptographer will first find some weaknesses before you can really
> forge a
> > meaningfull message that has the same hash. So you get some time for
> > re-stamping.
> > 
> > If this argument were used, then we should sign TWICE, i.e.  in case one
> > digital signature algorithm was broken. We do not do that. There is no
> > reason to do it for the hash function.
> > 
> > Regards,
> > 
> > Denis
> > 
> > > Hi.
> > >
> > > In the (now expired) latest PKIX draft on time-stamping protocols from
> > > Sept. 23, 1998, time-stamp requests and tokens support the insertion
> of
> > > a single message imprint.
> > >
> > > I think several message imprints should be supported. If a hash
> > > algorithm were broken, time-stamp tokens using it (as the single
> message
> > > imprint) would have to be regarded invalid (even if some kind of
> linking
> > > mechanism were implemented!). If several hashes had been used, the
> token
> > > would still be valid, and it could be promptly renewed in order to
> > > prevent invalidation should further advances in cryptography render
> > > other hashes obsolete!
> > >
> > > (One must be careful here: there are different extents to which a hash
> > > algorithm could be broken; in Appendix A of  PKITS-D3
> > > [http://www.fnmt.es/pkits] there is an interesting analysis of the
> > > implications that the different kinds of hash failures would have on
> the
> > > time-stamping process.)
> > >
> > > Of course the requirements on the time-stamp verification process
> would
> > > also have be modified to require ("MUST" level) *all* the hashes to
> > > correctly verify in order to regard the corresponding time-stamp token
> > > valid.
> > >
> > > Best regards,
> > >
> > >     - Manuel -
> > >
> > > ----
> > > Manuel Heras-Gilsanz ([email-masked])
> > > Independent Security Consultant
> > > Phone: +34-629 07 53 31
> 
> -- --------------------------------------------------------
> Prof. Jose A. Manas                     <[email-masked]>
> Dpt. Telematica                 http://www.dit.upm.es/~pepe
> E.T.S.I. Telecomunicacion           tel: [+34] 91 336 73 25
> Ciudad Universitaria                gsm: [+34] 607 73 38 94
> E-28040 Madrid, SPAIN               fax: [+34] 91 336 73 33
>

---

From: Denis Pinkas <[email-masked]>
Date: Wed, 14 Apr 1999 09:04:03 +0200

> trusted, including the TSA's.

I concur with Robert.

> Thus, I am reluctant to include multiple
> hashes within the message imprint.

Me too.

Regards,

Denis

> It will not actually help if the hash

---

From: Manuel Heras Gilsanz <[email-masked]>
Date: Thu, 15 Apr 1999 00:39:10 +0200

Robert,

> algorithm used to sign the token is broken.  [...]

I don't agree with you in the importance assigned to the hashes used in
the request itself and those used in the signatures. I think both hashes
have unequal impact on the process, for several reasons:

-The digital signature is not necessarily the single evidence supporting
the validity of time-stamp tokens; there could exist some form of
linking, there could be inter-TSA cross-time-stamping, etc., and in
these cases the weakest point in the architecture is the path from the
user document to the TSA, i.e., the message imprint(s) provided by the
user in the time-stamp request. [In fact, reliable time-stamping schemes
can be devised without resort to digital signatures.]

-Digital signatures can become obsolete (they will when the certificates
of the user, the TSA and/or main CA expire), but in time-stamping
operations time is essential, and TS-tokens should survive to the pass
of time. If a hash were broken, the digital signatures could be
re-issued (time is not essential in them), whereas time-stamps using
this (single) algorithm for imprint generation would have to be
invalidated.

-Whereas there is (in principle) no imposed restriction on the structure
of user documents to be time-stamped, the digitally signed constructs
follow rigid definitions that limit the degrees of freedom in a search
for collisions to a hash function.

-New document imprints cannot be obtained without cooperation from the
user, whereas additional digital signatures can be provided by the TSA
independently. Therefore providing support for several message imprints
in a single request would greatly reduce the need of user intervention,
and would increase the time between renewals.

> Also, as I stated earlier, if

In Section 2.1, "Requirements on the TSA" of the current TS PKIX draft,
point 8 specifies that the OIDs of the hashes provided by the users must
be analyzed by the TSA in order to check that they are "sufficiently
secure"; this is a very important and appropriate requirement,
introduced to prevent the use of potentially weak hashes. According to
this requirement, users cannot (unilaterally) define new hash OIDs in
order to aggregate several "normal" hashes into one, since these OIDs
would be unknown to the TSA, and therefore rejected. Apart from this
conflict with the requirements on TSA operation, I sincerely believe it
is much easier to accomodate the multiple-imprints construct within the
protocol structures, thus avoiding the need of agreeing on a full set of
OIDs for multiple-hash functions.

Best wishes,

     - Manuel -