WEP - analysis of vulnerabilities and attacks
Number 0x02: 15/02/2007
[ --- The Bug! Magazine
_____ _ ___ _
/__ \ |__ ___ / __\_ _ __ _ / \
/ /\/ '_ \ / _ \ /__\// | | |/ _` |/ /
/ / | | | | __/ / \/ \ |_| | (_| /\_/
\/ |_| |_|\___| \_____/\__,_|\__, \/
|___/
[ M . A . G . A . Z . I . N . E ]
[ Numero 0x02 <---> Edicao 0x01 <---> Artigo 0x05 ]
.> 14 de Fevereiro de 2007,
.> The Bug! Magazine < staff [at] thebugmagazine [dot] org >
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
WEP - Analise de Vulnerabilidades e Ataques
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
.> 10 de Novembro de 2006,
.> wishbone < andreguedes85 [at] gmail [dot] com >
Index
- First Words
- Introduction
- WEP Vulnerabilities
- 3.1. Key Size
- 3.2. Key Management
- 3.3. Key Reuse
- 3.4. IV passed in Course
- 3.5. Inefficient authentication protocol
- 3.6. Denial of Service (DoS)
- 3.7. The Algorithm Implementing ICV is Unsuitable
- 3.8. RC4 Problems
- 3.9. Packet Re-injection
- Attack Analysis
- 4.1. Chopchop Attack
- 4.2. FMS Attack
- 4.3. DoS Attack
- 4.3.1. Radio frequency based dos
- 4.3.2. Packet Based DoS
- Conclusion
- References
1. First Words
Essentially, this article analyzes the vulnerabilities presented by the WEP protocol, a security protocol still widely used in wireless 802.11 (Wi-Fi) networks. I also discuss, in an objective way, the main existing attacks that can compromise the security of a Wi-Fi network.
I strongly recommend a previous study on the WEP protocol functioning mechanisms. It is of utmost importance that the reader has a solid knowledge about the forms of authentication, integrity and confidentiality of the WEP protocol. In addition, I also recommend that the reader has a general idea of the architecture and operation of an 802.11 network.
I will only cover security at the link layer level. I will not be concerned with other layer solutions, e.g. VPN.
2. Introduction
Due to the need for interconnectivity and mobility the deployment of wireless networks has presented a very significant growth in corporations and corporations and homes. According to some researches, wireless technology will be the technology of the future. Among all wireless technologies, Wi-Fi has stood out because it meets the needs of users due to its particular characteristics. More and more, the number of hotspots is growing considerably.
In terms of security there are some differences that can make wireless networks more vulnerable than wired ones. A LAN (Local Area Network) is generally protected by physical security mechanisms (e.g., access control to rooms, buildings, etc.) that are effective in a controlled physical area. However, this approach is not effective for WLANs (Wireless Local Area Network), since the radio waves used for communication are not necessarily confined by the walls of the area where the devices composing the network are located.
Currently there are three security protocols for Wi-Fi networks: WEP (Wired Equivalent Privacy), WPA (Wi-Fi Protected Access) and WPA2 (Wi-Fi Protected 2, technically known as 802.11i), respectively in chronological order. Even though it is the most inefficient and vulnerable, WEP is still the most used protocol, even in corporate networks.
Perhaps WEP is still widely used because a change in the security protocol (WPA or WPA2) can imply high costs with the purchase of new equipment. Perhaps it is also due to lack of information about the vulnerabilities that WEP presents.
This article is organized in chapters. In chapter 3, I discuss the vulnerabilities presented by WEP. In chapter 4, I discuss the main attacks against WEP, presenting more details through demonstrations. Finally, in chapter 5 I make my conclusion about this work and in chapter 6 the references.
3. WEP vulnerabilities
3.1 Key Size
Originally when WEP was released, the static WEP key was only 40 bits long. Keys of this size can be broken by brute force using current machines. To solve this problem, manufacturers of Wi-Fi products released WEP2 with 104-bit and 232-bit static keys, while maintaining the 24-bit IR. With this it has become almost impossible to brute force break the key.
3.2 Key Management
WEP does not have a key management protocol, so the key used by devices cannot be changed dynamically. This makes it difficult to maintain the networks since the key exchange is done manually on each machine. Because of this, the keys are not exchanged frequently, which causes a security breach. Since WEP is a mechanism strongly based on the secrecy of its key, it is necessary to change the key frequently.
3.3 Key Reuse
The 24 bits of the initialization vector (IV) allow for just over 16.7 million different vectors. This number of possibilities is relatively small.
According to the network traffic volume the IVs will repeat from time to time and therefore the keys used by RC4 will also repeat. If the IVs are chosen randomly, the frequency of repetitions can increase significantly given the birthday paradox. According to the paradox, after 4823 packets there is a 50% probability of an IR repeat. Repeating keys hurts the nature of Vernan Ciphers which will no longer guarantee data confidentiality.
Let's see why after a key repetition WEP no longer guarantees data confidentiality.
Dados:
M1 = Mensagem 1
M2 = Mensagem 2
C1 = Cifra da M1 (ou seja, e' a M1 cifrada)
C2 = Cifra da M2
iv = vetor de inicializacao
chave = Chave estatica WEP
--
Inicio:
C1 = M1 XOR RC4(iv, chave)
C2 = M2 XOR RC4(iv, chave)
C1 XOR C2 = (M1 XOR RC4(iv, chave)) XOR (M2 XOR RC4(iv, chave))
* A XOR A = 0, logo RC4(iv, chave) XOR RC4(iv, chave) = 0
C1 XOR C2 = M1 XOR M2 XOR 0
* B XOR 0 = B, portanto
C1 XOR C2 = M1 XOR M2This means that doing an XOR between two packets encrypted under the same key is the same thing as doing an XOR between the messages they contain. With this, if one of the messages is known, then it is possible to decrypt all the other messages encrypted over the same key. See the figure.
+-----------+ +----+ +----+
| C1 XOR C2 | = | M1 | XOR | M2 | <----- Qualquer que seja M2,
+-----------+ +----+ +----+ sera' possivel
A A decodifica-la atraves de
| | uma simples operacao XOR
Este valor sempre Se uma das
sera' conhecido mensagens
for conhecida
Ou seja,
+----+ +----+ +-----------+
| M2 | = | M1 | XOR | C1 XOR C2 |
+----+ +----+ +-----------+
A (conhecido) (conhecido)
|
conhecido por
consequencia
3.4 IV passed in the clear
The initialization vector is passed in the clear since it is needed for the decoding process. Since IV is the initial part of the key, we are obfuscating a part of the key that encrypted the packet. Because of this flaw, powerful attacks like FMS (which will be covered soon) could be created.
3.5 Inefficient authentication protocol
In Shared-Key authentication mode the attacker can with a simple listen to the traffic get access to a clear packet (challenge-text packet) and its respective cipher (encrypted challenge-text packet). With this data it is possible to find the keystream and use it to create a valid response for any challenge text (see figure below). Therefore, the attacker can authenticate without knowing the WEP key.
+----------+ +------------------+ +-----------+
| Mensagem | XOR | Respectiva Cifra | = | KeyStream |
+----------+ +------------------+ +-----------+
________________________________________________|
|
v
+-----------+ +-------------------+ +--------------+
| KeyStream | XOR | Qualquer Mensagem | = | Cifra valida |
+-----------+ +-------------------+ +--------------+
* isto ocorre porque os textos-desafio enviados pelo AP tem
sempre o mesmo tamanho.The use of MAC Filtering does not guarantee any authentication security, since MAC Spoofing attacks can be easily used. An attacker can quickly discover a valid MAC Address by listening to traffic and use the discovered address to bypass MAC Filtering.
3.6 Deny of Service (DoS)
It is possible to forge De-Authetication packets and send them either in broadcast mode or directly to a specific client using its associated MAC address. Open source tools like void11 and aircrack implement this type of attack. This vulnerability is not only present in the WEP protocol but in all other Wi-Fi security protocols (WPA, WPA2).
3.7 The Algorithm Implementing BCI Is Not Appropriate
The CRC-32 used to compute ICV can detect with high probability changes in the message, serving as an integrity check. The truth is that CRC algorithms were not developed with security in mind, but rather to detect changes due to interference on the communication channel. Therefore, CRC is insecure in cryptographic terms. The main insecure characteristic is the fact that CRC is a linear function. Based on this property of CRC, an attacker can modify the contents of a packet and easily correct the ICV, making the packet appear authentic.
3.8 RC4 Problems
RC4 is the cryptographic algorithm used by WEP. It is subdivided into two other algorithms: Key-Scheduling Algorithm (KSA) and Pseudo-Random Generation Algorithm (PRGA). The KSA is quite simple, it initializes an array of 256 positions with values from 0 to 255. Then it performs a series of swaps, permuting the array. The swapping is done according to the key, different keys swap the array in different ways. PRGA also performs one swap and generates one byte as output that will be used in the XOR operation. In [4], it is demonstrated that the KSA algorithm presents a weakness. From this, it was developed a statistical attack that reveals the WEP key. This attack became known as FMS. To discover the WEP key through FMS it is necessary to capture a large number of packets with different IVs, i.e. a large number of unique IVs. Based on the FMS attack and h1kari's optimizations, KoreK attacks were created that can break the WEP key with a smaller number of IVs.
3.9 Packet Re-Injection
WEP secured networks are susceptible to traffic re-injection attacks. This type of attack does not directly affect network security, but can be used to increase network traffic and thus decrease the time needed for attacks such as FMS to break the WEP key.
4. Attack Analysis
4.1 Chopchop Attack (Inverse Arbaugh Attack)
The Chopchop Attack decodes the packet byte-by-byte without knowledge of the WEP key, just by using the AP as the decoder.
The first step is to capture a packet. The last byte of the packet is changed to a known value. The packet is sent to the AP. If the AP sends the packet back to the network, it means that the value of the byte chosen in the change was correct. If not, the byte is changed by another value until the correct value is found. Fortunately there are only 256 possible values (from 0 to 255) for the byte plaintext. More details about chopchop can be seen in [1, 2, 3].
To alter a packet it is necessary to alter two parts: the payload and the ICV. The attacker creates a bitmask according to the change he wants to make to the payload. After the bitmask is created, an XOR is made between the payload and the bitmask, thus generating the altered payload. But the ICV of the original packet is not valid for the altered packet, so we have to calculate a new ICV. The calculation of the new ICV is quite simple. Just calculate the CRC-32 of the bitmask and do an XOR with the original ICV. The result of the XOR is the ICV of the changed packet! See the figure.
+-------------------------+
| +---------+ +-----+ |
Pacote Capturado --> | | Payload | | ICV | |
| +---------+ +-----+ |
+-------------------------+
| |
XOR XOR
| |
+---------+ CRC +-------+
| bitmask |----->|ICV do |
+---------+ |bitmask|
| +-------+
| |
| |
v v
+--------------------------+
|+----------+ +----------+|
Pacote Alterado --> || Payload | | ICV ||
|| Alterado | | Alterado ||
|+----------+ +----------+|
+--------------------------+But... is that true? The result of the XOR of the ICVs has as answer the ICV of the changed package? Let's prove it!
Dados:
P = payload do pacote original
P' = payload do pacote alterado
ICV = CRC-32 do pacote original
ICV' = CRC-32 do pacote alterado
bm = bitmask gerado pelo atacante
ICVbm = CRC-32 do bitmask
+------------------------------------+
|Objetivo: Mostrar que CRC(P') = ICV'|
+------------------------------------+
Inicio:
CRC(P) = ICV (fato!)
CRC(P' XOR bm) = ICV' XOR ICVbm
* como a funcao CRC e' linear, ou seja, CRC(A XOR B) = CRC(A) XOR CRC(B)
CRC(P') XOR CRC(bm) = ICV' XOR ICVbm
------- ------- ---------------
A B C
* A XOR B = C <==> A = C XOR B logo,
CRC(P') = ICV' XOR ICVbm XOR CRC(bm)
* CRC(bm) = ICVbm
CRC(P') = ICV' XOR ICVbm XOR ICVbm
* A XOR A = 0
CRC(P') = ICV' XOR 0
* A XOR 0 = A
CRC(P') = ICV' (PROVADO!)Therefore, it is possible to change the frame payload and easily correct the ICV.
4.2 FMS Attack
The FMS is an attack that reveals the WEP key. Once in possession of this key, the attacker can gain access to all network resources.
FMS basically boils down to capturing a large amount of packet (this amount varies according to the size of the WEP key) and running a probabilistic algorithm that will discover the key. Note that according to the description above, FMS is a passive attack.
This attack was developed due to a flaw in RC4 published in [4], this flaw occurs more specifically in KSA. Some Weak IVs do not work very well in RC4, because it does not permute the array in a proper way, making it easy to deduce the WEP key.
For the demonstration of this attack a deeper RC4 approach is needed. Below are the two algorithms that compose RC4.
Key-Scheduling Algorithm:
KSA(K)
K[] = array que representa a chave WEP
l = tamanho da chave em bytes (IV + chave WEP)
Initialization:
For i = 0 to 255
S[i] = i
j = 0
Scrambling:
For i = 0 to 255
j = (j + S[i] + K[i mod l]) mod 256
Swap(S[i], S[j])As we can see above, KSA initializes the array S[] with values from 0 to 255. Right after initialization, it performs 256 swaps. Note that the choice of elements that will take part in the swap depends directly on the key used.
Pseudo-Random Generation Algorithm:
PRGA(K)
Initialization:
i = 0
j = 0
Generation Loop:
i = i + 1
j = (j + S[i]) mod 256
Swap(S[i], S[j])
Output z = S[(S[i] + S[j]) mod 256]As the name of the algorithm suggests, it is responsible for generating an output byte 'randomly'.
It is important to remember that first the KSA is executed and only after the end of its execution, the PRGA is started.
The FMS is a statistical attack based on weak but unique IVs (Weak IV). This means that repeated IVs do not influence the breaking of the key. But what is a weak IV?
All IVs that fit this pattern are considered weak IVs
+---------+--------+-----+
| A + 3 | N -1 | X |
+---------+--------+-----+Where:
- A : byte of the WEP key you want to break
- N : size of the internal RC4 array, in the case of WEP, N = 256
- X : can be any value
Let's demonstrate the attack.
After capturing a huge amount of packets with IVs different from each other, we effectively execute the attack.
We will attack the first byte of the key, so we need an IV where:
- A = 0
- N = 256
- X = any value
We take one of the captured packets in which the IV meets these requirements, for example: IV = 3, 255, 7
Let's set the WEP key = 22222, at first we do not know the value of the key, but this information will be necessary to compare with the result obtained.
Given this information our current situation is:
+-------------------------------------------------------------------------+
K[]=| K[0]=3 | K[1]=255 | K[2]=7 | K[3]=? | K[4]=? | K[5]=? | K[6]=? | K[7]=? |
+-------------------------------------------------------------------------+Our goal is to find the first byte of the WEP key, i.e. K[3].
We start the cracking process by simulating the KSA
KSA no 1o loop:
S[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... , 255}
i = 0
j = 0 + S[0] + K[0] -> j = 0 + 0 + 3 -> j = 3
Swap(S[0], S[3])
KSA no 2o loop:
S[] = {3, 1, 2, 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... , 255}
i = 1
j = 3 + S[1] + K[1] -> j = 3 + 1 + 255 -> j = 259 mod 256 -> j = 3
Swap(S[1], S[3])
KSA no 3o loop:
S[] = {3, 0, 2, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... , 255}
i = 2
j = 3 + S[2] + K[2] -> j = 3 + 2 + 7 -> j = 12
Swap(S[2], S[12])
KSA no 4o loop:
S[] = {3, 0, 12, 1, 4, 5, 6, 7, 8, 9, 10, 11, 2, 13, ... , 255}
i = 3
j = 12 + S[3] + K[3] -> j = 12 + 1 + K[3] --> mas qual o valor de K[3]??
Swap(S[3], S[j])Apparently, we are stopped, because we don't know the value of K[3] (of course! that's what we want to find out!). However, we know that at the end of the encryption process an XOR is done between the byte of the packet and the byte that leaves the PRGA, thus generating the encrypted byte.
+----------------+ +------------------+ +-------------+
| plaintext byte | XOR | PRGA output byte | = | cipher byte |
+----------------+ +------------------+ +-------------+In this way we can find the first byte generated by PRGA if we do an XOR between the first encrypted byte and its respective value (plaintext byte).
+------------------+ +-------------+ +----------------+
| PRGA output byte | = | cipher byte | XOR | plaintext byte |
+------------------+ +-------------+ +----------------+Knowing which is the first encrypted byte is very simple, just look at the captured packet (remember that the packet is encrypted). But what about its respective value?
The first byte of the 802.11 frame payload corresponds to the IP protocol header (in most cases). According to the IEEE specification, the first field of the IP header is SNAP whose default value is 170 in decimal (or 0xAA in hexadecimal), so we know the plaintext of the first byte!
Then, let's consider that the encrypted byte corresponds to 165. This way we find 'z', the output of PRGA.
z = 170 XOR 165
z = 15 (I)Now we run the PRGA in the first loop.
PRGA 1o loop:
i = 1
j = 0 + S[1] -> j = 0 + 0 -> j = 0
Swap(S[1], S[0])
z = S[S[1] + S[0]] -> z = S[3 + 0] -> z = S[3] (II)
a partir de I e II, z = 15 e z = S[3]
S[3] = 15This means that in the 4th KSA loop there was a swap between S[3] and S[15] (see KSA on the 4th loop, line 4), so in the 4th KSA loop the value of j was 15.
j = 12 + 1 + K[3]
15 = 12 + 1 + K[3]
K[3] = 15 - 13
K[3] = 2We found the first byte of the WEP key! Note that this result is according to what was predicted! (remember? WEP key = 22222)
Note that we made some abuses: we considered that from the 4th KSA loop on the values of S[0], S[1] and S[3] didn't suffer more swaps (nothing prevents that during the rest of the KSA execution these values are changed). According to [4] this abuse costs us a probability of 5% (e-3). If by chance we had considered that only two of these values do not suffer more swaps, the probability of being right would be 13% (e-2).
See that the probability of being correct is very small, so to apply the FMS attack we need to have enough IVs to be able to say with greater certainty which is the key. Note also that for this reason repeated IVs do not influence this attack.
4.3 DoS Attack
We can divide DoS attacks into two distinct classes:
- Radio Frequency Based DoS
- Packet-Based DoS
4.3.1 Radio Frequency Based DoS (Old School DoS)
The main representative of this category of DoS is the RF-Jamming Attack, which is nothing more than to create a deliberate interference via radio waves to prevent the reception of signals in a specific frequency band, in short it means creating enough interference capable of bringing down the wireless connection.
This requires equipment capable of emitting signals at a frequency of 2.4 GHz. There are several pieces of equipment that can be used to attack the network, such as radio transmitters, microwaves, bluetooth devices, and others.
4.3.2 Packet-Based DoS
We know that in 802.11 networks there are three types of frames:
- Data Frames
- Management Frames
- Control Frames
All Wi-Fi security protocols (WEP, WPA, WPA2) are concerned only with Data Frames, i.e. all the security of these protocols are applied only to this type of frame. The other two types (management and control) have no security at all. Therefore, once a frame of these types is forged, it will be valid. The DoS attacks of this category take advantage of this flaw, let us see the main ones:
Duration Attack
802.11 type networks use CSMA-CA (Carrier Sense Multiple Access - Collision Avoidance) as their medium access protocol. When a device wants to send packets, it first reserves the medium for a period of time. This reservation is made through a Control Frame of type RTS (Request to Send). Other devices on the network do not send packets until the reservation time is up.
The Duration Attack consists of forging and injecting RTS Control Frames with high values in the duration field. This way, other clients are stuck waiting for the medium to become available. Thus, the attacker keeps reserving the medium through massive injections of RTS and the other clients cannot access the network services, because the medium is reserved.
De-authentication Attack
The De-authentication Attack consists in forging Management Frames of the De-authentication type. In the source field is placed the MAC Address of the Access Point (AP), and in the destination field you can put the MAC Address of a particular client or put FF:FF:FF:FF:FF to send in Broadcast (if you want to disconnect all clients on the network). Once the client receives a packet of this type, it disconnects, believing that the packet came from the AP.
Association Flood Attack
The AP has a limit of simultaneous associations. If the number of clients associated with the AP reaches this limit, the AP will not allow any more associations to occur.
This attack consists in the attacker forging several Authentication/Association Request Frames simulating several associations. With this, the AP will reach its association limit and will not allow new clients to access the network.
5. Conclusion
As we have seen in this article, the WEP protocol is very vulnerable. WEP vulnerabilities are very easy to exploit. Anyone with some knowledge of existing tools can attack a WEP secured Wi-Fi network, even if they don't know how the attack actually works. In this way, the security of most Wi-Fi networks can be compromised.
I recommend that the 'new' security protocols (WPA and WPA2) be used instead of WEP. Even taking into account that WPA and WPA2 have some vulnerabilities, they are by far more secure than WEP.
6. References
- Netstumbler - http://www.netstumbler.org/showthread.php?t=12489
- informit.com - Byte-Sized Decryption of WEP with Chopchop, Part 1 Disponivel em: http://www.informit.com/guides/content.asp?g=security&seqNum=196&rl=1
- informit.com - Byte-Sized Decryption of WEP with Chopchop, Part 2 Disponivel em: http://www.informit.com/guides/content.asp?g=security&seqNum=197&rl=1
- Fluhrer, S., Mantin, I. and Shamir, A. - Weaknesses in the key scheduling algorithm of RC4 Disponivel em: http://www.cs.umd.edu/~waa/class-pubs/rc4_ksaproc.ps
- Hulton, David (h1kari) - Practical Exploitation of RC4 Weaknesses in WEP Environments Disponivel em: http://www.dachb0den.com/projects/bsd-airtools/wepexp.txt
- Stubblefield, A., Ioannidis, J. and Rubin, A. - Using the Fluhrer, Mantin, and Shamir Attack to Break WEP
- Borisov, N., Goldberg, I. and Wagner, D. - Intercepting Mobile Communications: The Insecurity of 802.11
