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.
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.
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.
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.
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.
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.
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.
- Open Authentication is really not authentication at all, and anyone can join a network with this form of authentication.
- Shared Key uses challenge-response type authentication, in which the management frames to initiate the authentication and after that are not done using WEP. Since the management frames are sent in the clear, very little needs to be done for an attacker to authenticate without knowing the shared secret, simply by spying on the traffic. The attack consists of capturing specific parts of another users authentication (which is not WEP-ed) and reusing it for the attackers authentication. Pictured is the sequence of the management frames that are sent between the user and the authenticator, along with if information is encrypted via WEP.
- Shared Secret Access Control also has some weaknesses, and usually the secret is the SSID, which is not secure at all. SSIDs can be sniffed off the air, and found even when not broadcasted from the access point.
Wired Equivalent Privacy (WEP) 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.
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.
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.
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.
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.
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.
802.11 Security Extensions
[ 802.11x - WPA - 802.11i ]
A system for just authentication, 802.11x is the building block
for all future 802.11 security measures. The handshake works as follows:
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
The Attacks
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 Knudsen Attack
Our Work
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)
Conclusion
Top -^
References
Top -^
Team: Mike Perry, Chris Grier, John Washington, Jeff Kramer