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

From: Manuel Heras Gilsanz <[email-masked]>
Date: Thu, 08 Apr 1999 22:45:47 +0200

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

---

From: Denis Pinkas <[email-masked]>
Date: Fri, 09 Apr 1999 10:41:40 +0200

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

---

From: Manuel Heras Gilsanz <[email-masked]>
Date: Fri, 09 Apr 1999 11:58:42 +0200

Denis,

Re-time-stamping *requires* cooperation from the user. Re-signing can be
performed by the TSA without user cooperation. Therefore the document and the
signature hashes do not demand the same "contingency planning".
The thing is, most users will time-stamp their documents and then forget to keep
track of the cryptographic advances. If the TSA finds itself unable to contact
some user, it will be unable to re-time-stamp the document; on the other, if a
new signature algorithm were needed, a renewed time-stamp could be obtained even
if the user were having holidays in Bahamas, with the mobile phone switched off.

On yet another hand, if the TSA implements some linking protocol in which
several hashes are used, then there is no need to re-issue tokens whose
signature hashes are broken. The TSA can again take appropriate measures without
the user cooperation.

Best regards,

    - Manuel -

---

From: "Jose A. Manas" <[email-masked]>
Date: Mon, 12 Apr 1999 10:24:42 +0200

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

> > Independent Security Consultant

-- --------------------------------------------------------
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