7.2 Symmetric Key AlgorithmsSymmetric key algorithms are used primarily for the bulk encryption of data or data streams. These algorithms are designed to be very fast and have a large number of possible keys. The best symmetric key algorithms offer excellent secrecy; once data is encrypted with a given key, there is no fast way to decrypt the data without possessing the same key. Symmetric key algorithms can be divided into two categories: block and stream. Block algorithms encrypt data a block (many bytes) at a time, while stream algorithms encrypt byte by byte (or even bit by bit). 7.2.1 Cryptographic Strength of Symmetric AlgorithmsDifferent encryption algorithms are not equal. Some systems are not very good at protecting data, allowing encrypted information to be decrypted without knowledge of the requisite key. Others are quite resistant to even the most determined attack. The ability of a cryptographic system to protect information from attack is called its strength. Strength depends on many factors, including:
In general, cryptographic strength is not proven; it is only disproven. When a new encryption algorithm is proposed, the author of the algorithm almost always believes that the algorithm offers "perfect" security[6]—that is, the author believes there is no way to decrypt an encrypted message without possession of the corresponding key. After all, if the algorithm contained a known flaw, then the author would not propose the algorithm in the first place (or at least would not propose it in good conscience).
As part of proving the strength of an algorithm, a mathematician can show that the algorithm is resistant to specific kinds of attacks that have been previously shown to compromise other algorithms. Unfortunately, even an algorithm that is resistant to every known attack is not necessarily secure, because new attacks are constantly being developed. From time to time, some individuals or corporations claim that they have invented new symmetric encryption algorithms that are dramatically more secure than existing algorithms. Generally, these algorithms should be avoided. As there are no known attack methods against the encryption algorithms that are in wide use today, there is no reason to use new, unproven encryption algorithms that might have flaws lurking in them. 7.2.2 Key Length with Symmetric Key AlgorithmsAmong those who are not entirely familiar with the mathematics of cryptography, key length is a topic of continuing confusion. As we have seen, short keys can significantly compromise the security of encrypted messages because an attacker can merely decrypt the message with every possible key to decipher the message's content. But while short keys provide comparatively little security, extremely long keys do not necessarily provide significantly more practical security than keys of moderate length. That is, while keys of 40 or 56 bits are not terribly secure, a key of 256 bits does not offer significantly more real security than a key of 168 bits, or even a key of 128 bits. To understand this apparent contradiction, it is important to understand what is really meant by the words key length, and how a brute force attack actually works. Inside a computer, a cryptographic key is represented as a string of binary digits. Each binary digit can be a 0 or a 1. Thus, if a key is 1 bit in length, there are two possible keys: 0 and 1. If a key is 2 bits in length, there are four possible keys: 00, 01, 10, and 11. If a key is 3 bits in length, there are eight possible keys: 000, 001, 010, 011, 100, 101, 110, and 111. In general, each added key bit doubles the number of keys. The mathematical equation that relates the number of possible keys to the number of bits is:
If you are attempting to decrypt a message and do not have a copy of the key, the simplest way to decrypt the message is to do a brute force attack. These attacks are also called key search attacks, because they involve trying every possible key to see if a specific key decrypts the message. If the key is selected at random, then on average, an attacker will need to try half of all the possible keys before finding the actual decryption key. Fortunately, for those of us who depend upon symmetric encryption algorithms, it is a fairly simple matter to use longer keys. Each time a bit is added, the difficulty for an attacker attempting a brute force attack doubles. The first widely used encryption algorithm, the DES, used a key that was 56 bits long. At the time that the DES was adopted, many academics said that 56 bits was not sufficient: they argued for a key that was twice as long. But it has been conjectured that the U.S. National Security Agency did not want a cipher with a longer key length widely deployed, most likely because such a secure cipher would significantly complicate its job of international surveillance.[7] To further reduce the impact that the DES would have on its ability to collect international intelligence, U.S. corporations were forbidden from exporting products that implemented the DES algorithm.
In the early 1990s, a growing number of U.S. software publishers demanded the ability to export software that offered at least a modicum of security. As part of a compromise, a deal was brokered between the U.S. Department of Commerce, the National Security Agency, and the Software Publisher's Association. Under the terms of that agreement, U.S. companies were allowed to export mass-market software that incorporated encryption, provided that the products used a particular encryption algorithm and the length of the key was limited to 40 bits. At the same time, some U.S. banks started using an algorithm called Triple-DES (basically, a threefold application of the DES algorithm) to encryp some financial transactions. It has a key size of 168 bits. Triple-DES is described in the following section. In October 2000, the National Institute of Standards and Technology (NIST) approved the Rijndael encryption algorithm as the new U.S. Advanced Encryption Standard. Rijndael can be used with keys of 128, 192, or 256 bits. The algorithm's extremely fast speed, combined with its status as the government-chosen standard, means that it will likely be preferable to the DES, Triple-DES, and other algorithms in the future. So how many bits is enough? That depends on how fast the attacker can try different keys and how long you wish to keep your information secure. As Table 7-1 shows, if an attacker can try only 10 keys per second, then a 40-bit key will protect a message for more than 3,484 years. Of course, today's computers can try many thousands of keys per second—and with special-purpose hardware and software, they can try hundreds of thousands. Key search speed can be further improved by running the same program on hundreds or thousands of computers at a time. Thus, it's possible to search a million keys per second or more using today's technology. If you have the ability to search a million keys per second, you can try all 40-bit keys in only 13 days. If a key that is 40 bits long is clearly not sufficient to keep information secure, how many bits are necessary? In April 1993, the Clinton Administration introduced the Clipper encryption chip as part of its Escrowed Encryption Initiative (EEI). This chip used a key that was 80 bits long. As Table 7-1 shows, an 80-bit key is more than adequate for many applications. If you could search a billion keys per second, trying all 80-bit keys would still require 38 million years! Clipper was widely criticized not because of the key length, but because the Clipper encryption algorithm was kept secret by the National Security Agency, and because each Clipper chip came with a "back door" that allowed information encrypted by each Clipper chip to be decrypted by the U.S. government in support of law enforcement and intelligence needs.
Increasing the key size from 80 bits to 128 bits dramatically increases the amount of effort to guess the key. As the table shows, if there were a computer that could search a billion keys per second, and if you had a billion of these computers, it would still take 10,783 billion years to search all possible 128-bit keys. As our Sun is likely to become a red giant within the next 4 billion years and, in so doing, destroy the Earth, a 128-bit encryption key should be sufficient for most cryptographic uses, assuming that there are no other weaknesses in the algorithm used. Lately, there has been considerable interest in the field of quantum computing. Scientists postulate that it should be possible to create atomic-sized computers specially designed to crack encryption keys. But while quantum computers could rapidly crack 56-bit DES keys, it's unlikely that a quantum computer could make a dent in a 128-bit encryption key within a reasonable time: even if you could crack 1 x 1023 keys per second, it would still take 108 million years to try all possible 128-bit encryption keys. It should be pretty clear at this point that there is no need, given the parameters of cryptography and physics as we understand them today, to use key lengths that are larger than 128 bits. Nevertheless, there seems to be a marketing push towards increasingly larger and larger keys. The Rijndael algorithm can be operated with 128-bit, 192-bit, or 256-bit keys. If it turns out that there is an as-yet hidden flaw in the Rijndael algorithm that gives away half the key bits, then the use of the longer keys might make sense. Why you would want to use those longer key lengths isn't clear, but if you want them, they are there for you to use. 7.2.3 Common Symmetric Key AlgorithmsThere are many symmetric key algorithms in use today, as shown in Table 7-2.
7.2.4 Attacks on Symmetric Encryption AlgorithmsIf you are going to use cryptography to protect information, then you must assume that people who you do not wish to access your information will be recording your data, and, if they determine it is encrypted, may try to decrypt it forcibly.[14] To be useful, your cryptographic system must be resistant to this kind of direct attack.
Attacks against encrypted information fall into three main categories. They are:
7.2.4.1 Key search (brute force) attacksAs we saw earlier, the simplest way to attack an encrypted message is simply to attempt to decrypt the message with every possible key. Most attempts will fail, but eventually one of the tries will succeed and either allow the cracker into the system or permit the ciphertext to be decrypted. These attacks, illustrated in Figure 7-3, are called key search or brute force attacks. There's no way to defend against a key search attack because there's no way to keep an attacker from trying to decrypt your message with every possible key. Figure 7-3. A key search attackKey search attacks are not very efficient. And, as we showed earlier, if the chosen key is long enough, a key search attack is not even feasible. For example, with a 128-bit key and any conceivable computing technology, life on Earth will cease to exist long before even a single key is likely to be cracked! On the other hand, many key search attacks are made considerably simpler because most users pick keys based on small passwords with printable characters. For a 128-bit key to be truly secure, all 128 bits must be randomly chosen. That is, there must be 2128 distinct keys that could possibly be used to encrypt the data. If a "128-bit key" is actually derived from a password of four lower-case letters, then even though the key appears to be 128 bits long, there are really only 26 x 26 x 26 x 26, or 456,976 different keys that could actually be used. Instead of a 128-bit key, a key that is chosen from four lower-case letters has an effective key length between 18 bits and 19 bits! (This is because 218 = 262,144, while 219 = 524,288.) From this simple analysis, it would appear that any of the strong algorithms described earlier with a 128-bit key length should be sufficient for most cryptographic needs—both now and forever more. Unfortunately, there are a number of factors that make this solution technically, legally, or politically unsuitable for many applications, as we'll see later in this chapter. 7.2.4.2 CryptanalysisIf key length were the only factor determining the security of a cipher, everyone interested in exchanging secret messages would simply use codes with 128-bit keys, and all cryptanalysts (people who break codes) would have to find new jobs. Cryptography would be a resolved branch of mathematics, similar to simple addition. What keeps cryptography interesting is the fact that most encryption algorithms do not live up to our expectations. Key search attacks are seldom required to divulge the contents of an encrypted message. Instead, most encryption algorithms can be defeated by using a combination of sophisticated mathematics and computing power. The result is that many encrypted messages can be deciphered without knowing the key. A skillful cryptanalyst can sometimes decipher encrypted text without even knowing the encryption algorithm. A cryptanalytic attack can have two possible goals. The cryptanalyst might have ciphertext and want to discover the plaintext, or might have ciphertext and want to discover the encryption key that was used to encrypt it. (These goals are similar but not quite the same.) The following attacks are commonly used when the encryption algorithm is known, and these may be applied to encrypted files or Internet traffic:
The only reliable way to determine if an algorithm is strong is to hire a stable of the world's best cryptographers and pay them to find a weakness. This is the approach used by the U.S. National Security Agency. Unfortunately, this approach is beyond the ability of most cryptographers, who instead settle on an alternative known as peer review. Peer review is the process by which most mathematical and scientific truths are verified. First, a person comes up with a new idea or proposes a new theory. Next, the inventor attempts to test his idea or theory on his own. If the idea holds up, it is then published in an academic journal or otherwise publicized within a community of experts. If the experts are motivated, they might look at the idea and see if it has any worth. If the idea stands up over the passage of time, especially if many experts try and fail to disprove the idea, it gradually comes to be regarded as truth. Peer review of cryptographic algorithms and computer security software follows a similar process. As individuals or organizations come up with a new algorithm, the algorithm is published. If the algorithm is sufficiently interesting, cryptographers or other academics might be motivated to find flaws in it. If the algorithm can stand the test of time, it might be secure, pending some new mathematical discovery or technique being developed. It's important to realize that simply publishing an algorithm or a piece of software does not guarantee that flaws will be found. The Wireless Encryption Protocol (WEP) encryption algorithm used by the 802.11 networking standard was published for many years before a significant flaw was found in the algorithm—the flaw had been there all along, but no one had bothered to look for it. The peer review process isn't perfect, but it's better than the alternative: no review at all. Do not trust people who say they've developed a new encryption algorithm but also say that they don't want to disclose how the algorithm works because such disclosure would compromise the strength of the algorithm. In practice, there is no way to keep an algorithm secret: if the algorithm is being used to store information that is valuable, an attacker will purchase (or steal) a copy of a program that implements the algorithm, disassemble the program, and figure out how it works.[15] True cryptographic security lies in openness and peer review, not in algorithmic secrecy.
7.2.4.3 Systems-based attacksAnother way of breaking a code is to attack the cryptographic system that uses the cryptographic algorithm, without actually attacking the algorithm itself. One of the most spectacular cases of a systems-based attack was the VC-I video encryption algorithm used for early satellite TV broadcasts. For years, video pirates sold decoder boxes that could intercept the transmissions of keys and use them to decrypt the broadcasts. The VC-I encryption algorithm was sound, but the system as a whole was weak. (This case also demonstrates the fact that when a lot of money is at stake, people will often find the flaws in a weak encryption system, and those flaws will be exploited.) Many of the early attacks against Netscape's implementation of SSL were actually attacks on Netscape Navigator's implementation, rather than on the SSL protocol itself. In one published attack, researchers David Wagner and Ian Goldberg at the University of California at Berkeley discovered that Navigator's random number generator was not really random. It was possible for attackers to closely monitor the computer on which Navigator was running, predict the random number generator's starting configuration, and determine the randomly chosen key using a fairly straightforward method. In another attack, the researchers discovered that they could easily modify the Navigator program itself so that the random number generator would not be executed. This entirely eliminated the need to guess the key. Covert channels are another concern. The U.S. Department of Defense's 1985 Trusted Computer System Evaluation Criteria define a covert channel as "any communication channel that can be exploited by a process to transfer information in a manner that violates the system's security policy." For example, even if an attacker cannot decrypt encrypted email messages, he may be able to gain information by examining the message sender, recipient, timing, path through the network, character set encoding, or other features that are often overlooked by those concerned about message confidentiality or integrity alone. |