Mark Stamp - Information Security

The Enigma was initially broken by Polish cryptanalysts. After the fall of Poland, these cryptanalysts escaped to France, but shortly thereafter France fell to the Nazis. The Polish cryptanalysts eventually made their way to England, where they provided their knowledge to British cryptanalysts. 9 A British team that included computing pioneer Alan Turing developed improved attacks on the Enigma.

An illustration of the “wiring diagram″ for the Enigma cipher appears in Figure 2.5. Additional details on the inner workings of the Enigma are given in the problems at the end of this chapter and a cryptanalytic attack is presented in the cryptanalysis material available on the textbook website.

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, 10 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.

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.

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.