If a public/private key pair is associated with a given service, for example a web server, then the public key can be disseminated over the network, and the web server, the only machine possessing the private key, can be authenticated to anyone who connects to it. If if another machine could intercept all the messages, it could not impersonate the web server without a copy of the private key. Which raises the question of how the public key becomes known and trusted, since if the public key could be switched with another, the entire scheme would be defeated. An attacker could simply generate his own public/private key pair, then disseminate the public key under the false pretense of it belonging to the server being compromised. One solution is to manually set which keys authenticate which servers, but for applications to scale up to Internet proportions, manual configuration is clearly inadequate. To automate the process, certificates are used, which allow highly trusted keys to authenticate others.
A certificate is a cryptographically sealed data object that includes the server's identity and public key. The certificate is signed by computing its hash value and encrypting this with an issuer's private key. If even one bit is changed in the certificate, the hash value changes, and the signature becomes invalid. If the client already possesses the issuer's public key, and trusts the issuer to verify the identity of the server, then the client can be sure that the public key in the certificate is the public key of the server. Certificates are a form of key chaining, but are used for authentication keys, not encryption keys. An interloper would have know either the private key of the server or the private key of the issuer to successfully impersonate the server.
As it turns out, only a handful of issuers, termed certificate authorities (CAs), are needed. For example, VeriSign, the major U.S. issuer, issues certificates only after a background check insures both the identity of the subject, and their authority over a particular DNS name. VeriSign's public keys are hardwired into both Netscape's and Microsoft's web browsers, so a web server with a VeriSign-signed certificate can be authenticated by a browser with no additional information. If the server presents a certificate not signed by VeriSign (or another recognized authority), or if the DNS name of the server doesn't match the DNS name in the certificate, a warning message is displayed, and the user may decide how to proceed.
The most common type of certificate is an X.509 certificate, an ASN.1 encoded block of data specified in ISO Standard X.509. As an example of an X.509 certificate, here's a decode (generated with openssl) of one of www.freesoft.org's old certificates; the actual certificate is about 1KB in size. It was issued (signed) by Thawte (since acquired by Verisign), as stated in its Issuer field. It's subject (me) contains a lot of personal information, but the most important part is the common name (CN) of www.freesoft.org - this is the part that must match the host being authenticated. Next comes an RSA public key (modulus and public exponent), followed by the signature, computed by taking an MD5 hash of the rest of the certificate and encrypting it with Thawte's RSA private key.
Certificate:
Data:
Version: 1 (0x0)
Serial Number: 7829 (0x1e95)
Signature Algorithm: md5WithRSAEncryption
Issuer: C=ZA, ST=Western Cape, L=Cape Town, O=Thawte Consulting cc,
OU=Certification Services Division,
CN=Thawte Server CA/Email=server-certs@thawte.com
Validity
Not Before: Jul 9 16:04:02 1998 GMT
Not After : Jul 9 16:04:02 1999 GMT
Subject: C=US, ST=Maryland, L=Pasadena, O=Brent Baccala,
OU=FreeSoft, CN=www.freesoft.org/Email=baccala@freesoft.org
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public Key: (1024 bit)
Modulus (1024 bit):
00:b4:31:98:0a:c4:bc:62:c1:88:aa:dc:b0:c8:bb:
33:35:19:d5:0c:64:b9:3d:41:b2:96:fc:f3:31:e1:
66:36:d0:8e:56:12:44:ba:75:eb:e8:1c:9c:5b:66:
70:33:52:14:c9:ec:4f:91:51:70:39:de:53:85:17:
16:94:6e:ee:f4:d5:6f:d5:ca:b3:47:5e:1b:0c:7b:
c5:cc:2b:6b:c1:90:c3:16:31:0d:bf:7a:c7:47:77:
8f:a0:21:c7:4c:d0:16:65:00:c1:0f:d7:b8:80:e3:
d2:75:6b:c1:ea:9e:5c:5c:ea:7d:c1:a1:10:bc:b8:
e8:35:1c:9e:27:52:7e:41:8f
Exponent: 65537 (0x10001)
Signature Algorithm: md5WithRSAEncryption
93:5f:8f:5f:c5:af:bf:0a:ab:a5:6d:fb:24:5f:b6:59:5d:9d:
92:2e:4a:1b:8b:ac:7d:99:17:5d:cd:19:f6:ad:ef:63:2f:92:
ab:2f:4b:cf:0a:13:90:ee:2c:0e:43:03:be:f6:ea:8e:9c:67:
d0:a2:40:03:f7:ef:6a:15:09:79:a9:46:ed:b7:16:1b:41:72:
0d:19:aa:ad:dd:9a:df:ab:97:50:65:f5:5e:85:a6:ef:19:d1:
5a:de:9d:ea:63:cd:cb:cc:6d:5d:01:85:b5:6d:c8:f3:d9:f7:
8f:0e:fc:ba:1f:34:e9:96:6e:6c:cf:f2:ef:9b:bf:de:b5:22:
68:9f
To validate this certificate, we need another certificate, one that matches the Issuer (Thawte Server CA) in the first certificate. Then we take the RSA public key from the second (CA) certificate, use it to decode the signature on the first certificate to obtain an MD5 hash, which must match an actual MD5 hash computed over the rest of the certificate. Here's the CA cert:
Certificate:
Data:
Version: 3 (0x2)
Serial Number: 1 (0x1)
Signature Algorithm: md5WithRSAEncryption
Issuer: C=ZA, ST=Western Cape, L=Cape Town, O=Thawte Consulting cc,
OU=Certification Services Division,
CN=Thawte Server CA/Email=server-certs@thawte.com
Validity
Not Before: Aug 1 00:00:00 1996 GMT
Not After : Dec 31 23:59:59 2020 GMT
Subject: C=ZA, ST=Western Cape, L=Cape Town, O=Thawte Consulting cc,
OU=Certification Services Division,
CN=Thawte Server CA/Email=server-certs@thawte.com
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public Key: (1024 bit)
Modulus (1024 bit):
00:d3:a4:50:6e:c8:ff:56:6b:e6:cf:5d:b6:ea:0c:
68:75:47:a2:aa:c2:da:84:25:fc:a8:f4:47:51:da:
85:b5:20:74:94:86:1e:0f:75:c9:e9:08:61:f5:06:
6d:30:6e:15:19:02:e9:52:c0:62:db:4d:99:9e:e2:
6a:0c:44:38:cd:fe:be:e3:64:09:70:c5:fe:b1:6b:
29:b6:2f:49:c8:3b:d4:27:04:25:10:97:2f:e7:90:
6d:c0:28:42:99:d7:4c:43:de:c3:f5:21:6d:54:9f:
5d:c3:58:e1:c0:e4:d9:5b:b0:b8:dc:b4:7b:df:36:
3a:c2:b5:66:22:12:d6:87:0d
Exponent: 65537 (0x10001)
X509v3 extensions:
X509v3 Basic Constraints: critical
CA:TRUE
Signature Algorithm: md5WithRSAEncryption
07:fa:4c:69:5c:fb:95:cc:46:ee:85:83:4d:21:30:8e:ca:d9:
a8:6f:49:1a:e6:da:51:e3:60:70:6c:84:61:11:a1:1a:c8:48:
3e:59:43:7d:4f:95:3d:a1:8b:b7:0b:62:98:7a:75:8a:dd:88:
4e:4e:9e:40:db:a8:cc:32:74:b9:6f:0d:c6:e3:b3:44:0b:d9:
8a:6f:9a:29:9b:99:18:28:3b:d1:e3:40:28:9a:5a:3c:d5:b5:
e7:20:1b:8b:ca:a4:ab:8d:e9:51:d9:e2:4c:2c:59:a9:da:b9:
b2:75:1b:f6:42:f2:ef:c7:f2:18:f9:89:bc:a3:ff:8a:23:2e:
70:47
This is an example of a self-signed certificate; note that the issuer and subject are the same. There's no way to verify this certificate except by checking it against itself; we've reached the top of the certificate chain. So how does this certificate become trusted? Simple - it's manually configured. Thawte is one of roughly a dozen certificate authorities recognized by both Microsoft and Netscape. This certificate came with your web browser (you can find it listed in the security settings); it's trusted by default. As a long-lived (note the expiration date), globally trusted certificate that can sign pretty much anything (note the lack of any constraints), it's matching private key has to be one of the most closely guarded in the world.
What would happen if the private key matching the Freesoft certificate was stolen? The certificate would have to be revoked. Certificate Authorities maintain Certificate Revocation Lists (CRLs) indicating which certificates have been revoked before their natural lifespan would expire.
PGP defines (in RFC 2440) its own certificate format. PGP certificates are used primarily to implement the PGP Web of Trust, a certification system far more decentralized than X.509. The Web of Trust defines trust relationships based on personal certification by known and trusted individuals. To participate in the Web of Trust, you need to find someone already trusted to certify you.
Other than it's far more decentralized nature, the PGP Web of Trust is actual quite similar to the X.509 system. Though neither the PGP nor the X.509 certificate design is completely satisfactory, in fact most PGP certificates could be converted into parallel X.509 certificates, and the entire Web of Trust reproduced using X.509 syntax. Likewise, X.509 certificates could implement a Web of Trust. Using off-the-shelf tools like openssl, I could create a Freesoft Certificate Authority, have it authenticated by other, well-known websites, and in turn authenticate other sites.
Yet the X.509 system has been adopted by corporate America, and it shows. The average X.509 certificate expires in a year or two and costs at least $100. Renewals typically cost almost as much as the original. That's just for a server certificate, that can't be used to sign other certificates. Chaining certificates, that can sign other certificates, cost thousands of dollars, though there are some real technical issues here that need to be resolved before chaining certificates can be more widely used.
A solution may be on the horizon in the form of secure DNS. A DNS resource record type (CERT) has been defined (RFC 2538) to carry X.509 or PGP certificates. Progress is being made (see RFC 3130) towards cryptographically securing DNS, so within a few years we may see signed DNS domains that can carry CERT records. In my opinion, this would make a lot more sense than the present scheme... if corporate America moves to adopt it.
\end{soapbox}