Computer Security Basics, 2nd Edition (2011)
Part III. Communications Security
Chatper 7: Encryption
Chatper 8: Communications and Network Security
Chapter 7. Encryption
The study of encryption is called cryptography, from the Greek kryptos meaning “hidden,” and graphia, meaning “writing.” The process of trying to decrypt encrypted information without the key (to “break” an encrypted message) is called cryptanalysis. The study of code creation and breaking together is sometimes referred to as cryptology. To write something in a cipher so that only those authorized to do so can decode and read it is called encryption.
Encryption is an ancient form of information protection that dates back 4,000 years. Encryption has taken on new significance in the modern computer age. It’s a particularly effective way to protect sensitive information—for example, passwords —that’s stored in a computer system, as well as information that’s being transmitted over radio or microwave channels and communications lines.
By changing or substituting or scrambling the order of letters and words, encryption has through the ages protected communications while they were being transmitted through a hostile environment—usually one involving war or diplomacy. Of course, once the message is received, it must be unencrypted to be meaningful. Thus begins the fascinating story of cryptography, literally “secret writing,” much of which forms the basis for computer and network security today.
Hundreds or even thousands of years ago, messages worthy of encryption might have included letters from a battlefield general to the home front. Encryption protected the communication in case the soldier carrying the letter was captured. In modern times, this might mean encrypting an electronic mail message containing sensitive information (of military, corporate, or personal importance) transmitted across a network. Encryption protects the information in case an intruder taps into the network.
Information that’s encrypted remains secure even when it’s transmitted over a network that doesn’t provide strong security—in fact, even if the information is publicly available. In most versions of the Unix operating system, for example, the file containing user passwords stores those passwords in encrypted form. Encryption protects these passwords effectively, to the point that if somebody does access the file, encryption would make it very difficult for an attacker who obtained the file to be able to decipher the passwords.
Because encryption has historically been an expensive method of computer security (expensive in terms of product cost as well as computer time needed to encrypt), it has most often been used to protect only classified or particularly sensitive information—for example, military information, intelligence information, information about funds transfers, and information about the passwords in a computer system. Encryption is now becoming a more popular and inexpensive method of protecting both communications and sensitive stored data. For example, numerous web browser providers offer an encryption service to users. Inexpensive or free encryption software that can help ensure message security is available for PCs and wireless devices. As awareness of encryption benefits grows, as more laws mandate penalties for failing to protect information, and as encryption technology becomes more accessible and affordable, encryption is likely to be used as a matter of course to protect data—whether it’s classified information being transmitted over a network, or ordinary user data stored on an office computer system.
This chapter describes basic encryption techniques and how they’re used to protect data. Chapter 8 discusses communications security (of which encryption is an important part) and networking concepts, and elaborates on how encryption fits into overall communications security.
Cryptography is a complex topic. This chapter provides an introduction to basic encryption techniques, but it doesn’t try to describe the mathematical basis of encryption algorithms or explore all the complexities of the topic. For detailed information, an excellent reference is Network Security: Private Communication in a Public World, by Charlie Kaufman, Radia Perlman, and Mike Speciner (Prentice Hall).
The earliest encryption systems, sometimes called codes or ciphers, date back to early Egyptian days—around 2000 B.C., when funeral messages consisting of modified or encrypted hieroglyphs were carved into stone—and were designed not to keep the messages a secret, but to increase their mystery. (This leads to the question: considering that hieroglyphs often contain of pictures of animals—could a dyslexic stone cutter have gotten into trouble for flipping the bird?)
The history of cryptography extends through the centuries from ancient Egypt to India, Mesopotamia, Babylon, Greece, and on into Western civilization and eventually to the dawn of the computer age.
From the Spartans to Julius Caesar, from the Old Testament ciphers to the Papal plotters of the fourteenth century, from Mary, Queen of Scots to Abraham Lincoln’s Civil War ciphers, cryptography has been a part of war, diplomacy, and politics. Mary, Queen of Scots, for example, lost her life in the sixteenth century because an encrypted message she sent from prison was intercepted and deciphered. During the Revolutionary War, Benedict Arnold used a codebook cipher to communicate with the British. Throughout history, governments and individuals have protected secret communications by encoding them. The development of ciphers and ciphering devices over the centuries has culminated in the complex computer-based codes, algorithms, and machines of modern times.
The protection of communications has always been particularly critical in times of war and political strife. The development of modern cryptography owes much to the research conducted under the pressures of World War II, and particularly to the breaking of codes produced by a machine known as the Enigma machine.
The Enigma machine was originally developed in Germany by an electrical engineer, Arthur Scherbius, during World War I. He offered an early version of the machine to the German navy and foreign office as early as 1918. The machine was originally rejected, but after some additional security enhancements were made to the commercial model, the German navy began using Enigma machines early in 1926.
The Enigma machine (shown in Figure 7-1) worked as follows: an operator typed the original text of the first letter of the message to be encrypted on the machine’s keyboard-like set of buttons. The battery-powered machine encrypted the letter and, using a flashlight-type bulb, illuminated a substitute letter on a glass screen. What was special about the Enigma machine was a set of wheels known as rotors. Made of rubber or some other nonconducting material, the rotors contained electrical contacts, which were wired in such a way that turning the rotors would change the correspondence between letters. Before the encryption began, the operator would set these rotors to an initial position. When the operator typed the first character—“A”, for example, the machine might illuminate a light corresponding to “P”. The operator would then copy the letter “P” onto an encryption worksheet, the machine would advance the rotors, and the operator would enter the next letter. With the new rotor settings, the correspondence between letters would change. An “A” might now be translated to an “X”. This process would continue until the entire message was encrypted. The encrypted message could now be transmitted by radio to its destination, usually a U-boat in the Atlantic.
Figure 7-1. The Enigma machine (reproduced by permission of the Smithsonian Institution)
At the other end of the communication, the operator trying to decrypt a message coded by the Enigma machine would need another, identically built Enigma machine and would also need to know the original settings of the rotors.
The first breakthrough in solving the Enigma codes came from Poland. In the late 1920s, the Poles formed a code cracking team that applied the science of cryptanalysis to work on breaking the German codes. Marian Rejewski and two other mathematicians cracked some of the early Enigma messages.
In the early 1930s in France, a German named Hans-Thilo Schmidt offered French intelligence some information about setting the Enigma keys. The French cryptanalysts didn’t have the resources to take advantage of this information and the British also rejected the information as being insufficient. The French offered the information to Poland, where Rejewski used it to make additional brilliant advances in cracking the Enigma codes.
After the fall of Poland in 1939, the Poles passed their information on to the French and the British. As the Germans continued to change keys and to modify the design of the Enigma machine, the British built on the Polish solution. Under the direction of mathematician Alan Turing, and with the help of Enigma documents captured from U-boats sunk during the remainder of the war, the highly secret “Ultra” project began to decrypt German naval messages on a regular and timely basis. In the early 1940s, Americans—some of them from IBM—made their own contributions, based on knowledge they’d gained reconstructing Japanese diplomatic cipher machines through the “Purple” project.
In the decades since World War II, the use of computers to break codes has transformed the codebreaking game and has contributed greatly to the use of cryptography in military and intelligence applications, as well as in systems used in everyday computer systems.
What Is Encryption?
Encryption (sometimes called enciphering) transforms original information, called plaintext or cleartext, into transformed information, called ciphertext, codetext, or simply cipher, which usually has the appearance of random, unintelligible data. The transformed information, in its encrypted form, is called the cryptogram.
When encryption is used to send messages, it is reversible. After transmission, when the information has reached its destination, the inverse operation (decryption, sometimes called deciphering) transforms the ciphertext back to the original plaintext. (There are cases in which encryption is one way only. These will be explained later.)
The technique or rules selected for encryption—known as the encryption algorithm —determines how simple or how complex the process of transformation will be. Most encryption techniques use rather simple mathematical formulas that are applied a number of times in different combinations. Most also use a secret value called a key to encrypt and decrypt the text. The key is a kind of password, usually known only to the sender and the recipient of encrypted information. The encryption algorithm mathematically applies the key, which is usually a long string of numbers, to the information being encrypted or decrypted.
Unlike a regular password, a key doesn’t directly give you access to information. Instead, it’s used by the algorithm to transform information in a particular way. With the key, information that’s been locked (encrypted) by the key can readily be transformed; without the key, that information is inaccessible. The examples shown later in this chapter will help make encryption keys more understandable.
The type of encryption algorithm, the secrecy of the key, and a number of other characteristics together form what’s called the strength of the encryption; cryptographic strength determines how hard it is to break an encrypted message.
An important consideration in assessing the strength of any encryption algorithm is not whether it can be broken (given sufficient pairs of plaintext and ciphertext, any secret message—except one encoded with a so-called "one-time pad,” described later in this chapter—can theoretically be decrypted) but how likely it is that decryption can be performed in a reasonable amount of time. A message that can be broken, but only with a network of supercomputers grinding away for decades, is very safe indeed.
Early cryptographic systems depended on the secrecy of the encryption algorithm to provide security. Gradually, cryptography has come to depend upon the secrecy, and usually the length, of the key to keep messages secret. The most reliable cryptographic algorithms, in fact, are now expected to pass through several rounds of public scrutiny before most organizations will trust them. The most secret codes, of course, have secure algorithms as well as secret keys. There is no point in giving the opponent a head start. It is tremendously difficult to create reliable algorithms and to be able to test them thoroughly, however. Only a few nations have such a capability.
Remember that a poorly chosen, or improperly protected, encryption key opens the door to an intruder, just as a shared or stolen password does. If an intruder gets access to an encryption key, even the strongest encryption algorithm won’t protect your data. Also, public key encryption, to be discussed later, depends on the mathematical difficulty of deriving a private key when presented with a public one. Certain efforts to increase the strength of encryption keys have led to research in a number of areas. Most current codes deal with the relationship between prime factors of very large numbers. Others depend on a relationship established by elliptic curves crossing an axis. One field, called quantum encryption, uses the curious relationship of spinning photons of light to increase security and make it easier to detect if a message has been read.
Figure 7-2 shows simple encryption and decryption.
Figure 7-2. Simple encryption and decryption
Encryption provides security in three of the four security categories introduced in Chapter 1. (Encryption is not a particularly effective way to achieve the fourth category, availability.)
Secrecy or confidentiality
Encryption is very good at keeping information a secret. Even if someone is able to steal your computer or to access an encrypted file, that person will find it extremely difficult to figure out what’s in the file.
Accuracy or integrity
Encryption is also very good at ensuring the accuracy or the integrity of information. In addition to keeping information secret, certain types of encryption algorithms protect against forgery or tampering. This type of processing detects even the slightest change—malicious or inadvertent—in the information. While military, intelligence, and many corporate users care a lot about secrecy, financial institutions are more concerned about accuracy: making sure that a decimal point or a zero hasn’t slipped, or that an electronic embezzler hasn’t rounded off a few transactions here and there. Integrity checking is also a way that network users can ensure that their communications have not been affected by viruses or other penetrations.
Encryption is also very good at making sure that your information is authentic, that is, that is comes from who it says it does. Certain encryption techniques let you confirm absolutely who sent a particular piece of information. This is extremely important to financial or legal transactions. An important authentication technique is a digital signature. A digital signature is unique for every transaction and is very difficult to forge. Digital signatures are described later in this chapter.
Transposition and Substitution Ciphers
There are two basic types of encryption ciphers:
Rearrange the order of the bits, characters, or blocks of characters that are being encrypted or decrypted. They are sometimes called permutation ciphers.
Replace the actual bits, characters, or blocks of characters with substitutes (for example, one letter replaces another letter).
With a very simple transposition cipher (shown in Figure 7-3), the letters of the original text (the plaintext) are scrambled. With this type of cipher, the original letters of the plaintext are preserved; only their positions change.
Figure 7-3. A simple transposition cipher
With a very simple substitution cipher (two variations are shown in Figure 7-4), the letters of the plaintext are replaced with other letters, numbers, or symbols. With this type of cipher, the original positions of the letters of the plaintext are preserved, but the letters themselves change.
Figure 7-4. Simple substitution ciphers
More about transposition
In the fifth century B.C., the Spartans used a particularly interesting type of transposition cipher. During the Peloponnesian War, Spartan rulers encoded official messages by writing them on a long strip of parchment wound in a spiral around a wooden staff called a skytale. A message written in this fashion could be deciphered only by an official Spartan reader who had been given a baton of identical diameter. Thucydides, Plutarch, and Xenophon all have written about the use of this early cryptographic device.
Figure 7-5 shows another example of a transposition cipher.
Figure 7-5. Another transposition cipher
More about substitution
Although earlier substitution ciphers existed, Julius Caesar’s military use of such a cipher was the first clearly documented case. Caesar’s cipher, shown in Figure 7-6, was a simple form of encryption in which each letter of an original message is replaced with the letter three places beyond it in the alphabet.
Figure 7-6. The Caesar substitution cipher
The cipher used in Edgar Allan Poe’s short story, “The Gold Bug,” is a good example of a substitution cipher. Another example from literature is the cipher used in Sir Arthur Conan Doyle’s Sherlock Holmes tale, “The Adventure of the Dancing Men.”
Usually, cipher alphabets are much more complex than these examples. Sometimes an alphabet will have multiple substitutes for a letter, sometimes the alphabet will include substitutes that mean nothing, and sometimes several alphabets are used in rotation or combination. This is called a polyalphabetic cipher.
The Enigma machine described earlier in this chapter used substitution to encrypt communications.
Cryptographic Keys: Private and Public
More complex ciphers do not use simple substitutions or transpositions. Instead, they use a secret key to control a long sequence of complicated substitutions and transpositions. The key and the algorithm work together to change the original information into an encrypted version of itself. In most cases, the operation of the encryption algorithm is fixed and well known. It is the key that produces the unique encrypted version of the information.
Modern cryptographic systems fall into two general categories (identified by the types of keys they use): private key and public key systems.
Private key cryptography
Private key (sometimes called symmetric key, secret key, or single key) systems use a single key. That key is used both to encrypt and to decrypt information. (See Figure 7-7.) A separate key is needed for each pair of users who exchange messages, and both sides of the encryption transaction must keep the key secret. The security of the encryption method is completely dependent on how well the key is protected. The Data Encryption Standard (DES) algorithm, described later in this chapter, is a private key algorithm.
Figure 7-7. Private key encryption/decryption
Public key cryptography
Public key (sometimes called asymmetric key or two key) systems use two keys: a public key and a private key. Within a group of users—for example, within a computer network—each user has both a public key and a private key. A user must keep his private key a secret, but the public key is publicly known; public keys may even be listed in directories of electronic mail addresses.
Public and private keys are mathematically related. If you encrypt a message with your private key, the recipient of the message can decrypt it with your public key. Similarly, anyone can send anyone else an encrypted message, simply by encrypting the message with the recipient’s public key; the sender doesn’t need to know the recipient’s private key. When you receive a message encrypted with your public key, you, and only you, can decrypt it with your private key. The RSA cryptographic algorithm, described later in this chapter, is an example of a public key algorithm.
In addition to providing an encryption facility, some public key systems provide an authentication feature which ensures that when the recipient decrypts your message he knows it comes from you and no one else.
In Figure 7-8, a banker named Joe uses his private key (known only to him) to encrypt a message. When the message is sent to the bank clearinghouse, the clearinghouse officer applies Joe’s public key (known to everyone within the bank). Because decryption produces an intelligible message, the officer knows that only Joe could have created the message, and proceeds to follow Joe’s instructions.
Figure 7-8. Public key encryption/decryption
This example shows one of the disadvantages of public key encryption. Using a private key to encrypt a message and a public key to decrypt it proves that the message originated with who it is claimed, but anyone who can access the public key can decrypt the message. This provides authenticity without confidentiality. On the other hand, encrypting a message with a public key and decrypting it with a private key means that the message is secure (only the private key can decrypt it), but because anyone could have obtained the public key, it does nothing to demonstrate authenticity.
The solution lies in combining a little bit from each, as shown in Figure 7-9. The sender can encrypt the message using his own private key, and then encrypt the result using the intended receiver’s public key. Since only the receiver’s private key can be used to decrypt the final result, secrecy is maintained. The receiver uses her private key to decode the doubly encrypted message and thereby obtains the message originally encrypted by the sender’s private key. She then uses the sender’s public key to decode that message, thereby obtaining the original message. She is confident in the authenticity of the message because if the message can be decrypted with a given public key, the message was encoded by the corresponding private key. It is assumed, of course, that the sender still has control of the private key or the computer or equipment that contains it, and that the sender was operating the equipment intentionally, and not under duress.
Figure 7-9. Public and private key encryption used together
Encoding and decoding the entire message two times is unnecessarily burdensome. And as long as the security is being provided by the sender using the recipient’s public key, only a small portion of the message need be encoded using the sender’s private key to show authenticity. In fact, using a snippet in this way is the principal behind digital signatures.
Key Management and Distribution
A major problem with encryption as a security method is that the distribution, storage, and eventual disposal of keys introduces an expensive and onerous administrative burden. This is called the key distribution problem. Historically, cryptographic keys were delivered by escorted couriers carrying keys or key books in secure boxes. In some cases, this is still the way it’s done. With most modern high-security cryptographic products, government agencies do the actual key distribution, delivering the keys on magnetic media or semiconductor media to individual sites.
Another approach is to distribute a master key, which is then used to generate additional session keys. A site must follow strictly enforced procedures for protecting and monitoring the use of the key, and there must be a way to change keys at every site that will be receiving the encrypted messages, preferably at the same time. Even with all these restrictions, there’s always a chance that the key will be stolen or compromised. Keys are kept in secure areas in safes. Instructions given to couriers for modern mobile encryption units usually require that the security modules of these devices never leave the sight of cleared individuals. This includes trips to the restroom. Fortunately, the secure modules are usually pocket-sized, and can be detached from the actual encryption units.
Of course, if a key is lost, there’s another problem. Because deciphering encrypted information depends on the availability of the key, the encrypted information will be lost forever if you can’t locate the key.
The difficulty of key distribution, storage, and disposal has limited the wide-scale usability of many cryptographic products in the past. Automated key variable distribution is problematic because it’s difficult to keep the keys secure while they’re being distributed, but this approach is finally becoming more widely used. The Department of Defense-sponsored Secure Telephone Unit (STU-III) project is an example of a system that uses automated key distribution.
Standards for key management have been developed by the government and by such organizations as ISO, ANSI, and the American Banking Association (ABA).
One approach for encryption, called a one-time pad (see Figure 7-10) or a one-time cipher key, can be proven mathematically to be foolproof. As its name indicates, the pad is used only once, and the key must then be discarded or destroyed.
Figure 7-10. A one-time pad
With a one-time cipher, you create two copies of a pad containing a set of completely random numbers. (These are numbers produced by a secure random number generator, possibly one based on some physical source of randomness. Sometimes, one-time pads are based on the process of nuclear radioactive decay.) The set contains at least as many numbers as the number of characters in your message. The sender of the message gets one copy of the pad; the recipient gets the other. On a computer system, one way to encrypt or decrypt a one-time message is to use a mathematical function called an exclusive OR, or XOR. When the sender XORs the message with the first copy of the pad, the process creates the encrypted message. When the recipient XORs the encrypted message with the second copy of the pad, the process recreates the original message. This method of encryption is also known as the Vernam Cipher, named for its inventor, Gibert Vernam, who developed the cipher in 1918 for use with telegraphy.
One-time pads are sometimes used to encrypt important diplomatic communications, but they’re not practical for most communications because of the difficulty of key distribution. (For each possible pair of users who might wish to communicate, a key has to be generated and distributed to those users; the key must be longer than all the messages they might wish to exchange.) One-time pads must never be reused. Most of the successful cryptographic attacks against these systems have involved operators attempting to reuse old pads.
Modern military communications equipment is often equipped with a long list of keys, up to several hundred. This may allow secure communications for up to a period of years. The keys reside with the unit and are never transmitted, but indexing messages communicate to the receiving system which of the keys it should start with, and how the keys increment thereafter. These units also come with instructions to operators instructing them to never leave the unit out of the care of the cleared person. An “overrun” command allows emergency erasure of the keys in the event the unit appears about to fall into untrusted or enemy hands.
End-to-End and Link Encryption
There are two basic communications levels at which encryption can be performed. With end-to-end encryption (sometimes called off-line encryption), a message is encrypted when it is transmitted and is decrypted when it is received. The network may not even need to be aware that the message is encrypted. This type of encryption may sometimes be selected as an option by the user. The message remains encrypted through the entire communications process, from start to finish. This has the advantage of not depending on secure waypoints at every stage in the message path. This is the principle used by tunnel-style message encryption systems such as SSL, or TLS as it is known today.
With link encryption (sometimes called online encryption), a message is encrypted when it is transmitted, but is decrypted and then encrypted again each time it passes through a network communications node. The message may therefore be encrypted, decrypted, and reencrypted a number of times during the communications process, and the message is exposed within each node. With link encryption, the encryption is performed just before the message is physically transmitted. Encryption is typically invisible to the user; it is simply part of the transmission process.
There are advantages and disadvantages to each method of encryption. Advantages of end-to-end encryption are as follows:
§ It is more flexible; the user may be able to encrypt only certain information, and each user can have a distinct key.
§ It makes key management and distribution easier.
§ It protects data from start to finish through the entire network.
§ It is more efficient; the network doesn’t need to have any special encryption facilities.
Disadvantages of end-to-end encryption are as follows:
§ It may need to process some information (e.g., headers and routing information) in unencrypted form.
§ Each system needs to be able to perform the same kind of encryption.
§ It only secures the contents of a message, but does nothing to hide the fact that a message transmission has taken place.
Advantages of link encryption are as follows:
§ It is easier; the user doesn’t need to take any action.
§ It is more convenient in a network that provides many nodes.
§ It doesn’t compromise the entire network if a single key is compromised. Each pair of network nodes can use a distinct key.
§ It encrypts all information, including headers and routing information.
Disadvantages of link encryption are as follows:
§ Key distribution and management are more difficult because all nodes in the network must receive a key.
§ There are more points of vulnerability because the message is reduced to its original form several times along its path.
The Data Encryption Standard
During the 1960s, with the burgeoning of computer technology and concerns about the secrecy and privacy of communications, interest in a national encryption standard began to build. The idea of this standard was that it could be used by the many different types of government computer systems and networks, as well as in the systems used by government contractors, and potentially in commercial systems as well. The drive toward a national cryptographic standard culminated in the development of the Data Encryption Standard (DES).
Since 1965, when the Brooks Act was passed, the National Bureau of Standards (NBS, now known as NIST) had held the authority to research and develop standards for the protection of computer systems. The NBS study of government computing security needs, spanning the years 1968-1971, touched upon the need for an encryption standard. Development of the standard was clearly in NBS’s bailiwick, and, with the cooperation of NSA, NBS initiated a cryptography program. The goal from the beginning was to develop a single public standard for protecting unclassified government or sensitive private-sector information—a standard that would be viable for approximately 10-15 years (a goal the DES far exceeded) and that would be able to be used on different types of systems (interoperability).
NSA already had its own encryption algorithms used for the protection of classified military and intelligence information. NSA lent a lot of technical support to NBS, including the evaluation of proposed encryption standards. However, for national defense reasons, NSA never intended either to share its own secret algorithms with the public or to use the public standard to encrypt classified communications.
In the Federal Register of May 1973, NBS invited vendors to submit data encryption techniques that might be used as the basis of a high-quality public cryptographic standard. Only a few responses were received, and these were unacceptable to the NSA evaluators. In August of 1974, NBS tried again. This time, with the prodding of NSA, IBM submitted an algorithm, which proved acceptable to NSA.
At IBM, work had been proceeding for some time on the development of several encryption algorithms. One was a 64-bit algorithm used to protect financial transactions. Another was a 128-bit algorithm known as Lucifer. IBM was particularly interested in the protection of automated funds transfers, especially those involving communication between online terminals.
There have been charges that NSA deliberately weakened the Lucifer algorithm before accepting it as the basis for a national cryptographic standard—some say to allow the agency to crack encrypted communications. These charges were fueled by the fact that NSA urged IBM to submit its algorithm, and by the modifications made in the Lucifer algorithm (the shortening of the key from 128 bits to 56 bits and changes in the algorithm’s substitution functions, or S-boxes). A U.S. Senate panel has investigated these charges and upheld the integrity of DES.
NBS solicited comments about the DES in the Federal Register of March and August, 1975, and in a letter sent to Federal Information Processing Standards (FIPS) contacts in federal agencies. In an effort to be responsive to comments and to the controversy brewing around NSA’s involvement in the algorithm, NBS sponsored two workshops. One examined the feasibility—both technical and financial—of cracking the DES through computational brute force. The other examined the mathematical basis of the DES. In addition, NBS discussed with the Department of Justice issues regarding competition.
The approval of the DES by the Department of Commerce in 1976, and its publication in 1977 as the Data Encryption Standard (FIPS PUB 46, updated and revised as FIPS PUB 46-1 in 1988) as the official method for protecting unclassified data in the computers of U.S. government agencies was a landmark in the history of cryptography. The approval included a provision that NBS review the algorithm every five years to determine whether it should be reaffirmed as a public standard. The DES was subsequently adopted as an ANSI standard.
The following FIPS PUBs and ANSI X3 (Information Processing) Committee publications contain standards for the DES and its use:
FIPS PUB 46-1
Data Encryption Standard
FIPS PUB 74
Guidelines for Implementing and Using the NBS Data Encryption Standard
FIPS PUB 81
DES Modes of Operation
FIPS PUB 113
Computer Data Authentication
Data Encryption Algorithm (DEA)
Data Link Encryption
DEA Modes of Operation
ANSI’s X9 (Financial Services) Committee has also published standards related to the use of DES in the banking community.
What Is the DES?
FIPS PUB 46 describes the DES as follows:
The Data Encryption Standard (DES) specifies an algorithm to be implemented in electronic hardware devices and used for the cryptographic protection of computer data ... Encrypting data converts it to an unintelligible form called cipher. Decrypting cipher converts the data back to its original form. The algorithm... specifies both enciphering and deciphering operations which are based on a binary number called a key ... Data can be recovered from cipher only by using exactly the same key used to encipher it.
FIPS PUB 46 recommends that certain kinds of data be protected by the DES:
Data that is considered sensitive by the responsible authority, data that has a high value, or data that represents a high value should be cryptographically protected if it is vulnerable to unauthorized disclosure or undetected modification during transmission or while in storage. A risk analysis should be performed under the direction of a responsible authority to determine potential threats.
Federal Standard 1027, Telecommunications for Use in the DES, in the Physical Layer of Data Communications, published by the General Services Administration in 1982, is a standard for how the DES algorithm should be built into cryptographic hardware or firmware—for example, in unclassified link encryption, voice encryption, and satellite systems. Equipment bought by the government for unclassified use must meet the 1027 standard.
The DES consists of two components: an algorithm and a key. The published DES algorithm involves a number of iterations of a simple transformation, which uses both transposition and substitution techniques applied alternately. This algorithm uses a single key to encode and decode messages. DES is a so-called private key cipher. As you may recall from earlier in this chapter, with this type of cipher, data is encrypted and decrypted with the same key. Both the sender and the receiver must keep the key a secret from others. Because the DES algorithm itself is publicly known, learning the encryption key would allow an encrypted message to be read by anyone.
The DES key is a sequence of eight bytes, each containing eight bits (seven key bits and a parity bit). During encryption, the DES algorithm divides a message into blocks of 64 bits (plaintext). It operates on a single block at a time, dividing the block in half and encrypting the characters one after another. The characters are scrambled 16 times, under control of the key, resulting in 64 bits of encrypted text (ciphertext). The key has 56 meaningful bits (the eight parity bits are discarded by the first permutation). Figure 7-11 (adapted from a diagram included in FIPS PUB 46-1) shows the basic processing performed during DES encryption. If you are interested in the details, you can consult that publication for an explanation of DES processing.
Figure 7-11. How DES works
It must be noted that the government’s own acceptance of DES was halfhearted at best. It never was allowed to be used in sensitive government communications, but only for sensitive but nonclassified materials. At the very time that politicians and government agency officials were making speeches about its strength (usually including references to its not being able to be cracked for multiples of the known age of the universe), a determined group of researchers working for the Electronic Freedom Foundation developed a specialized device named Deep Crack out of Field Programmable Gate Arrays (FPGAs) that demonstrated an uncanny knack of sawing through supposedly uncrackable DES ciphertext. Also, in 1997, a cooperative effort on the Internet using over 14,000 computers, deciphered a test message after using 18 quadrillion of the 72 quadrillion possible DES keys.
There were three immediate effects. First the industry stopped listening for a time to almost anything the government said about privacy. Second, successive government initiatives to provide “free encryption for all,” such as the “clipper chip,” were laughed back into oblivion. Third, it was discovered that DES cracks did not really matter. In most transactions, there is a time window in which information must be kept absolutely secret. After that window expires, disclosure doesn’t much matter, especially in financial transactions. Whatever information was urgent will be old news, and its effect will already have been discussed in the newspapers.
Because DES has fallen, many organizations use triple DES (3DES), which is essentially DES repeated three times. This effectively increases the key length, boosting security, but no one is under the illusion 3DES will forever be adequately secure. Estimates of the length of key required to offer true privacy grow larger with each increase in computer power. In the early 2000s, math coprocessors began to appear in some personal computers again, along with dual-core architectures, drastically multiplying decryption power while lowering its costs.
DES lives on, curiously, because everybody can use it, and it can keep secrets for a little while, which is enough for many applications. For material that has to be kept absolutely confidential, or kept confidential over the long term, DES is not the best choice. Look to its replacement, the Advanced Encryption System (AES) or one of its siblings. (AES will be discussed later in this chapter.) For many applications, however, including telecommunications and mobile radios, DES will do fine.
Analyzing DES is highly instructive. Understanding it makes it easier to understand its successors. The DES provides four distinct modes of operation that differ in complexity and use. The following summarizes these modes very briefly. For a description of how the modes work, and an explanation of chaining and other technical terms, see FIPS PUB 81.
Electronic Codebook. A basic block encryption method. This mode operates like a codebook; for a given block of plaintext and a given key, it always produces the same block of ciphertext. The ECB mode is sometimes used to encrypt keys.
Cipher Block Chaining. An enhanced version of ECB that chains together blocks of ciphertext. Unlike the ECB mode, which encrypts identical input blocks to produce identical output blocks (perhaps revealing a pattern), the CBC mode encrypts each block using the plaintext, the key, and a third value, which is based on the previous block. This repetitive encryption, called chaining, hides repeated patterns.
Cipher Feedback. Uses previously generated ciphertext as input to the DES to generate pseudo-random output. This output is combined with plaintext to produce ciphertext, thus chaining together resulting ciphertext. The CFB mode is often used to encrypt individual characters.
Output Feedback. Very similar to the CFB. OFB does not chain the ciphertext as does CFB, although it does reprocess some plaintext. The OFB mode is often used to encrypt satellite communications.
The CBC and CFB modes perform message authentication as well as encryption. Message authentication ensures that the information received matches the information sent. During encryption by the DES, the blocks of text are linked; in CBC and CFB modes, the encryption of each block depends on the results of encoding the block that preceded it. Because of this link, the final encrypted block is changed if a single character is altered anywhere in the message. The final block serves as a message authentication code—a cryptographic checksum used to check the accuracy of the transmission and to detect whether there’s been any tampering with the message.
See the discussion in the section "Message Authentication" later in this chapter.
Application of the DES
DES technology has been embedded in many commercial products and remains a popular choice for applications requiring fast and continuous processing, such as stream ciphers and has been used for devices such as police radios or secure telephones. One example of a DES-based product would be a mobile radio that uses a chip built on the DES algorithm to encrypt voice communications. Other DES products include encryption boxes for use with microwave, satellite, and other types of communications.
Although the government cannot use the DES to protect classified or extremely sensitive unclassified information, DES products have been very popular in all but the most secret government agencies. For example, DES is found in applications in the Department of Energy communications systems. The DES was also the basis of the Department of the Treasury’s electronic funds transfer program, and the Federal Reserve used DES to encrypt connections between Depository Financial Institutions and Federal Reserve banks. Off the shelf military communications systems are often built on DES.
Historically, NSA has supported the DES through the Government Endorsed Data Encryption Standard Equipment Program. Through this program, NSA evaluates DES-based products, places successfully evaluated products on the NSA Endorsed Data Encryption Standard Products List (NEDESPL), and publishes this list in the Information Systems Security Services and Products Catalogue, available from the Government Printing Office. In some cases, this role is now delegated to approved independent laboratories.
In 1986, the agency surprised the industry by announcing that as of January 1988, it would not endorse DES-based products as complying with Federal Standard 1027. In addition, the agency said that it would recommend that NIST not reaffirm the DES when the standard next came up for review (in 1988). NSA did say that products already endorsed would continue to be available and would continue to be listed, and that NSA would continue to provide keys as needed for these products for a time. (NSA historically provided keys to owners of DES equipment.) In addition, the agency would continue to evaluate modifications to previously endorsed products, as long as the modifications did not affect the security of the products.
What’s the alternative to the DES? NSA for a time tried to get both government and industry to use its own classified algorithms. Through the Commercial Communications Security Endorsement Program (CCEP), described in the later section "Government Cryptographic Programs,” qualified vendors may be allowed access to these algorithms, embedded in tamperproof integrated circuit modules, that could be used in in their products.
There was a sizable reaction—much of it negative—to NSA’s decision to drop DES endorsement. In 1987, in the wake of NSA’s announcement, when NIST published a request for comments, 31 of 33 responding organizations (including federal agencies, the American Bankers Association, and the Computer and Business Equipment Manufacturers Association) supported reaffirmation of the standard. (Of the other two, one did not oppose reaffirmation, and the other supported reaffirmation for financial encryption.) Respondents pointed out that the DES was used extensively in existing products and applications, and that there was no clear and currently available alternative. Without the DES, information might be left unprotected while organizations waited for an appropriate alternative algorithm.
Vendors had other concerns about losing the DES. They were worried about the future market for existing DES-based products. There was also concern about using government-supplied or -mandated encryption chips, for fear that this would somehow help government agencies such as NSA to more easily penetrate messages sent using the vendors’ equipment, decreasing its attractiveness to buyers. (Revelations about a global monitoring network called Echelon eventually made it plain that this concern may have been valid.) Finally, because the classified algorithms have more stringent export restrictions than DES-based products, companies that use these products in their U.S. and foreign offices (and in communications between these offices) could be seriously affected. There was a time in which versions of software with built-in encryption were not approved for export.
Industry complaints, many coordinated by the American Bankers Association on behalf of banks and financial institutions (prime users of the DES for encryption of financial transactions), led NSA to reconsider its decision. NSA eventually announced that it would continue to support the DES for the encryption of financial data—for example, for FedWire transactions—“until transition to a new cryptographic technology is possible.” The government also eased export restrictions in the late 1990s, to all but a few nations considered hostile to the United States. This was very helpful to businesses with worldwide operations.
Overwhelming support for the DES, caused NIST to recommend to the Secretary of Commerce that the DES be reaffirmed for five more years, until 1992, and the cycle for creating a new encryption algorithm was begun in earnest within a few years after that.
Realizing the DES is no longer secure for many applications, and suspicious of how long 3DES may last, those who are concerned about real security cast about for other algorithms that may allow them to continue in reasonable confidentiality. The government, through NIST, was heavily involved in the selection process.
The Advanced Encryption Standard
The government, via NIST, determined that the next nationwide algorithm should be called the Advanced Encryption Algorithm, to be used in the Advanced Encryption Standard (AES). Several rounds of competition were held to determine the algorithm that should be the basis of AES. From five semifinalists, the winning algorithm was selected to be the Rijndael algorithm, created by Joan Daemen and Vincent Rijmen.
NIST announced the approval of the Federal Information Processing Standard (FIPS) for the Advanced Encryption Standard, in FIPS-197. This standard specifies the Rijndael algorithm as a FIPS-approved symmetric encryption algorithm that may be used by U.S. government organizations (and others) to protect sensitive information. Because of the difficulty of proving that an algorithm is truly secure, many nations and entities besides the United States have joined in supporting the AES. The more people there are to test an algorithm, and problems are not found, the more likely it is that people will gain confidence that it is secure.
Overview of the AES Development Effort
NIST worked for years with the cryptographic community to develop an Advanced Encryption Standard. The overall goal was to develop a FIPS that specifies an encryption algorithm(s) capable of protecting sensitive government information for a decade or more (into the early decades of this century). The algorithm or algorithms were expected to be used by the U.S. Government and, on a voluntary basis, by the private sector.
NIST announced the initiation of the AES development effort in January 1997, with a formal call for algorithms in September 1997. NIST listed the following requirements:
§ The design for AES would be that it would be unclassified, that is, the algorithm would be subject to public scrutiny.
§ AES was to use a symmetric key algorithm.
§ The algorithm was to be made freely available, without charging royalties, worldwide.
§ Additionally, the algorithm was to be a block cipher, and at a minimum support block sizes of 128 bits and key sizes of 128, 192, and 256 bits.
In August 1998, NIST announced that 15 algorithms, submitted by cryptographers worldwide, had been chosen as the first candidate group. NIST requested public comments on the candidate algorithms. Candidates met to review and discuss the various algorithms and the analysis in March 1999, two weeks after the period for comments closed. Based on the review, NIST selected 5 finalists from the 15 algorithms. The AES finalist candidate algorithms were MARS, RC6, Rijndael, Serpent, and Twofish. NIST then solicited public comments on the remaining algorithms, including but not limited to cryptanalysis, reviews of the intellectual property involved, and overall recommendations and implementation issues. NIST also provided a discussion forum for interested parties to discuss the AES finalists and relevant AES issues.
In April 2000, NIST sponsored a third meeting—an open, public forum for discussion of the analyses of the AES finalists. Submitters of the AES finalist algorithms were invited to attend and engage in discussions regarding comments on their algorithms, deliver papers, and make presentations. After studying all available information, NIST announced that it had selected Rijndael as the proposed AES algorithm. After another comment period, a draft FIP was published for public comment in February 2001. After a review, the standard was at last implemented in the summer of 2001.
How AES Works
Rijndael works on a byte-by-byte basis, matching up the input cleartext to the cipher key in a matrix of 16 bytes (4 × 4 matrix). The key is divided, or scheduled, so as to be injected in several repetitive rounds a little bit at a time. The first part of the key is added in before beginning 10 processing rounds. In each of these rounds, bytes are substituted, rows are shifted, and columns are mixed. (See Figure 7-12.)
Figure 7-12. Operation of AES
In the substitution process, the bytes of the input text are placed into a substitution box (S-box). This is a 16 × 16 matrix with a byte stored at the intersection of each row and column. The correct substitution is achieved by taking the first nibble (hex integer) of a cleartext byte and using it to determine the row of the S-box, and then the second nibble to determine the column. The character stored at the intersection of the selected row and column becomes the substitute byte (SubByte) for the cleartext. This process is repeated for each of the 16 bytes in the matrix.
Row shift and mix columns
The bytes to be encoded, now swapped with replacements, are next subjected to a row shift. Imagine the first row being undisturbed, the second row moved right one space, with the byte that falls out rolling over and assuming the empty spot at the start of the row. The third row shifts two bytes, and the final row three. This is followed by a Mix Columns phase, in which each column of the matrix is multiplied by another matrix to change its position.
Next, a round key is added to each column. Think of the round key as a little bit of the secret key, injected so as to result in further encryption.
Do it again
These transforms are applied for nine more rounds. There is no operation to mix columns on the final round. A round key is added to the final result, yielding the ciphertext. The key is shifted and rounded and added to itself as well.
The AES algorithm resulted from a multiyear evaluation process led by NIST with submissions and review by an international community of cryptography experts. AES is gradually showing up in many different encryption protocols including IEEE 802.11, IPsec, S/MIME, and TLS. RSA Laboratories—one of the five finalists in the AES competition—recently submitted a proposal for using AES to encrypt wireless data packets, a system called AES-CCM.
A great deal of information about the AES algorithm is available at the NIST web site: http://csrc.nist.gov/encryption/aes/.
 Miles E. Smid and Dennis K. Branstad, The Data Encryption Standard: Past and Future, National Institute of Standards and Technology, Gaithersburg (MD).
Other Cryptographic Algorithms
Not all of the encryption algorithms in existence were presented for consideration for the AES. Some were reserved for copyright reasons. And there were also algorithms that were submitted but not selected for the original 15. These algorithms have not disappeared. It is likely that they will be encountered form time to time. Among them are:
§ REDOC II
§ HPC (The Hasty Pudding Cipher)
You can obtain more information about these algorithms at the following web sites:
AES Round 1 Candidate Algorithms
The algorithm which were considered for the first round of the AES selection process, as well as some of their proponents are listed next:
§ CAST-256: Entrust Technologies, Inc. (represented by Carlisle Adams)
§ CRYPTON: Future Systems, Inc. (represented by Chae Hoon Lim)
§ DEAL: Richard Outerbridge, Lars Knudsen
§ CNRS: Centre National pour la Recherche Scientifique, Ecole Normale Superieure (represented by Serge Vaudenay)
§ E2 NTT: Nippon Telegraph and Telephone Corporation (represented by Masayuki Kanda)
Public Key Algorithms
The DES and AES are examples of private key algorithms. The keys are kept secret, and the key is the same on both ends of the link. A completely different type of cryptographic algorithm, the public key algorithm, was introduced by Whitfield Diffie and M.E. Hellman in 1976. (See the section "Cryptographic Keys: Private and Public" earlier in this chapter for an introduction.) Two examples of public key cryptography (PKC) are the Merkle and Hellman trap-door knapsack encryption method (which was broken in 1982) and the RSA algorithm introduced by Ronald Rivest, Adi Shamir, and Leonard Adleman.
The very first public key algorithm, proposed by Diffie and Hellman, cannot be used for encrypting messages or files by itself, but can be used to exchange keys used with other cryptosystems, and also for identification and related purposes. Drs. W. Diffie and M.E. Hellman disclosed this method in a 1976 paper entitled “New Directions in Cryptography.” The security of the Diffie-Hellman public key system is based on the mathematical difficulty of the discrete logarithm problem. For this scheme to be secure, the keys have to be long.
One particular implementation of the Diffie-Hellman algorithm, included by Sun Microsystems as part of its widely used Network File System (NFS) protocol, used keys of 192 bits. In 1989, at AT&T’s Bell Laboratories, Andrew Odlyzko and Brian LaMacchia broke this particular discrete logarithm problem. With their solution, it’s possible to calculate the secret key using only a few minutes of computer time (although the program that implements the calculation took months of time by cryptography experts to develop). One important result of the work of Odlyzko and LaMacchia is that for secure operations, it shows that you have to use public key algorithms with long keys. This increases the computational burden on the machines used to encoded and decode the messages.
The RSA Algorithm
Typically, private key algorithms such as DES can’t protect against fraud by the sender or the receiver of a message. (The reason being that the key used to encrypt the DES message could have been stolen and used to encrypt a message by a false entity.) The RSA algorithm, on the other hand (as well as some other public key algorithms), provides authentication (a way of ensuring that a message was sent by a certain user), as well as encryption. Named for its developers, Rivest, Shamir, and Adleman, who invented the algorithm at MIT in 1978, the algorithm uses two keys: a private key and a public key. With RSA, there is no distinction between the function of a user’s public and private keys. A key can be used as either the public or the private key.
The keys for the RSA algorithm are generated mathematically—in part, by combining prime numbers. Most big numbers can be built by multiplying smaller ones together. Once you do this, the smaller numbers will be mathematically related, and knowing one can help you determine the other. This is the situation you are looking for with private/public key pairs. But once the numbers get really huge, knowing one of the factors does not mean it is easy to find its companion. There are many false choices, and only the right one will help decrypt the message. The security of the RSA algorithm, and others like it, depends on the use of very large numbers. (Most versions of the RSA use 154-digit or 512-bit keys.) It is hard, sometimes impossible, to reliably factor extremely large numbers, such as those that are hundreds of digits long. Some research efforts have succeeded in cracking very large numbers, but it’s still highly unlikely that an intruder will choose number-cracking as a cost-effective way to break into a system.
Rivest, Shamir, and Adleman licensed the patent on the algorithm from MIT, and in 1982 began offering the algorithm as a commercial product. A number of government and corporate users now use the RSA algorithm; these include Lotus Development (in its Notes groupware product), the U.S. Navy, the Department of Labor, and a number of other federal agencies and universities. Although the RSA algorithm is patented inside the United States, it cannot be patented abroad (because the algorithm was published before it was patented), so it is in fairly wide use outside this country.
Digital Signatures and Certificates
In addition to providing encryption and message authentication, some encryption systems also use an authentication tool called a digital signature to verify the origin of the message and the identity of the sender and to resolve any authentication issues between sender and receiver. A digital signature is distinct for each specific transaction. It is unforgeable and can potentially be used as a valid signature in legal contracts. Public key encryption systems such as the RSA can produce digital signatures quite readily. When a message is encrypted at the sender’s end, the sender’s key digitally signs the message. When the message is decrypted at the recipient’s end, the receiver’s key is used to validates the digital signature. If any alteration in either signature or message occurs, the signature won’t verify any more.
An algorithm that provides both encryption and a digital signature might work like this. Suppose Joe is sending a message to Claudia:
1. Joe encrypts the message with his private key (to sign it).
2. Joe now applies Claudia’s public key to the message (to keep it a secret from anyone but Claudia).
Now, suppose Claudia has received a message, supposedly from Joe:
1. Claudia decrypts the message with her private key (to validate the signature that is part of the message).
2. Claudia now applies Joe’s public key to the message to verify that he sent the message. (It won’t validate unless Joe’s private key was used to encode it.)
There has been discussion about expanding the use of digital signatures so they can be used as digital pseudonyms. This would be a way of preventing attackers (people trying to intercept a message) from figuring out a sender’s identity via cross-matching or other techniques.
In cryptography, a public key certificate (or identity certificate) is a short document that can be used to verify that a public key belongs to an individual. The certificate uses a digital signature to bind together a public key with information such as the name of a person, an organization, or address information.
A certificate usually follows the ITU-T X.509 standard, which includes the following:
§ The public key being signed.
§ A name, which can refer to a person, a computer, or an organization.
§ A validity period during which the certificate should be considered to be reliable.
§ The Internet address (URL) of a revocation center that can be consulted to determine if the certificate has been declared to be invalid.
Certificates make it possible to use public-key cryptography on a large scale. To securely exchange secret keys between network users becomes impractical as the number of users increases beyond a few (the key distribution problem). The system used to exchange keys as networks scale in size is called the Public Key Infrastructure (PKI). If user Beatrice wants others to be able to send her encrypted messages, she publishes her public key. Anyone who obtains it can then send her a secure message.
Unfortunately, user Mark can outwit Beatrice by publishing a public key for which he, not Beatrice, has the associated private key. Mark then claims that the public key belongs to Beatrice and intercepts some of the messages intended for her. Beatrice can counter this, however, by building her public key into a certificate requesting that a third party digitally sign it. Anybody who trusts the third party can then check the certificate to see whether the embedded public key is truly Beatrice’s.
In this PKI, the third party is a Certificate Authority (CA). The CA is must be trusted by all participants, that is, each user must decide whether to trust the CA when the CA asserts that a particular public key belongs to a particular user.
There are many commercial CAs that charge for their services. Institutions and governments may have their own CAs. You can find free CAs on the Internet. In a large network, users may not be familiar with each other’s certificate authority. In this case, appeal is made to a higher level Certificate Authority, sometimes called CA2. This can be accomplished by including the public key of the local CA, signed by a higher level CA, which is likely to be recognized by the message recipient. This leads to a hierarchy of certificates, with the root certificate at the top. The root certificate represents a CA that is so central and well known that no additional third-party authentication is needed.
If it is discovered or suspected that a given private key has been compromised, or if the relationship between a certificate and a private key is no longer valid (by a person changing jobs, for instance), it is possible to revoke a certificate. This is done by placing it onto a certificate revocation list (CRL), which is stored at the revocation center, and which should be scanned when two computers need to trust each other.
A final note about certificates is that they are built on varying levels of trust. The level of trust dictates how sure you can be that the individual who owns the digital certificate is real, or is who she claims to be. Validation checking can encompass checking the corporate registry and legal status of a company, verifying whether or not they truly own the domain for which they wish to obtain a certificate. You should also check the ID of the person making the request; make sure he is an authorized representative of the requesting organization.
NSA has always had secret algorithms that it guards very closely. Some of these are now available to members of the Commercial Communications Security Endorsement Program (CCEP) for inclusion in so-called “high-grade” cryptographic products. Founded in 1984, CCEP is a business relationship designed to combine government cryptographic knowledge with corporate product development expertise. Through CCEP, several dozen companies have developed cryptographic products.
NSA and NIST have also joined forces to create a joint committee that’s developing a set of new algorithms for use with sensitive, unclassified information. Several algorithms are known to be under consideration:
§ A DES-like algorithm used to protect confidentiality.
§ A public key algorithm used to distribute keys for the confidentiality algorithm.
§ An algorithm used to provide a digital signature for messages. This algorithm would perform a one-way hash of the message.
§ A second algorithm used to provide a digital signature for messages. This algorithm would sign the hash in digital fashion.
 W. Diffie and M.E. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory, Volume IT-22, Number 6, November 1976.
 Merkle and M.E. Hellman, “Hidden Information and Signatures in Trapdoor Knapsacks,” IEEE Transactions in Information Theory, September 1978.
 Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public Key Cryptosystems,” Communications of the ACM, Volume 21, Number 2, February 1978.
As mentioned previously, encrypting a message makes the message a secret, but it doesn’t automatically authenticate it. Encryption protects a message from disclosure. Only authentication protects a message from modification.
What does authentication do for a message? It ensures that the message has not been altered, either maliciously or inadvertently, during transmission. It has arrived exactly as it was sent. Authentication also ensures that the message is not a repeat (called a replay) of a message previously sent, that the message came from the origin stated in the message (was not forged by an imposter), and that the message went to the intended recipient (was not falsified—for example, to alter the date of receipt).
Authentication can be used alone—just to ensure against modification and forgery—or it can be used in conjunction with encryption. In the first case, the plaintext is authenticated. In the second case, the ciphertext is authenticated.
Historically, computer and communications systems have used such techniques as checksums (adding up the digits in a message before and after transmission to see if they have changed), parity checks (counting the ones and zeroes in a message to determine if the number of ones is odd or even, and verifying that whatever the state was before transmission, that it is the same after), and test words (special codes or words inserted in or preceding a message to signify authenticity) to check that the information received matched the information sent, and that nothing had been modified—either intentionally or unintentionally. The message authentication capabilities included in modern encryption technologies provide an extremely reliable replacement for the old checking techniques. Both private-key and public-key encryption algorithms allow for message authentication, though public key systems are better equipped to perform this function due to their two-key mechanism.
With the DES algorithm, for instance, certain modes (CBC or CFB) perform message authentication. Encrypting the data also produces a message authentication code, which is appended to the encrypted message. At the receiving end, the DES independently calculates the code for the message and compares it to the message authentication code sent with the message. If the two codes are identical, it’s extremely likely that the message was sent without alteration.
There are a number of elaborations on this theme. To provide privacy as well as authentication, the DES can be used with two different secret keys, one for authentication and one for encryption. To safeguard against the sender or the receiver of a message forging or denying that he sent the message, you can use a digital signature (described earlier). Although it’s possible to create a digital signature via the DES (using a message authentication code), public-key systems such as the RSA algorithm often do it more efficiently.
Government Cryptographic Programs
The government has a keen interest in cryptographic products. NSA, NIST, and the Department of the Treasury have all developed programs for evaluating cryptographic algorithms and products.
NSA’s Communications Security Cryptographic Endorsement Program, introduced earlier in this chapter, evaluates so-called “high-grade” cryptographic products. All algorithms used in high-grade products are designed by NSA and are classified. Chip implementations of the algorithms are provided to vendors with protective coating so they can’t be reverse-engineered.
NSA classifies high-grade cryptographic products developed under CCEP as either Type 1 or Type 2:
Type 1 products are designed to encrypt classified data; they can also be used to encrypt sensitive unclassified data. An example of a Type 1 product is the Secure Telephone Unit (STU), a telephone that encrypts voice and data communications and provides secure key distribution. STU-II and STU-III are NSA-sponsored projects aimed at developing secure telephones for government agencies and government contractors. The telephones operate over ordinary telephone circuits and use encryption to provide secure voice and data communication. The first versions are being developed by AT&T, General Electric, and Motorola. DoD has recently bought thousands of STU-III units for use by both government employees and contractors. Other Type 1 products include trunk encryption devices and network communications products.
Type 2 products are designed to encrypt sensitive unclassified data; the government doesn’t allow these products to be used to encrypt classified data. Examples of Type 2 products include authentication devices, transmission security devices, and secure LANs. Type 2 equipment is effectively intended as a replacement for DES-based equipment.
Until recently, NSA’s Government Endorsed Data Encryption Standard Equipment Program evaluated products based on the DES algorithm. Although NSA no longer endorses new DES-based products through this program, it does continue to list and provide keys, as necessary, for already endorsed products.
NIST’s cryptographic responsibilities include the development of both standards and validation systems. NIST assists the Department of the Treasury by offering a system that tests the conformance of vendors’ systems to the ANSI X9.9 message authentication standard. The system also checks for conformance to FIPS 113 (Computer Data Authentication). The validation is automated and can be initiated remotely via telephone lines. NIST is currently developing a system that tests the conformance of systems to the ANSI X9.17 key management standard. NIST is also working on systems that use digital message authentication codes in place of written signatures in government transactions.
Since 1988, the Department of the Treasury has required that all of the department’s electronic funds transfer messages be authenticated. The Treasury certifies authentication devices developed by vendors to ensure that they conform to Federal Standard 1027 (DES implementation) as well as to ANSI standard X9.17 (key management). The Electronic Funds Transfer Certification Program for Authentication Devices is aided by technical input and testing services provided by NSA and NIST.
Cryptographic Export Restrictions
The U.S. government closely regulates the sale and export of cryptographic products developed within the United States. Export regulations are intended to restrict the use of products that ultimately could make an enemy nation’s communications more difficult for U.S. intelligence agencies to decipher.
Most cryptographic export restrictions were eased under the Clinton administration, nevertheless, it is imperative that you verify that there are no restrictions in place against each nation with which you use cryptography.
In general, licenses are issued only for the governments and government contractors of the NATO countries, plus certain “friendly” governments, such as Canada, Australia, and New Zealand. License applications are considered on a case-by-case basis. NSA sometimes requires a vendor to change its own encryption algorithm to qualify for an export license. Licenses are easier to get for internationally based financial institutions with recognized needs for encryption.
Often, once overseas customers have acquired a product stripped of its cryptographic capabilities, they’ll insert a different, home-grown encryption algorithm in the product.
By the same token, there are countries whose governments do not wish their populace to have access to powerful encryption. This was in fact the case here in the United States, where the developer of the Pretty Good Privacy encryption system found himself in no end of trouble for a few years for developing a powerful and efficient method of encrypting documents and email.
Generally speaking, encryption control falls into the categories of input, export, and domestic use, with come countries denying all three. A useful table is maintained by RSA Laboratories at the following web address: http://www.rsasecurity.com/rsalabs/node.asp?id=2333.
From the secret writing systems of early times to the secure encryption algorithms of today, encryption has been part of the arts of war and diplomacy. Commercial security has now increased in importance to the point that encryption is a common tool in daily business. A requirement for privacy—say for patient records and other sensitive data—has moved encryption into the medical market. Even educational records deserve a certain amount of encryption to protect family privacy.
Modern cryptology depends upon thoroughly vetted encryption algorithms, coupled with the secure use and transmission of keys, either public or private. This is the basis of maintaining message confidentiality, integrity, and authenticity.