Re: IETF and ISO alignment on Time Stamping

[Roland Mueller <roland@xxxxxxxxx>]

Paul,

the current document proposes in its part 2 a few mechanisms, none of
them under patent restrictions. I copied this part after my signature.
Sorry but i's quite some stuff and the figures are not included. If
interested I can also provide the whole doc but then it's PDF and it
does not reflect the results of the discussions we had last week. 

Roland

---------------------------------------
First Protocol (TSA checks T and signs receipt)
Step 1 (Originator): For a given document D, the originator creates a
time-stamp receipt using the current time T and a hash value H(D)
computed on the document D.  We assume that the originator has access to
a trusted clock that provides current time T.
Step 2 (Originator): The originator provides or transmits the time-stamp
receipt to a Time-Stamping Authority (TSA).
Step 3 (TSA): Optionally, the TSA performs a consistency check on the
received time-stamp receipt to ensure that the data contained in the
time-stamp receipt is consistent with data maintained at and controlled
by the TSA.
Step 4: (TSA): The TSA also verifies that the (now) current time T' and
the time value T in the time-stamp receipt are equal to within some
pre-established time window.  For example, it may be pre-arranged that
the time values T and T' are specified to the nearest whole minute,
e.g., by rounding up to the nearest whole minute.  That is, the clock
values are accurate to the nearest minute.  Thus, if T and T' are equal
with respect to year, month, day, hour, and minute, then they are
considered equal, even though they may not be equal if greater accuracy
were used.  (T and T' could differ by several seconds and still be equal
to the nearest whole minute.)  We assume that the TSA has access to a
trusted clock that provides current time T'.
Step 5 (TSA): If the time-stamp receipt is acceptable, the TSA signs the
time-stamp receipt with its private signature generation key.  We assume
that the TSA has a public and private key pair used for signing
time-stamp receipts.  The private signing key is available only to the
TSA, whereas the public key is made available to anyone so that they can
verify the signatures on time-stamp receipts generated by the TSA.  The
public key of the TSA can be stored in a certificate signed by a
Certification Authority (CA), so that the TSA's public key can validated
and, hence, trusted by those using that public key.
Step 6 (TSA): The TSA provides or transmits the signed time-stamp
receipt to the originator.






 			


Figure 1.  Time-Stamping in First Protocol

Differences:  In Fischer [1], the TSA operates on TSA-generated clock
signals.  In the alternative protocol, the TSA operates on clock signals
generated by the originator. In Haber [2, 3], the TSA creates the
receipt.  In the alternative protocol, the originator creates the
receipt.

4 Second Protocol (TSA computes age of time-stamped receipt)
Step 1 (Originator): For a given document D, the originator creates a
time-stamp receipt using the current time T and a hash value H(D)
computed on the document D.  We assume that the originator has access to
a trusted clock that provides current time T.
Step 2 (Originator): The originator provides or transmits the time-stamp
receipt to a Time-Stamping Authority (TSA).
Step 3 (TSA): Optionally, the TSA performs a consistency check on the
received time-stamp receipt to ensure that the data contained in the
time-stamp receipt is consistent with data maintained at and controlled
by the TSA.
Step 4 (TSA): The TSA computes a time difference, ?, between the time T
in the received time-stamp receipt and the now current time T', e.g., ?
= T' - T, where ? is referred to as an age value, or the age of the
document.  We assume that the TSA has access to a trusted clock that
provides current time T'.
Step 5 (TSA): If the received time-stamp receipt is acceptable, the TSA
creates an augmented time-stamp receipt from the computed age value of
the document and the received time-stamp receipt.
Step 6 (TSA): The TSA signs the augmented time-stamp receipt with its
private signature generation key.  We assume that the TSA has a public
and private key pair used for signing time-stamp receipts.  The private
signing key is available only to the TSA, whereas the public key is made
available to anyone so that they can verify the signatures on time-stamp
receipts generated by the TSA.  The public key of the TSA can be stored
in a certificate signed by a Certification Authority (CA), so that the
TSA's public key can validated and, hence, trusted by those using that
public key.
Step 7 (TSA): The TSA provides or transmits the signed augmented
time-stamp receipt to the originator.







 			


Figure 2.  Time-Stamping in Second Protocol


Differences: In Fischer [1], the TSA operates on a digital input and a
TSA-generated clock value.  In the alternative protocol, the TSA
operates on a digital input and a computed age value.  In Haber [2,3],
the TSA creates a receipt comprising a digital input and a TSA-generated
clock value.  In the alternative protocol, the TSA creates a receipt
comprising a digital input and a computed age value.
5 Third Protocol (TSA validates MAC on time-stamp receipt)
In the third protocol, the TSA provides both a "local" time-stamping
service and a "global" time-stamping service.  The distinction between
"local" and "global" is this: A local time-stamping service is one that
produces time-stamp receipts that can be validated only by the TSA that
generated them.  Therefore, only that particular TSA can "vouch" for the
time-stamp receipt.  A global time-stamping service is one that produces
time-stamp receipts that can be validated universally, by any entity. 
For our purposes, a local time-stamp receipt is one produced using a
keyed-hash function, or symmetric key cryptography; a global time-stamp
receipt is one produced, as is the usual case, using public key
cryptography.
A local time-stamping service could be beneficial in its own right. 
However, in the third protocol the local time-stamping service is shown
in combination with a global time-stamping service, where (in this case)
the local time-stamping service provides the originator with a local
time-stamp receipt that it can later choose to translate to a global
time-stamp receipt.  The fees for local and global time-stamping
services might be priced differently to provide customers with a wider
selection of time-stamping options.
Step 1 (Originator): The originator sends a hash value H(D) computed on
the document D to a TSA.  
Step 2 (TSA): The TSA creates a time-stamp receipt using the current
time T and H(D).  The TSA has access to a trusted clock that provides
current time T.
Step 3 (TSA): The TSA generates a secret random value K, e.g., a secret
key.  The TSA generates a Message Authentication Code (MAC) on the
time-stamp receipt using the generated secret value K.  Each generated K
is saved and later retrieved and used to validate the MAC (step 6 in the
protocol), after which K can be discarded.  The stored K is indexed
using any convenient method that links the time-stamp receipt to the
stored value of K, e.g., a sequential receipt number R.  Or, the MAC
(treated as a binary number) might be used to index a direct access file
composed of values of the form (MAC, K).
Step 4 (TSA): The TSA provides or transmits the time-stamp receipt and
MAC to the originator.
Step 5 (Originator): At a later time, the originator optionally provides
or transmits the time-stamp receipt and MAC, received at step 4 in the
protocol, to the TSA, requesting the TSA to certify the time-stamp
receipt.
Step 6 (TSA): The TSA locates K and uses it to validate the received
time-stamp receipt and MAC. If the time-stamp receipt and MAC are valid,
the protocol continues.
Step 7 (TSA): The TSA signs the received MAC with its private signature
generation key.  We assume that the TSA has a public and private key
pair used for signing time-stamp receipts.  The private signing key is
available only to the TSA, whereas the public key is made available to
anyone so that they can verify the signatures on time-stamp receipts
generated by the TSA.  The public key of the TSA can be stored in a
certificate signed by a Certification Authority (CA), so that the TSA's
public key can be validated and, hence, trusted by those using that
public key.
Step 8 (TSA): The TSA provides or transmits the signed MAC and K to the
originator.  K is provided to allow the originator to validate the
received signed MAC value.  
NOTE:  Once the TSA validates the time-stamp receipt and MAC, step 6 in
the protocol, there is no loss in security for the TSA to divulge K,
provided of course that its stored copy of K is erased or marked
"unusable."  Erasing K or marking it unusable will prevent a subsequent
spoofing attack in which the originator generates a new MAC on a forged
time-stamp receipt using K.
Step 9 (Originator): The originator validates the time-stamp receipt and
MAC received at step 4 in the protocol.  This is accomplished by using
the received value of K to generate a MAC on the time-stamp receipt and
then comparing the generated MAC with the MAC received at step 4 in the
protocol, for equality.  If the MAC received at step 4 in the protocol
is valid, the originator then validates the signed MAC, received at step
8 in the protocol, using the public key of the TSA.  Finally, the
originator forms a new record consisting of [time-stamp receipt, MAC, K,
and Signed MAC], which will allow time-stamp receipt to be validated by
any third party.







 			




 			


Figure 3.  Time-Stamping in Third Protocol
7.1 Third Protocol Variation
In a variation on the third protocol, the TSA does not store secret K
values.  Instead, the TSA has a secret master key KM that is uses to
encrypt the K values.  It has another secret key Kmac that it uses to
generate message authentication codes on the concatenation of K and
MAC.   In this case, there are two levels of MAC.  One is based on a
dynamic key K that the TSA later divulges to the originator, the other
is based on a persistent key Kmac that the TSA does not divulge to the
originator, or to anyone.
Steps 1 (Originator): unchanged. 
Step 2 (TSA): unchanged.  
Step 3 (TSA): The TSA additionally encrypts K under KM to produce the
encrypted key value eKM(K) and it additionally generates a message
authentication code, denoted MAC2, on K and MAC using Kmac.  In this
case, K and MAC are treated as data values and combined, e.g., by
concatenating the values. 
Step 4 (TSA): The TSA provides or transmits the time-stamp receipt, 
MAC, encrypted key eKM(K), and MAC2 to the originator.  
Step 5 (Originator): The originator provides or transmits the time-stamp
receipt,  MAC, eKM(K), and MAC2 to the TSA.  
Step 6 (Originator): The TSA retrieves K by decrypting the received
value of eKM(K) with its stored and retrieved copy of KM.  Next, the TSA
validates MAC2 by computing a message authentication code on K and MAC
using its stored copy of Kmac and comparing the computed message
authentication code with the received value of MAC2, for equality.  If
the combination of K and MAC (e.g., the concatenation of K and MAC) are
valid, the TSA validates the received time-stamp receipt and MAC using
K.  This is accomplished by computing a message authentication code on
the received time-stamp receipt using the retrieved and authenticated
value of K and then comparing the computed message authentication code
with the received MAC for equality.  If the validation operations
succeed, then the inputs are accepted as valid.  Otherwise, the values
are rejected.  
Step 7 (TSA): This step executes only if all validation operations in
step 6 succeed.  
Step 8 (TSA): This step is different in that there is no stored copy of
K at the TSA to be erased.  Divulging K does not subvert security, since
even with knowledge of K, the originator (or an adversary) cannot
generate a valid MAC2 without knowledge of Kmac, which is necessary in
order to spoof the TSA at step 6.  
Step 9 (Originator): unchanged. 






 			




 			

Figure 4.  Time-Stamping in the Third Protocol (Variation)
Differences: In Fischer [1], the TSA operates on two values, a digital
input and a TSA-generated clock value.  In the alternative protocol, the
TSA operates on one value, a digital input (i.e., a MAC).  In Haber [2,
3], the TSA certifies a receipt comprising an input digital document and
a clock value.  In the alternative protocol, the TSA certifies a digital
input (i.e., a MAC).
6 Fourth Protocol (TSA creates two records coupled via a nonce)
Step 1 (Originator): The originator sends a hash value H(D) computed on
the document D to a TSA.  
Step 2 (TSA): The TSA generates a nonce value, N.   
NOTE: It is important that N does not repeat for a given signing key. 
If N is randomly generated, we assume that the length of N is adjusted
to ensure adequate security.  If N is the value of an incrementing
counter or sequence number, we assume that it is large enough to ensure
that it does not repeat or cycle. 
Step 3 (TSA): The TSA creates a first receipt (N, T), which is a
time-stamp receipt, consisting of the nonce N and the current time T. 
The TSA has access to a trusted clock that provides current time T.
Step 4 (TSA): The TSA creates a second receipt (N, H(D)) consisting of
the nonce N and  H(D).
Step 5 (TSA): The TSA generates two signatures.  It signs the first
receipt (N, T), produced at step 3, with its private signature
generation key.  It signs the second receipt (N, H(D)), produced at step
4, with its private signature generation key.
Step 6 (TSA): The TSA provides or transmits the signed time-stamp
receipt (N, T) and the signed receipt (N, H(D)) to the originator.







 			


Figure 5.  Time-Stamping in Fourth Protocol

Differences: In Fischer [1], the TSA operates simultaneously on the
digital input and a TSA-generated clock value.  In the alternative
protocol, the TSA operates separately on the digital input and the
TSA-generated clock value.  In Haber [2, 3], the TSA certifies a receipt
comprising an input digital document and a clock value.  In the
alternative protocol, the TSA certifies two receipts, but these two
receipts are different from the single receipt in Haber.
7 Fifth Protocol (TSA computes time difference on time-stamp receipt
using the public verification key certificate)
The fifth protocol is similar to the second protocol, in that the TSA
computes a time difference, ?, between two time values.  But, in the
fifth protocol, ? is the difference between the time T recorded in the
public key certificate corresponding to the TSA's private signing key
and the now current time T', as measured by the TSA, i.e., ? = T - T'. 
Hence, in the fifth protocol, ? does not represent the age of document
D, but rather it is an arbitrary value, representing neither the current
time nor the age of the document.  Since the public key certificate,
containing T, is always available to validate a time-stamp receipt,
containing ?, one is assured that T can be readily determined.
NOTE:  The fifth protocol will operate in situations where the TSA's
public key certificate is signed by a CA or where it is signed by the
TSA using it's private signing key (self-signing).  In the latter case,
some cross certification of certificates may also be useful or
necessary, depending on how the protocol is operated.
Step 1 (Originator): The originator sends a hash value H(D) computed on
the document D to a TSA.  
Step 2 (TSA): The TSA computes a time difference, ?, between the time T
recorded in the public key certificate corresponding to the TSA's
private signing key and the now current time T', e.g., ? = T' - T.  The
TSA has access to a trusted clock that provides current time T'.
NOTE:  The value of T in the public key certificate is a value that may
be established by the TSA when requesting a certificate, it may be
determined by the CA or some combination of both the TSA and CA, or some
completely independent means.
Step 3 (TSA): The TSA creates a time-stamp receipt from the computed
value of ? and the received H(D).
Step 4 (TSA): The TSA signs the time-stamp receipt with its private
signature generation key.  We assume that the TSA has a public and
private key pair used for signing time-stamp receipts.  The private
signing key is available only to the TSA, whereas the public key is made
available to anyone so that they can verify the signatures on time-stamp
receipts generated by the TSA.  The public key of the TSA can be stored
in a certificate signed by a Certification Authority (CA), so that the
TSA's public key can be validated and, hence, trusted by those using
that public key.
Step 7 (TSA): The TSA provides or transmits the signed time-stamp
receipt to the originator.







 			


Figure 6.  Time-Stamping in Fifth Protocol
Differences: In Fischer [1], the TSA operates on a digital input and a
TSA-generated clock value.  In the alternative protocol, the TSA
operates on a digital input and a computed time difference.  In Haber
[2,3], the TSA creates a receipt comprising a digital input and a
TSA-generated clock value.  In the alternative protocol, the TSA creates
a receipt comprising a digital input and a computed time difference.  In
both cases, the signed time-stamp receipt does not contain enough
information to determine the current time T'.  The additional
information needed to compute T' is carried outside the signed
time-stamp receipt, in the TSA's public key certificate.
8 Sixth Protocol (time is completely determined by the public key
certificate) 
In the sixth protocol, the TSA's public key certificate alone determines
the time-stamp.  To illustrate the idea, suppose that the TSA issues a
new public key certificate daily.  That is, a new public and private
signing key pair is generated and used each day.  In this case, any
document signed with the TSA's daily signing key establishes the date
and time, to within 24 hours, when the document was received by the
TSA.  
The idea could be extended by generating new key pairs more frequently,
e.g., hourly, or in increments of a few minutes.  In such a case, the
TSA would not only return the signed value of H(D), but it would also
return the associated public key certificate, thereby allowing the
originator to verify the time-stamp.  In turn, the originator could
provide the signed H(D) and certificate to third parties interested in
validating the time-stamp.  The TSA would also escrow its public key
certificates in case users inadvertently lose or misplace them.  
For  TSAs with high volumes of traffic, the sixth protocol could be
attractive, since the time information is completely carried in the
certificate, and hence users only need to handle signed documents, in
the usual sense.
The TSA still needs to have access to a trusted clock to ensure that
keys roll over at the proper times.
Differences: In Fischer [1], the TSA operates on a digital input and a
TSA-generated clock value.  In Haber [2,3], the TSA creates a receipt
comprising a digital input and a TSA-generated clock value.  In the
alternative protocol, the TSA merely signs the digital input H(D) from
the originator.  The certificate contains a start and stop time, and is
signed.  But, this is not a time-stamp, since the times established in
the certificate are not indicative of the current time when the
certificate is generated, received, or signed.
9 References
A. M. Fischer, "Public/Key Date-Time Notary Facility," U.S. Patent
5,001,752, issued March 19, 1991.
S. A. Haber and W. S. Stornetta, Jr., "Method for secure time-stamping
of digital documents," U. S. Patent 5,136,647, issued August 4, 1992.
S. A. Haber and W. S. Stornetta, Jr., "Method for secure time-stamping
of digital documents," U. S. Patent Re. 34,954, issued May 30, 1995.
B. Schneier, "Applied Cryptography" (second edition), John Wiley & Sons,
Inc., 1996, pp. 75-78.


Paul Koning wrote:
> 
> Could you give an example of an application for the proposed Mechanism
> Identifier field?  While more generality can be a good thing, it's
> useful to have an example to justify added stuff.
> 
>         paul
begin:vcard 
n:Mueller;Roland
tel;fax:(512) 795-0495
tel;work:(512) 795-0494
x-mozilla-html:FALSE
org:TUVIT Inc.
version:2.1
email;internet:roland@tuvit.net
adr;quoted-printable:;;8716 North MoPac=0D=0ASuite 220;Austin;Texas;78759;U.S.A.
x-mozilla-cpt:;-1
fn:Mueller, Roland
end:vcard