If I had written this book ten years ago, cryptography would have been the topic of the first chapter. The terms network security and cryptography were considered to be synonymous. Today, we understand that cryptography is merely a useful tool, not a panacea.
What makes network security different from traditional computer security is that without cryptography, each machine in the network is essentially alone; there is no way for a machine to know with any confidence where any information came from unless it was obtained from a direct, physical connection to another machine. The attacker exploits this isolation. Cryptography provides “cement” that allows us to establish durable, trustworthy connections between machines regardless of their physical connectivity.
Like cement, cryptography is a powerful tool that almost every architect will employ in some fashion in almost every building, but there is much more to architecture than the correct use of cement, and few buildings that are constructed entirely out of cement have won public praise and affection.
Cryptography allows us to remove some of the differences between Internet crime and traditional methods that are stacked in favor of the Internet criminal. We must, however, remember that the similarities are at least as important as the differences.
Cryptography was used to keep secrets in ancient Rome. Suetonius describes Julius Caesar’s use of a simple cipher in which every letter in a word was replaced by the letter that appears three letters before it in the alphabet:
The problem with this approach became apparent in the civil war following Caesar’s assassination. When Romans fought against Romans, everyone knew the code. This led his successor, Augustus Caesar, to change the imperial cipher to use a one letter shift. In cryptography terms, he changed the key from 3 to 1.
This scheme is easily broken by trial and error because the Latin alphabet in Caesar’s day only had 24 letters and thus only 23 possible Caesar ciphers. The ROT-13 encryption that is sometimes used on the Internet to hide punch lines to jokes or answers to quizzes is a Caesar cipher with a shift of 13 letters. Encrypting twice results in a shift of 26 letters, and the text returns to its original form.
Shifting letters by a fixed number of places does not provide enough variations to be interesting. If we allow any letter to be substituted for any other, we have more than 1025 possibilities, a respectable number of variations for any cipher. This is known as a substitution cipher; whereby each message is encrypted using the same basic technique (substitute one letter for another), but this technique allows a large number of variations. Our new (larger) key is the substitution table.
The substitution cipher is easily broken, despite the vast number of possibilities, by noting the frequency with which letters appear in the encrypted text. If the letter r appears most often in the encrypted text, it is almost certainly being used to substitute for a commonly occurring letter such as e.
Solving a substitution cipher is a bit like solving a crossword puzzle. If you enjoy solving crossword puzzles, you might like to try decrypting the message in Figure 10-1.
The substitution cipher can be made much stronger if the substitution table is changed each time a letter is encoded. This type of cipher is known as a stream cipher because the text that is encrypted is combined with a stream of data that is ideally random but is known as the cipherstream. For example, we might use the Caesar cipher technique of shifting letters by a certain number of spaces but shift the first letter by 23 places, the second by 12, the third by 2, the fourth by 0, and so on.
The strength of this scheme depends on how we arrive at the sequence of shift values and whether we ever use the same sequence twice. If the sequence is genuinely random and used only once, the scheme is known as a one-time pad and is provably unbreakable if the pad is only used once. If the sequence is not random, the code can be broken by guessing the sequence.
A simple way to generate a sequence of apparently random letter shift values is to use another text. For example, we might use the Declaration of Independence to provide our sequence. The first letter W is the twenty-third letter of the alphabet, the second e is the fifth. “We the People ...” gives us the sequence 23, 5, 20, 8, 5, 16, 5, 15, 16, 12, 5 ... as our cipher stream (see Figure 10-2).
Using another document to provide cipherstream isn’t random enough to be secure. The letter e occurs four times in the first three words of the Declaration of Independence. This type of cipher can be broken even when both texts are unknown by combing our knowledge of the frequency with which certain letters appear with knowledge about the frequency with which one letter follows another.
If the one-time pad is simple and provably unbreakable, why do we hear about ciphers being broken? Unfortunately, a system can be both simple and secure without being practical.
Alice and Bob can only use a one-time pad to communicate their secrets securely if they have a secure means of communicating the one-time pad. The one-time pad must be at least as long as the message they want to exchange, and they must never use the pad a second time.
If an attacker is able to get hold of two messages that are encoded using the same pad, he can subtract one message from another, and the cipherstream cancels out. The unbreakable code is now reduced to the difficult but breakable two texts problem we just saw. Instead of the two plaintexts being added, one is subtracted from the other, but this is essentially the same problem to the cryptanalyst. Instead of having a signal that is entirely masked by a completely random signal, we have two signals with a regular pattern mixed together (see Figure 10-3).
The lesson here is that cryptographic security schemes can be secure in theory but brittle in practice. The unbreakable security of the one-time pad is entirely dependent on the feature that makes it so inconvenient to use.
Before computers became cheap, the only practical way to create a reliably random cipherstream was to use a physical process such as throwing a large number of dice many times. This might be why the KGB reused some of the one-time pads they had used to encrypt diplomatic traffic in the early 1940s. What appears to be an elementary cryptographic mistake is perhaps understandable when it is considered that in 1941 the German army had reached Moscow.
The mistake was spotted by a group of U.S. cryptanalysts who produced a series of intelligence decrypts known by the code name VENONA. The VENONA intelligence led to the discovery and execution of the U.S. atomic spy Julius Rosenberg and his wife Ethel mentioned in Chapter 3, “Learning from Mistakes.” It also led to the unmasking of Alger Hiss, Klaus Fuchs, and Donald Mclean as Soviet spies.
The art of cryptography was essentially in a stalemate until the arrival of mechanical computers. With the important exception of the cumbersome one-time pad system, every cipher that could be applied using a paper and pencil could be broken using a paper and pencil.
The ability to automate the process of encrypting and decrypting messages allowed the use of ciphers that were not only much stronger than the paper-and-pencil schemes but could present almost any desired degree of difficulty to an attacker by building a big enough machine. Machine cryptography demonstrates the power of exponential growth. A small incremental increase in the complexity of the encryption machine can multiply the effort required for an attack many times. Two small increases gives the square, three the third power, and so on.
Modern computer ciphers generally use a large number expressed as a series of binary digits (bits) as a key. For a secure symmetric cipher, each additional bit in the key doubles the difficulty of breaking the cipher. If a 56-bit cipher takes a purpose-built computer a day to break a key, then a 57-bit cipher will take two days, a 59-bit cipher more than a week, a 61-bit cipher a month, a 65-bit cipher more than a year, and a 72-bit cipher a century. Computer security protocols generally use ciphers that have 128 bits, and the purpose-built computer would take approximately 13 billion, billion years, or about a billion times the age of the universe.
The German Enigma machine has become the best-known mechanical encryption system because of the work done by Alan Turing and his colleagues at Bletchley Park to break it during World War II. Intelligence from the Enigma decrypts provided the critical edge that allowed Britain to win the Battle of Britain and prevent Hitler’s planned invasion.
The Enigma machine consists of a keyboard with a series of lights mounted above (see Figure 10-4). To encrypt a character, the operator presses a key, and the corresponding encrypted character appears on the light board. The heart of the machine consists of a set of three or four rotors, which are metal disks with a sequence of electrical contacts on either side. Inside the disk, the contacts are wired so that each contact on the left side of the disk is connected to a contact at a different position on the right. The circuitry inside the machine connects the keys to the lights on the light board in such a way that the current flows through each rotor twice. Each time the operator presses the key, the rotors advance one position, in effect changing the code. The difficulty of breaking the code was further increased by a plug-board, which superimposed a fixed substitution cipher onto the varying substitution cipher implemented by the rotors.
The achievement of Turing’s team is all the more remarkable when it is understood that the Nazi confidence in the Enigma system was largely justified. The three-rotor Enigma has approximately 1023 different rotor and plugboard settings. This is equivalent to breaking a 76-bit cipher and would take the hypothetical purpose-built modern computer approximately 2,800 years to break.
The reason that the codes were breakable was that the machine had a small number of flaws that allowed the problem to be reduced to a series of smaller problems that could be solved separately.
Even so, breaking the Enigma codes required an unprecedented amount of computing power that was far beyond the capabilities of any mechanical apparatus and required the invention of the modern electronic computer to break.
A mechanical encryption machine similar in appearance to the Enigma is stolen from a Soviet Embassy in Istanbul in the second James Bond film, From Russia with Love, where it is called the Lector. Even though both Fleming and the KGB knew that the Enigma machines had been broken, it is quite believable that a Soviet embassy would have used a mechanical machine for low-sensitivity diplomatic traffic as late as the 1960s.
Let us return to the unbreakable one-time pad. The system is unbreakable, but only if you have a secure means of distributing the cipher stream to your correspondents. This means that the use of a one-time pad to secure diplomatic communications requires secure distribution of large quantities of cipherstream. A one-time pad might contain 25 rows of 15 numbers, 375 in all. Each time the embassy cipher clerk encrypts or decrypts a letter, a number is crossed off the pad. This paragraph contains 617 letters (not counting spaces), and encrypting it would require almost two pages from a pad. A busy embassy communicating large amounts of sensitive information could easily run through dictionary-sized quantities of cipherstream.
Distribution of cipherstream was a major headache for security agencies during the peak years of the Cold War even without enemy tanks outside their gates. Large numbers of young men were dispatched to visit world capitals with briefcases strapped to their wrists.
Use of one-time pads could only be afforded for the most sensitive communications. Bulk traffic was sent using cipher machines, which allowed a message of any length to be encrypted using a fixed-length secret key. This made the problem of key distribution much easier; even if the keys were changed several times a day, a single sheet of paper could list enough keys to last a month. But the problem was not eliminated; use of encryption was only possible if the parties had planned in advance.
The arrival of the minicomputer in the 1970s resulted in a dramatic rise in the amount of data being created, which in turn resulted in a rise in the quantity of data that needed to be moved securely. The rising demand for cipherstream was in particular felt by the British cryptographers at GCHQ. Transporting cipherstream to foreign embassies was requiring the British Navy to commit a large part of its remaining fleet to touring foreign ports engaging in that quaint diplomatic euphemism “flying the flag.”
This problem led a GCHQ cryptographer named James Ellis to propose a new type of cryptography system he called no-secret encryption. But it seems unfair to have to use a secret to encrypt a message; what we really want is a system where the information required to encrypt the message is public knowledge and the only information that needs to be secret is the key used to decrypt the message. It is easy to build a mechanical system that provides this property. I can put a letter in a post box even though I don’t have the key to open it. The problem of realizing a secure mathematical no-secret encryption scheme resisted solution for several years until it was solved in 1973 by Clifford Cocks.
The GCHQ system was developed in a world where use of cryptography was considered the exclusive prerogative of governments. No-secret encryption was a technology that might have changed the world but was instead kept a closely guarded secret, a mathematical oddity known only by a handful of cryptographers in Britain and the U.S.
Fortunately for the Internet, the principle of no-secret cryptography was rediscovered by Whitfield Diffie and Martin Hellman, who called their idea public key cryptography.[1] Diffie and Hellman proposed an encryption scheme with two keys: a public key used to encrypt the message, and a private key to decrypt the message that the holder would keep secret.
To send an encrypted message to a person using public key cryptography, you could look up his public key in a directory that looked like a telephone book with very, very long telephone numbers. If the directory was accurate, the message could only be decrypted by the intended recipient, who would be the only person with access to the secret private key. Like Ellis before them, Diffie and Hellman were unable to realize a scheme that had all the properties they proposed for a public key encryption scheme known, but they did come up with a system that comes very close, known as Diffie-Hellman, which allows two people to use their own private key in combination with the public key of the other to securely create a common cryptographic key (see Figure 10-5).
No-secret cryptography had little effect on military communication until after its reinvention as public key cryptography revolutionized the academic field. Diffie and Hellman clearly defined a mathematical challenge unlike any before it, to discover a problem that was
Easy to compute in one direction (that is, it should be easy to encrypt the message)
But very hard to compute in the reverse direction (that is, it should be difficult for an attacker to decrypt the message)
Unless the person had available a particular piece of information that made it easy to compute in the reverse direction (that is, it should be easy for the intended recipient to decrypt the message using the private key)
Many mathematical puzzles are easy to create but hard to solve. If you choose two prime numbers at random, you can multiply them using a pocket calculator in a fraction of a second. But reversing the process (factoring) takes a lot more effort. If the numbers chosen are large enough, factoring would take the largest computers ever built millions of years.
In 1977, Ron Rivest, Adi Shamir, and Len Adleman, three professors at MIT, used the factoring problem to create a public key cryptography scheme known as RSA after the authors’ initials. RSA is the de facto standard public key algorithm in use today securing e-commerce transactions and the chip-and-pin credit cards used in Europe.
Public key cryptography uses different keys for the encryption and decryption operations. For this reason, it is often referred to as asymmetric key cryptography. Traditional cryptography, in which the same key is used to encrypt and decrypt, is known as symmetric key cryptography.
Besides the use of two keys instead of one, there are two other important differences between asymmetric and symmetric key cryptography. The first is that asymmetric keys must be much longer to achieve the same degree of security as symmetric keys. Using current techniques, breaking an RSA key of 1024 bits requires approximately the same degree of computational effort as breaking an 80-bit symmetric key.[2] Although this has in the past generally been considered to provide an adequate degree of security, the use of 2048-bit RSA keys is greatly preferred, which provides a more comfortable safety margin equivalent to 112 bits in a symmetric scheme. Achieving a level of security equivalent to a 128-bit cipher requires a 3072-bit key.
The second important difference is speed. A moderately fast PC with a 2MHz Pentium 4 processor can encrypt or decrypt a stream of data using AES, the standard single key (symmetric) cipher, at 60Mbps (megabits per second).[3] This is faster than the typical computer can read information from a disk drive. The same machine takes about 30 milliseconds to perform a single 2048-bit RSA decryption operation. That means it takes the machine about the same time to perform one 2048-bit RSA operation or encrypt the entire text of this book using AES.
Encrypting an entire book using RSA would be completely impractical without special-purpose hardware designed to perform RSA calculations very quickly, and the result could only be decrypted by another computer equipped with special hardware.
To avoid the need for special hardware, we combine the use of symmetric and asymmetric cryptography to get the best features of both—the speed of symmetric key cryptography and the flexibility of public key cryptography. We do this by first encrypting a document under a randomly chosen key called a session key. Then we encrypt the session key under the public key of each intended recipient.
Having described the invention and rediscovery of public key cryptography, it is time to remember that throughout this book, we have identified authentication rather than confidentiality as our primary security concern. Unless we get authentication right, we cannot solve the confidentiality problem, because we could end up encrypting the data for the wrong person’s key.
In e-mail phishing, the attacker gains access to confidential information (the credit card number) by impersonating the bank. To block this type of attack, we need to be able to securely authenticate messages from the bank.
What we need is a cryptographic system that allows the sender of a message to add a “digital signature” to the message such that
The signature can only be created by the sender of the message.
The signature can be verified by any person receiving the message.
The verification process allows any modification of the message to be detected.
The RSA public key cryptography scheme can also be used to create a digital signature (see Figure 10-6). A digital signature is a blob of data added to the message that is created using the private key and verified using the public key. Any modification of the message will cause verification of the signature to fail.
As with public key encryption, a practical implementation of an RSA digital signature scheme requires the public key encryption scheme to be combined with a faster cipher that can be performed at high speed. This is called a message digest function. Because all we want to do is to authenticate the message, the message digest does not need a key. The message digest takes all the bits in our document, applies what amounts to a “digital shuffle,” and emits a fixed-length string of 160 or so bits of data.
A message digest function is sometimes referred to as a one-way function because a good message digest is easy to calculate in one direction but prohibitively difficult to calculate in the opposite one. Unlike a public key cryptography system, there is no private key that allows the holder to take a shortcut.
Passwords provide a paradoxical form of authentication. If Alice knows the password, then she can authenticate herself to Bob by telling him the password. But this only works if Bob also knows the password. If Alice tells Mallet the password, mistaking him for Bob, it is no longer secret, and the whole system collapses.
Public key cryptography provides a convenient and secure method of authentication, where Alice can authenticate herself to anyone at all using her private key without ever revealing it.
This particular property of public key cryptography makes it the queen of authentication techniques. It is quite likely that you already carry one or more private keys around with you today without even knowing it. If you have an American Express Blue credit card or a card issued by a European bank, there is a private key in the chip hidden beneath the gold contact pads. Most cell phones have a private key embedded in either the phone itself or a chip that is inserted into the phone before use.
A true smartcard has a microprocessor embedded in it that performs all the public key cryptography operations involving the private key. The private key cannot be read using ordinary techniques, although it is possible for a well-funded attacker equipped with an electron microscope to obtain it from the card.
The main drawback of using smartcards for Internet authentication is that few computers come with a reader. If every computer keyboard had a smartcard reader, those readers could replace passwords, and credit card numbers and the phishing problem would be eliminated.
Fortunately, smartcard technology is now becoming available in a form factor that plugs directly into a standard USB port. These smartcards are similar in size to a door key and are designed to be carried on a key fob (see Figure 10-7).
Public key cryptography provides an elegant mathematical solution to a precisely stated problem. She is a seductive mistress, and it is easy to fall in love with her beauty and believe that every security problem can be reduced to mathematics until the real world intrudes to remind us forcefully that she is unattainable.
I am reminded of the phrase “the crystalline purity of logic” that Wittgenstein used in Philosophical Investigations when he realized that language could not be reduced to pure logic. The philosopher continued, “We have got on to slippery ice where there is no friction and so in a certain sense the conditions are ideal, but also, just because of that, we are unable to walk. We want to walk: so we need friction. Back to the rough ground!”
To secure e-mail against phishing attacks, we must do more than make use of cryptography possible; we must make it ubiquitous and accessible. A digital signature does not tell a consumer that an e-mail has come from a bank unless every single e-mail from that bank is signed, and this information is conveyed to the consumer in a manner that is effective, unobtrusive, and unforgeable.
Cryptography is a key tool of network security.
It is only one tool, and it is easy to be overconfident.
Symmetric ciphers have the following characteristics:
They use the same key to encrypt and decrypt.
They are fast but require a key distribution mechanism.
128-bit ciphers offer a sufficient degree of security for most purposes.
Public key cryptography (asymmetric cryptography) is characterized by the following:
It uses two keys: public and private.
Public key is used to encrypt; private key is used to decrypt.
Private key is used to sign; public key to verify a signature.
It is slow, but it can be used in a hybrid system where public key cryptography is used for key distribution and symmetric cryptography is used for the bulk cipher.
In the RSA scheme, 2048 bits is a preferred size; larger is better.