DRAFT 

NIST Special Publication 800-102 

Recommendation for Digital 

Signature Timeliness 

Elaine Barker 

Computer Security Division 

Information Technology Laboratory 

C O M P U T E R S E C U R I T Y 

November 2008 

U.S. Department of Commerce 

Carlos M. Gutierrez, Secretary 

National Institute of Standards and Technology 

Patrick D. Gallagher, Director 
SP 800-102 DRAFT November 2008 

 Abstract 

Establishing the time when a digital signature was generated is often a critical 

consideration. A signed message that includes the (purported) signing time provides no 

assurance that the private key was used to sign the message at that time unless the 

accuracy of the time can be trusted. With the appropriate use of timestamps from a 

Trusted Timestamp Authority (TTA) and/or verifier-supplied data, the signatory can 

provide some level of assurance about the time that the message was signed. 

KEY WORDS: digital signatures, timeliness, timestamp, Trusted Timestamp Authority 

ii
SP 800-102 DRAFT November 2008 

Acknowledgements 

The National Institute of Standards and Technology (NIST) gratefully acknowledges and 

appreciates contributions by Rich Davis from the National Security Agency concerning 

the many security issues associated with this Recommendation. NIST also thanks the 

many contributions by the public and private sectors whose thoughtful and constructive 

comments improved the quality and usefulness of this publication. 

iii
SP 800-102 DRAFT November 2008 

iv

5

5

6

6

8

8

9

9

10

10

11

13

15

18

19

21

24

24

25

25

27

30

Table of Contents 

1 Introduction................................................................................................

2 Authority...................................................................................................

3 Definitions and Acronyms.........................................................................

3.1 Definitions............................................................................................................ 

3.2 Acronyms............................................................................................................. 

3.3 Symbols................................................................................................................ 

4 Using Timestamps from a Trusted Timestamp Authority.........................

4.1 Notation................................................................................................................ 

4.2 Timestamp Provision by a TTA......................................................................... 

4.3 Signatory Provision of a Timestamp with a Signed Message............................ 

4.3.1 Optional (or No) User Information Provided to the TTA...................... 

4.3.2 A Hash of M is Provided to the TTA..................................................... 

4.3.3 A Digital Signature on M is Provided to the TTA................................. 

4.4 Using an Additional Timestamp ........................................................................ 

4.4.1 Entity A Requests the Second Timestamp............................................. 

4.4.2 Entity B Requests the Second Timestamp............................................. 

5 Evidence of Timeliness Using Verifier-Supplied Data...........................

5.1 The Basic Scheme.............................................................................................. 

5.2 Using a Timestamp to Obtain More Precision................................................... 

5.2.1 Entity A Requests the Timestamp.......................................................... 

5.2.2 Entity B Requests the Timestamp.......................................................... 

Appendix A: References...............................................................................
SP 800-102 DRAFT November 2008 

Recommendation for Digital Signature Timeliness 

1 Introduction 

A digital signature is an electronic analogue of a written signature; the digital signature 

can be used to provide assurance that the claimed signatory signed the information. In 

addition, a digital signature may be used to detect whether or not the information was 

modified after it was signed (i.e., to detect the integrity of the signed data). 

Establishing the time when a digital signature was generated is often a critical 

consideration. A signed message that includes the (purported) signing time provides no 

assurance that the private key was used to sign the message at that time unless the 

accuracy of the time can be trusted. With the appropriate use of timestamps from a 

Trusted Timestamp Authority (TTA) and/or verifier-supplied data, the signatory can 

provide some level of assurance about the time that the message was signed. 

2 Authority 

This document has been developed by the National Institute of Standards and Technology 

(NIST) in furtherance of its statutory responsibilities under the Federal Information 

Security Management Act (FISMA) of 2002, Public Law 107-347. 

NIST is responsible for developing standards and guidelines, including minimum 

requirements, for providing adequate information security for all agency operations and 

assets, but such standards and guidelines shall not apply to national security systems. 

This recommendation is consistent with the requirements of the Office of Management 

and Budget (OMB) Circular A-130, Section 8b(3), Securing Agency Information 

Systems, as analyzed in A-130, Appendix IV: Analysis of Key Sections. Supplemental 

information is provided in A-130, Appendix III. 

This Recommendation has been prepared for use by Federal agencies. It may be used by 

non-governmental organizations on a voluntary basis and is not subject to copyright 

(attribution would be appreciated by NIST.) 

Nothing in this Recommendation should be taken to contradict standards and guidelines 

made mandatory and binding on Federal agencies by the Secretary of Commerce under 

statutory authority. Nor should this Recommendation be interpreted as altering or 

superseding the existing authorities of the Secretary of Commerce, Director of the OMB, 

or any other federal official. 

Conformance testing for implementations of this Recommendation will be conducted 

within the framework of the Cryptographic Module Validation Program (CMVP), a joint 

effort of NIST and the Communications Security Establishment of the Government of 

Canada. The requirements of this Recommendation are indicated by the word “shall.” 

5
SP 800-102 DRAFT November 2008 

3 Definitions, Acronyms and Symbols 

3.1 Definitions 

Approved FIPS-approved and/or NIST-recommended. An algorithm or 

technique that is either 1) specified in a FIPS or NIST 

Recommendation, or 2) adopted in a FIPS or NIST 

Recommendation or 3) specified in a list of NIST-approved 

security functions. 

Digital signature The result of a cryptographic transformation of data that, when 

properly implemented, provides origin authentication, assurance 

of data integrity and signatory non-repudiation. 

Entity An individual (person), organization, device or process. Used 

interchangeably with “party”. 

Hash value The result of applying a hash function to data. 

Key A parameter used in conjunction with a cryptographic algorithm 

that determines its operation. Examples applicable to this 

Recommendation include: 

1. The computation of a digital signature from data, and 

2. The verification of a digital signature. 

Message The data that is signed. 

Nonce A time-varying value that has at most a negligible chance of 

repeating, for example, a random value that is generated anew 

for each use, a timestamp, a sequence number, or some 

combination of these.

Party An individual (person), organization, device or process. Used 

interchangeably with “entity”. 

Private key A cryptographic key that is used with an asymmetric (public 

key) cryptographic algorithm. The private key is uniquely 

associated with the owner and is not made public. It is used to 

compute a digital signature that may be verified using the 

corresponding public key. 

6
SP 800-102 DRAFT November 2008 

Public key A cryptographic key that is used with an asymmetric (public 

key) cryptographic algorithm and is associated with a private 

key. The public key is associated with an owner and may be 

made public. In the case of digital signatures, the public key is 

used to verify a digital signature that was signed using the 

corresponding private key. 

Relying party A party that depends on the validity of the digital signature 

process. 

Security strength A number associated with the amount of work (that is, the 

number of operations) that is required to break a cryptographic 

algorithm or system. 

Shall Used to indicate a requirement of this Recommendation. 

Signatory The entity that generates a digital signature on data using a 

private key. 

Signature generation The process of using a digital signature algorithm and a private 

key to generate a digital signature on data. 

Signature verification The process of using a digital signature algorithm and a public 

key to verify a digital signature on data. 

Timestamp A token or packet of information that is used to provide 

assurance of timeliness; contains timestamped data, including a 

time, and a signature generated by a Trusted Timestamp 

Authority (TTA). 

timestamp Contains the time and, possibly, other information. 

timestamped_data The data on which a digital signature is generated by a TTA. 

timestamp_packet A unit of information that is transmitted by a TTA that contains 

timestamped_data and a timestamp_signature. 

timestamp_signature A digital signature that is generated using a TTA’s private 

signature key. 

timestamp_time The time provided in a timestamp. 

7
SP 800-102 DRAFT November 2008 

Trusted timestamp A timestamp that has been signed by a Trusted Timestamp 

Authority. 

Trusted Timestamp 

Authority 

An entity that is trusted to provide accurate time information. 

TTA_supplied_info Additional information that is included in the timestamped_data

by a TTA during the generation of a timestamp_signature. 

user_supplied_info Additional information that is provided by an entity when 

requesting a timestamp from a TTA. 

Verifier The entity that verifies the authenticity of a digital signature 

using the public key. 

3.2 Acronyms 

FIPS Federal Information Processing Standard. 

FISMA Federal Information Security Management Act. 

NIST National Institute of Standards and Technology. 

OMB Office of Management and Budget. 

TSP Timestamp Packet. 

TTA Trusted Timestamp Authority. 

3.3 Symbols 

D The signed and timestamped message. 

H(M) A hash value that is generated on M. 

M Message 

SIGE(...) A digital signature generated by the entity E using an approved

hash function and an approved digital signature algorithm. The 

data that is signed is the information contained within the 

parentheses. 

8
SP 800-102 DRAFT November 2008 

 

4 Using Timestamps from a Trusted Timestamp Authority 

One method of obtaining assurance of the time of digital signature generation is by the 

use of a trusted timestamp authority (TTA) that is trusted by both the signatory and the 

verifier. The discussions in this section are intended to assist the reader in determining 

exactly what assurances are obtained using different timestamp schemes. 

4.1 Notation 

A trusted timestamp authority (TTA) is an entity that is trusted to produce timestamp 

packets. A timestamp packet (TSP) is transmitted by a TTA and contains: 

• A digital signature (the timestamp_signature) that is generated using the TTA’s 

private key, and 

• The timestamped_data upon which the digital signature is generated. 

The timestamped_data includes a timestamp — an accurate, unambiguous representation 

of the time of generation of the accompanying timestamp signature. 

The following notation will be used in this discussion. Note that the commas are used to 

indicate a list of data, not to indicate the order or format of that data. 

1. TSP = timestamp_packet = timestamped_data, timestamp_signature

where the TSP contains both timestamped_data and a timestamp_signature, 

although the exact format of the TSP is not specified herein. 

2. timestamp_signature = SIGTTA (timestamped_data) 

where “SIGTTA” is a digital signature operation on the timestamped_data using 

the TTA’s private digital signature key. This private key shall only be used for 

the generation of digital signatures on timestamped_data.

3. timestamped_data = user_supplied_info, TTA_supplied_info, timestamp, 

where 

a. user_supplied_info is information that is provided by an entity when 

requesting a timestamp from the TTA; the user_supplied_info may, in 

fact, be Null. If provided, the information is used by the TTA during 

timestamp_signature generation, but need not be transmitted in the 

timestamp packet returned to the requestor. However, this information 

must be available to entities that will verify the timestamp_signature. 

b. TTA_supplied_info is additional information that is used by the TTA 

during timestamp_signature generation; the TTA_supplied_info may, in 

fact, be Null. All or part of this information may be omitted from the 

timestamp packet transmitted by the TTA if the omitted portion(s) can be 

recreated and used by the entities that will verify the timestamp_signature. 

c. timestamp contains the time and possibly other information. 

9
SP 800-102 DRAFT November 2008 

Therefore, the generic TSP produced by a TTA has the form: 

TSP = user_supplied_info, TTA_supplied_info, timestamp, 

SIGTTA(user_supplied_info, TTA_supplied_info, timestamp) 

where user_supplied_info and TTA_supplied_info may be Null. 

4.2 Timestamp Provision by a TTA 

A TTA may either broadcast a timestamp packet (TSP) or provide a TSP in response to a 

request from a requesting entity. The requesting entity and any other party that needs to 

verify the TTA’s digital signature (i.e., a relying party) must be aware of the security 

strength provided by the TTA’s digital signature. If an X-bit security strength is required 

by the requesting entity’s or relying party’s application, then the TTA’s digital signature 

shall provide at least X-bits of security strength in order to fulfill that requirement (see SP 

800-57). 

When a TTA broadcasts a TSP, the user_supplied_info in the TSP is Null. The 

timestamp_signature is generated on the TTA-supplied_info (which may be Null) and the 

timestamp. The TSP is then assembled and broadcast. Portions of the TTA_supplied_info

that are known by all intended recipients of the TSP may be omitted from the data 

transmitted in the timestamped_data field of the TSP, even though the entire 

TTA_supplied_info is included in the data used during the generation and verification of 

the timestamp_signature. 

When an entity requests a timestamp, the requesting entity provides user_supplied_info 

(which may be Null) to the TTA in the request. A timestamp_signature is generated on 

the user_supplied_info, the TTA-supplied_info (which may be Null), and a timestamp. A 

TSP is assembled from the timestamp_signature and timestamped_data, and then sent to 

the requesting entity. Portions of the TTA-supplied_info that are known by all intended 

recipients of the TSP, and the user_supplied_info that is otherwise made known to the 

verifying entity may be omitted from the data transmitted in the timestamped_data field 

of the returned TSP, even though they must be included in the (complete) version of the 

timestamped_data that is used during the generation and verification of the 

timestamp_signature. 

4.3 Signatory Provision of a Timestamp with a Signed Message 

There are several useful schemes in which an entity A obtains a timestamp packet (TSP) 

from a trusted timestamp authority (TTA) and then combines the TSP with a message 

(M) and a signature into a payload of data (D) that is sent to recipient entity B. 

In the following schemes, signatures are generated by entity A or a TTA using an 

approved digital signature algorithm. Let SIGA( ) be a signature generated by entity A, 

and let SIGTTA( ) be a signature generated by a TTA. SIGA( ) is verified using entity A’s 

public signature verification key, and SIGTTA( ) is verified using the TTA’s public 

signature verification key. The following discussions assume that entity B successfully 

verifies all received signatures. 

10
SP 800-102 DRAFT November 2008 

4.3.1 Optional (or No) User Information Provided to the TTA by Entity A 

As shown in Figure 1, entity A may request a timestamp from a TTA, or entity A may use 

a timestamp that is broadcast from a TTA (i.e., entity A does not explicitly request a 

timestamp from the TTA). 

1. The Request message in Figure 1 is sent only if entity A explicitly requests a 

timestamp from the TTA. If the request is sent, the Request message contains any 

desired user_supplied_info (see Section 4.1). 

Figure 1: No User Info Provided to the TTA 

2. The TTA sends a TSP to entity A (or broadcasts a TSP that is obtained by A), 

where: 

TSP = timestamped_data, timestamp_signatureTTA.

If a Request message was sent (in step 1): 

timestamped_data = user_supplied_info, TTA-supplied_info, timestamp. 

timestamp _signatureTTA = SIGTTA(user_supplied_info, TTA_supplied_info, 

timestamp). 

If a Request message was not sent (in step 1): 

timestamped_data = TTA_supplied_info, timestamp.

timestamp_signatureTTA = SIGTTA(TTA_supplied_info, timestamp), 

i.e., user_supplied_info is Null in the case of a broadcast TSP. 

If there is a mutual agreement between entity A and the TTA, the following 

information may be omitted from the TSP data that is transmitted by the TTA: 

• Any portion of the user_supplied_info may be omitted, since it is known 

11
SP 800-102 DRAFT November 2008 

by entity A. 

• Any portion of the TTA_supplied_info may be omitted when this 

information is known by entity A. 

However, any such information omitted from the transmitted data shall be 

included in the timestamped_data that is used in the generation / verification of 

timestamp_signatureTTA = SIGTTA(timestamped_data). 

Upon receiving the TSP from the TTA, entity A should verify 

timestamp_signatureTTA using the TTA’s public signature verification key. 

3. Entity A signs (M, TSP), assembles D and sends it to entity B: 

D = M, TSP, SIGA(M, TSP), 

where the TSP is as specified in step 2. 

If any portion of the user_supplied_info was omitted from the TSP received from 

the TTA, then the entire user_supplied_info shall be inserted into the TSP used in 

the assembly of D unless there is a mutual agreement between entity A and entity 

B, in which case, any portion of the user_supplied_info may be omitted from the 

TSP data transmitted by entity A if it is known by entity B. However, the entire 

user_supplied_info shall be included in the timestamped_data that is used in the 

generation / verification of timestamp_signatureTTA and SIGA(M, TSP). 

If any portion of the TTA_supplied_info was omitted from the TSP received from 

the TTA, then the entire TTA_supplied_info shall be inserted into the TSP used in 

the assembly of D unless there is a mutual agreement between entity A and entity 

B, in which case, any portion of the TTA_supplied_info may be omitted from the 

TSP data transmitted by entity A if it is known by entity B. However, the entire 

TTA_supplied_info shall be included in the timestamped_data that is used in the 

generation / verification of timestamp_signatureTTA and SIGA(M, TSP).. 

4. Upon receiving D, entity B does the following: 

• Verifies timestamp_signatureTTA using the TTA’s public signature 

verification key, and 

• Verifies SIGA(M, TSP) using entity A’s public signature verification key. 

Note that it is irrelevant which of these steps is performed first; it is only 

important that both verifications are successful. 

 Entity B knows the following: 

a. M could have been assembled either before or after the TSP was received. 

b. SIGA(M, TSP) was generated at some point after the time indicated by the 

timestamp in the TSP. 

c. D was assembled after the time indicated by the timestamp in the TSP. 

If a more precise time is required for the generation of SIGA(M, TSP), a second trusted 

timestamp may be acquired (as specified in Section 4.4) that will provide assurance that 

12
SP 800-102 DRAFT November 2008 

(M, TSP) had existed and been signed by (at least) the time indicated in the second 

timestamp. 

4.3.2 A Hash of M is Provided to the TTA by Entity A 

Entity A may provide the hash value of M to the TTA when requesting a timestamp as 

shown in Figure 2. Let H denote a hash value that is generated on M using an approved

hash function (i.e., H = Hash(M)). 

1. Entity A sends H to the TTA in a timestamp request, i.e., the user_supplied_info

contains H (user_supplied_info = H, other_info). Note that other_info may be 

Null. 

A B

TTA

2. TSP

3. D = M, TSP, SIGA(M, TSP)

1. H, other_

info

2. The TTA returns a TSP to entity A: 

Figure 2: Entity A Provides a Hash Value to the TTA 

TSP = timestamped_data, timestamp_signatureTTA 

where: 

timestamped_data = user_supplied_info, TTA-supplied_info, timestamp.

timestamp_signatureTTA = SIGTTA(user_supplied_info, TTA_supplied_info, 

timestamp). 

If there is a mutual agreement between entity A and the TTA, the following 

information may be omitted from the TSP data that is transmitted by the TTA: 

• Any portion of the user_supplied_info may be omitted, since it is known 

by entity A. 

13
SP 800-102 DRAFT November 2008 

• Any portion of the TTA_supplied_info may be omitted if this information 

is already known by entity A. 

However, even though they may be omitted from the transmitted data, the entire 

user_supplied_info and the entire TTA_supplied_info shall be included in the 

timestamped_data that is used in the generation / verification of 

timestamp_signatureTTA = SIGTTA(timestamped_data). 

Upon receiving the TSP from the TTA, entity A should verify 

timestamp_signatureTTA using the TTA’s public signature verification key. 

3. Entity A signs (M, TSP), assembles D and sends it to entity B: 

D = M, TSP, SIGA(M, TSP) 

where the TSP is as defined in step 2. 

If any portion of the user_supplied_info was omitted from the TSP received from 

the TTA, then the entire user_supplied_info shall be inserted into the TSP used in 

the assembly of D unless there is a mutual agreement between entity A and entity 

B, in which case, the following information may be omitted from the TSP data 

transmitted in D by entity A: 

• H may be omitted, since it can be (re)calculated by entity B. 

• Any portion of the other_info in the user_supplied_info may be omitted if 

this information is already known by entity B. 

However, the entire user_supplied_info shall be included in the 

timestamped_data that is used in the generation / verification of 

timestamp_signatureTTA and SIGA(M, TSP).. 

If any portion of the TTA_supplied_info was omitted from the TSP received from 

the TTA, then the entire TTA_supplied_info shall be inserted into the TSP used in 

the assembly of D unless there is a mutual agreement between entity A and entity 

B, in which case, any portion of the TTA_supplied_info may be omitted from the 

TSP data transmitted by entity A if the information is already known by entity B. 

However, the entire TTA_supplied_info shall be included in the 

timestamped_data that is used in the generation/ verification of 

timestamp_signatureTTA and SIGA(M, TSP). 

4. Upon receiving D, entity B does the following: 

• Computes H′ = Hash(M). If H was received in D (see step 3), then entity B 

also verifies that H′ = H. 

• Verifies timestamp_signatureTTA using the TTA’s public signature 

verification key, and 

• Verifies SIGA(M, TSP) using entity A’s public signature verification key. 

Note that it is irrelevant which signature verification is performed first; it is only 

important that both verifications are successful. 

14
SP 800-102 DRAFT November 2008 

Entity B knows the following: 

1. M was assembled, and H was generated prior to the time indicated by the 

timestamp in the TSP obtained from the TTA; in particular, H was included in the 

timestamped_data that was signed by the TTA. 

2. M has remained unchanged since the time indicated by the timestamp in the TSP. 

3. SIGA(M, TSP) was generated at some point after the time indicated by the 

timestamp in the TSP. 

4. D was assembled after the time indicated by the timestamp in the TSP.

If a more precise time is required for the generation of SIGA(M, TSP), a second trusted 

timestamp may be acquired (as specified in Section 4.4) that will provide assurance that 

(M, TSP) had been signed by (at least) the time indicated in the second timestamp. 

4.3.3 A Digital Signature on M is Provided to the TTA by Entity A 

Entity A may provide the digital signature of M to the TTA when requesting a timestamp 

as shown in Figure 3. 

A B

TTA

2. TSP

3. D = M, TSP, SIGA (M, TSP)

1. SIGA(M), other_

info

1. Entity A sends SIGA(M) to the TTA in a timestamp request, i.e., 

user_supplied_info contains SIGA(M) (user_supplied_info = SIGA(M), 

other_info). Note that other_info may be Null. 

Figure 3: Entity A Provides a Signature to the TTA 

2. The TTA returns a TSP to entity A: 

TSP = timestamped_data, timestamp_signatureTTA 

where: 

timestamped_data = user_supplied_info, TTA_supplied_info, timestamp.

timestamp_signatureTTA = SIGTTA(user_supplied_info, TTA_supplied_info, 

15
SP 800-102 DRAFT November 2008 

timestamp). 

If there is a mutual agreement between entity A and the TTA, the following 

information may be omitted from the TSP transmitted by entity A: 

• Any portion of the user_supplied_info may be omitted, since it is known 

his 

d the entire TTA_supplied_info shall be 

by entity A. However, if SIGA(M) is omitted from the TSP, it shall be 

inserted back into the TSP when sent to entity B (see step 3). 

• Any portion of the TTA_supplied_info may be omitted when t

information is known by entity A. 

However, the entire user_supplied_info an

included in the generation / verification of timestamp_signatureTTA. 

Upon receiving the TSP from the TTA, entity A should verify 

timestamp_signatureTTA using the TTA’s public signature verifi

Entity A signs (M, TSP), assembles D and sends it to entity B: 

cation key. 

3. 

where

info was omitted from the TSP received from 

D = M, TSP, SIGA(M, TSP) 

 TSP is as defined in step 2. 

If any portion of the user_supplied_

the TTA, then the entire user_supplied_info shall be inserted into the TSP used in 

the assembly of D unless there is a mutual agreement between entity A and entity 

B, in which case, any portion of the user_supplied_info may be omitted from the 

TSP transmitted to entity B if it is known by entity B. However, the entire 

user_supplied_info shall be included in the timestamped_data that is used in the 

generation / verification of timestamp_signatureTTA and SIGA(M, TSP).. 

If any portion of the TTA_supplied_info was omitted from the TSP received from 

the TTA, then the entire TTA_supplied_info shall be inserted into the TSP used in 

the assembly of D unless there is a mutual agreement between entity A and entity 

B, in which case, any portion of the TTA_supplied_info may be omitted from the 

TSP data transmitted by entity A. However, the entire TTA_supplied_info shall be

included in the timestamped_data that is used in the generation / verification of 

timestamp_signatureTTA and SIGA(M, TSP). 

4. Upon receiving D, entity B does the following: 

 signature verification key, 

) using entity A’s public signature verification key. 

 Entity

erated before the time indicated by the TSP’s 

• Verifies SIGA(M) using entity A’s public

• Verifies timestamp_signatureTTA using the TTA’s public signature 

verification key, and 

• Verifies SIGA(M, TSP

Note that the order of performing these steps is irrelevant; it is only important that

all verifications are successful. 

 B knows the following: 

1. M and SIGA (M) were gen

16
SP 800-102 DRAFT November 2008 

timestamp, and SIGA(M) was included in the timestamped_data that was

by the TTA. 

M has remaine

 signed 

2. d unchanged since the time indicated by the timestamp in the TSP. 

4. he time indicated by the timestamp in the TSP. 

If a trusted 

4.3.4 A Digital Signature on M is Provided to the TTA by Entity B 

ity A as 

1. Entity A signs M, assembles D and sends it to Entity B: 

Entity B may verify SIGA(M) u entity A’s public signature 

s 

2. tamp request, i.e., 

A(M), 

3. SIGA(M, TSP) was generated at some time after the time indicated by the 

timestamp in the TSP. 

D was assembled after t

 more precise time is required for the generation of SIGA(M, TSP), a second

timestamp may be acquired (as specified in Section 4.4) that will provide assurance that

SIGA(M, TSP) was generated by (at least) the time indicated in the second timestamp. 

Entity B may provide a digital signature to the TTA that was received from ent

shown in Figure 4. 

A B

1. D = M, SIGA(M)

TTA

2. SIG

A(M), other_info

3. TSP

Figure 4: Entity B Provides a Signature to the TTA 

D = M, SIGA(M) 

pon receipt using 

verification key, and may record the (approximate) time that the signature wa

received from Entity A for his own purposes. 

Entity B sends SIGA(M) to the TTA in a times

user_supplied_info contains SIGA(M) (user_supplied_info = SIG

other_info). Note that the other_info may be Null. 

17
SP 800-102 DRAFT November 2008 

3. The TTA returns a TSP to entity B: 

TSP = timestamped_data, timestamp_signatureTTA 

where: 

timestamped_data = user_supplied_info, TTA_supplied_info, timestamp.

timestamp_signatureTTA = SIGTTA(user_supplied_info, TTA_supplied_info, 

timestamp). 

If there is a mutual agreement between entity B and the TTA, the following 

information may be omitted from the TSP transmitted by entity B: 

• Any portion of the user_supplied_info may be omitted, since it is known 

by entity B. 

• Any portion of the TTA_supplied_info may be omitted when this 

information is known by entity B. 

However, the entire user_supplied_info and the entire TTA_supplied_info shall be 

included in the generation / verification of timestamp_signatureTTA. 

4. Upon receiving the TSP, entity B does the following: 

• Verifies timestamp_signatureTTA using the TTA’s public signature 

verification key, and 

• Verifies SIGA(M) using entity A’s public signature verification key if it 

was not verified prior to sending it to the TTA. 

Note that the order of performing these steps is irrelevant; it is only important that 

all verifications are successful. 

Entity B has evidence that M and SIGA (M) were generated before the time indicated by 

the TSP’s timestamp, and SIGA(M) was included in the timestamped_data that was signed 

by the TTA. This evidence can be presented to any third party who also trusts the TTA. 

4.4 Using an Additional Timestamp 

A refinement of the signature generation time may be obtained if a second timestamp is 

requested from a TTA. Any entity could make the request, although requests by entity A 

and entity B are discussed below. This procedure has the most value if the timestamp 

request is made as close as possible to the generation of entity A’s signature on the first 

timestamp packet; thus, a minimal time interval is established during which the signature 

was generated. The discussions assume that all digital signatures are successfully 

verified. 

In the following schemes, the initial steps of a scheme specified in Sections 4.3.1 - 4.3.3 

are executed first, with the following changes: 

• user_supplied_info becomes user_supplied_info1, 

• the other_info within user_supplied_info1 becomes other_info1. 

18
SP 800-102 DRAFT November 2008 

• TTA_supplied_info becomes TTA_supplied_info1, 

• timestamp becomes timestamp1, 

• TTA becomes TTA1 (alternatively represented as TTA1 in a subscript), and 

• TSP becomes TSP1. 

The schemes indicate the use of two TTAs: TTA1 and TTA2. TTA2 may, in fact, be the 

same TTA as TTA1. 

4.4.1 Entity A Requests the Second Timestamp 

Both timestamps may be obtained by entity A. The TTA(s) providing the timestamps 

must be trusted by both entity A and entity B, and also by any third party that needs to be 

convinced of the signature generation time. 

Figure 5 shows that the first timestamp is obtained as specified in Section 4.3.1, 4.3.2, or 

4.3.3, after which entity A requests a second timestamp. The first two steps are the same 

as those specified for the schemes in 4.3.1 - 4.3.3. 

A B

TTA1

2. T

S

P1

5. D = M, TSP1, TSP2

1. u

s

e

r_s

upplie

d_info1

TTA2

4. T

S

P2

3. S

I

G

A

M( , TS

P1), oth

e

r

_info

The process continues as follows, where H denotes a hash value that is generated on M

using an approved hash function (i.e., H = Hash(M)): 

The process continues as follows, where H denotes a hash value that is generated on M

using an approved hash function (i.e., H = Hash(M)): 

Figure 5: After Using a Scheme from 4.3, Entity A Requests A Second Timestamp 

3. Entity A generates SIG 3. Entity A generates SIGA(M, TSP1) and sends it to TTA ) and sends it to TTA2 in a second timestamp in a second timestamp 

request, i.e., request, i.e., user_supplied_info user_supplied_info2 contains SIG contains SIGA(M, TSP1) (user_supplied_info user_supplied_info2 = 

19
SP 800-102 DRAFT November 2008 

SIGA(M,TSP1), other_info2). Note that other_info2 may be Null. 

TSP1 is defined to be the TSP used for the scheme in 4.3.1, 4.3.2 or 4.3.3. 

 4. 

TTA2 

whe

tamped_data2 = SIGA(M, TSP1), TTA_supplied_info2, timestamp2. 

2, 

If there is a mutual agreement between entity A and TTA2, the following 

TTA2 returns TSP2 to entity A: 

TSP2 = timestamped_data2, timestamp_signature

re: 

times

timestamp_signatureTTA2 = SIGTTA2(SIGA(M, TSP1), TTA_supplied_info

timestamp2). 

information may be omitted from the TSP2 data transmitted by TTA2: 

• Any portion of the user_supplied_info may be omitted, since it is known 

transmitted

by entity A. However, if SIGA(M, TSP1) is omitted from the TSP, it must 

be inserted back into the TSP when sent to entity B (see step 5). 

• Any portion of the TTA_supplied_info2 may be omitted when the

information is known by entity A. 

However, even if they are omitted from the TSP2 data, 

both the entire SIGA(M, TSP1) and the entire TTA_supplied_info2 shall be 

included in the timestamped_data2 that is used in the generation / verification of 

mestamp_signatureTTA2

5. 

where appropriate subsection of Section 4.3, and TSP2 is as 

timestamp_signatureTTA2 = SIGTTA2 (timestamped_data2). 

Upon receiving TSP2 from TTA2, entity A should verify ti

using the TTA2’s public signature verification key. 

Entity A assembles D and sends it to entity B: 

D = M, TSP1, TSP2

TSP1 is defined in the

defined in step 4. Note that if SIGA(M, TSP1) was not transmitted in the 

timestamped_data of the TSP sent from the TTA, it shall be inserted into

used in the assembly of D.

If omitted from the TSPs re

 TSP1

ceived from the TTAs, the entire user_supplied_info1

SP2

and the entire TTA_supplied_info1 shall be inserted into TSP1, and the entire 

user_supplied_info2 and the entire TTA_supplied_info2 shall be inserted into T

unless there is a mutual agreement between entity A and entity B, in which case 

the following may be omitted from the transmitted TSP1 and TSP2 data in D: 

• Any portion of user_supplied_info1 that is present in TSP1 may be omitted 

if it is known or can be determined by entity B. 

• Any portion of user_supplied_info2 that is present in TSP2 may be omitted 

t in TSP1 may be omitted 

if it is known or can be determined by entity B. 

• Any portion of TTA_supplied_info1 that is presen

20
SP 800-102 DRAFT November 2008 

if it is already known by entity B. 

• Any portion of TTA_supplied_info2 may be omitted if it is already known 

ormation omitted from the transmitted

by entity B. 

However, any such inf data shall be 

included in the appropriate timestamped_data field (timestamped_data1 and/or 

timestamped_data2) used in the generation / verification of the quantities: 

timestamp_signatureTTA1 = SIGTTA1 (timestamped_data1), 

SIGA(M, TSP1), and 

timestamp_signatureTTA2 = SIGTTA2 (timestamped_data2). 

6. Upon r

entity B computes H′ = Hash(M). 

1) using entity A’s public signature verification key, 

ies timestamp_signatureTTA2 using TTA2’s public signature 

orming these verifications is irrelevant; it is only 

Entity B own in the appropriate scheme 

SP1) was generated between the times indicated in timestamp1 and 

b. 

4.4.2 Entity B Requests the Second Timestamp 

nd verifying the message D

es 

f 

cond timestamp after receiving the message D

tep 4), the scheme proceeds as follows: 

2 to TTA2

eceiving D, entity B does the following: 

• If the scheme in Section 4.3.2 was used, 

If H was received by entity B in D, entity B also verifies that H′ = H. 

• Verifies timestamp_signatureTTA1 using TTA1’s public signature 

verification key, 

• Verifies SIGA(M, TSP

and 

• Verif

verification key. 

Note that the order of perf

important that all verifications are successful. 

 knows the following in addition to what is kn

from Section 4.3: 

a. SIGA(M, T

timestamp2, and was included in the timestamped_data signed by TTA2. 

D was assembled after the time indicated by timestamp2. 

Entity B may request a second timestamp after receiving a

from entity A (see step 4 of the schemes in Sections 4.3.1 - 4.3.3). The TTA that provid

the first timestamp must be trusted by both entity A and entity B, but the TTA that 

provides the second timestamp (TTA2) may need to be trusted only by entity B. In 

general, any party that relies on the accuracy of the bounds on the generation time o

SIGA(M, TSP1) must trust both TTAs. 

Figure 6 shows entity B requesting a se

from entity A. The first four steps of this scheme are the same as those specified in one of

the schemes in Sections 4.3.1 - 4.3.3. 

After verifying the signatures in D (in s

5. Entity B sends entity A’s digital signature from D in user_supplied_info

21
SP 800-102 DRAFT November 2008 

in a timestamp request (shown as message 4 in Figure 6), where

user_supplied_info2 = SIGA (M, TSP1), other_info2. Note that oth

Null. 

er_info2 may be 

6. TTA2 returns TSP2 to entity B (shown as message 5 in Figure 6): 

whe

tamped_data2 = SIGA (M, TSP1), TTA_supplied_info2, timestamp2 

2, 

If there is a mutual agreement between entity B and TTA2, the following 

A B

TTA1

2. TSP1

3. D = M, TSP1, SIGA (M, TSP1)

1. user_

supplied_

info1

TTA2

5. TSP2

4. SIGA (M, TSP1), other_info

Figure 6: Entity A Used a Scheme from 4.3; Entity B Requests the Second 

Timestamp

TSP2 = timestamped_data2, timestamp_signatureTTA2 

re: 

times

timestamp_signatureTTA2 = SIGTTA2(SIGA (M, TSP1), TTA_supplied_info

timestamp2). 

information may be omitted from the TSP2 data transmitted by TTA2: 

• Any portion of the user_supplied_info may be omitted, since it is known 

of TTA_supplied_info2 may be omitted if the information is 

omitted from the transmitted

by entity B. 

• Any portion 

already known by entity B. 

However, even though they may be TSP2 data, 

the entire user_supplied_info and the entire TTA_supplied_info2 shall be included 

in the timestamped_data2 that is used in the generation / verification of 

 timestamp_signatureTTA2 = SIGTTA2 (timestamped_data2). 

22
SP 800-102 DRAFT November 2008 

7. ic signature 

In addi rom each scheme, entity B now has evidence that the 

nd 

Entity B then verifies timestamp_signatureTTA2 using TTA2’s publ

verification key. 

tion to what is known f

signature SIGA(M, TSP1) was generated between the times indicated in timestamp1 a

timestamp2. This evidence can be presented to any third party who also trusts the TTA. 

23
SP 800-102 DRAFT November 2008 

5 Evidence of Timeliness Using Verifier-Supplied Data 

Independent of the use of a trusted timestamping service by entity A, entity A can 

provide evidence to the verifier (entity B) of the timeliness of its signature by: 

• Combining fresh data that was supplied by the intended verifier with any other 

data to be included in the message, and 

• Generating a digital signature on the combination. 

In the following schemes, a nonce is used to assist in establishing timeliness. A nonce is a 

time-varying value, represented as a byte string that has (at most) a negligible chance of 

repeating. For example, a nonce may be composed of one (or more) of the following 

components: 

1. A random value that is generated anew for each nonce, using an approved

random bit generator. The security strength of the RBG used to obtain each 

random value shall be equal to or greater than the security strength associated 

with the digital signature process. The appropriate security strength shall have 

been determined prior to the generation of this random value. The length of the 

RBG output shall be at least the security strength associated with the digital 

signature process (e.g., if the security strength of the digital signature process is 

112 bits, then the length of the RBG output shall be at least 112 bits). A nonce 

containing a component of this type is called a random nonce. 

2. A timestamp of sufficient resolution (detail) so that it is different each time it is 

used. 

3. A monotonically increasing sequence number. 

If a combination of a timestamp and a monotonically increasing sequence number is used 

without a random nonce, the sequence number shall be reset only when the timestamp 

changes. (For example, a timestamp may show the date but not the time of day, so a 

sequence number is appended that will not repeat during a particular day.) 

When using a nonce, a random nonce should be used. 

In the following schemes, let Nonce be the verifier-supplied data (i.e., supplied by entity 

B). Let D be the signed message to be sent to entity B, and let SIGA( ) be the digital 

signature that is computed by entity A using an approved hash function and an 

approved signature algorithm; SIGA( ) is verified using entity A’s public signature 

verification key. The discussions assume that entity B successfully verifies all digital 

signatures. 

Figure 7: Using Verifier Supplied Data 

5.1 The Basic Scheme 

As shown in Figure 7, the scheme 

proceeds as follows: 

1. Entity B sends a newly 

24
SP 800-102 DRAFT November 2008 

generated Nonce to entity A. 

2. Entity A signs (M, Nonce), assembles D, and sends it to entity B, where: 

D = M, SIGA(M, Nonce). 

3. Upon receiving D, entity B then verifies SIGA(M, Nonce) using entity A’s public 

signature verification key. 

 Entity B knows the following: 

a. M could have been assembled either before or after the Nonce was received from 

entity B. 

b. SIGA(M, Nonce) was generated at some time after the Nonce was received by 

entity A. 

c. D was assembled by entity A after the Nonce was received.

If a more precise time is required for the generation of SIGA(M, Nonce), a trusted 

timestamp may be acquired as specified in Section 5.2; the timestamp will provide 

assurance that SIGA(M, Nonce) was generated by (at least) the time indicated in the 

timestamp. 

5.2 Using a Timestamp to Obtain More Precision 

When verifier-supplied data is used, a more precise time for the generation of a digital 

signature can be provided by requesting a timestamp. Any entity could make the request, 

although requests by entity A and entity B are discussed below. This procedure has the 

most value if the timestamp request is made as close to the generation of entity A’s 

signature as possible, since it may be used to establish a minimal time interval during 

which entity A’s signature was generated. The discussions assume that entity B 

successfully verifies all digital signatures. 

5.2.1 Entity A Requests the Timestamp 

Entity A may request a timestamp before sending a message to entity B. The TTA that 

provides the timestamp must be trusted by both parties. 

Figure 8 depicts the case where entity A provides more precision as to when SIGA(M, 

Nonce) was generated. Note that the Nonce supplied by entity B could include a 

timestamp, in which case, this (additional) timestamp could establish an interval during 

which SIGA(M, Nonce) was generated. 

The first step is the same as that specified in Section 5.1. The process continues as 

follows: 

2. Entity A generates SIGA(M, Nonce) and sends it to the TTA in a timestamp 

request, where user_supplied_info = SIGA(M, Nonce), other_info. Note that 

other_info may be Null. 

3. The TTA returns a TSP to entity A: 

TSP = timestamped_data, timestamp_signatureTTA 

25
SP 800-102 DRAFT November 2008 

where: 

timestamped_data = SIGA(M, Nonce), TTA_supplied_info, timestamp.

timestamp_signatureTTA = SIGTTA(SIGA(M, Nonce), TTA_supplied_info, 

timestamp). 

A B

4. D = M, TSP

TTA

3. T

S

P

2. S

GI A

M( , No

n

c

e), oth

e

r_info

1. Nonce

If there is a mutual agreement between entity A and the TTA, the following 

information may be omitted from the TSP data transmitted by the TTA: 

Figure 8: Entity A Requests a Timestamp 

• Any portion of the user_supplied_info may be omitted, since it is known 

by entity A. However, if SIGA(M, Nonce) is omitted from the TSP, it must 

be inserted back into the TSP when sent to entity B (see step 4). 

• Any portion of the TTA_supplied_info may be omitted if this information 

is already known by entity A. 

However, even though they may be omitted from the transmitted TSP data, 

both the entire user_supplied_info and the entire TTA_supplied_info shall be 

included in the timestamped_data that is used in the generation / verification of 

 timestamp_signatureTTA = SIGTTA(timestamped_data). 

Upon receiving the TSP from the TTA, entity A should verify 

timestamp_signatureTTA using the TTA’s public signature verification key. 

26
SP 800-102 DRAFT November 2008 

4. Entity A assembles D and sends it to entity B: 

D = M, TSP 

where TSP is as defined in step 3. 

If any portion of the user_supplied_info was omitted from the TSP received from 

the TTA, then the entire user_supplied_info shall be inserted into the TSP used in 

the assembly of D unless there is a mutual agreement between entity A and entity 

B, in which case, any portion of the user_supplied_info may be omitted from the 

TSP data transmitted to entity B if it is known by entity B. However, the entire 

user_supplied_info shall be included in the timestamped_data that is used in the 

generation / verification of timestamp_signatureTTA and SIGA(M, Nonce). 

If any portion of the TTA_supplied_info was omitted from the TSP received from 

the TTA, then the entire TTA_supplied_info shall be inserted into the TSP used in 

the assembly of D unless there is a mutual agreement between entity A and entity 

B, in which case, any portion of the TTA_supplied_info may be omitted from the 

TSP data transmitted by entity A if it is known by entity B. However, the entire 

TTA_supplied_info shall be included in the timestamped_data that is used in the 

generation / verification of timestamp_signatureTTA and SIGA(M, Nonce). 

5. Upon receiving D, entity B does the following: 

• Verifies SIGA(M, Nonce) using entity A’s verification public key, and 

• Verifies timestamp_signatureTTA using the TTA’s public signature 

verification key. 

Note that the order of performing these verifications is irrelevant; it is only 

important that both verifications are successful. 

In addition to what has been determined by entity B in Section 5.1, entity B now has 

determined that SIGA(M, Nonce) was generated between the time that the Nonce was sent 

to entity A and the time indicated in the timestamp 

5.2.2 Entity B Requests the Timestamp 

Entity B may request a timestamp after receiving the message D from entity A. The TTA 

that provides the timestamp may need to be trusted only by entity B unless another party 

needs to be convinced of the signature generation time. 

Figure 9 depicts the case where entity A provides evidence of timeliness using data 

supplied by entity B, and entity B determines (more precisely) when the digital signature 

generated by entity A was received. This scheme is similar to the scheme in Section 

4.3.4, with the only difference being the nonce sent from entity B to entity A. Note that 

the Nonce supplied by entity B could include a timestamp (trusted by both entity A and 

entity B), in which case, this (additional) timestamp would establish an interval during 

which the signature was generated. 

The first three steps are the same as those specified in Section 5.1. After verifying the 

signature in D, the scheme proceeds as follows: 

27
SP 800-102 DRAFT November 2008 

4. Entity B sends SIGA(M, Nonce) as the user_supplied_info to the TTA in a 

timestamp request (shown as message 3 in Figure 9); therefore,user_supplied_info

contains SIGA(M, Nonce), i.e., user_supplied_info = SIGA(M, Nonce), other_info. 

Note that other_info may be Null. 

5. The TTA returns a TSP to entity B (shown as message 4 in Figure 9): 

 TSP = timestamped_data, timestamp_signatureTTA 

where: 

timestamped_data = SIGA(M, Nonce), TTA_supplied_info, timestamp

timestamp_signatureTTA = SIGTTA(SIGA(M, Nonce), TTA_supplied_info, 

timestamp). 

If there is a mutual agreement between entity B and the TTA, the following 

information may be omitted from the TSP data transmitted by the TTA: 

• Any portion of the user_supplied_info may be omitted, since it is known 

by entity B. 

• Any portion of theTTA_supplied_info may be omitted when this 

information is known by entity B. 

However, even though they may be omittted from the transmitted TSP data, both 

the entire SIGA(M, Nonce) and the entire TTA_supplied_info shall be included in 

the timestamped_data that is used in the generation / verification of 

timestamp_signatureTTA = SIGTTA(timestamped_data). 

Figure 9: Entity B Requests a Timestamp 

A B 2. D = M, SIGA(M)

TTA

2. SIG

A(M), other_info

3. TSP

1. Nonce

28
SP 800-102 DRAFT November 2008 

6. Entity B then verifies timestamp_signatureTTA using the TTA’s public signature 

verification key. 

In addition to what has been determined by Entity B in Section 5.1, entity B has proof 

that timestamp_signatureTTA was generated before the time indicated in the timestamp. 

29
SP 800-102 DRAFT November 2008 

30

Appendix A: References 

[1] Federal Information Processing Standard (FIPS) 186-3, The Digital Signature 

Standard, dated XXX. 

[2] NIST Special Publication (SP) 800-57, Recommendation for Key Management −

Part 1: General, Revised June 12, 2006. 

[3] Request for Comment 3161, Internet X.509 Public Key Infrastructure Time-Stamp 

Protocol (TSP), IETF Standards Track, August 2001. 

[4] ISO/IEC 18014, Information Technology – Security Techniques – Time-stamping 

Services, 2002. 

[5] ANS X9.95, Trusted Timestamp Management and Security, 2005.