Basic Cryptographic Primitives

TCPA makes use of the following cryptographic primitives:

• Random number generation

• Key generation

• Encryption (both asymmetric and symmetric)

• Hash functions (also called hashing operations)

• Digital signatures

• Public key certificates (often referred to simply as certificates)

Generation of Random (or Pseudorandom) Bits and Sequences

The security of many cryptographic mechanisms that are used in TCPA depends upon the generation of unpredictable quantities. Examples include the primes in the RSA encryption and digital signature schemes, the secret key in the DES and 3DES encryption algorithms, and the nonce used in challenge-response integrity-checking systems. In all these cases, the quantities generated must be of sufficient size and be random in the sense that the probability of any particular value being selected must be sufficiently small to preclude an adversary from gaining advantage through optimizing a search strategy based on such probability. In this section, we provide a summary of techniques for the generation of random and pseudo-random bits and numbers.

Ideally, secrets required in cryptographic algorithms and protocols should be generated with a (true) random bit generator. However, the generation of random bits is an inefficient procedure in most practical environments. Moreover, it may be impractical to securely store and transmit a large number of random bits if these are required in applications such as the one-time pad. In such situations, substituting a random bit generator with a pseudo-random bit generator can ameliorate the problem.

A pseudo-random bit generator is a deterministic algorithm which, given a binary sequence of length k, outputs a binary sequence of length l >> k which “appears” to be random. The input to the generator is called the seed, while the output of the generator is called a pseudo-random bit sequence.

Random bit generation can use one of the following three generators: hardware-based generators, software-based generators, and de-skewing.

Pseudo-random bit generation can use a hash function f by first selecting a random seed s and then applying the function to the sequence of values s+1, s+2, …. The output sequence is f(s), f(s+1), f(s+2), …. Depending on the properties of the one-way function used, it may be necessary to keep only a few bits of the output values f(s+i) in order to remove possible correlations between successive values. Examples of suitable one-way functions f include a cryptographic hash function such as SHA-1 or a block cipher such as DES with a secret key. Although such ad-hoc methods have not been proven to be cryptographically secure, they appear sufficient for most applications. Two such methods for pseudo-random bit and number generation that have been standardized are the ANSI X9.17 [ANSI X9.17] generator and the FIPS 186 [FIPS 186] generator.

Pseudo-random bit generation can also use number-theoretic problems, such as the RSA problem and the integer factorization problem. The security of each generator relies on the presumed intractability of an underlying number-theoretic problem. Those pseudo-random bit generators are called cryptographically secure pseudo-random bit generators. Examples include the RSA pseudo-random bit generator, the Micali-Schnorr pseudo-random bit generator, and the Blum-Blum-Shub pseudo-random bit generator [Menezes et al. 1997, Section 5.5].

In the TCPA specification v1.1 [TCPA 2001a], both a random number generator and a pseudo-random number generator are acceptable. The choice depends upon the particular implementation. For example, on those devices that have a hardware source of entropy, a random number generator may be implemented.

The random number generator (or pseudo-random number generator) for the TPM will consist of the following three components: an entropy source and collector, a state register, and a mixing function. These are described in the following list:

• The entropy source is the process or processes that provide entropy. These types of sources could include noise, clock variations, air movement, and other types of events. The entropy collector is the process that collects the entropy, removes bias, and smoothes the output. The collector may have special code to handle any bias or skewing of the raw entropy data. For instance, if the entropy source has a bias of creating 60 percent 1s and only 40 percent 0s, then the collector design takes that bias into account before sending the information to the state register.

• The output of the entropy collector is the primary input to the update function of the state register. The state register implementation may use two registers: a non-volatile register and a volatile register.

• The mixing function takes the state register and creates the output of the random number generator. The output must conform to the requirements for pseudo-random number generator from FIPS 140-2 [FIPS 140-2]. Each use of the mixing function must affect the state register.

More detailed information about random number generation can be found in [Schneier 1996, Section 17.14] and [Menezes et al. 1997, Chapter 5].

Key Generation

Generally, key generation involves an algorithm-dependent process. A random number source is involved in key generation, and it is essential that the random numbers used are sufficiently unpredictable.

TCPA requires generation of asymmetric key pairs and symmetric keys as follows:

• To generate RSA key pairs, the implementation of the generate function must be in accordance with IEEE P1363 [IEEE P1363], which is available in http://grouper.ieee.org/groups/1363/.

• To generate a symmetric key, we recommend that you take the next n bits from the TPM random number generator (or pseudo-random number generator).

For further details on key generation of RSA public key encryption, please see [Menezes et al. 1997, Section 8.2.1]. More specifically, the prime number generation can be implemented by using random search, Gordon's algorithm, Maurer's algorithm, or the NIST method described in [Menezes et al. 1997, Chapter 4].

Encryption

Cryptographic encryption techniques are used to protect the confidentiality of stored or transmitted data. An encryption algorithm provides an encryption process and a decryption process. The encryption process is applied to data (often called plaintext), with the result being encrypted data (or ciphertext). A decryption process is used to transform ciphertext back to the original plaintext.

The encryption algorithm should be designed so that the ciphertext yields no information about the plaintext except, perhaps, its length.

Encryption algorithms work in association with a key. According to the different types of keys, encryption algorithms are divided into two basic types: symmetric encryption and asymmetric encryption. In a symmetric encryption algorithm, the same secret key is used in both the encryption and decryption processes. In an asymmetric encryption algorithm, different but related keys are used for encryption and decryption.

An encryption algorithm operates either as a block cipher or a stream cipher. In a block cipher, the encryption function operates on a fixed-size block of plaintext. In a stream cipher, the encryption function operates on a plaintext message or stream of data of arbitrary size.

A great number of encryption algorithms exist. This appendix introduces only those algorithms that are recommended in TCPA specification v1.1 [TCPA 2001a].

TCPA specification v1.1 [TCPA 2001a] requires only supporting RSA encryption and DES/3DES (and AES [AES] when available). Let's consider such concepts in more detail.

Asymmetric Encryption

An asymmetric encryption algorithm includes two related transformations: a public transformation (defined by the public key) used for encryption, and a private transformation (defined by the private key) used for decryption. The two transformations have the property that, given the public transformation, it is computationally infeasible to derive the associated private transformation.

RSA encryption algorithm— named after its inventors, Ron Rivest, Adi Shamir, and Len Adleman of the Massachusetts Institute of Technology (MIT)—is a widely used asymmetric encryption algorithm.

The security of RSA depends upon the factorization problem—that factoring the product of two large prime numbers is difficult. If the numbers are sufficiently large, factoring requires enormous processing resources to the extent that the problem is considered to become computationally infeasible.

From TCPA specification v1.1 [TCPA 2001a], a TPM must use the RSA algorithm for encryption; a TPM must support key sizes of 512, 1024, and 2048 bits; and the minimum recommended key size is 1024 bits.

TCPA specification v1.1 [TCPA 2001a] contains no requirement concerning how the RSA algorithm is to be implemented. TPM manufacturers may use implementations of the Chinese Remainder Theorem (CRT) or any other suitable method. (See [Menezes et al. 1997, Section 2.120] for more information on the CRT.) Designers should review IEEE P1363 [IEEE P1363] for guidance on RSA implementations.

For details on how to implement RSA encryption, please see [Menezes et al. 1997, Section 8.2]. More specifically, a number of different algorithms to increase the speed of RSA implementations exist. Detailed information about those algorithms, including the one using CRT, can be found in [Menezes et al. 1997, Chapter 14].

Symmetric Encryption

A symmetric encryption algorithm makes use of the same secret key in both the encryption and decryption processes. Knowledge of this key is required to perform both encryption and decryption, so knowledge of the secret key must be restricted to those parties authorized to access the data that the key is used to encrypt.

There is no requirement that a TPM must support a symmetric encryption algorithm, although a TPM may implement a symmetric algorithm [TCPA 2001a].

However, a TSS must provide the symmetric encryption process. TCPA requires the TSS to support both DES and 3DES, but DES should be used only when the 3DES is not allowable.

The Data Encryption Standard (DES) is a block cipher, which processes plaintext blocks of 64 bits, producing 64-bit ciphertext blocks. The effective size of the secret key is 56 bits; more precisely, the input key is specified as a 64-bit key, 8 bits of which (bits 8, 16, …, 64) may be used as parity bits.

Triple-DES (3DES) involves an initial encryption of a 64-bit block using a DES Key 1, followed by a decryption of the result using a DES Key 2, and followed by an encryption of that result using a DES Key 3. This algorithm is generally believed to be many orders of magnitude stronger than DES.

More detailed information about DES and 3DES can be found in [Menezes et al. 1997, Chapter 7].

TCPA specification v1.1 [TCPA 2001a] also requires the TSS to support the Advanced Encryption Standard (AES) when it becomes available. AES, the cipher Rijndael, is a block cipher, which supports block and key lengths of 160 and 224 bits. Detailed information about AES can be found in [AES].

From TCPA specification v1.1 [TCPA 2001a] onward, a TPM must support the storage of at least 256-bit symmetric keys.

Hash Functions

A hash function (refer to [FIPS 180-1] and [ISO/IEC 10118]) takes a message as input and produces an output referred to as a hash code. Hash functions have two basic classes: unkeyed hash functions and keyed hash functions.

Most unkeyed hash functions are designed as iterative processes that hash arbitrary-length inputs by processing successive fixed-size blocks of the input, with the design intent that it be infeasible in practice to produce the same output from two different inputs. So a hash code can be used as a compact representative image (sometimes called an imprint, digital fingerprint, or message digest) of an input string.

Keyed hash functions, because their specific purpose is message authentication, are called Message Authentication Codes (MACs). A keyed hash function takes two functionally distinct inputs—a message and a secret key—and produces a fixed-size output. The design intent of a keyed hash function is that it be infeasible in practice to produce the same output without knowledge of the key.

A TPM must support the unkeyed hash function SHA-1 and also must support the keyed hash function HMAC [TCPA 2001a] (described below).

The Secure Hash Algorithm (SHA-1), based on MD4, was proposed by the U.S. National Institute for Standards and Technology (NIST) for certain U.S. federal government applications. It is a 160-bit hash function and uses five 32-bit chaining variables. Information on how to implement SHA-1 can be found in [ISO/IEC 10118].

When AES is supported in TCPA, a longer length hash function than SHA-1 will need to be used. Options include SHA-256 that provides hash codes of lengths up to 256 bits; SHA-384 that provides hash codes of lengths up to 384 bits; and SHA-512 that provides hash codes of lengths up to 512 bits. Information on how to implement SHA-256, SHA-384, and SHA-512 can be found in [ISO/IEC 10118-3].

Hash-based Message Authentication Code (HMAC) requires two applications of a hash-function to compute a MAC value. For a key K and an unkeyed hash function h, which can be selected from ISO/IEC 10118-3 (for example, SHA-1 above), we compute the MAC on a message m as HMAC(m) = h(K || p₁ || h(K || p₂ || m)), where p₁, p₂ are distinct strings of sufficient length to pad K out to a full block for the compression function. The overall construction is quite efficient despite two calls to h, because the outer execution processes only a two-block input, independent of the length of m.

Detailed information about HMAC implementations can be found in [ISO/IEC 9797-2].

Digital Signatures

Digital signature algorithms are based on asymmetric cryptographic techniques and include two related transformations: a private signature transformation (defined by the private signature key) and a public verification transformation (defined by the public verification key).

A digital signature algorithm must satisfy three security requirements:

The TPM must use the RSAalgorithm for signature operations [TCPA 2001a].

In practice, a number of different algorithms are available to implement RSA signatures in order to make RSA signatures more efficient and to be able to prevent some possible attacks. Detailed information about this process can be found in [Menezes et al. 1997, Chapter 11].

The TPM may implement other asymmetric algorithms such as DSA or elliptic curve algorithms.

The Digital Signature Algorithm (DSA) is an algorithm based on the discrete logarithm problem in a (mathematical) multiplicative group comprising the set of integers modulo some prime. Elliptic curves are one basis for generating such groups.

Elliptic curve-based digital signature systems have recently been implemented in some commercial products. For example, the signature scheme EC-DSA is the elliptic curve analogue of the DSA signature scheme (see [ISO/IEC 15946-2]).

Public Key Certificates

Public key certificates are used to distribute public keys with the design intent of building a high level of trust for the users of the public keys. A certificate, generally speaking, is a data structure that is digitally signed by some party (sometimes called a Certification Authority, or CA for short) in whom users of the certificate place their trust.

A public key certificate consists of a data part and a signature part. The data part consists of the name of an entity, the public key corresponding to that entity, and possibly additional relevant information. The signature part consists of the signature of a Certification Authority over the data part.

[TCPA 2001a] requires using PKCS#1 version 2.1 [RSA PKCS1 v2.1] data formatting and X.509public key certificates [ISO/IEC 9594-8]; here's why:

• The PKCS standards were developed by industrial collaboration led by RSA Laboratories, and they are periodically updated.

• X.509 is one part of a series of specifications outlining directory services for Open Systems Interconnection (OSI) and other systems. X509.v3 is a 1995 technical corrigendum with a certificate extension field added. Standard extensions for v3 certificates are defined in a further amendment. The OSI frameworks project is specified in seven parts of [ISO/IEC 10181].