C.3. Combined CryptographyThe basic building blocks (encryption, cryptographic hashes, and random numbers) can be put together to create various larger systems that meet needs beyond simply hiding data. These include digital signatures and certificates.
C.3.1. Digital SignaturesWhat is a digital signature ? It is the digital equivalent of putting your signature on a document. When you sign a paper document, you are permanently attaching something that identifies you with a particular piece of information. The assumption is that only you can create your signature and your signature cannot be transferred to another document.
Normal signatures are relatively easy to work around. For instance, somebody can forge your signature, photocopy your signature, and stick it on another document, or change the document after you've signed it. Over the years, people have developed a number of systems to help prevent these kinds of attacks, with varying amounts of success. This includes ways of telling originals of documents from photocopies (ranging from the simple trick of signing in a pen that's not black to complicated ways of making documents that don't photocopy well), systems where you sign and date every page of a document to keep people from substituting pages, and ways of physically protecting multiple copies so that nobody can modify them all. None of these systems is foolproof.
Tampering is prevented by using a cryptographic hash function to generate a hash of the document or data. The hash is then combined with the private key using the digital signature algorithm to produce something that can be produced only by you and is bound to a particular piece of data.
When you sign something, you use your private key; when recipients get the signature, they use your public key to verify it. This means that recipients must have access to a reliable data source that includes your public key information. This is identical to the paper versions. Organizations that are serious about signatures (banks, for instance) keep a sample of your signature on record so that they can make comparisons. Anybody who can replace that sample can authenticate as you.
A private key is an important authenticator, like a physical credit card. If you lose control of your credit card, there is a possibility that somebody else will use it, and you will need to make that credit card invalid. If you destroy the credit card accidentally, you need to get a new card, but there's no particular need to make the old one invalid.
The only person who should have the key you use to make signatures is you -- there should not be any copies of the key. Somebody who has a copy of the key can pretend to be you. On the other hand, if you lose the ability to use your key, it does not prevent already signed documents from being verified, and nothing prevents you from generating and using a new key.
In order to be successful, a digital signature system not only has to provide an algorithm that lets you sign something, it also has to provide the infrastructure that lets people verify that signature. That infrastructure has to support a number of operations. You need to be able to generate a new key if you can't use the old one, and you need to be able to cancel a key if you lose control over it. The process of canceling a key is called revocation, and it is one of the hardest parts of successfully designing a digital signature system.
C.3.2. CertificatesWhat is a certificate ? A certificate is a digitally signed piece of binary data that contains a set of public keys, some attributes and values, and an expiration date. Some of the values are designed to be displayed to humans, and others are intended for use by programs. Humans are interested in things such as names, the organization you work for, or your telephone number. Programs may be interested in things like your public key, your employee number, or the identifier of your manager. Sometimes values like an electronic mail address are useful to both humans and programs.
A certificate has similarities to a driver's license or a passport. These physical documents are deliberately made to be difficult for ordinary people to duplicate or alter because they are often used when you need to prove your identity. The authorities or organizations that create these documents usually go to some length to make sure they are given to the right people. This is because the organization ends up being a common point of trust between you and whomever you show the documents to.
There is one crucial and very important distinction between a signed digital certificate and a physical document such as a driver's license or a passport. The digital signature on a certificate is designed so that it cannot be forged; it doesn't matter how good you are with computers or with guessing numbers; your chances of being able to fool someone with a made up or altered certificate are impossibly small. There are, of course, ways to trick people into issuing real documents containing bogus information, and just as in the real world, it is possible with digital certificates. If the cryptography is sound, then it is really a problem with people or the processes used to create digital certificates, not a flaw in the certificate itself.
So who digitally signs a certificate? As in the real world, it is useful for a common point of trust to digitally sign a certificate. This might be the organization you work for or some externally recognized authority, depending on who you want to communicate with. In order for a certificate to be useful, the receiver has to be able to verify that it's valid.
In order to perform this verification, the receiver has to establish a connection from some certificate that the receiver knows is OK to the certificate in question. There may be additional certificates that must be checked in order to go from the entity who the verifier trusts to the certificate being checked. The connection between the common point of trust and the certificate being checked is called the trust path, and the collection of all the certificates is called the certificate chain. If all of the certificates in the trust path are valid, then the certificate verifier will trust the certificate.
This kind of process goes on with physical documents as well, but it's much slower, and the responsibility is all on the certificate holder. For instance, if you want to write a check to the grocery store, you will be asked for identification. Most grocery stores won't accept out-of-state driver's licenses for identification; they can't verify the validity of the license. But if you want to get a local driver's license, the license bureau will accept your out-of-state driver's license, allowing you to build up a certificate chain that lets you successfully authenticate to the grocery store.
What can a certificate be used for? A certificate can be used to provide information about your identity to someone you have not previously arranged to share information with. Certificates are often used as a way to verify public keys, for example. But they will work only if there is a common point of trust between you; everybody involved has to trust a common certificate authority.
In order to potentially be able to use a digital certificate to communicate with anyone alive, you need to have a common standard and a global infrastructure that supports certificates. There are currently two certificate standards being proposed for use on the Internet. One is called Simple Public Key Infrastructure (SPKI), and the other is called Public-Key Infrastructure X.509 (PKIX).
These certificate formats have some things in common. One common value in the contents of a certificate is an expiration date. An expiration date means that a certificate has a lifetime, and beyond that point, you will no longer believe that the contents of the certificate are valid. If a key is to be used beyond that point, the certificate will have to be re-signed.
Another thing in common between the design of the two infrastructures is a way to handle the situation when a certificate becomes invalid. This is the same problem we discussed previously for digital signatures; there needs to be a way to make a certificate unusable. For instance, certificates that contain public keys need to be made unusable if you want to tell people to stop using a public key, either because the private key is no longer available (so that messages encrypted with the public key are no longer readable), or because somebody other than the original holder has access to the private key and it can no longer be trusted. A certificate authority might also want to get rid of a certificate for other reasons (the authority might discover that the certificate holder lied about some of the information in the certificate or that the certificate holder's check bounced).
In all of these situations, you no longer want the certificate to be thought of as valid, but if this occurs before the certificate expires, there must be a way to get rid of it, which is called revoking the certificate. You cannot just get rid of the copy of the certificate that is at the certificate authority because anyone with a local copy will still use the certificate, without knowing that there's something wrong with it. What usually happens is that the key is placed on a special list, and for PKIX, this list is called the Certificate Revocation List (CRL). When someone wants to use a certificate, he or she first checks to see if it is on the CRL. If it isn't, then the certificate can be used. A revoked certificate needs to remain on this list until the certificate expires.
The CRL creates a problem; if you give a certificate a short lifetime, you will need to keep regenerating certificates, but if the lifetime is too long, you may need to keep a large CRL. The parameters for these things will depend entirely on the use of certificates. If you were a university, then you might wish to issue certificates with a lifetime of a year if you didn't want to continually sign certificates. On the other hand, you might choose to expire certificates at the end of each session of classes if you thought that lots of people will lose their certificates or need them revoked. An additional problem with CRLs is that they must be available when performing authentication. This can be difficult if, for example, your network is not working, and you are trying to authenticate the instructions to fix it.
C.3.3. Certificate Trust ModelsA trust model defines the ways in which certificate authorities build up a chain of trust, so that two widely separated entities can find a common trusted authority. There are two basic certificate trust models. One is strictly hierarchical, and the other is a mesh.
The hierarchical model is like a chain of command and is frequently represented as a tree (this is a tree as in the data structure used in computer science). If you pick any two parts of the tree, it is always possible, by going upwards in the tree, to find a point where the two parts join. It is a very simple algorithm, and it always works. It is the model used by the PKIX standard.
To implement such a model globally you would need quite a large amount of infrastructure, not to mention dealing with the political wrangling for who wants to be at the top. For this reason, the PKIX standard allows a number of separate trees to be joined (which is called cross certification). This means that there can be a number of trees. However, the top of each tree is then made to be part of every other tree (making a full mesh between the tree tops!). This means that if the trees are joined, there will always be a certificate chain to reach anyone else, although it may be a very long chain.
The other model is a mesh and is sometimes called a web of trust. In this model, connections can be made voluntarily between any two certificate authorities. If any two parts of a web of trust are chosen, there may or may not be a way that they are connected. This model is used by PGP. In fact, PGP normally uses a model in which individuals are themselves the certificate authorities, choosing which other keys they will sign, and which keys they will trust based on who has signed them.
In theory, a web of trust is not as reliable as a hierarchical model. In reality, when certificates are used to identify individual human beings, it is not usually a problem. People rarely spontaneously wish to communicate with strangers. Most interactions are between a known group of people. If a web already exists between these people and a new person joins, there will be a way for the new person to communicate with the rest of the group.
C.3.4. Key Distribution and ExchangeBefore you can communicate any data using a symmetric key algorithm, you have to make sure that all participants have the same symmetric key. You can't just send out that key the same way you're going to send the encrypted data because then anybody who's watching that channel will have the key (and if you don't think anybody's watching the channel, you don't need to encrypt the data in the first place). If you're using a public key algorithm, you have a different problem; you need to be sure that you have the correct public key for the entity you want to encrypt things for. These kinds of problems are called key distribution problems.
There are three common ways for symmetric keys to be distributed. The first method is called manual keying, which simply means that there is no defined way for the key to be distributed and some human being has to get it in. The assumption is that the human will get the key via some reasonably secure method that can't be compromised by the same techniques that would compromise the encryption system itself (so, for instance, if the encryption system is for a network protocol, the key will be sent via fax, not over the network).
anual keying is regrettably common in systems that use long-lived keys and is bearable only in such systems; if you have to change keys frequently, having people involved is unusably slow and error prone. In addition, people frequently compromise manual keying systems (for instance, by sending keys in unencrypted electronic mail or by leaving the fax of the key lying around where attackers can find it).
Symmetric keys may also be distributed using public key cryptography ; this simply changes the problem to one of public key distribution, which we'll discuss later. In systems that do this, one party decides on a symmetric key and encrypts it using the other party's public key. As long as the public key information is trustworthy, only the desired other party can read the symmetric key.
Finally, symmetric keys may be distributed using a key exchange algorithm. Key exchange algorithms are a special class of public key algorithms that don't encrypt data but do allow two sides of a transaction to figure out the same unpredictable number. The basic principle behind current algorithms is that each side picks a random number, performs a calculation on it, and sends the other side the result. Each side then performs another calculation, still using its original random number, on the other side's initial result, and the two sides come out with the same answer, which is used as a secret key. In order for this to be secure, it must be difficult for an eavesdropper who has the two intermediate results to calculate the final result.
Because public keys are not secret, they are in some ways easier to distribute than symmetric keys; you can send them around without trying to hide them. On the other hand, you need some way to verify that a public key is the correct public key for the entity you want to communicate with. If an attacker can convince you that the attacker's public key belongs to a friend of yours, you will cheerfully encrypt all the data you want to send to your friend so that the attacker can read it (but your friend can't).
There are two common ways to verify a public key. First, you can use a certificate authority (certificates are described earlier). Second, you can use external means to verify the key. One way, which was made popular by PGP, is to verify a key's fingerprint. A fingerprint for a key is usually a hexadecimal representation of a cryptographic hash of the public key. External verification of public keys, like manual exchange of symmetric keys, is flexible but clunky. In practice, keys that require external verification are almost never verified. It is also important to verify a fingerprint independently from the source used to obtain the public key. For instance, if your software vendor prints the fingerprint of a public key on the CDs they send out, then a suitably able attacker could produce similar CDs using a fake public key and print the bogus fingerprint on the CD.
Copyright © 2002 O'Reilly & Associates. All rights reserved.