in the field. In the 1990s the Clipper Chip and the development of a replacement for the aging DES were two of the many crypto highlights.
Governments continue to fund major organizations that work in crypto and related fields. However, itś clear that the crypto genie has escaped from its classified bottle, never to be put back.
2.6 A Taxonomy of Cryptography
In the next three chapters, weĺl focus on the three broad categories of ciphers, namely, symmetric ciphers, public key cryptosystems, and hash functions. Here, we give a very brief overview of these different categories.
Each of the classic ciphers discussed above is a symmetric cipher. Modern symmetric ciphers can be subdivided into stream ciphers and block ciphers. Stream ciphers generalize the one‐time pad approach, sacrificing provable security for a key that is manageable. Block ciphers are, in a sense, the generalization of classic codebooks. In a block cipher, the key determines the codebook, and as long as the key remains fixed, the same codebook is used. Conversely, when the key changes, a different codebook is selected.
While stream ciphers dominated in the post–World War II era, today block ciphers are the kings of the symmetric crypto world—with a few notable exceptions. Generally speaking, block ciphers are easier to optimize for software implementations, while stream ciphers can be optimized for hardware.
As the name suggests, in public key crypto, encryption keys can be made public. For each public key, there is a corresponding decryption key that is known as a private key. Not surprisingly, the private key is not public—it must remain private.
If you post your public key on the Internet, anyone with an Internet connection can encrypt a message for you, without any prior arrangement regarding the key. This is in stark contrast to a symmetric cipher, where the participants must agree on a key in advance. Prior to the adoption of public key crypto, secure delivery of symmetric keys was the Achilles heel of modern cryptography. A spectacular case of a failed symmetric key distribution system can be seen in the exploits of the Walker family spy ring. The Walker family sold cryptographic keys used by the U.S. military to the Soviet Union for nearly two decades before being discovered. Public key cryptography does not completely eliminate the key distribution problem, but it does change the nature of the problem.
Public key cryptography has another somewhat surprising and extremely useful feature, for which there is no parallel in the symmetric key world. Suppose that Alice “encrypts″ a message with her private key. Since the public key undoes the public key, and the public key is public, anyone can decrypt this message. At first glance such encryption might seem pointless. However, such “encryption″ can serve as a digital form of a handwritten signature—anyone can verify the signature, but only the Alice could have created the signature. As with all of the topics alluded to in this section, weĺl have much more to say about digital signatures in a later chapter.
Anything we can do with a symmetric cipher we can also accomplish with a public key cryptosystem. Public key crypto also enables us to do things that cannot be accomplished with a symmetric cipher. So why not use public key crypto for everything? The primary reason is efficiency—symmetric key crypto is orders of magnitude faster than public key. As a result, symmetric crypto is used to generate the vast majority of ciphertext today. Yet public key crypto has several critical roles to play in modern information security.
The third major crypto category weĺl consider is cryptographic hash functions.11 These functions take an input of any size and produce an output of a fixed size. In addition, cryptographic hash functions must satisfy some very stringent requirements. For example, if the input changes in one or more bits, the output should change in about half of its bits. For another, it must be computationally infeasible to find any two inputs that hash to the same output. It may not be obvious that such a function is useful—or that such functions actually exist—but weĺl see that they do exist and that they turn out to be extremely useful for a surprisingly wide array of problems.
2.7 A Taxonomy of Cryptanalysis
The goal of cryptanalysis is to recover the plaintext, the key, or both. By Kerckhoff's principle, we assume that Trudy, in the role of cryptanalyst, has complete knowledge of the inner workings of the algorithm. Another basic assumption is that Trudy has access to the ciphertext—otherwise, why would we bother to encrypt? If Trudy only knows the algorithms and the ciphertext, then she must conduct a ciphertext only attack. This is the most disadvantageous scenario from Trudyś perspective.
Trudyś chances of success might improve if she has access to known plaintext. That is, it could be to Trudyś advantage if she knows some of the plaintext and observes the corresponding ciphertext. These matched plaintext‐ciphertext pairs might provide information about the key. Itś often the case that Trudy has access to (or can guess) some of the plaintext. For example, many kinds of data include stereotypical headers (email being a good example). If such data is encrypted, the attacker can likely guess some of the plaintext that corresponds to some of the ciphertext.
Surprisingly often, Trudy can actually choose the plaintext to be encrypted and see the corresponding ciphertext. Such a scenario is known as a chosen plaintext attack. How is it possible for Trudy to choose the plaintext? Weĺl see that some security protocols encrypt anything that is sent and return the corresponding ciphertext. Itś also possible that Trudy could have limited access to a cryptosystem, allowing her to encrypt plaintext of her choice. For example, Alice might forget to log out of her computer when she takes her lunch break. Trudy could then encrypt some selected messages before Alice returns. This type of “lunchtime attack″ takes many forms.
Potentially more advantageous for the attacker is an adaptively chosen plaintext attack. In this scenario, Trudy chooses the plaintext, views the resulting ciphertext, and chooses the next plaintext based on the observed ciphertext. In some cases, this can make Trudyś job significantly easier.
Related key attacks are also relevant in some applications. The idea here is to look for a weakness in the system when the keys are related in some special way.
There are other types of attacks that cryptographers occasionally worry about—mostly when they feel the need to publish another academic paper. In any case, a cipher can only be considered secure if no potentially useful shortcut attack is known.
Finally, there is one particular attack scenario that applies to public key cryptography, but not the symmetric key case. Suppose Trudy intercepts a ciphertext that was encrypted with Aliceś public key. If Trudy suspects that the plaintext message was either “yes″ or “no,″ then she can encrypt both of these putative plaintexts with Aliceś public key. If either matches the ciphertext, then the message has been broken. This is known as a forward search. Although a forward search attack is not applicable to symmetric ciphers, weĺl see that this approach can be used to attack hash functions in some applications.
We've previously seen that the size of the keyspace must be large enough to prevent an attacker from trying all possible keys. The forward search attack implies that in public key crypto, we must also ensure that the size of the plaintext message space is large enough so that the attacker cannot simply encrypt all possible plaintext messages. As weĺl see in Chapter 4, this is easy to achieve in practice.
2.8 Summary
In this chapter we covered several classic cryptosystems, including the simple substitution, the double transposition, codebooks, and the one‐time pad. Each of these illustrates some important points that weĺl return to again in later chapters. We also discussed some elementary aspects of cryptography
