Summary: Fluhrer, S. Mantin, I. Shamir, A. The proposed KSA (Key Schedule Algorithm) is based on the basis for the improved KSA attack method. The new method has higher attack efficiency compared to the KSA attack proposed by Fluhrer. With this method, the attack on the 802.11 network link security protocol - WEP is successfully realized, and the original add--delegated key is successfully restored. This article describes this attack in detail, and some security recommendations are proposed for security issues in the 802.11 network. Keywords: wired equivalent encryption key scheduling algorithm pseudo-random number generator With the development of 802.11 standards and related software and hardware technology, 802.11 Wireless LAN products have become more and more wide. It has a wide range of communication, and the data transmission rate is characterized to bring 802.11 to the Bluetooth protocol to become one of the optional protocols of Wireless LANS, widely used in office, conference, etc. The PC card used in these occasions provides a negative protocol called WEP (Wired Equivalent Privacy). WEP is easy to manage, each 802.11 card has an encryption key (Key). In actual use, most devices use the same encryption key, including access point AP (Access Point).
802.11 By WEP to prevent illegal access to the LAN, providing users with a communication environment with traditional wired local area security. The RC4 algorithm used in WEP is a symmetric stream additive algorithm. Since the encryption or decryption speed of the RC4 algorithm is very fast, it provides a considerable intensity, so it has been widely used. Its most important application is the SSL (Security Socket Layer) encryption socket protocol layer and WEP. In response to the RC4 algorithm and its weaknesses, many studies have conducted many studies, most of which are theoretical research and does not have practical significance. Until recently, Borisov, Goldberg and wagner pointed out that 1: In WEP, some vendors set IV to zero when they were initialized, and then plus one. This improper use causes a significant increase in key re-use, which can be used for simple cryptographic analysis. In addition, the authors also pointed out that since IV is too small, the same key reusing problem will inevitably lead to the same key reuse. FluHRER, MANTIN AND Shamir describes a passive ciphertext attack method for RC4 algorithm adopted by WEP 2 authors initialize the status of RC4, and proposes a KSA attack method. The severe vulnerability in WEP is revealed. Based on the literature 2: The KSA attack method proposed, a more efficient attack method is proposed. In the actual environment, an attack on WEP is successfully implemented.
The experimental results show that the method proposed in this paper has the advantages of high efficiency compared to the KSA attack proposed in Document 2, and the amount of data required is smaller. 1 RC4 algorithm 1.1 RC4 overview
The RC4 algorithm belongs to a binary or synchronous stream password algorithm. The key length is variable. In WEP, the key length can be selected 128bit or 64bit.
RC4 algorithm by pseudo-random number generation algorithm PRGA (Pseudo Random Generation Algorithm) and key scheduling algorithm KSA
Key Schedule Algorithm Two parts make up. Where PRGA is the core of the RC4 algorithm, it is used to generate a pseudo random number sequence that is different or a mortuary.
The function of the A algorithm is to map the key to the initialization state of the pseudo-random number generator, complete the initialization of the RC4 algorithm. The RC4 algorithm is actually an algorithm that is parameter to encapsulate block size. The parameter n is the word length of the RC4 algorithm. In WEP, n = 8. The internal state of the RC4 algorithm includes a state table of 2N words and two sizes of one word. Status table, also known as the status box (S-Box, below with s), used to save
The 2N value transposed state. Two counters are represented by I and J, respectively. The KSA algorithm and PRGA algorithm can be represented as follows:
KSA: PRGA:
Initialization: Initialization: for i = 0 to 2N-1 i = 0, J = 0
S [i] = i generation loop:
J = 0 i = i 1
Scrambling: J = J S [i]
For i = 0 to 2N-1 SWAP (s [i], s [j])
J = j s [i] k [i mod l] OUTPUT Z = S [S [i] s [j]]
SWAP (s [i], s [j])
Where l is the length of the key.
1.2 RC4 Algorithm Security Analysis Carefully Study the RC4 algorithm process, it is not difficult to find that the state box S starts from a unified 2N word to the only operation of it is to exchange. S always saves a certain transpose state of 2N words, and the transpose is updated over time. This is also the intensity of the RC4 algorithm. The internal state of the algorithm is stored in M = N2N 2N bits, since S is a transposition, this state is approximately saved information of log2 (2n!) 2n ≈1700bit. The initialization state of the state box is only dependent on the encryption key K, so if the encryption key is known, the RC4 can be completely cracked. The encryption key is completely and uniquely determines the pseudo random number sequence, and the same key is always the same sequence. In addition, the RC4 algorithm itself does not provide data integrity check function, and the implementation of this feature must be implemented by other methods (such as the data integrity check vector, i.e., ICV). Some special attack models are considered, and these models are closely related to the security issues of RC4 to be discussed.
The RC4 algorithm belongs to one of the synchronous stream password algorithm. Since the output of the pseudo-random number generator PRNG (Pseudo Random Number Gernerator is completely determined by the encryption key, the two conditions must be met for a design good stream password algorithm: Each bit of the output should depend on all bits of all encryption keys; and the relationship between any bit or some bit of the encryption key should be extremely complicated. The first condition described above means that each bit of the output depends on the value of all bits of the encrypted key. The change in any of the keys in the key has a chance of 1/2 affects each bit of the output. If this condition is met, then cracking this encryption requires all possible key values, and the output value has almost no contact between the encryption key. If the above conditions are not met, then it can be used to attack it. For example, assume that one 8 bits of the output rely on an 8 bits of the encryption key, then all possible values of this 8-bit key can be made simply, and it is obtained with the actual output. The value of the 8-bit key, which greatly reduces the amount of calculation required for exhaustion attacks. Therefore, if the output is determined by a relatively high probability by certain bits of the key, this information can be utilized to attack the stream password. The second condition means that even if the connection between the two encryption keys is known, the connection between the PRNG output cannot be obtained. This information can also be used to reduce the search space of exhaustive attacks, resulting in a decrease in encryption strength. The RC4 algorithm belongs to a binary or stream password, and the same key always produces the same PRNG output. In order to solve the problem of key reusability, the initialization vector IV (INITIALIZATION vector) is introduced. The initialization vector is a random number, randomly generates each time it is encrypted. The initialization vector is combined with the original key in some form as the encrypted encryption key. Since IV does not belong to a portion of the key, there is no need to keep confidentiality, and more use in clear text. Although the use of the initialization vector solves the problem of key re-use,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, The KSA attack method proposed in this paper will be discussed in detail below.
2 KSA Attack This article focuses on the RC4 algorithm used in WEP, that is, the RC4 algorithm of the initialization vector IV is added. 2.1 KSA Considers KSA, notice that the only impact status table is the exchange operation. Therefore, each element of the status table is exchanged once (although it is possible to exchange itself). Suppose J is a uniform distributed random number, then considering a special element in the status table, jex does not point to this element during all initialization periods:
P = (255/256) ∧255 ≈ 37%
(The index is 255 because it can be ignored when Index2 and Counter are equal.
This means that 37% of the probability of a particular element is only swap once during initialization.
It can be seen from this:
Given a key length k (bytes), if E Similarly, only the first few elements in the status table are processed, that is, when I is a relatively small, S [J] has a high probability equal to j. Therefore, you can get: The most likely value of element S [E] (E] (E comparative hours) in the status table is: note that both element operations are operated in the mold 256. Based on the above analysis, the probability of each element satisfies B can be calculated. In order to meet the probability of the above formula in the statistical status table, the 8-bit RC4 algorithm is used to experiment. Here is 1 00000 48th elements in S [E] in 00000 experiments meet the probability of the above formula: PROBABILITY % 8 ~ 15 30.9 29.8 28.5 27.5 26.0 24.5 22.9 21.6 16 ~ 23 20.3 18.9 17.3 16.1 14.7 13.5 12.4 11.2 24 ~ 31 10.1 9.0 8.2 7.4 6.4 5.7 5.1 4.4 32 ~ 39 3.9 3.5 3.0 2.6 2.3 2.0 1.7 1.4 40 ~ 47 1.3 1.2 1.0 0.9 0.8 0.7 0.6 0.6 The results show that after KSA, the actual value of some of the elements in the status table is correlated with the value predicted by B. 2.2 weak key First define IT, JT, respectively, the KSA algorithm, the value of the two counters, and the ST is the state of the KSA after the T step. It can be seen from the process that the PRNG first byte output is only dependent on three values in the status box S: S [1], S [S [1]] and S [S [1] S [S [1]] ]. If this three values are known, you can completely determine the first byte output of the PRNG. Ksa After I step (i> 1), set Si [1] = x, s [x] = y, assume that J is a uniform distribution random number, then s [1], s [x], s [x y The probability that is not involved in the remaining exchange is approximately E-3 ≈ 0.05, and the first-byte output of RC4 is S [X Y]. Assuming the length of the IV is i byte, IV is attached to the key KEY to form an encryption key K, ie k = IV | key, and we know the value of the front B byte (initialization B = 0) . If the KSA is satisfied after I B-1 iteration: Si B-1 [1] Si B-1 [1] Si B-1 [Si B-1 [1]] = i b Consider the I B iteration: II b = i b JI B = JI B-1 S [i B] K [(i b) MOD L] swap Si B-1 [II B], Si B-1 [Ji B]: Si B [II B] = Si B-1 [JI B], Si B [JI B] = Si B-1 [II B] In the case of satisfying the above conditions, S [1], S [S [1]] and S [S [1] S [S [1]]] These three elements are high probably (greater than 5%). Do not participate in the remaining exchange operations of KSA, That is, the first-byte output is satisfied with a high probability: OUT = Si B-1 [JI B] = Si B-1 [JI B-1 K [B] Si B-1 [i B]] In this case, by reconstructing KSA, information can be successfully obtained from a particular byte k [i b] in the encryption key in the first byte output: K [b] = s [out] -JI B-1-Si B-1 [i b]] S [OUT] represents the position of the element OUT in the status table. As can be seen from the previous analysis, when Si [1]
County counts [0. . . 255] = 0 For Each Packet-> P IF resolved? (P.iv) Counts [SimulatedResolved (p, currentkeygues)] = 1 For each selectmaximalindexeswithbias -> byteguescurrentKeyguess [keybyte] = byteguess IF equal? (KeyByte, Keylength) IF CHECKCHECKSUMS (CURRENTKEYGUESS) Return CurrentKeygues Else Key = RecoverWepkey (CurrentKeyguess, Keybyte 1) IF notequal? (KEY, FAILURE) RETURN Key Return Failure 2.3 Algorithm improvement It can be seen that in the above attack method, all predictions about K [i b] are based on all keys (k [0], ..., k [i b-1]) known as it is known. In other words, the previous prediction error will directly lead to an error prediction of K [i B]. So can I speculate K [0] from K [i B] ,. . . , Information about K [i b-1]? Consider KSA, if it is temporarily iterated, it is satisfied: I Si [1] ≤i Then Si [1] and Si [Si [Si [1]] do not participate in the iteration between the first step and the first step in a large probability ((254/256) L-I≈1). At the same time, j does not point to great probability Si [i] ,. . . , Si [i b] these elements. which is: Si [1] = Si B-1 [1] IL-1 = L-1 JI B-1 = Ji Si [i] . . . Si [i b-1] k [i] . . . K [i b-1] Consider paragraph 1: II b = i b ji b = ji b-1 Si [i b] k [i b] Switch S [I], S [J], then Si B [i B] = Si B-1 [JI B]. If Si B-1 [JI B], Si B-1 [1] and Si B-1 [Si B-1]] do not participate in the remaining exchange operation, the output is: OUT = Si B-1 [JI B] and analyzed by the previous analysis It can be seen that Si B-1 [JI B] is not involved in the previous exchange operation with a high probability (approximately 1), i.e., Si B-1 [JI B] = JI B. This can be seen that OUT = Ji Si [I] . . . Si [i b-1] k [i] . . . K [i b-1] Si [i b] k [i b] can successfully introduce the relationship between different K bytes, thereby accelerating attacks. In addition, since the key is manually inputs when the key is managed, the key is only an ASIIC character in most cases. This greatly reduces the search space of the key and improves attack efficiency. 3 Experimental results and conclusions were verified to the above algorithms and experimented. The hardware used in the experiment is the ORINOCO wireless network card of Lucent, and the operating system is redhat7.1. The experimental results show that the algorithm proposed herein has averaged the original encryption key in the case of collecting 1 million to 2 million encrypted packets. With fluhrers. Mantini. ShamiR A. The proposed KSA attack requires 4 million to 6 million packets, and the attack efficiency has been greatly improved. Based on the above analysis, it is not difficult to see that there is a major security vulnerability in the existing WEP encryption, which is not improved due to the increase in the length of the encryption key, so it is equally existing in WEP2. To this end, it is recommended that existing 802.11 users:. Suppose 802.11 link layers do not provide security measures; . In order to ensure the safety of network communication, high-level encryption methods such as IPSec or SSH; . Place all users accessible by 802.11 outside the firewall. . Replace the key frequently, while the key should be used to use some Hash algorithm to avoid encryption keys using all ASIIC characters.
