Attacks on the Keys

The problem with keys in general is that there are so many ways to get at them. Let's take a simple case of a burglar who wants to break into a bank vault. The walls are thick steel and so the burglar has concluded that the only viable way in is through the vault door, which needs a key. What are the options? Well, here are a few:

• Find where the key is stored and steal it.

• Get a job in the bank and finagle a few moments of access to the key; make an impression to copy later.

• Point a gun at the manager and make him unlock the vault.

• Make lots of different keys and try them all.

• Pick the lock.

The list goes on, and a real burglar would have a few more to suggest as well. All of these attacks have an analogy in Wi-Fi LAN security, and by no means do they all involve clever cryptography. Let's get the most obvious one out of the way first. The simplest way to get a key is to look over the shoulder of a person as she enters a password or simply to ask a disgruntled employee to tell you. It is well known that thieves are able to observe and remember sequences of digits typed into a phone when a victim uses a calling card. This is a problem whenever you expose your key information to people. Humans are a weak link in security.

One solution is to keep the keys inside the computer and not visible to the human operator. The problem with this approach is that, if the computer is stolen, the key goes with it and the thief can get access by masquerading as the valid user until the theft is discovered. In general, the best protection comes from choosing good passwords and changing them regularly.

One-Time Passwords

A clever solution that avoids human weakness is the use of the one-time password. As the name suggests, the idea is that each and every time you log on or connect, you use a new password hence each password is only used once. In a typical case, the user has a credit card-sized gadget that displays a set of digits. The display changes once per minute to a new number. Back at headquarters is a special server, running off an accurate clock, which knows which number is being displayed by the card at any point in time. When the user logs on, she types in the number currently displayed and the server checks that it is valid. However, five minutes later, if the same password is entered, the server will reject it. The idea is that the password, if memorized, is of very limited value and the card stays with the user even if the computer is stolen quite a clever system.

One-time passwords incorporate a concept called liveness that is vital to good security. Liveness is simply the inclusion of something that changes in time so you can detect whether someone is using old (and hence probably copied) information.

Burying the Keys

If you try to hide the key information from the user, it is still vulnerable to eventual discovery by a sufficiently dedicated attacker. This is particularly true if the enemy has physical access to the equipment where the key is stored. For example, if the enemy can take a laptop home and work on it, and if he has sufficient technical skills, he can probably get the key, no matter how deeply it is buried in the software or hardware of the device. As an example, a large corporation in the United States had Wi-Fi wireless LAN adapters custom-made so the WEP key was programmed into the flash memory of the adapters before shipment and was never visible to the software on the computer. Despite this precaution, eventually someone was able to reverse-engineer the key value and publish it on the Internet. At that moment, the security of all the cards the company possessed plummeted to nothing.

Another example involves the cracking of the password on a mobile phone SIM card (Kocher et al., 1999). SIM cards are thumbnail-sized smart cards used in European and some U.S. cellular phones. The benefits of a smart card are its self-contained memory and built-in microprocessor. Therefore, the key can be stored inside and is not accessible from the outside. When you want to check whether a password is correct, you send it to the microprocessor in the card. The microprocessor does the check and simply tells you "correct" or "incorrect." It would seem an ideal solution because no one, including the manufacturer, can read the password once it leaves the factory. And yet attackers did find several ways to crack the passwords.

In one particularly clever approach, they obtained a copy of the program that the little microprocessor used. They had realized that the specific instructions that the processor executed depended on the value of the password. When the password byte presented was correct, it took one path; and when it was wrong, it took another. Astonishingly they realized that they could guess which type of instruction was being executed simply by carefully measuring the electrical current consumption used by the smart card. This meant they could try each byte of the password one at a time until they saw the card perform the "equal" test. It was like cracking a ten-digit combination lock when the lock beeps every time you enter one digit correctly. They cracked the code in very little time. Now, of course, smart cards have been modified so the instruction operation is not signaled by the current consumption, but this story once more illustrates the ingenuity of attackers.

A third example when burying the key failed concerns the protection of DVD movies. To stop people from reading DVD movies into their computers, the contents on the discs are encrypted. However, a DVD player obviously has to know the keys in order to decrypt and play the contents. Therefore, each DVD manufacturer has to sign up to very tough licensing restrictions, and those who have access to the encryption key must use special care to keep it safe. Did this work? No. As you might expect, only a couple of years passed before programs appeared that could decrypt a DVD. A Finnish teenager reverse-engineered a ROM chip from a DVD player and determined not only a valid key but also the previously unknown proprietary encryption algorithms. There is little the industry can do now because they can't change the key without making obsolete millions of consumers' DVD players. They have resorted to taking aggressive legal action against anyone who tries to distribute the program (Salkever, 2000).

One of the main lessons of these examples is the well-known security policy that you should change the master keys from time to time. We will discuss how often is appropriate in the later section on network configuration.

Wireless Attacks

Most of the things that have been said so far about protecting keys apply regardless of the type of security system you are using. They are not specific to wireless. Wireless, of course, introduces a whole new set of opportunities for attackers trying to get keys because it is so easy to access the data streams, even though they may be encrypted. Imagine a hacker ten years ago, before the advent of wireless LAN. The hacker would like to get access to the network inside a corporation. It's very risky because access to the building is restricted; and even after the attacker got inside, there would be limited time to sample the data. "Wouldn't it be great," the hacker dreams, "if I could get in there and install a radio transmitter that sent all the data outside, where I could pick it up in safety." Today, not only has the hacker's dream come true but also someone else (the corporation) has already bought the equipment and installed it! Life's not usually like that.

The problem for the attacker is that the data is encrypted and she needs the keys. Assuming you don't change the keys, she has as much time as she wants to capture sample messages and analyze them. What to do next?

First, let's look at a couple of assumptions we need to make about what the attacker knows. To do this, we need to introduce some common terms:

• Plaintext: The data before encryption this is what we want to protect

• Ciphertext: The encrypted version that the enemy can see over the radio link

• Keys: The secret value that is used to encrypt/decrypt the message

• Cipher: The algorithm and rules used to perform the encryption and decryption

To summarize, the ciphertext is created by processing the plaintext with the ciphersuite using the keys (see Figure 4.2). This process is sometimes written as a formula: Ciphertext = Cipher (Key, Plaintext).

Figure 4.2. Encryption Terms

Okay, coming back to our attacker. We know that she has a copy of the ciphertext because that can be snooped directly. We know that she doesn't know the key because getting it is her objective. What about the cipher and the plaintext?

One of the rules of modern cryptography is that you should assume that the attacker knows the algorithm used for encryption.^[4] Most attack methods rely on finding weaknesses in the underlying algorithm or in its implementation. If, however, the attacker does not know the algorithm, an attack is almost impossible. So it might seem that keeping the algorithm secret is a good idea. This type of thinking, also known as security by obscurity, has been adopted in some security systems. For example, the encryption algorithm used in most European cellular phones is a secret and may be different from one mobile phone operator to another. However, security experts feel that keeping the algorithm secret is a bad idea for (at least) two reasons:

^[4] This is known as Kirchoff's criterion.

• It is impossible to keep a secret forever, no matter how hard you try. People have to know the algorithm in order to implement it, and sooner or later someone will be bribed, get drunk at a crypto conference (yes, it could happen), or have their laptop stolen. Sooner or later, the secret will come out, and the bad guys might get the secret. That leaves all of us users vulnerable without knowing it.

• The other disadvantage of keeping the cryptographic algorithm a secret is that this approach doesn't allow legitimate researchers to look for flaws. If there is a flaw, it is better that a researcher finds it and alerts everyone before an attacker finds and exploits it. The weaknesses of IEEE 802.11 WEP were found and publicized in this way. The equipment manufacturers may not be pleased by such publication. They tend to argue that it is better to keep flaws quiet and fix them in the background. However, this is a dangerous approach you can be sure that if only 1% of people know about the flaw, the hacker community is included in the 1% along with the manufacturers. So by publication, the public is well served.

So, now we are assuming that the attacker knows the ciphertext and the cipher. Does she have the plaintext? This might seem like a silly question because if she has the plaintext, why does she need to crack the code at all? However, consider that the objective is not to crack a single message; it is to get the keys so every message can be read. The hacker may know the plaintext of a single message and use that to attack the keys. So let's ask that again could the enemy get a sample of the plaintext?

In fact, there are quite a few ways in which this might be done. The first way has already been mentioned: protocol headers. In IEEE 802.11, the MAC header is not encrypted, but all the rest of the message is (for more discussion, see Chapter 5). If you are using a protocol such as TCP/IP, this means that the header portion of the TCP/IP message is part of the plaintext that is converted to ciphertext. The danger is that the header always occurs in the same place (at the start of the packet) and that some of the fields have fixed values, or values that can be easily guessed. This means that an attacker immediately has some knowledge about the plaintext. Furthermore, some IP messages are of a known format, such as DHCP discover messages used in assigning network addresses. These are encrypted but can be identified from their length. In these cases, an attacker might correctly guess the entire plaintext.

It gets worse! If a person is accessing a Web site, and the attacker can guess which Web site, he can get the plaintext just by going to the same site. Suppose that someone goes to a popular news Web site. The home page is downloaded and sent encrypted across the wireless link. If the attacker can correctly guess which frames are which, he has the plaintext as well as the ciphertext. Guessing which frames are which is not as hard as you might think because the number of bytes in certain parts of the home page, such as pictures, provides a clue. The last method for getting plaintext is the simple approach of sending e-mail. If an attacker knows the e-mail address of a user at the target, he could send the user a message that at some point might be read. The attacker has a chance to identify when his message is read from the length. Alternatively, the e-mail might persuade the user to click a link to the home page of a Web site that the attacker knows.

Because there are so many ways for attackers to guess or obtain samples of plaintext, we have to assume that they can obtain all three components: the ciphertext, the plaintext, and the cipher. Once they have all three, they can start an attack on the keys.

Attacking the Keys Through Brute Force

The first thing anyone thinks about when it comes to working out the keys is the brute force attack. We'll look at this because the statistics are fun. Basically, the brute force method means that an attacker tries every possible key until he finds a match. Given that he knows the ciphertext and protocol, he would start with a key value of all zeros, decrypt the message, and see whether it matches the plaintext (or any fragments he has). If he keeps adding 1 to the key value, in principle, he will sooner or later hit on the right key because all possible keys will have been tried. Well, "sooner or later" is probably "later or never" in any real encryption system. In fact, if an attacker felt lucky enough to stumble on the key this way, he should buy a ticket for the state lottery. The odds of winning are considerably higher for the lottery.

The time taken for a brute force attack depends on the key size, or more correctly the key entropy (see Chapter 2). This is one of the reasons that government export controls tend to be set according to key length. For example, it used to be that you could not export any security technology from the United States with a key length of more than around 40 bits. This was one reason why in the original IEEE 802.11 standard, WEP used a 40-bit key.

To crack a 40-bit key using brute force, you would, on average, have to try 2³⁹ times,^[5] which equals 550 billion different keys. That's a big number, but it's not impossible. Say you have a supercomputer that can conduct one test per microsecond; you could crack the key in about a week.

^[5] The total number of combinations is 2⁴⁰ but on average you would only have to try half of them before finding the right one. Hence 2³⁹.

Because the 40-bit key is crackable, many security systems use larger keys 128 bits is common. In an attempt to strengthen security, some wireless LAN manufacturers brought out IEEE 802.11 systems using 104-bit keys, a length that was eventually adopted as a de facto standard. Most Wi-Fi systems support 104-bit keys, although strictly this has never been part of the IEEE 802.11 standard. The use of a longer key really renders brute force attacks completely ineffective, assuming the underlying cryptographic algorithm has no weaknesses. Let's suppose supercomputers become faster and we can try a hundred keys in a microsecond. With a 104-bit key, you would still need (on average) 3,200,000 billion years to find the right key. Yes, 3 million billion years and if that doesn't put you off, then you must be an avid lottery player. If you want to check the calculation yourself, here is the formula:

Ave Time = 2¹⁰³ / (num tries per sec) / (num secs per year)

Dictionary Attacks

Given that you can so easily defeat brute force attacks by adding a few bits to the key, any attacker with an IQ in the double digits will look for another approach. Here's the idea: Instead of trying every possible key, try only those keys that you think the user is likely to use. For example, the attacker could assume that the key is made up entirely of letters and numbers, as is typical for user-chosen passwords. As we discussed in Chapter 2, this reduces key entropy. A 104-bit key is now only as effective as a 78-bit key because only 6 bits of every byte are used. However, 78 bits is still uncrackable using brute force so the attacker must narrow down further. This approach to reducing the number of keys to test brings us to the idea behind a dictionary attack (Bishop, 2002; Salkever, 2000).

In a dictionary attack, the enemy uses a huge dictionary, or database, containing all the likely passwords. This will certainly include every word in the English language and may contain other languages as well. It will contain thousands of place names and proper names. It will contain words extracted from every street address in the United States (for example). Every name registered in the phone book, including first and last names, will be there. Every common pet name, strings of digits for every zip code, the date of every day in the year, and on and on.

The creation of such a database might seem like a formidable task, but the hacker community shares material, and bit by bit more data is added to the dictionary. Of course, in the end there will be millions of entries in the dictionary but remember that the enemy is reducing the key space from multiple gazillions, so getting it down to a few million is a real advantage.

With such a database, if the enemy can take home a sample of ciphertext and plaintext and leave it crunching away, the password could be cracked in a few days rather than a few billion years. The availability of such attack dictionaries explains why security managers want users to define passwords that use both upper- and lowercase (in unexpected places), and to insert digits or other strange characters. The attack works only against human-readable passwords or keys derived from such passwords in a known way.

Certain security protocols are more susceptible to dictionary attack than others. It depends to some extent on how the master password, selected by the user, is applied to the encryption process. For example, a password such as "Vesuvius" would easily be discovered by a dictionary attack. However, if the key used for encryption were derived from "Vesuvius" through a number of processing steps, dictionary attacks would not be easy. Consider the following: A user has chosen the password "Vesuvius". But before the key is used, the letters are swapped around in a known way to give "svsuieVu". This new version is used for the key instead. Both ends of the link know how to swap the bytes around, so it is not a problem for the friendly devices; but the letter-swapping will foil a simple dictionary attack. Of course, if the enemy knows the rule for swapping the letters, he can build this rule into the attack, so you could arrange to use a different swapping pattern depending on some other information known to both ends of the link. Swapping the bytes is a simple example and not a practical secure method. However, there are much more sophisticated ways to obscure the passwords before use, some of which are used in the new IEEE 802.11 security protocol (see Chapter 10). As a result of such key derivation, most modern security systems are not susceptible to dictionary attack.

Algorithmic Attacks

If the enemy cannot mount a brute force or a dictionary attack, another approach is to try to break the algorithm that is, to try to find a flaw in the way the encryption is performed that might expose the key value. We will see later that this was the successful attack made on WEP. It is difficult to describe these algorithmic attacks generally because they depend so much on the algorithm and understanding the weaknesses often requires that you are a cryptographic expert. However, there is a straightforward analogy with safe breaking.

In many B movies involving safe breaking, the master criminal is seen with a doctor's stethoscope, listening to the front door of a large safe and carefully turning the dial. When we were kids, we had no idea why anyone would do that and assumed that the criminal was seeing whether the safe was sick and hence easy to break into. The use of the stethoscope was never explained, as if the movie producers assumed all viewers were master safecrackers and would know what was going on. Years later, we realized that the purpose was to try to find one digit of the combination at a time by listening to faint clicking noises coming from the levers inside. This is a prime example of attacking the algorithm. The safecracker knows how the mechanism (algorithm) works and knows that it leaks information about the combination due to the noises. In particular, it leaks information about one digit at a time. By exploiting the leak one digit at a time, the combination is discovered. Furthermore, the time required goes up only in proportion to the number of digits, whereas the difficulty of a brute force attack goes up exponentially with the number of digits.

The algorithmic style of attack is very similar to that used against WEP. A weakness in the algorithm allows one byte of the key to be attacked at a time. Although it takes a while to crack each byte of the key, the total time is proportional to the number of bytes. This means that it is only slightly more difficult to crack a 104-bit key than it is a 40-bit key.

Successful attacks against the algorithm are frightening because, once the method is discovered, it is usually easy to build automatic tools to find out the keys. And, as has been observed, after the keys are discovered, your only chance is detection of the intruder.