Attacks Against the Previous IEEE 802.11 Security
Mechanisms
Unfortunately, all of the
security mechanisms defined in the 1999 version of the IEEE 802.11 standard have
been proven ineffective. The problems range from issues with the lowest
primitives up to the high-level protocols used.
Confidentiality
There are numerous flaws in both RC4 as used in WEP and in WEP
itself that indicate that WEP provides no effective protection at this
point.
RC4 Problems
Since 1994, researchers have identified a series of small flaws
in RC4, none of which resulted in a practical attack. More recently, however,
Itsik Mantin and Adi Shamir described a reliable distinguisher for RC4
ciphertext. While this flaw was not a break, it identified a statistical bias in
the second output word of RC4's pseudorandom generator. Shortly thereafter,
Scott Fluhrer joined Mantin and Shamir in authoring a paper that did result in a
practical and complete break (key recovery) of RC4 as used in WEP, and their
attack has subsequently been implemented and released in several open source
projects.
Mantin and Shamir Bias Flaw
In a paper presented at the Fast Software Encryption (FSE) 2001
conference, Mantin and Shamir (2001)
described a bias in the second word of the pseudorandom stream produced by RC4:
Zero occurs as the second word with twice the expected probability (1/128
instead of 1/256) in what should be a pseudorandom sequence with all values
equally likely. While this may seem a minor problem, it allows ciphertext
produced by RC4 to be easily distinguished from ciphertext produced with random
cipher systems and it lays the groundwork for a much larger result described
below.
Fluhrer, Mantin, and Shamir Key Schedule Attack
Several months later, Scott Fluhrer and colleagues found a
devastating attack against a class of keys used in RC4 that leak information
about the secret key. Unfortunately for WEP, the class of weak keys found by
Fluhrer, Mantin, and Shamir were exactly those used by WEP (Fluhrer et al., 2001).
Fluhrer and his colleagues found that when RC4 is used with an
initialization vector appended or prepended to the secret key, certain values of
the IV produce a weak key. An adversary who collects enough of these weak keys
passively through eavesdropping can recover the secret key in linear time with
respect to the key size; in other words, an attack against 104-bit WEP is only
slightly more difficult than an attack against 40-bit WEP. Furthermore, the
attack relies only on the first byte of output from the RC4 pseudorandom
generator, as determined by the equation: S[S[1] + S[S[1]]], where S is the S-box used in the implementation
of RC4.
In most cases, determining the first pseudorandom byte would be
difficult because of the variability of the underlying plaintext. But because
WEP is used in an IP data-networking environment, the first byte of the vast
majority of packets is 0xAA, a value in the LLC header. Thus, we have known
plaintext and can easily recover the first pseudorandom byte.
Recovering the secret key now involves passively collecting
enough packets of the form <keybyteindex+3, 0xFF,
N>, where keybyteindex is the index of
the secret key we are trying to recover and N is
any byte value. This form of packet lets us guess the true key byte with an
accuracy of 5%, and the trick is to collect enough such packets to ensure a
correct guess. Fluhrer et al. estimate that approximately 60 such packets are
required, and Stubblefield et al. (2002)
found that 256 packets always selected the correct key byte. This process is
iterated until all key bytes are determined.
Fluhrer et al. estimated they would need approximately four
million packets to recover a 104-bit key. However, Stubblefield et al.
implemented the attack and found they needed between four and six million
packets to recover each key byte in an unoptimized attack. Stubblefield also
optimized the attack so as to reduce the number of required packets to one
million. Recovering this quantity of packets depends on the network load and can
range from less than one hour in a moderately to heavily used network (300 or
more packets per second) to several hours in a lightly used network.
Other WEP Problems
In addition to the problems with RC4, WEP itself has a number
of flaws running the entire range of field elements in the protocol.
IV Space
WEP uses a pitifully small 24-bit IV space (224 or
16,777,216). Assuming a moderate to heavy network load, this
space is exhausted within a few hours and creates an IV collision—that is, the
same <IV,K> pair is used to encrypt two
different plaintexts. When multiple hosts share the same encryption key in a
network, the time between collisions is obviously much shorter.
The consequence of an IV collision is significant with a stream
cipher. Because of the linearity of the XOR combining function, deriving the
underlying plaintext is much easier.
Given two ciphertexts produced with the same <IV, K> pair:
C1 = RC4(IV,K) 
P1
C2 = RC4(IV,K) P2
XORing the two ciphertexts together removes the pseudorandom
stream generated by RC4 and produces the XOR of the two plaintexts (Borisov et al.,
2001).
C1 C2 =
(RC4(IV,K) P1)
(RC4(IV,K) P2)
C1 C2 =
P1 P2
The XOR of two plaintexts makes it significantly easier to
recover the two plaintexts because of their well-known structure.
Replay Attacks
The WEP protocol provides no form of message authentication;
thus, it allows intercepted messages to be replayed or sent again without
modification (Borisov et al., 2001). While
replaying packets will not permit an adversary to become a peer on the network,
it can result in a significant denial-of-service attack and can also be used to
reduce the cost of other attacks. This lack of message authentication also
permits attackers to create man-in-the-middle attacks.
WEP Message Modification
WEP uses a 32-bit CRC that is a linear function of the
plaintext. Although WEP's RC4 encryption covers the ICV, the stream encryption
also uses a linear combiner, XOR. As a result, we can manipulate an intercepted
packet by flipping bits in the data and CRC portions of the packet to create a
new—but still valid—packet with a different plaintext than the original (Walker, 2000;
Borisov et al,
2001).
Recall how WEP produces ciphertext C by XORing the plaintext with the key stream. The
attacker's goal in this attack is to produce a new ciphertext C´that decrypts to a new valid message with a valid
ICV. Unfortunately, the attacker can accomplish this without knowing the value
of the secret encryption key. Because both the RC4 encryption and the ICV are
linear in nature, the attacker can modify an intercepted message by XORing the
appropriate bits in the message portion of the ciphertext, and then calculating
a new CRC of the changes and XORing this new CRC with the CRC portion of the
datagram. The following equations, taken from Borisov et al. (2001), show
this process mathematically.
C' = C < D, CRC(D) >
C' = RC4(IV,K) < M,CRC(M) > < D, CRC(D) >
C' = RC4(IV,K) < M D, CRC(M) CRC(D) >
C' = RC4(IV,K) < M', CRC(M D) >
C' = RC4(IV,K) < M', CRC(M')
>
The above derivation works because the WEP CRC is linear—that
is, CRC(M) CRC(D) = CRC(M D). An example message modification is shown in Appendix B.
An Active Implementation of Fluhrer, Mantin, and
Shamir
The research literature has not discussed the possibility of
using active measures to speed the process of obtaining enough packets for a
successful Fluhrer, Mantin, and Shamir attack. Obviously, active measures only
make sense on lightly loaded networks.
The two possible approaches are simple. In the first and
easiest approach, traffic analysis identifies an address resolution protocol
(ARP) request packet. The ARP request is replayed continuously (remember WEP has
no replay protection) until it collects enough packets from the ARP responses to
determine the RC4 key. The second approach involves slightly more work. Here, we
wait until we see an ARP request message and build upon it until it provides
enough known plaintext to recover an adequate pseudorandom stream to forge
Internet Control Message Protocol (ICMP) ping packets (Petroni, 2003). Ping packets
are forged and the responses collected until the RC4 key can be collected.
Experimentation indicates that approximately 450 ping packets
and replies can be sent per second between a station (STA) and an AP, and thus
we can collect the required one million packets in approximately thirty-seven
minutes. Of course, this attack fully loads the network, but if done during
off-hours, it would likely remain unnoticed.
Several vendors, however, are now filtering most of the Fluhrer
weak IVs in their firmware. This prevents the attacker from collecting enough
weak IVs to recover the WEP secret key, but it reduces the cost of a previous
attack against WEP, as described next.
An Inductive Chosen Plaintext Attack
This attack leverages several poor design aspects of WEP. The
first is the lack of replay protection, the second is the nature of the CRC
used, and the third is the fact that WEP is a stream cipher rather than a block
cipher. The attack involves two steps (Arbaugh, 2001 and Petroni,
2003). The first step, or base phase, involves recovery of an initial amount
of pseudorandom stream from traffic analysis (eavesdropping). The second step,
the inductive phase, then forges messages with the recovered pseudorandom until
a dictionary of all IVs is created.
Base Phase
During the base phase, we need to collect enough pseudorandom
stream for a given IV so that we can begin to forge packets. The commonly used
Dynamic Host Control Protocol (DHCP) makes this easy. We simply wait until we
see a DHCP discover or request message that provides us with a base of known
plaintext. This base is 38 bytes in length, composed of the following known
elements:
|
|
6 bytes |
|
|
20 bytes |
|
|
8 bytes |
|
|
4 bytes |
This provides us with a total of 38 bytes of pseudorandom
stream, which is sufficient to forge ICMP echo request packets, also known as
ping packets. We use a ping packet because it elicits a response from the
targeted host, and it permits an arbitrary amount of data to be appended to the
echo request.
Inductive Phase
Once we've recovered enough pseudorandom stream, we can begin
the inductive phase. The inductive phase has two parts: recovery of the maximum
transmission unit (MTU) and building the dictionary.
MTU Recovery
We need to recover a full MTU of the pseudorandom byte stream
so we can recover a full MTU of the pseudorandom byte stream for every ping
packet transmitted. The method that we use is the most complicated aspect of
this attack, and it leverages the fact that the CRC provides redundant
information about the underlying plaintext and the fact that WEP is a stream
cipher rather than a block cipher. Our goal is to recover the MTU 1 byte at a
time by guessing the next byte, and waiting for confirmation that we guessed
correctly.
We begin by crafting a ping packet in a very specific fashion.
We start with the 38 bytes recovered in the inductive phase, and we set n = 38. A proper ping packet without any additional
payload is 34 bytes (38 bytes when the CRC or ICV is added), but we want to send
a packet of 39, or n + 1 bytes. We do this by
guessing the 39th byte and constructing the ping packet as shown in Figure 15.4.
We create a packet of n – 3
bytes (or 35 bytes—ping packet plus 1 payload byte). This is the data portion in
Figure 15.4. We next calculate the
CRC/ICV over this data portion, but we append only the first 3 bytes of the
result. Now, we XOR this data with the n bytes of
the pseudorandom stream, and prepend the IEEE 802.11 header and the appropriate
IV, which results in a packet of n bytes.
Finally, we guess the n + 1 byte and append it to
the packet. Now, we have the specially crafted ping packet. We transmit it, and
wait a small amount of time for a response. If we get a response, we know we
guessed the correct n + 1 byte and we can proceed
to recover the corresponding pseudorandom byte. If we don't get a response, then
we guessed incorrectly and we continue to try the remaining 255 byte
possibilities. Once we get a response, we need to recover the n + 1 pseudorandom byte, as shown in Figure 15.5.
Because the host we pinged responded with an ICMP echo response
packet, we know that the byte we guessed was the correct ciphertext byte for our
packet. We also know the corresponding plaintext byte—the fourth byte of the ICV
that we didn't use in creating the packet. We now XOR these 2 bytes together
(known plaintext with corresponding ciphertext), and we recover the n + 1 pseudorandom byte.
Now because we recovered the n +
1 pseudorandom byte, we continue this process (increasing n by one to recover the n +
2 pseudorandom byte) until we recover a full MTU—usually 1,500 bytes for
Ethernet.
Building the Dictionary
Once we've recovered the full MTU, we need to build a
dictionary of all of the 224 (16,777,216) possible IVs used. This
dictionary (assuming an indexed flat file) will be approximately 23.5
gigabytes—well within range of today's laptop computers.
The actual recovery of the pseudorandom stream for each IV
leverages the fact that the ICMP echo response returns exactly the same data
that was appended to the ICMP echo request. Thus, if we send a ping equal in
size to the MTU, we'll get a response of exactly the same size. But, it will be
encrypted with a different IV than the one in which we transmitted the IV.
Therefore, we once again have known plaintext (the data we appended to the ping
request) along with the corresponding plaintext. This permits the recovery of a
full MTU's worth of pseudorandom for the returned IV. To build the full
dictionary, we continue the above process until we have every IV.
Cost of the Attack
The cost of the inductive chosen plaintext attack depends on
how aggressive the attacker wants to be. We'll assume a moderately aggressive
attacker in our calculations so we can approximate worst case for the
defender.
In an implementation of the attack, the average time of
recovery for a single byte in the inductive phase was 1.7 seconds/byte, and the
average time to recover a full MTU (1,500 bytes) was 42.8 minutes. Once a full
MTU is recovered, we need to build the dictionary. A current implementation of
the attack recovers IVs at a rate of 11.5 msec/IV, or 53.7 hours to recover all
224 IVs with a single host—a fairly significant amount of time.
However, building the dictionary is embarrassingly parallel and the total time
to build the dictionary can be found by dividing 53.7 hours by the number of
attacking hosts. Thus, an attacker using eight different hosts in the attack can
reduce the time to around six hours—something to worry about, especially because
the time required is completely independent of the key size. In other words, it
takes approximately six hours to build the dictionary (or seven hours total) for
both 40- and 104-bit WEP keys.
Effects of Filtering IVs
A number of vendors are now filtering IVs to protect against
the multiple open source implementations of the Fluhrer et al. attack (see Chapter 16). The most
aggressive filtering reduces the IV space by 6 bits to 218
(262,144)—a significant reduction in IV space, and a significant reduction in
the overall time of the inductive chosen plaintext attack. The reduction in time
occurs only with building the dictionary so we still must take 42.8 minutes to
recover a full MTU. But now instead of taking over 53 hours to build the
dictionary with one attacking host, we can build the dictionary in 50.3
minutes—a serious reduction in time and the size of the dictionary shrinks
considerably as well.
Ironically, the countermeasure to one attack makes another
attack significantly better—better in some respects than the attack the
countermeasure was designed to prevent.
Access Control
While the 1999 version of the IEEE 802.11 standard does not
define a mechanism for access control, most implementations use MAC
address-based access control lists. In addition, a major vendor has implemented
a proprietary access control mechanism entitled Closed Network. This section
describes the significant flaws found in each.
Problems with MAC-Based Access Control Lists
In theory, ACLs provide a reasonable level of security when we
use a strong form of identity. Unfortunately, MAC addresses do not provide
strong identity for two reasons. First, an attacker can easily observe MAC
addresses because they must appear in the clear even when WEP is enabled.
Second, some wireless cards allow their MAC address to be changed via software.
As a result, an attacker can easily eavesdrop to determine valid MAC addresses
and program the desired address into the wireless card, bypassing access control
and gaining access to the network.
Problems with Proprietary Closed Network Access
Control
In most IEEE 802.11 wireless networks, the access point
broadcasts the network identity using a text string called SSID. This allows a
mobile device to search for specific networks by listening to broadcasts called
beacons. The idea of the closed network is to treat the network name or SSID as
a secret so the mobile device must have prior knowledge of the SSID before
connecting. In practice, security mechanisms based on a shared secret are
robust, provided the secrets are well protected when in use and when
distributed. Unfortunately, although the SSID can be hidden in the beacon, there
are several other management messages in IEEE 802.11 that contain the network
name in the clear. (The actual messages containing the SSID depend on the vendor
of the access point.) As a result, an attacker can easily sniff the network name
to determine the shared secret and gain access to the network. This flaw exists
even with WEP-enabled networks because management frames are not
protected.
Authentication
As previously discussed, the 1999 version of IEEE 802.11
provides only two forms of authentication. Obviously, the open method of
authentication provides no security as all stations are permitted to associate.
Unfortunately, although the shared-key authentication method was designed with
security in mind, it is not secure.
Shared-Key Authentication
An attacker can easily exploit the original IEEE 802.11
shared-key authentication through a passive attack by eavesdropping on one leg
of a mutual authentication. The attack works because of the protocol's fixed
structure, wherein the only difference between authentication messages is the
random challenge, and the weaknesses in WEP (Arbaugh et al., 2001; Arbaugh et al.,
2002). The attacker first captures the second and third management messages
from the authentication exchange. The second message contains the random
challenge in the clear, while the third message contains the challenge encrypted
with the shared authentication key. Because the attacker now knows the random
challenge P, the encrypted challenge ciphertext
C, and the public IV, the attacker can derive the
pseudorandom stream produced using WEPK, IVPR, with the
shared key K and the public initialization
variable, IV, as shown below:
The recovered pseudorandom stream, WEPK,
IVPR, is the same size as the authentication frame because all
the frame's elements are known: algorithm number, sequence number, status code,
element ID, length, and the challenge text. Furthermore, all but the challenge
text will remain the same for all authentication
responses. The attacker now has all of the elements to successfully authenticate
to the target network without ever knowing the shared secret K. The attacker requests authentication of the AP it
wishes to associate/join. The AP responds with an authentication challenge in
the clear. The attacker uses the random challenge text R and the pseudorandom stream—WEPK,
IVPR—to compute a valid authentication response frame body by
XORing the two values together. The attacker then computes a new ICV, as
described by Borisov et al. (2001).
Finally, the attacker responds with a valid authentication response message and
associates with the AP to join the network
Sections
Archive
Syndication
