Encryption is the process of reversibly hiding information. When you encrypt something, you take a piece of data (called the plaintext) and apply a process that produces another piece of data (called the ciphertext). There must also be a process for turning the ciphertext back into plaintext.

It’s not practical to think up a new algorithm every time you want to encrypt something. Useful encryption algorithms therefore use an extra piece of data called a key. In order to decrypt data, you need not only the decryption algorithm, but also the key; this means that you can use the same algorithm to encrypt different things and share them with different people. If an encryption algorithm doesn’t use a key, then as soon as you know the decryption algorithm, you can decrypt all the things encrypted with the algorithm.

Cryptographic wisdom considers an encryption process secure when the only way to recover a plaintext message from ciphertext is to know or discover the key. Furthermore, this rule should still be true even if every other detail about the encryption process is known. In fact, cryptographers become very concerned about the security of an algorithm when more than a key must be kept secret (for instance, when the algorithm or an important part of it is not disclosed).

There are some things that encryption cannot do. When you encrypt something, you conceal its content, which doesn’t necessarily conceal everything useful about it. Attackers may be able to gain important information by looking at the lengths of messages, or the times they’re sent, or the senders and receivers; none of that will be changed by encryption.

Furthermore, encrypting something does not protect it from being changed. Somebody who has access to the ciphertext can change it. They won’t be able to predict exactly what plaintext you’ll get, but it will almost certainly be different. This sort of tampering is normally easy for a human to detect in text but not so if the plaintext was binary data. Since computers are unable to comprehend text, they cannot detect tampering by inspection as humans can. In order to protect a message from modification, and in a way that a computer can detect, you must use integrity protection, which we will discuss. Although some integrity protection systems use encryption, encryption by itself does not provide integrity protection.

A checksum is a number calculated on a given set of data that is designed to detect changes or errors in communication of that data. This is useful for a communications channel; if a sender calculates a checksum as data is being sent and a receiver does the same as it is being received, the two can simply compare checksums to see if the data arrived intact or if an error occurred during transmission. Another use might be to store the checksum and then repeat the calculation at a later time. If the two checksums are different, then something changed in the data.

A checksum is usually just several bytes long and will take up much less space than the original data. While this makes them easier to store, it also means that there must be situations where a checksum will give the same answer for two different pieces of data. This is called a collision, and checksum algorithms are designed to make collisions unlikely to occur for the differences they are designed to detect. Checksum algorithms for communications are designed to detect random bursts of errors or chunks of missing data because they are the kinds of differences that you often get on a telephone line or a radio transmission (to humans listening, these errors sound like clicks or pops).

What if the error was not random and a deliberate change was intended? If so, is it possible to make a deliberate change and keep the checksum the same? For many checksums, this is certainly possible because the checksums are not designed to make this difficult. There are ways to design checksum algorithms so that it is impossibly difficult to make a deliberate change and still have the checksum match. Algorithms designed this way are called cryptographic hash functions, cryptographic checksums, or message digest functions.

Note that the terminology used for the different techniques and uses of cryptographic hashes is confusing and overlapping. As a result, terms are not used very consistently; about the best you can say is that any term involving integrity, digest, or the acronym MAC (Message Authentication Code) probably refers to some process that uses some kind of hash. If you care about the details, investigate them, rather than trusting that terms are used consistently from one document to another.

The term hash comes from another situation where it is useful to have a short fixed-length string that you can generate consistently from a larger string and that has large changes in the output as a result of small changes to the input. Hash algorithms and checksum algorithms are not always used for the same purposes, but if you extend either concept for cryptographic security, you reach the following set of conditions for a cryptographic hash:

There are two principal uses for cryptographic hashes. First, they are used to detect changes in data. If you have a cryptographic hash for a piece of data and the hash is kept secure, you can be sure that if you recalculate the hash and it is the same, then the data hasn’t been modified. This is the basis for digital signatures, which are discussed later in this appendix.

Cryptographic hashes are also frequently used in authentication systems. In most cases, passwords are not encrypted, but hashed. If you use encryption on a password, it is possible to decrypt it and get back the password, which an attacker could then use somewhere else. This makes storing and sending encrypted passwords dangerous. Instead, secure systems store a hash of the password and, when a user wants to authenticate to the system, compute a hash of the password provided by the user. If the hashes match, the user must know the correct password.

This technique does not help if a user can directly provide the hash, instead of the password (for instance, if the user is logging in over a network and what the system actually receives is the hash). If the hash is sent around, it simply becomes another fixed and reusable password. (This is discussed further in Chapter 21.) For this reason, good network authentication systems use a random piece of data that changes on every transaction, often called a nonce. Adding this changing value into the information that gets hashed and exchanged prevents eavesdroppers from reading and reusing the hashes.

It is possible to use a block cipher in a special way to calculate a cryptographic hash. When a cipher is used like this, the resulting checksum may be called a Message Authentication Code (MAC), a Message Integrity Code (MIC), or a Message Digest Check (MDC).

The use of block ciphers for calculating cryptographic hashes is often seen in older cryptographic protocols. In particular, they frequently use the Data Encryption Standard (DES) to produce 64-bit values. Most modern cryptographic protocols explicitly use cryptographic hash algorithms. One reason is that cryptographic hash algorithms tend to produce results that are 128 to 160 bits in size. This significantly reduces the chances of being able to come up with a different piece of data that produces the same hash value.

One of the most important uses of cryptographic hashes is to provide integrity protection. A cryptographic hash can be used to verify that no changes to data have been made, but this won’t work if you include the hash value with the data. All someone wishing to change the data would have to do is replace the hash value with a new value computed from the changed data. Some way is needed to protect the cryptographic hash from being changed to the desired new value.

One way is to encrypt the cryptographic hash using a public key algorithm; this is essentially a digital signature, as we discuss later. Because of the slowness of public key encryption, it is not always a usable solution. Alternatives have been developed that are based on the calculation of cryptographic hashes, which include a secret key as part of the calculation. Without that key, someone wishing to change the data cannot recalculate a new and valid checksum. Many recent Internet protocols use a method called HMAC^[1] for combining a key with a cryptographic hash. The HMAC technique can be used with any cryptographic hash function that produces at least 128 bits of output. HMAC is described in RFC 2104.

Many parts of cryptography depend on being able to generate random numbers, or at least numbers that can’t be predicted. For instance, if you need to send authentication information across the network in a form that’s not reusable, you will want an unpredictable changing value to add in with the information. If an attacker can figure out what that value is, the attacker may be able to use the value to authenticate or to figure out the authentication data for later use.

Computers are very bad at being random because they are designed to be able to repeatedly calculate the same answer if given the same data to work with. If you have an algorithm for giving you random numbers, you will get the same list of random numbers whenever you run it. This is why random number generators on computers are called pseudo-random. Knowing the algorithm and the starting information, and having a faster computer, would allow you to predict what the numbers were going to be. Truly random numbers cannot be predicted.

So where can a source of acceptable random numbers come from? It is easy if the computer has some hardware to generate random numbers; if not, then some random information can be obtained from peripheral devices attached to the computer. It has to be done very carefully because it is easy to overestimate how random some sources of information are. Sampling a fast running clock is not really a good way to get random numbers because typically only a small number of bits will change each time the clock is sampled.^[2]

Several free Unix operating systems, including Linux, have special code as part of the low-level device drivers, which continuously collects random input events from the keyboard and other hardware devices and allows applications to obtain a source of random data.

What 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^[3] 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.

Digital signature algorithms try to provide a much more consistent set of guarantees, with mixed success. Digital signature technology combines public key cryptography and cryptographic hashing; public key cryptography provides a way to prove your identity, and cryptographic hashing provides a way to guarantee that the information to which you attached your identity has not been modified.

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.

What 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.

A 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.

Before 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).

Manual 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.

In a perfect world, it would be possible to select the perfect encryption algorithm for clients and servers to use once, and no negotiation would be necessary. The real world doesn’t work this way. Sometimes it’s necessary for some clients or servers to use relatively weak encryption (either because they have computational limits and can’t do stronger encryption fast enough to keep up, or because legal or licensing restrictions control what kind of encryption they can do). In this situation, you don’t want to hold back all connections to the lowest common denominator, so you need to support negotiation.

Even when this kind of negotiation isn’t needed, most protocols support negotiation in order to allow future implementations to change the encryption algorithm that is used. New encryption algorithms are frequently discovered, and so are new problems with old encryption algorithms. You don’t want to be stuck using an encryption algorithm that somebody has figured out how to decrypt easily, or an algorithm that’s half the speed of the newest and best thing. Once again, you need to be able to negotiate.

Safe negotiation is difficult. It should be possible for each end of the connection to specify what algorithms are acceptable. If one end can convince the other to negotiate little or no security, a hostile client or server can force connections that will leak information. Even more importantly, it should not be possible for any third party to influence the negotiation. You do not want an attacker to be able to select the encryption that’s easiest to break!

A secure protocol uses a negotiation that:

In general, when people worry about authentication, they worry about client authentication; how does the server tell that it is offering services to the right client? In a secure protocol, it is also important for the client to be sure about what server it is talking to. The client is going to offer authentication data to the server. That authentication data is valuable to an attacker, and you don’t want to blindly hand it out to anybody that asks.

A secure protocol therefore provides for mutual authentication; the server authenticates itself to the client, and the client authenticates itself to the server. There are various ways of doing this, most of them based on the same trick where each side proves that it can decrypt a value with a secret that only the authentic participant could know. This secret could be a key used with a symmetric algorithm, or it could be the private half of a public key/private key pair; it makes a difference in configuring the servers and clients but doesn’t change the basis for the authentication. In either case, each side sends the other an unpredictable value and gets it back in a form that proves the other side could decrypt it.

As we’ve mentioned before, public key cryptography is slow. Very few network protocols can rely on public key cryptography to protect data simply because it takes too long. Protocols therefore need to have a shared secret that can be used for symmetric encryption. That secret can be something they both know already, but there are a number of reasons why it is convenient to use a temporary key (sometimes known as a session key) for most transactions, and to discard the key when the transaction is over:

For these reasons, secure protocols negotiate a key to be used for symmetric encryption for a single transaction. This key needs to be unpredictable, so some random numbers need to be involved in the process.

Encryption by itself will not keep people from altering data. A secure protocol needs to add something that will. In general, it will be some form of message integrity checksum, as discussed earlier in this appendix in the section about integrity protection.

Once you have decided to use a temporary shared secret, it is also important to destroy the secret when you are done with it. If there is a way to recreate the secret, then someone who recorded the session could, once they had the right information, decrypt it. If there is no way to recreate the secret, even with unlimited access to the computers on both sides of the communication, then you have achieved a cryptographic property called perfect forward secrecy.

Perfection is normally difficult or expensive to obtain, and perfect forward secrecy is no exception. In general, temporary keys are generated using information that is available to one or both sides of the transaction, and there are also usually situations where one side or the other is not sure whether or not the transaction has completed, and needs to keep the key around until the situation is clarified. For practical reasons, most systems implement partial perfect forward secrecy, where there is some period of time during which it is possible to recreate the shared secret. After this time period, things are reset, and the secret is destroyed.

These algorithms are designed to be used for encryption (reversibly obscuring information). As we’ve mentioned, it is often possible to use encryption algorithms for other purposes, and many of these algorithms are also used for digital signatures and/or for cryptographic hashing.

Digital signature algorithms were discussed earlier; they provide a way to combine public key encryption and cryptographic checksums so that a piece of information is attached to a specific identity:

Cryptographic hashes and message digests were discussed earlier; they are designed to take a long piece of data and generate a shorter value, in a way that makes it easy to detect changes to the long piece of data:

Key exchange algorithms are used to allow two parties to agree on a shared secret across an unsecured network. They are occasionally more correctly called key agreement algorithms:

Table 3.1 gives our recommendations for acceptable algorithm types and key lengths. This sort of information is volatile; weaknesses are continually being discovered in algorithms; new algorithms are being developed; and both the speed and memory capacity of computers is increasing all the time. However, these are what we were willing to use at the time this book was published. We don’t think it will ever be a good idea to use these algorithms with shorter keys than those shown.

Evaluating the strength of a cryptographic algorithm can be extremely difficult. It’s not unusual for people to find problems with algorithms that have been examined before by multiple professional cryptographers. However, this sort of analysis is needed only for new cryptographic algorithms. In general, a reasonably educated and suspicious person can do an adequate job of figuring out whether a cryptographic product is appropriately secure without delving into any of the details of the algorithms involved. A good resource is the “Snake Oil FAQ”, published regularly on the sci.crypt newsgroup.

In fact, in most cases, all you need is the suspicion. Cryptography is a difficult business: it’s hard to come up with good cryptographic algorithms; there are trade-offs between the speed of an algorithm, the memory requirements of an algorithm, and the strength of an algorithm; and no algorithm is perfectly unbreakable. Therefore, any product that advertises a magic new algorithm that runs really fast on small devices and can never be broken is at best over-optimistic and at worst fraudulent.

If you need to evaluate an algorithm, here are some questions you should ask:

If you can get good answers to these questions, the algorithms are probably acceptable for most purposes. If you are trying to conceal highly important secrets, you may want to hire a cryptographer to do the analysis for you.

Meanwhile, good luck with your firewall.