Wireless Security

By: Chris Grier, Mike Perry, and Andy Washington
[ Problem - Research - Implementation - References ]


Problem

802.11 networks are notoriously insecure. The encryption algorithm has been broken, authentication is nonexistent, access control is circumventable. The protocol is in a sad state of affairs.

Our project is to study current 802.11 security and weaknesses, and investigate current proposed changes to the protocol to determine if these changes do in fact address the current security weaknesses, and to determine if they introduce any vulnerabilities of their own.

Given time and equipment, it would be useful to investigate link-layer solutions, such as VPN's, etc. But this aspect of the project is looking time and equipment-prohibitive. As such, we focused the majority of our attention on the RC4 encryption algorithm used in WEP.

Research

  1. Overview of Protocols
  2. Packet Format
  3. Existing 802.11 Security
  4. 802.11 Security Extensions

Our approach is to gather as much information about the 802.11 protocols and corresponding encryption algorithms as possible. From there, we may implement some of the known attacks in an attempt to demonstrate an improved bound is possible. We will also be reviewing RFC drafts and proposals for these protocols.

802.11 Protocols

[
802.11a - 802.11b - 802.11g ]
802.11a
With rates topping out at 54 Mbit/second, 802.11a is the top of the line for the industry currently. It has great interference prevention and multiple channels. However, due to more expensive electronics and higher power consumption, it is not the standard.

802.11b
With good power consumption levels and error correction, 802.11b is the standard for WiFi access. However, it is only capable of transferring data at a rate of 11 Mbit/sec, making it ill-suited for high bandwidth applications.

802.11g
The successor to 802.11b, 802.11g is built to combine the best of both A and B. With A's data transfer rates and B's power consumption, range and error correction, 802.11g is the WiFi of the future. It rolls out in the middle of 2003.

Packet Format


Despite the fact that these three protocols operate at two different frequencies and at different data rates, they all share a common packet format for MAC. Unfortunately, this packet format is exceedingly complicated, consisting of 3 different types of packets with 25 subtypes and 3 different possible header sizes, not counting LLC encapsulation and WEP packet framing. This has lead to criticism that the excessive complexity of 802.11 headers causes significant
degradation in throughput.

Luckily, for our project, we are primarily concerned with only the packet format for WEP'ed traffic, which can take on only one of two formats.

Existing 802.11 Security

Authentication

802.11 provides standard security measures to authenticate, which include Open, shared key, and shared secret (such as an SSID).

As you can see, the methods that 802.11 has for authentication are all flawed and not acceptable as real forms of authentication for a user and a network. Any user can authenticate on a network, and the user usually has no way to ensure the access point that they are authenticating with is the desired one or an attacker. Some vendors have attempted to fix the authentication problems, although even some of their implementations have some problems.

Wired Equivalent Privacy (WEP)

WEP uses a 64 or 128 bit key to encrypt every packet with RC4. This key is constructed from the contactination of an 24 bit IV (initialization vector) and a 40 or 104 bit WEP key. The IV is sent in the clear with the packet. The ICV (Integrity Check Value) is a 4-byte checksum computed with the CRC-32 algorithm appended to the end of every packet. It is also encrypted.

Relatively weak encryption, WEP suffers from several problems in design and implementation that makes it vulnerable to security breaches. First, WEP has key problems. There is no key management incorporated in WEP, so keys are over-used and ill-constructed. Each piece of equipment in a WLAN must be re-keyed individually, making a key's lifetime enormous. Also, a 40 bit key can be brute forced in about a week, making it much too short.

Second, the IV is extremely small. With only 2^24 values (16,777,216), IV reuse becomes an issue. An attacker with an IV can use it to forge packets or decrypt subsequent transfers. WEP does not specify how the IV is chosen, so IVs are reused regularly. With two packets, the cipher stream can be discerned. With a regular return packet, an attacker can also decode the cipher stream.

Third, CRC-32 is a poor choice for an encrypted checksum. It utilizes a linear progression, which makes it very easy to spoof, and therefore, makes it easy to spoof regular packets. Furthermore, this checksum is computed on the plain text data. This makes it easy to mount dictionary attacks against the WEP key by attempting to decrypt packets with a guessed key and then checking to see if the checksum is valid.

Fourth, weak keys in RC4 are apparent via the IV values. 9000 of the 16 million IV values are tags for weak keys. By gathering weak keyed IV packets, an attacker only has to gather data for a short time and try a few keys to gain access to the network. In fact, the proportion of weak IVs rises with the size of the key, so larger key lengths are even easier to break.

Fifth, authentication messages are easily forgeable. By monitoring a challenge-response to the WLAN, an attacker can discern the cipher stream and adapt to any further challenges to his access.

Without knowing or attempting to determine the WEP key of a network, an attacker can do many other malicious things to other users traffic.

Packet Injecting - If an attacker were to determine the plain text of a single packet the attacker could then use the RC4 cipher against itself to create new packets, and have them be accepted by the network. To validate packets the access point decrypts and checks the CRC. The CRC tells the AP if the packet payload has been modified in transit. Since the attacker can encrypt his own packet (by xoring the plain text that he knows with the cipher text, and then again with the plain text he wants to encrypt) the attacker can also generate the CRC. Thus the attacker can have any packets he wants enter the network and be accepted by the AP without knowing the WEP secret key.

Decrypting without a key - Another attack that involves not knowing an entire packets plain text, is done through guessing headers, and other select parts of information. With this attack, the attacker adjusts the packet destinations without decrypting the packet to reroute to a different destination that he controls (A different type of man-in-the-middle attack). The packets arrive un-WEP'ed and readable by the attacker. This is mainly useful for clear text transmissions, such as telnet, and HTTP traffic. If a user were to have a vpn client or use ipsec for secure communications, then the effectiveness of this attack would be severely decreased.

Other attacks include the attacker posing as a AP, and performing a type of man in the middle monitoring of all network traffic.

As you can see, WEP has quite a few security holes that makes it a poor choice for hardened WLAN security.


802.11 Security Extensions

[
802.11x - WPA - 802.11i ]
802.11x
A system for just authentication, 802.11x is the building block for all future 802.11 security measures. The handshake works as follows:
  1. As soon as the user steps into an 802.11 enabled area, the WAP(Wireless Access Point) sends a "Request - Identify" packet to the user.
  2. The user responds with a "Request - Response" packet that is forwarded to the authentication server.
  3. The authentication server (most times a RADIUS or Diameter server) sends back a challenge, encrypted, to the WAP.
  4. The WAP reforms this challenge to send it to the user.
  5. The user responds, and this packet is forwarded to the authentication server. (Only strong mutual authentication for wireless traffic. Also, the number and type of authentication varies based on the system)
  6. The authentication server determines success and sets permissions via the WAP appropriately.

Wi-Fi Protected Access (WPA)
An interim solution until 802.11i can be fully implemented, WPA is still a quantum leap beyond WEP. It implements security via an 802.11x framework, creating key hierarchies, key management systems, and cipher and authentication negotiation. Also, while it still uses RC4, many of the problems are mitigated by the use of TKIP. Given time, an attacker can reconstruct the data, however, the bar is raised much higher by this technology.

802.11i
Fully implementing 802.11x, and utilizing the advanced AES encryption scheme, 802.11i is the future of 802.11 security. Most significantly, it will add preauthentication and peer-to-peer communications security.

Remote Authentication Dial In User Service (RADIUS)
The user gives value pairs to the authentication server which sets permissions appropriately. Diameter is the successor and replacement of RADIUS, and uses a full 32-bit permissions space, allowing greater interoperability and mobile use.

TKIP
Temporal Key Integrity Protocol is a temporary fix added by IEEE to 802.11 in order to fix some of the weak IV problems created by WEP. TKIP involves varying the key that is used to encrypt each time a packet is transmitted. TKIP basically ensures that each station uses a different WEP key, which is based off of the MAC and a large 16-octet IV to encrypt.

Cisco Wireless LEAP
Security methods such as the Cisco Wireless LEAP do not solve the problems of WEP and a bad protocol. LEAP consists of a system where a user authenticates with a ACS Radius server to obtain a dynamic key, all of which is done to provide "strong mutual authentication" to the user and the server. The possibility of stronger mutual authentication does not necessarily fix the problems that are inherited of from shared key authentication via 802.11. Since the Cisco Wireless LEAP protocol is not an open protocol, more analysis of the authentication methods with the ACS Radius server can not be done at this time. Some of the other problems with WEP are fixed, since they change their WEP keys on a regular basis.

Top -^


Implementation

The RC4 Algorithm
KSA(K)
  for i = 0..N-1
    S[i] = i;
  j = 0;

  for i = 0..N-1
     j = j + S[i] + K[i % l];
     Swap(S[i], S[j]);
  
i = j = 0;
PRGA(S)
  i = i + 1;
  j = j + S[i];
  Swap(S[i], S[j]);
  return S[S[i] + S[j]];
The Attacks

So our goal was to make an attempt at lowering the bound on the best known attacks on RC4, both for the weak IV attack as well as the Knudson state table attack. We read an exhaustive amount of literature on the subject of RC4, only the most useful papers of which are listed in our reference section.

Currently, WEP is considered "broken" due to the weak IV attack published by Fluhrer, Mantin, and Shamir. However, this attack can be avoided by new cards by simply not issuing weak IVs.

So initially, we considered attempting to search out new weak IVs and using optimizations such as those described by Stubblefield, et al, however it seems that AirSnort has already updated its code to cover these optimizations and new classes of weak IVs, so most likely vendors have already addressed this issue.

So we turned our focus to weakening the RC4 encryption algorithm itself (pictured above). We centered our approach around Knudson's Attack.

The Knudsen Attack

This attack is directed at the initial state array (from which the secret key can be derived using the algorithm at the end of the landmark Fluhrer, Mantin and Shamir paper). The main requirement for the attack is 2^n words of known output from the RC4 PRNG where n is the length in bits of the word. In otherwords, for the RC4-8 used in WEP, Knudson's attack requires less data than typically found in a single packet to reconstruct the permutation table and thus derive the key. Feasability of this attack would make many existing and proposed extensions to 802.11 security useless.

The description of the algorithm (from Knudson's paper) is for each t = 1,2,3,...m if S(t-1)[i(t)] or S(t-1)[j(t)], if S(t-1)[i(t)] isn't filled, choose a value at random, update the possible values of v, and then compute j(t) and choose S(t-1)[j(t)] (if not filled in). Some checks are then imposed, if the output word differs from all words previous, then no known index fields can exist; it output does equal a previous word, then S(t-1)[i(t)] + S(t-1)[j(t)] must be the correct index.

One can handle the cases where a inconsistent state is found in different ways, one could either look through all the different values for each variable and check each in order of probability, which is trivially parallelized.

Knudson(plaintext, cryptotext)
   RC4output = cryptotext XOR plaintext;
   i=j=0;
   //this returns the most probable distribution value for the 
   //given index and stores it in the current swap array.
   S.insert(1,1)= ProbDistSwap(i); 


   S.insert(1+S[i],1)= ProbDistSwap(i);
   KnudRecusive(S, i, j, 1);
   return(findSecretKey(S))   

KnudRecursive(S, i, j, t)
   if(S.isfilled()) return;

   updateProbDistSwap(S, i, j, t);

   i = i + 1;

   if(S.undefined(i))
         S(i, t)=ProbDistSwap(i);
	 KnudRecursive(S, i-1, j, t)

   j = j + S[i];

   Swap(i , j); //swaps i and j
   z = S[i]+ S[j];//S[j] is zero if undefined
   if(S.defined(i)&&S.defined(j)&&S.defined(z))
      if(RCoutput(i,j) == RC4output(t))
         KnudRecursive(S, i, j, t+1);

      else
         S.markUnusable(t);//removes state from consideration
         restart at the assignments of S[i], S[j], and S[z], starting 
         from previous swaps and moving back to the initial assignment 
         checking for other possible solutions.

   elseif(S.defined(i)&&S.used(RC4output(t))
      S(j, t)=S.locate(RC4output(t))-S[i];
      KnudRecursive(S, i, j, t+1);

   elseif(S.defined(i)&&S.defined(j))
      S(z,t)=RC4output(t);
      KnudRecursive(S, i, j, t+1);

   elseif(S.undefined(j))
      S(j, t) = ProbDistSwap(j);
      Swap(i,j);
      KnudRecursive(S, i , j - S[i], t)
      
Our Work

Unfortunately, this attack still has a time complexity of somewhere around 2^700 and is not a feasable attack against RC4. The authors mention a possible probabalistic improvement, where by instead of dropping states when an unknown swap occurrs or variable guess is needed, a probability distribution is maintained for these states to pick the most probable value and attempt to continue. As given in the paper, this improvement only deals with maintaining the probability distribution while the algorithm runs, and assumes a uniform distribution over the initial permutation table.

So given this, two ideas came to mind, both based on the realization that this initial distribution was not in fact uniform, and with the goal of providing this distribution to the attack. The first was unfortunately documented 8 years ago (unbeknownst to us at the time) in a sci.crypt posting by Arthur Roos, and thus nothing unknown to Knudson. Basically the idea was to "water down" the KSA by assuming that the value in S[i] was in fact i. This is a valid assumption, especially since the early values of S[i] have a low probability of swapping with an arbitrary j later on. Given this assumption, the most likely value in S[i] after the KSA i the sum of the first i bytes of the K and the first i integers. But this doesn't really get us anywhere anyway, since it requires knowledge of the key.

The second idea was inspired by a paper that derived a recurrence relation that determined the probability distribution over S given the assumption of perfectly random swaps. They came up with the fact that the identity permutation (S[i] = i) was the most likely result of this "randomized" RC4 KSA.

So this lead us to our final attempt, which was to write some code to build a probability distribution over S given a probability distribution over the key.

In order to achieve this distribution, we essentially just implemented RC4, but replaced all the detertministic operations with their probabalistic equivalents. The variable j became a vector where J[j] represented P(J = j). S became a 2D array where S[i][s] represented P(S[i] = s), as did the probability distribution over the key K. The update step for j was computed using a sum over the probability of all possible values of j times the probability of all possible values of S, times the probability of all possible valus of K.

The swapping step became probabalistic in the same way. It transfered the probability of S[j] to S[i] via a single sum over all possible values of j and S[j]. Then for the swap into j, all of S must be recomputed (because j is probabalistic. The probability that k is in an index of S is the probability that j caused a swap into s and Sprev[i] was k, plus the probability that J didn't cause a swap into s times the probability that S[s] already was k (after the swap for i).

We verified the correctness of this approach by assigning probabilities of 1 to each variable and using it in place of the deterministic RC4.

Conclusion

Unfortunately, all this was for naught as well. Our results were exactly a combination of Roos and the above paper. Given a 3 byte initialization vector, and a probability distribution over the keys similar to that of English plain text, the first 3 values of the permutation table were the sum of the key indexes with probability of 37%, almost exactly that which was predicted by Roos. Furthermore, the most likely element for all other indexes of the permutation table was the identity permutation.

So it would appear that the badly crippled, yet still breathing RC4 will live to see another day.

Top -^


References

  1. Weaknesses in the Key Scheduling Algorithm of RC4

  2. Analysis Methods for alleged RC4

  3. Not so random shuffles of RC4

  4. Using the Fluhrer, Mantin, and Shamir Attack to break WEP

  5. Weak Keys in the RC4 Stream Cipher

  6. My RC4 Weak Keys

  7. Analysis of the Stream Cipher RC4

  8. Your Wireless Network has No Clothes

  9. Cisco Aironet Security Solution Provides Dynamic WEP to Address Researchers Concerns

  10. Cisco Comments on Recent WLAN Security Paper from University of Maryland

  11. Cisco Wireless Lan Security BUlletin


Top -^



Team: Mike Perry, Chris Grier, John Washington, Jeff Kramer