Figure 2.5 Enigma wiring diagram

In the post–World War II era, cryptography made the move from a black art into the realm of a true science. The publication of Claude Shannonś seminal 1949 paper, “Information Theory of Secrecy Systems″ [109], marks the turning point. Shannon proved that the one‐time pad is secure and he also offered two fundamental cipher design principles, confusion and diffusion. These two principles have guided symmetric cipher design ever since.

      In Shannonś use, confusion consists of, roughly speaking, obscuring the relationship between the plaintext and ciphertext. On the other hand, diffusion is spreading of the plaintext statistics through the ciphertext. A simple substitution cipher and a one‐time pad employ only confusion, whereas a double transposition is a diffusion‐only cipher. Since the one‐time pad is provably secure, confusion alone is enough, while diffusion alone is apparently not.

      These two concepts—confusion and diffusion—are as relevant today as they were on the day that Shannonś paper was originally published. In subsequent chapters, it will become clear that these concepts remain crucial to modern block cipher design.

Until relatively recently, cryptography was almost exclusively the domain of governments and militaries. This changed dramatically in the 1970s, due in large part to the computer revolution which led to the need to protect large amounts of electronic data. By the mid‐1970s, even the U.S. government realized that there was a legitimate commercial need for secure cryptography. Furthermore, it was clear that the commercial products of the day were severely lacking. So, the National Bureau of Standards, or NBS,¹⁰ issued a request for cryptographic algorithms. The plan was that NBS would select an algorithm that would then become an official U.S. government standard. The ultimate result of this ill‐conceived process was a cipher known as the Data Encryption Standard, or DES.

      Itś difficult to overemphasize the role that DES has played in the modern crypto history. Weĺl have much more to say about DES in the next chapter.

      Post‐DES, academic interest in cryptography grew rapidly. Public key cryptography was discovered (or, more precisely, rediscovered) shortly after the arrival of DES. By the 1980s there were annual CRYPTO conferences, which are a consistent source of high‐quality work 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.¹¹ 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