|
Because classical cryptosystems use shared keys, it is not possible to bind an identity to a key.
Public key cryptosystems use two keys, one of which is to be available to all. The association between the cryptographic key and the principal is critical, because it determines the public key used to encipher messages for secrecy. If the binding is erroneous, someone other than the intended recipient could read the message.
For purposes of this discussion, we assume that the principal is identified by a name of some acceptable sort and has been authenticated to the entity that generates the cryptographic keys. The question is how some (possibly different) principal can bind the public key to the representation of identity.
An obvious idea is for the originator to sign the public key with her private key, but this merely pushes the problem to another level, because the recipient would only know that whoever generated the public key also signed it. No identity is present.
Creating a message containing a representation of identity, the corresponding public key, and a timestamp, and having a trusted authority sign it.
CAlice = { eAlice || Alice || T } dCathy
This type of structure is called a certificate.
A certificate is a token that binds an identity to a cryptographic key.
When Bob wants to communicate with Alice, he obtain's Alice's certificate CAlice. Assuming that he knows Cathy's public key, he can decipher the certificate. He first checks the timestamp T to see when the certificate was issued. (From this, he can determine if the certificate is too old to be trusted; see below.) He looks at the subject entity (Alice, to whom the certificate was issued). The public key in the certificate belongs to that subject, so Bob now has Alice's public key. He knows that Cathy signed the certificate and therefore that Cathy is vouching to some degree that the public key belongs to Alice. If he trusts Cathy to make such a determination, he accepts the public key as valid and belonging to Alice.
One immediate problem is that Bob must know Cathy's public key to validate the certificate. Two approaches deal with this problem. The first, by Merkle, eliminates Cathy's signature; the second structures certificates into signature chains.
Certificate Signature Chains
The usual form of certification is for the issuer to encipher a hash of the identity of the subject (to whom the certificate is issued), the public key, and information such as time of issue or expiration using the issuer's private key. To validate the certificate, a user uses the issuer's public key to decipher the hash and check the data in the certificate. The user trying to validate the certificate must obtain the issuer's public key. If the issuer has a certificate, the user can get that key from the issuer's certificate. This pushes the problem to another level: how can the issuer's certificate be validated?
Two approaches to this problem are to construct a tree-like hierarchy, with the public key of the root known out of band, or to allow an arbitrary arrangement of certifiers and rely on each individual's knowledge of the certifiers. First, we examine X.509, which describes certificates and certification in general. We then look at the PGP certification structure.
Certification Signature Chains
X.509the Directory Authentication Framework is the basis for many other protocols. It defines certificate formats and certification validation in a generic context. Soon after its original issue in 1988, I'Anson and Mitchell found problems with both the protocols and the certificate structure. These problems were corrected in the 1993 version, referred to as X.509v3.
The X.509v3 certificate has the following components.
-
Version. Each successive version of the X.509 certificate has new fields added. If fields 8, 9, and 10 (see below) are present, this field must be 3; if fields 8 and 9 are present, this field is either 2 or 3; and if none of fields 8, 9, and 10 are present, the version number can be 1, 2, or 3.
-
Serial number. This must be unique among the certificates issued by this issuer. In other words, the pair (issuer's Distinguished Name, serial number) must be unique.
-
Signature algorithm identifier. This identifies the algorithm, and any parameters, used to sign the certificate.
-
Issuer's Distinguished Name. This is a name that uniquely identifies the issuer.
-
Validity interval. This gives the times at which the certificate becomes valid and expires.
-
Subject's Distinguished Name. This is a name that uniquely identifies the subject to whom the certificate is issued.
-
Subject's public key information. This identifies the algorithm, its parameters, and the subject's public key.
-
Issuer's unique identifier (Version 2 and 3 certificates only). Under some circumstances, issuer Distinguished Names may be recycled (for example, when the Distinguished Name refers to a role, or when a company closes and a second company with the same Distinguished Name opens). This field allows the issuer to disambiguate among entities with the same issuer name.
-
Subject's unique identifier (Version 2 and 3 certificates only). This field is like field 8, but for the subject.
-
Extensions (Version 3 certificates only). X.509v3 defines certain extensions in the areas of key and policy information, certification path constraints, and issuer and subject information. For example, if an issuer has multiple certification keys, the "authority key identifier" allows the certificate to indicate which key should be used. The "basic constraints" extension indicates if the certificate holder can issue certificates.
-
Signature. This field identifies the algorithm and parameters used to sign the certificate, followed by the signature (an enciphered hash of fields 1 to 10) itself.
To validate the certificate, the user obtains the issuer's public key for the particular signature algorithm (field 3) and deciphers the signature (field 11). She then uses the information in the signature field (field 11) to recompute the hash value from the other fields. If it matches the deciphered signature, the signature is valid if the issuer's public key is correct. The user then checks the period of validity (field 5) to ensure that the certificate is current.
A certification authority (CA) is an entity that issues certificates.
If all certificates have a common issuer, then the issuer's public key can be distributed out of band. However, this is infeasible. For example, it is highly unlikely that France and the United States could agree on a single issuer for their organizations' and citizens' certificates. This suggests multiple issuers, which complicates the process of validation.
Suppose Alice has a certificate from her local CA, Cathy. She wants to communicate with Bob, whose local CA is Dan. The problem is for Alice and Bob to validate each other's certificates.
Assume that X<<Y>> represents the certificate that X generated for the subject Y (X is the CA that issued the certificate). Bob's certificate is Dan<<Bob>>. If Cathy has issued a certificate to Dan, Dan has a certificate Cathy<<Dan>>; similarly, if Dan has issued a certificate to Cathy, Cathy has a certificate Dan<<Cathy>>. In this case, Dan and Cathy are said to be cross-certified.
Two CAs are cross-certified if each has issued a certificate for the other.
Because Alice has Cathy's (trusted) public key, she can obtain Cathy<<Dan>> and form the signature chain
Cathy<<Dan>> Dan<<Bob>>
Because Alice can validate Dan's certificate, she can use the public key in that certificate to validate Bob's certificate. Similarly, Bob can acquire Dan<<Cathy>> and validate Alice's certificate.
Dan<<Cathy>> Cathy<<Alice>>
Signature chains can be of arbitrary length. The only requirement is that each certificate can be validated by the one before it in the chain. (X.509 suggests organizing CAs into a hierarchy to minimize the lengths of certificate signature chains, but this is not a requirement.)
Certificates can be revoked, or canceled. A list of such certificates enables a user to detect, and reject, invalidated certificates.
PGP Certificate Signature Chains
PGP is an encipherment program widely used to provide privacy for electronic mail throughout the Internet, and to sign files digitally. It uses a certificate-based key management infrastructure for users' public keys. Its certificates and key management structure differ from X.509's in several ways. Here, we describe OpenPGP's structure; but much of this discussion also applies to other versions of PGP.
An OpenPGP certificate is composed of packets. A packet is a record with a tag describing its purpose. A certificate contains a public key packet followed by zero or more signature packets. An OpenPGP public key packet has the following structure.
-
Version. This is either 3 or 4. Version 3 is compatible with all versions of PGP; Version 4 is not compatible with old (Version 2.6) versions of PGP.
-
Time of creation. This specifies when the certificate was created.
-
Validity period (Version 3 only). This gives the number of days that the certificate is valid. If it is 0, the certificate does not expire.
-
Public key algorithm and parameters. This identifies the algorithm used and gives the parameters for the cryptosystem used. Version 3 packets contain the modulus for RSA. Version 4 packets contain the parameters appropriate for the cryptosystem used.
-
Public key. This gives the public key. Version 3 packets contain the exponent for RSA. Version 4 packets contain the public key for the cryptosystem identified in field 4.
The information in an OpenPGP signature packet is different for the two versions. Version 3 contains the following.
-
-
Signature type. This describes the specific purpose of the signature and encodes a level of trust. For example, signature type 0x11 says that the signer has not verified that the public key belongs to the named subject.
-
Creation time. This specifies the time at which the fields following were hashed.
-
Key identifier of the signer. This specifies the key used to generate the signature.
-
Public key algorithm. This identifies the algorithm used to generate the signature.
-
Hash algorithm. This identifies the algorithm used to hash the signature before signing.
-
Part of signed hash value. After the data is hashed, field 2 is given the time at which the hash was computed, and that field is hashed and appended to the previous hash. The first two bytes are placed into this field. The idea is that the signature can be rejected immediately if the first two bytes hashed during the validation do not match this field.
-
Signature. This contains the encipherment of the hash using the signer's private key.
A Version 4 signature packet is considerably more complex, but as a Version 3 signature packet does, it binds a signature to an identifier and data. The interested reader is referred to the OpenPGP specifications.
PGP certificates differ from X.509 certificates in several important ways. Unlike X.509, a single key may have multiple signatures. (All Version 4 PGP keys are signed by the owner; this is called self-signing.) Also unlike X.509, a notion of "trust" is embedded in each signature, and the signatures for a single key may have different levels of trust. The users of the certificates can determine the level of trust for each signature and act accordingly.
EXAMPLE: Suppose Alice needs to communicate with Bob. She obtains Bob's public key PGP certificate, Ellen,Fred,Giselle,Bob<<Bob>> (where the X.509 notation is extended in the obvious way). Alice knows none of the signers, so she gets Giselle's PGP certificate, Henry,Irene,Giselle<<Giselle>>, from a certificate server. She knows Henry vaguely, so she obtains his certificate, Ellen,Henry<<Henry>>, and verifies Giselle's certificate. She notes that Henry's signature is at the "casual" trust level, so she decides to look elsewhere for confirmation. She obtains Ellen's certificate, Jack,Ellen<<Ellen>>, and immediately recognizes Jack as her husband. She has his certificate and uses it to validate Ellen's certificate. She notes that his signature is at the "positive" trust level, so she accepts Ellen's certificate as valid and uses it to validate Bob's. She notes that Ellen signed the certificate with "positive" trust also, so she concludes that the certificate, and the public key it contains, are trustworthy. |
In the example above, Alice followed two signature chains:
Henry<<Henry>> Henry<<Giselle>> Giselle<<Bob>>
and
Jack<<Ellen>> Ellen<<Bob>>
(where the unchecked signatures have been dropped). The trust levels affected how Alice checked the certificate.
A subtle distinction arises here between X.509 and PGP certificates. X.509 certificates include an element of trust, but the trust is not indicated in the certificate. PGP certificates indicate the level of trust, but the same level of trust may have different meanings to different signers.
Summary
The deployment and management of public keys is complex because of the different requirements of various protocols. Most protocols use some form of the X.509v3 certificates, although the extensions vary. The infrastructure that manages public keys and certification authorities is called a public key infrastructure. Several such infrastructures are in place, such as the PGP Certificate Servers and the commercial certificate issuers for World Wide Web browsers. |
Disclaimer
