Internet Draft                                   Parag Namjoshi
PKIX Working Group                                 May 28, 1999
Document Expiration: November 23, 1999


               Internet X.509 Public Key Infrastructure
           Extending trust in non repudiation tokens in time
        <draft-ietf-pkix-extend-trust-non-repudiation-token-00.txt>


Status of this Memo

This document is an Internet-Draft and is in full conformance
with all provisions of Section 10 of RFC2026 except that the
right to produce derivative works is not granted.

This document is an Internet-Draft.  Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups.  Note that other groups may also distribute
working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time.  It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.


Abstract

This document describes a way to maintain the trust in a token issued
by a non-repudiation Trusted Third Party (NR TTP) ( DCS/TSA/TDA )
after the key initially used to establish trust in the token expires.
The document describes a general format for storage of DCS / TS / TDA
tokens for this purpose .

The trust that non repudiation tokens established with initial
signature of TTP must continue to hold even after the key used
initially for signing the token has expired, as they may be required
to be produced as evidence after considerable amount of time since
first issue of token.

The storage format is general enough to establish chain of custody
for the data.

      The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
      NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED",  "MAY", and
      "OPTIONAL" in this document are to be interpreted as described in
      RFC 2119 [RFC2119].

Document Expiration: November 23, 1999                            Page 1

. Introduction

Many of the NR TTP tokens are of long term nature. They may be needed to
be produced as evidence years after they were issued initially. But the
certificates which were used by the TTP have limited lifetime. When the
key used to sign initial token issued by TTP expires ,the token can no
longer be verified. We cannot assume availability of authentic copies of
old CRL's to validate the tokens especially after long time periods.
For this purpose we define a procedure( using DCS protocol) & storage
format which allows us to keep alive the trust we had in the original
token.The format is general enough to generate chain of custody
evidence.We define a format to store NR tokens to facilitate above-said
transactions.

. Non repudiation token storage format

The NRStorage is defined as follows ,

NRStorage ::= SEQUENCE {
        timeToNxtUpdate         GeneralizedTime OPTIONAL
        -- The time for next update of token.
        nrTrees                 SEQUENCE OF NRTree
}

NRTree ::= SEQUENCE {
        data                    OCTET STRING,
        -- The root node of the tree will contain the data from the
        -- original request. In the other nodes it will contain the
        -- data used for requests, which will keep alive the trust in
        -- the signature .
        nrToken                 NRToken,
        listOfNRNodes           SEQUENCE OF NRTree OPTIONAL
}

NRToken ::= CHOICE {
        dcsToken                DCSToken,
        tsToken                 SignedData,
        tdaToken                TemporalDataToken
}

Signature algorithms and keys have a definite lifetime.  Therefore,
signatures have a definite lifetime.  The Data Certification Server
can be used to extend the lifetime of a signature.

In order to extend to lifetime of Non repudiation token we use this
capability of DCS. We use the DCS service "certify signature" (cs) to
extend lifetime of NR token (including DCS tokens). This necessitates
the presence of DCS server in the environment for this purpose.
The TimeStamp & Temporal Data Authorities do not verify contents of
the request. This forbids us from forming chains of TimeStamp or
Temporal Data requests since we cannot trust the contents : only the
fact that requester possessed the contents at specified time is
certified by such TTP's. ( For example , we cannot trust the timeStamp
token which was timestamped again.  If we have a timestamp token
and we timestamp it again , only thing it proves that is we had
something which looked like a timestamp token. It could be something

Document Expiration: November 23, 1999                            Page 2

which attacker could have forged using a his own set of keys. As the
availability of authentic sources of CRL's SHOULD NOT be assumed
there is no way to tell apart a valid token from a forged one.
In the interest of keeping Tokens as independent as possible we
SHOULD NOT depend on extrinsic parameters like CRL's ; the only
dependence being capability to validate a signature signed using
TSA's current certificate. )

The user will get the first tokens from TTP. The client SHOULD
set the value of timeToNxtUpdate to expiry time of the
certificate if it is earlier than value which is there(This case
will arise if NRStorage already has nrTrees.) This token will form
the root of a new nrTree.

The following steps SHOULD be performed each time TTP certificate
used for signing leaf node tokens is about to expire.

A) The signature of a TTP ( possibly the DCS itself ) is to be
   extended.

   1) The (possibly) signed message is presented to the Data
      Certification Server in the data field of DCSReqData under
      service type cs and an appropriate policy. The message field
      is of type SignedData & contains SignerInfos of all the TTP's
      which have signed the the data.

   2) The Data Certification Server verifies mathematical
      correctness of signatures of the requester (if present)
      & the TTP. Server verifies that signing keys are valid at the
      time by checking expiry dates and status information,
      and returns a data certification token.

B)  The certified token MUST be verified.

   1) The signature of the Data Certification Server in data
      certification token SHALL be verified using the Data
      Certification Server's valid verification key.

   2) The node is added to the tree by pointing it to
      the parent node. The client SHOULD traverse the all of the
      trees in NRStorage & update timeToNxtUpdate value.


C)  The certified token must be verified as evidence.

   1) Verify the validity of signature on the leaf node. The
      client MUST verify that signature belongs to a trusted
      DCS server.

   2) For the parent node token, the signature on the   token MUST
      be the same as the one which was certified in child node.
      The client MUST check if the signature was from a DCS server.
      This check MUST be done by checking mathematical correctness
      of signature on the request. ( Note that since the certificate
      has already expired, we can only verify mathematical correctness

Document Expiration: November 23, 1999                            Page 3

      of the signature. The trust for this token is due to the
      DCS token in the child node ).The client MUST verify that
      certificate in the token was for a trusted DCS server.

   3) The step 2 will continue till the root node is reached. If the
      root node verifies to be correct, then we may conclude that
      the data corresponding to the root node was valid at the time
      indicated in the root node token ( DCS / TS ).

The timeToNxtUpdate stores the time when the the tree should be next
updated. This value SHOULD be updated each time the nrTrees are
traversed.

.  Key/Algorithm strength issues :

Since the lifetime of NRTokens is expected to be in decades, it may
be possible that Key-lengths used to sign the data may not be enough.
( For example currently in many cases, RSA key lengths of 512 bits
are norm. )It may become feasible to break such keys in a few years
and 1024 bit keys some time later. The hashing algorithm may be broken.
This would invalidate all the tokens issued by keys of that length
or using broken hash algorithm.

When it is becoming apparent that weaknesses are arising in current
system, the TTP's will start using other algorithms. In such
scenarios, the client SHOULD get hash of parent NRToken certified
using CPD request. Since the CPD request only certifies
possession of data, a CS request should be used to certify
previous TTP signature. The combination of these two requests will
guaranty the continuing trust in the data. The CS request will extend
the lifetime of signature & CPD reply token will guaranty that
the trust tree existed before the system was broken.

Verifying of the tokens assures that parent token existed before
the algorithm were broken & thus allows safe usage of such tokens.

Please note that the further requests MUST continue to extend lifetime
of signature on CPD reply token itself. This will ensure continuing
trust in the data.

.  Chain of custody.

The DCS token storage format allows to establish a chain of custody.
To establish the chain of custody ,the current holder of token
sends a signed "cs" request to DCS (signed using his key) , with the
message field is of type SignedData & contains SignerInfos of the
TTP's which have acted upon the the data. The request SHOULD contain
a timestamp token. This would lend additional level of trust to the
token. The client MAY get hash of original data certified to prove
possession of data ( This provides improved evidence as this proves
that the client held the data & not only the token.) Both tokens
MUST point to the parent.

Please note that the further requests MUST continue to extend lifetime

Document Expiration: November 23, 1999                            Page 4

of user signature and the DCS token from CPD request . These would form
two separate "cs" requests from the one used to extend lifetime of TTP
signature as both these requests refer to different data sets.

Traversing the nrTree will yield the names & time at which various
entities held the data. Note that there is a possibility of multiple
users holding differing nrTrees as tokens are  updated independently
(in parallel) by different users. In such cases, the client MAY
interpret the multiple NRStorages to get a single chain of custody.
If two tokens from same TTP bear same time, serialNumber in DCSInfo
SHALL be used to order them. Its left to the client policies how to
treat tokens issued by different TTP's as there are various issues
such a lack of clock synchronization between servers etc. which are
out of scope for this document.

It is RECOMMENDED that same DCS server should be used to certify
all the tokens in a nrTree.


. Using multiple TTP's

In the case that the TTP's private key may be compromised
the whole nrTree becomes invalid . If the data is of critical
importance , it is RECOMMENDED to use more than one TTP's
to validate the data. In such circumstances, the client will
have multiple nrTrees in NRStorage with each tree starting with
a token originating from different TTP's.

This would also help in the transactions where same data may need
to be agreed with more than one entities. In such cases , the
TTP which are acceptable to all parties may not be the same and
NRStorage will contain more than one nrTrees to reflect this
situation.

In such cases client SHOULD continue to use same DCS consistently
for tokens within given tree.Please note that if any one of the
nrTrees verifies , then client may conclude that the data to be
valid at the time indicated in first token.

. Intellectual Property Rights

The IETF takes no position regarding the validity or scope of any
intellectual property or other rights that might be claimed to pertain
to the implementation or use of the technology described in this
document or the extent to which any license under such rights might
or might not be available; neither does it represent that it has made
any effort to identify any such rights.  Information on the IETF's
procedures with respect to rights in standards-track and standards-
related documentation can be found in BCP-11.  Copies of claims of
rights made available for publication and any assurances of licenses
to be made available, or the result of an attempt made to obtain a
general license or permission for the use of such proprietary rights
by implementers or users of this specification can be obtained from
the IETF Secretariat.


Document Expiration: November 23, 1999                            Page 5

The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights which may cover technology that may be required to practice
this standard.  Please address the information to the IETF Executive
Director.

The following United States Patents related to time stamping, listed in
chronological order, are known by the authors to exist at this time.
This may not be an exhaustive list.  Other patents MAY exist or be
issued at any time.  Implementers of this protocol SHOULD perform their
own patent search and determine whether or not any encumbrances exist
on their implementation.

# 5,001,752     Public/Key Date-Time Notary Facility
(issued) March 19, 1991
(inventor) Addison M. Fischer

# 5,022,080     Electronic Notary
(issued) June 4, 1991
(inventors) Robert T. Durst, Kevin D. Hunter

# 5,136,643     Public/Key Date-Time Notary Facility
(issued) August 4, 1992
(inventor) Addison M. Fischer
Note: This is a continuation of patent # 5,001,752.)

# 5,136,646     Digital Document Time-Stamping with Catenate Certificate
(issued) August 4, 1992
(inventors) Stuart A. Haber, Wakefield S. Stornetta Jr.
(assignee) Bell Communications Research, Inc.,

# 5,136,647     Method for Secure Time-Stamping of Digital Documents
(issued) August 4, 1992
(inventors) Stuart A. Haber, Wakefield S. Stornetta Jr.
(assignee) Bell Communications Research, Inc.,

# 5,373,561     Method of Extending the Validity of a Cryptographic
Certificate
(issued) December 13, 1994
(inventors) Stuart A. Haber, Wakefield S. Stornetta Jr.
(assignee) Bell Communications Research, Inc.,

# 5,422,95 Personal Date/Time Notary Device
(issued) June 6, 1995
(inventor) Addison M. Fischer

. References

[DCS] C. Adams, R. Zuccherato, Internet X.509 Public Key Infrastructure,
Data Certification Server Protocols , <draft-ietf-pkix-dcs-00.txt> ,1998
(work in progress).

[TSA] C. Adams, P. Cain, D. Pinkas, R. Zuccherato, "Internet X.509
Public Key Infrastructure, Time Stamp Protocols," draft-ietf-pkix-time-
stamp-01.txt, 1999 (work in progress).

Document Expiration: November 23, 1999                            Page 6


. Authors' Address

Parag Namjoshi
Frontier Computers Pvt. Ltd.
Sri Devichand Smarak Hall,
1194/11 Ghole Road, ShivajiNagar,
Pune 411005
India

parag@fcpl.co.in

APPENDIX A - Load Balancing of Requests

When the NR TTP's old certificate is about to expire, it may receive
a flood of requests to maintain the trust in the current tokens.

The servers may be overwhelmed by the requests .They may not be able
to reply to all the requests with transport dropping some of the
requests causing retransmissions, the time taken to reply may exceed
the time the client will wait for the response or in worst case
the TTP may crash due to excessive load.

It is RECOMMENDED that the time between generation of new key pair and
for the expiry of the old key of the TTP should be large enough for the
clients to load-balance the requests over a period of time. The client
MAY choose to generate a random time between generation of new keys &
expiration of the old key. The implementation SHOULD choose to use
policy appropriate to the environment (The policy MAY be to offer
no load-balancing at all for low traffic environments).


Document Expiration: November 23, 1999                            Page 7