Cracking Wi-Fi Protected Access (WPA), Part 1

Date: Mar 4, 2005

In this two-part series, Seth Fogie examines the internals of WPA and demonstrates how this wireless protection method can be cracked with only four packets of data. Part 1 outlines the details of WPA as compared to WEP and builds the foundation for Part 2, in which he describes in detail how WPA-PSK can be cracked.

Read Part 2 of this article.

WPA Overview

Since the turn of the century, wireless networking has grown from a very exclusive tech toy into a full-blown phenomenon. For less than $50, anyone who can plug in a toaster can essentially set up a wireless local area network (WLAN). The problem with this plug-and-play generation of users is that very few understand how their data is sent through the air, much less comprehend the associated risks. Even as I write this, an estimated 40–50% of all wireless users are not implementing any form of protection. On the bright side, this percentage is falling, albeit very slowly.

The security problem is exacerbated by the fact that early attempts at encryption were flawed. Wired Equivalent Privacy (WEP) was found to be vulnerable to various statistical weaknesses in the encryption algorithm it employed to scramble data passed over the WLAN. While attempts were made to correct the problem, it's still a relatively simple feat to crack WEP and essentially pull the password right out of the air. In addition, WEP suffers from other problems that make it unacceptable for use in any secure environment.

The wireless community knew early on that these problems existed. However, they also realized that it would take years until the standardized correction was designed and implemented into new hardware. In the meantime, millions of users needed reliable protection. The Wi-Fi Alliance stepped up to the challenge and created an interim "standard" called Wi-Fi Protected Access (WPA).

WPA did an excellent job of patching the problems in WEP. With only a software upgrade, it corrected almost every security problem either created or ignored by WEP. However, WPA also created new problems:

One flaw allowed an attacker to cause a denial-of-service attack, if the attacker could bypass several other layers of protection.
A second flaw exists in the method with which WPA initializes its encryption scheme. Consequently, it's actually easier to crack WPA than it is to crack WEP. This flaw is the subject of this article.

WPA Options

As indicated by its name, WEP serves to provide privacy. However, as I mentioned, its algorithms are flawed. WEP also doesn't include any support for authorization. To correct this problem, WPA has two main components:

The Temporal Key Integrity Protocol (TKIP) addresses the privacy concerns via enhanced encryption schemes.
The authentication component uses 802.1x and an authentication server to provide user-level access.

The authentication mechanism comes in two varieties, which is necessary because WPA has to address two very different markets: enterprise and consumer. The following list outlines the general security requirements for each variety.

Enterprise. Authorization, authentication, and auditing are all essential components for providing a secure resource to an enterprise user. As a result, it's possible to configure WPA to authenticate users, typically via a RADIUS server. (RADIUS is not the standard—just the most common way of implementing the standard.) During this process, the user obtains the primary master key (PMK), which is then used to set up the encryption algorithm used by TKIP. Because the PMK is derived as a result of the authentication process, there's no need for locally stored passwords. In addition, the authentication information is passed via an encrypted channel to protect it against eavesdroppers.
Consumer. WPA is not just an enterprise solution. It was also created to help secure the SOHO user. However, the consumer environment offers little justification for an authentication server. As a result, WPA had to include some internal method to create the PMK used to initialize the TKIP encryption process. This solution was created by using a pre-shared password that's previously configured in the access point and all nodes.

The attacks discussed in this article affect only the consumer version of WPA, known as WPA Pre-Shared Key (WPA-PSK). The enterprise solution is not susceptible to this particular attack, but that doesn't make it any less dangerous. With the widespread understanding that WEP is flawed, many SOHO users have switched to WPA-PSK without realizing the risks involved.

WPA Fixes

As previously mentioned, WPA accomplished its goal: Almost any legacy wireless equipment can be upgraded to meet WPA "standards" with little effort. This section provides a very general outline of the problems found in WEP, and what WPA did to correct them. Note that most of these fixes are specifically corrected by the privacy component known as TKIP.

Weak IVs and Collisions

The initialization vector (IV) value is used to provide each packet with a unique key (IV plus pre-shared key). This unique key provides a serious obstacle to any attacker, simply because each packet must be treated as a unique target. Cracking one packet's password only provides access to that one packet.

However, WEP's implementation of the IV is flawed:

The IV is only 24 bits. As a result, IVs are repeated every few hours. Therefore, over time, an attacker can leverage repeated IV values, known as collisions, to help gain access to the data.
WEP's algorithm is flawed. This flaw led to the widely known WEP cracking scandal that has surrounded wireless networking for years.

WPA corrected these problems in the following manner:

WPA increased the size of the IV to 48 bits, which provides at least 900 years of unique passwords and basically eliminates the problem of collision.
WPA alters the values acceptable as IVs. This fix allows WPA to use the same algorithm as WEP, but plugs the hole by controlling the IV values going into the algorithm. Finally, a new password is generated automatically every 10,000 packets. This is well below the threshold of even the most successful WEP cracking efforts and all but eliminates the threat of a statistical attack.

Integrity Check Value (ICV)

WEP uses an integrity check value (ICV) to ensure that packets are not corrupted during transmission. This integrity check has little to offer in the way of security, however. The algorithm is widely used and easy to fool.

To correct this problem, WPA incorporates an algorithm known as Michael that creates a unique integrity value, using the sender's and receiver's MAC addresses. However, Michael uses a simple encryption scheme that can be cracked using brute-force methods. To compensate for this issue, if Michael detects more than two invalid packets in under a minute, it halts the network for one minute and resets all passwords. But this arrangement opens the doors for a malicious attacker to perform a denial-of-service attack by purposefully injecting faulty packets; to accomplish this goal, however, the attacker must first work through several other layers of protection.

Forgery and Replay

WEP has no protection against forgery or replay attacks. Any attacker can inject any packet into a network. In addition, an attacker can reuse a captured packet in this injection. WPA incorporates protections against these attacks via the 48-bit IV value.

First, the IV is created using the MAC address of the sending network card and a sequential counter value. This technique stops forgery attacks because an attacker must know the MAC and IV values that are encrypted into the packet. Second, the IV includes a sequential counter (TSC). When a packet is received, its counter value must fall within an accepted range or it will be dropped. As a result, replay attacks don't work because the fake TSC probably won't be within the valid range.

User Authentication

WEP offers little in the way of authentication. It's possible to set up a shared authentication system, but enabling this method opens other security risks and is considered dangerous. To compensate, WPA includes support for authentication via 802.1x Extensible Authentication Protocol over LAN (EAPoL), generally with a RADIUS server.

As you can see, WPA has helped to increase the security available to wireless network users. Of course, this statement assumes that the WLAN owner knows about these technologies and uses them. Unfortunately, this is not often the case.

The Components of WPA-PSK

On the surface, WPA-PSK (the consumer version) looks and works much like WEP. The user sets up the access point by selecting WPA-PSK and enters a password or passphrase. He then does the same on the wireless device, resets the connection, and soon is securely surfing the Internet. And this is how it should be: simple, quick, and intuitive.

Ironically, WPA is anything but simple when you look at how it works behind the scenes. Not only does WPA-PSK include all the components and complexities of WEP (such as the KSA, PRGA, XOR, and ICV), but it adds other algorithms and technologies such as MD5, SHA-1, HMAC, PMK, PTK, and more. For more information about how WEP works, and doesn't work, review my article "Cracking WEP." The following sections focus only on the new components, which we'll examine closely to understand how they work. While this information may seem irrelevant, you have to understand the core technologies before you look at the cracking process.

Message Digest (MD5)

The Message Digest function is a widely used hashing algorithm that creates a unique digital signature based on the data input. The typical process is to pass a large file into the MD5 algorithm, which then creates a 128-bit "fingerprint." According to the specifications, no two MD5 hashes should be the same, and no MD5 value can be used to re-create the original data.

MD5 is fast and efficient and generally considered to be fairly secure. While collision flaws have recently been found within MD5 that affect its use as a reliable integrity tool in the future, MD5 is currently used to sign many types of files. For example, P2P programs, torrent files, JAR (Java) packages, and more are all validated via the MD5 algorithm.

Secure Hash Algorithm 1 (SHA-1)

The Secure Hash Algorithm 1 (SHA-1) is considered more secure than MD5. It works like MD5, but creates a unique 160-bit hash value based on the data input. The extra 32 bits indicate that SHA-1 is stronger than MD5; the assumption is that it takes more time to perform a brute-force attack on a longer hash value.

Hashing MAC (HMAC)

If you receive a message, how can you know for sure who it came from? The answer is found in a message authentication code (MAC), which generally combines a message and password via a block-cipher. The result is a small string that can be appended to the data to validate where it originated. Unfortunately, this process can require significant resources.

The Hashing MAC (HMAC) function borrows the speed and functionality of a hash algorithm and combines it with an authentication scheme. As a result, HMAC not only ensures data integrity, but provides a form of authentication. Let's take a closer look at the internals of the HMAC.

The following table describes the assumed and known values.

Value	Description
ipad	0x36 repeated 64 times
opad	0x5C repeated 64 times
K0	Pre-shared key buffered to 64-bytes with zeros
T	Text of message
H	Hash function (MD5 or SHA-1)

Here's how it works:

Buffer K to 64 bytes using zeros (K0)
XOR 64-byte K0 with 64-bit ipad value > K0 XOR ipad = K0i
Append text (T) to K0i > K0 XOR ipad, T = K0i.t
Hash K0i.t via MD5 or SHA-1 > H(K0 XOR ipad, T) = H(K0i.t)
XOR 64-byte K0 with 64-bit opad value > K0 XOR opad = K0o
Append #5 results with #4 results > K0opad, H(K0ipad.t)
Hash #6 results to create HMAC hash > H(K0opad, H(K0ipad.t))

Here's the complete algorithm:

H(K0 XOR opad, H(K0 XOR ipad, T)) > HMAC hash

This will produce either a 128-bit or 160-bit hash, depending on the hash function selected. The results can also be truncated to reduce the overhead. As you'll see shortly, the HMAC functions—and more importantly the MAC—play an important part in the WPA-PSK process.