Additional weak IV classes for the FMS attack ============================================= by Andrea Bittau (sorbo ) 9/12/2003 This paper is heavily influenced (copied) by h1kari's document both in content and layout 0. Abstract This document will describe how to detect IV's that rely on two key state elements not changing, in order to calculate the desired key byte. It also suggests how to detect IV's which become resolved in the successive key setup stage of the one we can calculate. 1. Introduction Current mechanisms of wep cracking heavily rely on the FMS [1] attack. Extensions to the attack were postulated by h1kari [2], where additional output bytes of the PRGA are being used to recover key bytes. However, such an attack is not seen in dwepcrack version 0.5 probably because: h1kari [2]: "In tests, this method doesn't prove entirely useful, mainly due to the amount of processing that is required to determine if certain ivs have this property." What drove my interest in wep was this: h1kari [2]: ... "and sometimes e ** -2 =~ 13% of the time in some cases when we only rely on 2 elements in the S permutation staying the same" this is also mentioned in SIR [3] section 4.3 "Special resolved cases". They also write "as Shamir pointer to us..." but I frankly did not see that written anywhere on Shamir's paper (at least explicitly). After some analysis, I concluded that this 13% family of IV's is not detectable with the standard IV filtering equation presented in the FMS paper. Part 1: Background Knowledge (skip) =================================== 1. WEP This will be a quick overview of WEP and some definitions. Please refer to the IEEE 802.11 standard. WEP is the encryption standard for the 802.11b protocol. If wep is used, a secret key must be distributed to the users of the network by some mean (key distribution is not part of the protocol). This is known as the shared key, which is also used for authentification when clients associate. The IEEE standard specifies to use 64bit keys, but common implementation allow 128bit. Only data packets, of which only the actual data payload is encrypted using WEP, so management frames for example are all in plain text. A standard 802.11 frame: [802.11 header] [ data ] [ crc ] A wep 802.11 frame: [802.11 header] [IV:4] [DATA] [ICV:4] [ crc ] If this was a data frame, only data and icv would be ciphered. The first 3 bytes of the IV are known as the Initialization Vector (IV). The last byte contains 2 bits of key index and 6 bits of padding (big endian). The ICV is the crc of the [DATA] portion (unciphered). The initialization vector is prepended to the shared key resulting in a seed which is fed into the ciphering algorithm. The key index is the identifier of the shared key to use with that IV to form the seed. The ICV is the crc32 algorithm run over the plain text version of data. This is used to see if decryption was successfull. Once the seed is setup, the algorithm used is standard RC4 which is a stream chipher (or more correctly a pseudo random generation algorithm). The output of RC4 is then bitwise xor'ed with the plain text to produce the cipher text. Important things to note: - IV will range from 0x000000 - 0xffffff resulting in 0x1000000 total possible iv's. - Key index is only 2 bits, resulting in only 4 possible keys per network. - 64bit key is referred to the seed, so the actualy shared key will only be 64-38 = 40bit. Common implementation interesting points: - IV is usually a little endian counter: 0x000000,0x100000,0x200000... - Hex keys are "hard to remember" so passphrase->key translation algorithm may be used - Windows XP maps passphrase->key using the ASCII value of each byte, also allows only passphrase lengths of 5 or 13 ONLY. 2. RC4 RC4 consists of two stages: 1) The key setup algorithm (KSA) 2) The pseudo random number generator algorithm (PRGA) From [2]: KSA(K) Initialization: For i = 0 ... N - 1 S[i] = i j = 0 Scrambling: For i = 0 ... N - 1 j = j + S[i] + K[i mod l] Swap(S[i], S[j]) PRGA(K) Initialization: i = 0 j = 0 Generation Loop: i = i + 1 j = j + S[i] Swap(S[i], S[j]) Output z = S[S[i] + S[j]] All operations are carried out modulo N. where N is 256. Definitions/Conventions: - byte: The seed byte starting from 0. (note key byte will be byte-3(IV len) ). - state: the S array. - stage x: the state when scrambling section of KSA reaches i=x Important things to note: - If we know seed untill byte x, we may calculate KSA untill stage x-1 - First output byte of PRGA is s[ (s[1] + s[s[1]]) % N ] 3. FMS attack (class 1) This is a brief overview of current public attacks. Plese refer to documentation in the reference section ad the end of this paper. As noted, first output byte relies on three elements: X=s[1], Y=s[X] and Z=s[ (X+Y) % N] where Z is the output. Definitions: - resolved: If at stage r X,Y,Z are equal to X,Y,Z of the final stage, then this particular seed results in a resolved condition at stage r. (FMS) If X,Y,Z are 3 distinct values, then the probability of resulting in a resolved state at stage r is e^(-3) approx 5%. Notice however that r must not be less than &X,&Y,&Z (& denotes 'index of'). This is so because in the KSA, i is incremental, so elements at index > current stage will swap no matter what. Also notice that we alwats know the first 3 bytes of the seed (it is the IV) so we may simulate KSA up to stage 2. We also notice that the key data is only used in the j pointer. If we somehow can calculate j of the next stage (3) we may be able to recover byte 3 of the seed (first key byte). Supposing we knew j3 (j stage 3), all we would have to do is: key[0] = seed[3] = ( j3-j2-S[3] % N ); The cleverness: Analysing further we see that at stage 3 S[j3] is swapped into S[3]. Suppose that with this seed, the KSA is resolved at stage 3 and that Z (output) = S[3]. So effectively the output will be S[j3] of stage 3 before the swap. Note that S[j3] of stage 3 is the same of S[j3] of stage 2 (the stage we can calculate). By simply searching for S[j3] (the output of PRGA which we know) in S2 (state at stage 2) we will recover j3 which will allow us to calculate seed[3] (i.e. the first shared key byte key[0]). Note: the output of the PRGA may be recovered by a xor of cipher text versus plain text (the plain text of the first few bytes is usually known: \xaa\xaa\x03). (would be interesting to put about 16 random bytes before the actual llc header...). We can re iterate through the process to attack the 4rth byte of the seed and so on. Notice that it is an incremental attack, so recovery of early seed bytes is crutial. I do not quite agree with h1kari here... From [2]: ... "ivs that match: (A + 3, N - 1, X) This is a particular condition that works almost all of the time and is not dependent on the preceding keys. " This attack relies on these points: - output is S[byte] (I call this partially resolved) - seed resolves at stage byte There is a subtle point here... resolves at stage BYTE. We only know stage byte-1 however. Infact we may only check if it resolves at stage b-1 which is ok but the case where the actual seed resolves at the next stage may exist (more about this later). We can check for the first condition, which is effectivly our IV filter. For the first output byte of the PRGA: &Z depends on X and Y &Y depends on X &X is 1 Note: We only know values of S which are at a position < byte because of the point made before that i is incremental. This means that X < byte (so we can calculate Y) and X+Y % N == byte. This is infact the suggested IV filter formula of KSA. Part 2: New? stuff ================== 1. Extension to KSA's IV filter (class 4) The SIR [3] paper suggests to check for this 13% class. Their approach was to check for duplicate values among X,Y,Z. Note that there is a unique element per index in the S array so we are effectively checking if we rely on only 2 elements in the S array. The way I saw the "problem" was: Is there duplication among the INDEX of X,Y or Z. Well for the FMS attack to work we know that &Z is byte. We also know that &X is 1 (for the first output byte). The first key byte is 3 so we will never get &Z to be 1. This leaves us with &Y which has to be 1 or byte. If &Y is 1, then X has to be 1 and so will Y, resulting in Z == 2. No good. This leaves us with &Y == byte. Which means X == byte. The FMS IV filter will fail since we do not know bytes at index > byte-1 (because of the usual i is incremental...). This is why I doubt that current software based on the FMS IV filter is able to detect such classes of iv's. However the whole attack relies on the output being S[byte] se we can safely assume we know S[byte] (it will just be the output). This will simply modify the FMS equation with X <= byte. Going back to the previous discussion, we now have: X = byte Y = Z = output Our goal is to output S[byte] so we need X+Y = byte. This leaves us with only one option for Y: 0. So if we have an output of Z = Y = 0, X = byte, we only rely on two elements not swapping, resulting in a probability of e^(-2) approx 13%. However notice in PRGA there is a swap before the actual output. &X and &Y are swapped. Normally this is not an issue since &Z is distinct from &X and &Y. However here &Z == &Y. This means that &X and &Z will swap before the output, resulting in X being the output. This may be used as a pre-ksa filter (such as h1kari's "fast iv filter") since we know that if a IV outputs byte it may be interesting. In the key recovery process however we treat everything before the PRGA swap and assume the output was a 0, so we search for a 0 in state at stage byte-1. 2. Cases that resolve at stage byte (and not byte-1) As previously noted, the correct definition of resolved is if at stage byte the wanted elements do not swap. The problem is that we may only check at stage byte-1 and there are circumstances in which the seed resolves at the next stage. There are some methos of detecting them but they rely on j being a specific value (thus are key dependant). For this reason, they might not reliable for use in practice. 2.1 5% Family "late resolve" cases Class 2: If at stage byte-1 we have: X=0 S[byte]=byte S[0]=Y=output If at the next step (i=byte), J=indexofy we will have (because of swap(&Y,byte)) X=0 S[byte]=output S[0]=Y=byte Which is a possible candidate. Class 3: Stage byte-1: X=output s[byte]=0 s[0]=Y=byte Next step J=indexofx swap(&X,byte) X=0 s[byte]=output s[0]=Y=byte 2.2 13% Family "late resolve cases" Class 5: Stage byte-1: X=0 s[byte]=byte Next step J=indexofx swap(&X,byte) X=byte s[byte]=Y=0 Note the other case J=indexofy does not "exist" since we will swap(byte,byte) 3. Other classes Class 7: Stage byte-1: X=indexofx-byte s[byte]=byte Next step J=indexofx swap(&X,byte) X=byte s[byte]=Y=indexofx-byte PRGA: I=indexofx X=byte J=byte Y=indexofx-byte X+Y=byte+indexofx-byte=indexofx swap(X,Y) Z=S[indexofx]=X=indexofx-byte (this relies on 2 elements only aswell) Class 6: Stage byte-1: X=byte Next step J=indexofx-byte swap(j,byte) X=byte s[byte]=Y=s[indexofx-byte] s[indexofx-byte] is usually equal to indexofx-byte because it is a value > byte-1 and it probably didn't get scrambled yet.. remember modulo N. Anyway that is the output so we can check. Then just follow the discussion above. 4. Mathematics (greetz Rafterman@freenode#math) The general formula for the probability of n elements not swapping after stage x is: P = [ (N-n)/N ] ^ (N-x) in our case N = 256; e.g. P = [ (256-3)/256 ] ^ (256-3) = ~.051 P = [ (256-2)/256 ] ^ (256-3) = ~.137 Once we calculate the probability for an individual iv we need to add the probabilities of all candidates. Suppose we have 5 candidates that say correct key value is 10 and each candidate has a 5% chance of being right. The general formula is: P(k) = 1 - (1-p1)^n1*(1-p2)^n1*(1-p3)^n3.... where p1 is the probability of candidate class 1 and n is count of candidates of class 1 and so on. e.g. P(k) = 1 - (1-.051)^60 = ~.957 That is why FMS reccomend 60 weak iv's. 5. Practical implementation I'm working on it... no info at this point... check out: http://sorbo.darkircop.org 6. Conclusion These additional IV's are crucial when performing the KSA attack where collected data is minimal. Also, it will reduce the time of the attack as the correct candidate for the key byte will have a higher probability than the rest. Why all this? well here is a little story... Once upon a time, 22 megs flew through the sky then one second on my laptop went by and now finally on the internet I can fly. Basically a guy that lives opposite my road uses wep. 7. References [1] Fluhrer, S. Mantin, I. and Shamir A. - Weaknesses in the Key Scheduling Algorithm of RC4. [2] Hulton, David (h1kari) - Practical Exploitation of RC4 Weaknesses in WEP Environments [3] Stubblefield, A. Ioannidis, J. and Rubin, A. - Using the Fluhrer, Mantin, and Shamir Attack to Break WEP