Nytro Posted September 9, 2013 Report Posted September 9, 2013 Practical Exploitation of RC4 Weaknesses in WEP EnvironmentsPractical Exploitation of RC4 Weaknesses in WEP EnvironmentsFebruary 22, 2002by David Hulton <h1kari@dachb0den.com> - (c) Dachb0den Labs 2002[http://www.dachb0den.com/projects/bsd-airtools.html]1. IntroductionThis document will give a brief background on 802.11b based WEP weaknesses andoutline a few additional flaws in rc4 that stem off of the concepts outlinedin "Weaknesses in the Key Scheduling Algorithm of RC4" (FMS) and "Using theFluhrer, Mantin, and Shamir Attack to Break WEP" (SIR) and describes specificmethods that will allow you to optimize key recovery. This document isprovided as a conceptual supplement to dweputils, a wep auditing toolset,which is part of the bsd-airtools package provided by Dachb0den Labs. Thebasic goal of the article is to provide technical details on how toeffectively implement the FMS attack so that it works efficiently with both asmall amount of iv collection time as well as cracking and processing time andto provide details on how other pseudo random generation algorithm (prga)output bytes reveal key information.2. BackgroundWEP is based on RSA's rc4 stream cipher and uses a 24-bit initializationvector (iv), which is concatenated with a 40-bit or 104-bit secret shared keyto create a 64-bit or 128-bit key which is used as the rc4 seed. Most cardseither generate the 24-bit iv using a counter or by using some sort of pseudorandom number generator (prng). The payload is then encrypted along with anappended 32-bit checksum and sent out with the iv in plaintext as illustrated: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | 802.11 Header | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IV[0] | IV[1] | IV[2] | Key ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . . . . . . SNAP[0] . . . . . | . . . . . SNAP[1] . . . . . . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . . . . . . SNAP[2] . . . . . | . . . . Protocol ID . . . . . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | | . . . . . . . . . . . . . Payload . . . . . . . . . . . . . . | | . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . . . . . . . . . . . 32-bit Checksum . . . . . . . . . . . . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ . - denotes encrypted portion of packetAfter the data is sent out, the receiver simply concatenates the received ivwith their secret key to decrypt the payload. If the checksum checks out, thenthe packet is valid.2.1. Current Cracking MethodsEssentially, most of the wep attacks out there these days are either based onbrute forcing methods, often times including optimizations based on how thekey is generated or by using a wordlist, or through statistical analysis ofinitialization vectors (ivs) and their first rc4 output byte, to setupconditions in the rc4 key scheduling algorithm (ksa) that reveal informationabout particular bytes in the secret key.2.1.1. Brute ForcingBrute forcing has been proven to be an effective method of breaking wep,mainly thanks to all of the work done by Tim Newsham. This method basicallyconsists of trying to decrypt the encrypted payload of a captured 802.11bpacket using a set of keys and verifying the validity by seeing if the 32-bitchecksum checks out. In most cases, if the key checks out it is important tocheck it with another packet to make sure the key is actually valid, sincemany times the packet can be decrypted with an invalid key and the checksumwill be valid. This mode of attack generally only requires 2 packets.Tim Newsham's most effective cracking method stems off of the weaknesses inthe password based key generation algorithm used by most 40-bit cards andaccess points. By taking advantage of this weakness, it reduces the 40-bitkeyspace down to 21-bit, which is trivial to crack (20-40 seconds with mostcurrent-day machines). Also, wordlist attacks prove almost equally effectiveon both 40-bit and 104-bit 802.11b networks, provided you have a decent listof commonly used passphrases. Even without using these optimizations, you canstill exhaust the entire 40-bit keyspace in roughly 45-days on a decentmachine, or in a very reasonable amount of time using a distributed network ofmachines.Although this mode of attack can be applied to many networks out there, itfails to be able to attack a properly secured 104-bit network, since theamount of time required to brute force 104-bit is generally longer than anattacker's great-grandchildren would want to wait.2.1.2. FMS AttackUp until now, all open source wep cracking utilities that use the FMS Attackhave used an extremely limited mode of operation as described in FMS inSection 7.1 "IV Precedes the Secret Key", and is also published by Wagner inWag95, which involves only looking for ivs that match: (A + 3, N - 1, X)This is a particular condition that works almost all of the time and is notdependent on the preceding keys. However, as described later on in FMS inSection A "Applying The Attack to WEP-like Cryptosystems", they recommend thatyou use the following equation on the S permutation immediately after the KSAto determine if an iv is weak: X = S{B + 3}[1] < B + 3 X + S{B + 3}[X] = B + 3This equation uncovers many more ivs than the 256 per key that mostimplementations currently use. This was made obvious in SIR in Section 4.1"Choosing IVs", but wasn't thoroughly expanded on about how to effectively usea pool of logged ivs to successfully perform this attack in a reasonableamount of time.The main dilemmas with applying this equation to all of the IVs that youcollect are that you have to check all of your logged ivs at least once forevery key byte that you try, and that it takes a considerable amount ofresources to apply this algorithm to a set of 2,000,000 ivs. So, not only doyou have to do a large amount of processing, but also for an extremely largeset of possibilities.Also, all of the current implementations only attack the 1st rc4 output byte,mainly because it is the one that provides the most accurate information aboutthe key bytes. However, by attacking the other bytes, it can also provideclues, although minute, to the static key that was used. This can sometimeprovide enough statistical data to derive key bytes in cases when you aren'table to collect a large amount of captured data, and have more time to spendprocessing.3. Additional Flaws in the KSAThe main flaw with rc4 that hasn't been thoroughly expanded, is usinginformation provided by other bytes in the prga output stream. This attack issimilar to the FMS attack, but requires additional processing because you haveto also emulate portions of the pseudo random generation algorithm (prga) todetermine if an iv gives out key information in byte A. However, the bytesthat you can attack using this method directly depend on the bytes of the keyyou have already recovered and are extremely hard to predict without excessiveprocessing. To demonstrate this, I will first provide background on thecurrent common mode of attack which attacks the first output byte and thenshow how it can be expanded to other bytes.3.1. Attacking the First ByteThe first byte attack works based on the fact that you can simulate part ofthe ksa using the known iv and derive the values of elements in the Spermutation that will only change 1 - (e ** -X) of the time, where X is thenumber of S elements that your attack depends on. This can be illustrated asfollows when attacking the first byte in the secret key (SK): Definitions: 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]] - For demonstration purposes N = 16, although it is normally 256 - Also, all addition and subtraction operations are carried out modulo N and negative results are added with N so results are always 0 <= x < N. Simulation: let B = 0 - byte in K that we are attacking let IV = B + 3, f, 7 let SK = 1, 2, 3, 4, 5 let K = IV . SK let l = the amount of elements in K assume that no S elements get swapped when i > B + 3 KSA - K = 3, f, 8, 1, 2, 3, 4, 5 Known Portion: 0 1 2 3 4 5 6 7 8 9 a b c d e f j S[i] K 3 0 i = 0, j = 0 + 0 + 3 = 3 0 1 i = 1, j = 3 + 1 + f = 3 d 2 i = 2, j = 3 + 2 + 8 = d Unknown Portion: f 1 i = 3, j = d + 1 + 1 = f - Note that S[B + 3] always contains information relating to SK[B], since SK[B] is used to calculate j. PRGA - S = 3, 0, d, f, 4, 5, 6, 7, 8, 9, a, b, c, 2, e, 1 Unknown Portion: 0 1 2 3 4 5 6 7 8 9 a b c d e f j S[i] S[i] S[j] 3 0 d f 4 5 6 7 8 9 a b c 2 e 1 Unknown KSA Output 0 3 i = 1, j = 0 + 0 = 0, z = S[0 + 3] = fIn this instance, f will be output as the first PRGA byte, which is in turnxor'ed with the first byte of the snap header. The first byte of the snapheader is almost always 0xaa, so we can easily derive the original f by simplyxor'ing the first byte in our encrypted payload with 0xaa. To reverse the fback into the first byte of the SK that was used to generate it, we justiterate through the KSA up until the point where we know the j and S[i] valuesthat were used to derive the f as provided in the previous demonstration. Oncethe j and S[i] values are derived, we can easily reverse it to SK[B] asillustrated: Definitions: let S{-1}[Out] be the location of Out in the S permutation let Out be z in the first iteration of the PRGA assume values in Known Portion of KSA from where i = 2 SK[B] = S{-1}[Out] - j - S[i + 1] Application: SK[B] = S{-1}[f] - c - S[3] = f - d - 1 = 1This method provides us with the correct key roughly e ** -3 =~ 5% of thetime, and sometimes e ** -2 =~ 13% of the time in some cases when we only relyon 2 elements in the S permutation staying the same. As you can see in the ksaand prga simulation above, we only rely on elements 0, 1, and 3 not changingfor the output byte to be reliable, so the probability of our output bytebeing f is 5%.By collecting many different SK[B] values the correct SK[B] values shouldbecome more evident as more data is collected. Additionally, once we determinethe most probable value for the first byte in the secret key, we can apply thesame algorithm to cracking the next byte in the secret key, and continue untilwe have cracked the entire secret key. In most implementations this method iscombined with brute forcing so the odds don't have to be perfect in order torecover the key.3.2. Attacking Additional Output BytesThis section will demonstrate a set of new unique ivs that provide clues tovarious bytes in the secret key and in some cases with greater probabilitythan the first bytes. I will first demonstrate what happens when rc4encounters one of these ivs, and then provide methods for detecting them.3.2.1. RC4 Encounters a 2nd-Byte Weak IVIn this demonstration, I will use a weak iv that attacks the 2nd byte and showhow certain ivs setup the S permutation so that secret key information isrevealed in the 2nd byte of output. This method also applies to other outputbytes and can be expanded depending on which secret key byte you areattacking. Here is what happens: Simulation: let B = 0 - byte in K that we are attacking let IV = 4, c, c let SK = 1, 2, 3, 4, 5 let K = IV . SK assume that no S elements get swapped when i > B + 3 KSA - K = 4, c, c, 1, 2, 3, 4, 5 Known Portion: 0 1 2 3 4 5 6 7 8 9 a b c d e f j S[i] K 4 0 i = 0, j = 0 + 0 + 4 = 4 1 i = 1, j = 4 + 1 + c = 1 f 2 i = 2, j = 1 + 2 + c = f Unknown Portion: 3 i = 3, j = f + 3 + 1 = 3 PRGA - S = 4, 1, f, 3, 0, 5, 6, 7, 8, 9, a, b, c, d, e, 2 Unknown Portion: 0 1 2 3 4 5 6 7 8 9 a b c d e f j S[i] S[i] S[j] 4 1 f 3 0 5 6 7 8 9 a b c d e 2 Unknown KSA Output 1 i = 1, j = 0 + 1 = 1, z = S[1 + 1] = f f 4 i = 2, j = 1 + f = 0, z = S[f + 4] = 3Then, since we also often times know that the second byte of the snap headeris 0xaa, we can determine the 2nd byte of prga output and reverse it back tothe original key, as demonstrated: SK[B] = S{-1}[3] - f - S[3] = 3 - f - 3 = 1As you can see, this particular iv will setup the ksa and prga so that thesecond output byte provides information about the first byte of our key inalmost every situation. Additionally, it relies on elements 0, 1, 2, and 3 notchanging for the second byte to be accurate, so it will only be correcte ** -4 =~ 2% of the time. Additionally, in cases where the previous outputbytes are derived from dependent elements, we can check to see if the actualoutputted byte matches up and determine if the output we are receiving hasbeen tampered with. In addition, if the output matches up, it greatlyincreases our odds since we now rely on less elements. In this particularcase, if the first output byte checked out, it would increase our probabilitywith the 2nd byte to e ** -2 =~ 13%.3.2.2. Finding Weak IVs for Additional Output BytesThe main problem with attacking additional output bytes is determining if aniv will reveal part of the secret key in a particular output byte, and alsodetermining if the probabilities are good enough to even consider it. How wecan detect if an iv is vulnerable to this sort of attack is similar to thefirst byte attack, but it requires looping through the prga up untili = (A + 1) where A = the offset in the prga stream of the byte you know thevalue for. For each iteration of the prga loop, if there are any instanceswhere j or i >= B + 3, we must discard the iv, since then we are relying onelements in the S permutation that will most likely change. This can beaccomplished by modifying the prga algorithm so that it is similar to: PRGA(K) Initialization: For i = 0 ... N - 1 P[i] = 0 P[B + 3] = 1 i = 0 j = 0 Generation Loop: While i < A + 1 i = i + 1 j = j + S[i] If i or j >= B + 3 Then Fail Swap(S[i], S[j]) Output z = S[S[i] + S[j]] P[i] = 1 P[j] = 1 Verification: If S[i] + S[j] = B + 3 Then Success Probability Analysis: j = 0 For i = 0 ... N - 1 If P[i] > 0 Then j = j + 1This algorithm also works almost identically to the equation for determiningif an iv is vulnerable to the first byte attack and can be expanded todetecting ivs that reveal keys in any byte in the prga output. You can thenweigh the probabilities and determine if it is worth considering.In tests, this method doesn't prove entirely useful, mainly due to the amountof processing that is required to determine if certain ivs have this property.Since each iv has to be checked for each previous secret key byte that youtry, it would probably be most practical to manually derive a table ofvulnerable ivs, so it doesn't require much work during key recovery.In most cases it'd be more practical to collect more ivs and only use thefirst bytes to perform key recovery, however in cases when you have a limitedset of sample data, it could greatly reduce the time required for recovery.4. ImplementationThis section will focus on practical methods for making use of all of the 1stbyte weak ivs without hindering performance. It will also cover optimizationsfor applying brute forcing and fudging methods to greatly reduce crackingtime. The result of the optimizations will allow you to perform key recoverywith only 500,000-2,000,000 packets and < 1 minute processing time.Although, in SIR it is mentioned that they were able to crack wep with asimilar number of packets, this mode of attack does not require that the wepkey be ascii characters, and isn't dependent on what key generator the victimused.4.1. Filtering Weak IVsThe main problem with attacking wep using all of the first byte weak ivs, isthat the equation specified in FMS has to be applied to each of the ivs forevery key that you try. Since often times you'll have a total of 2,000,000packets that you've collected and thousands of keys you need to try before youfind the correct one. It has thus far been impractical to use this mode ofattack, since it requires a large amount of memory as well as resources.The way I have managed to get around this dilemma is by analyzing the patternsof weak ivs and how they are related to the key bytes they rely on. This isthe basic pattern that I've found. Definitions: let x = iv[0] let y = iv[1] let z = iv[2] let a = x + y let b = (x + y) - z Byte 0: x = 3 and y = 255 a = 0 or 1 and b = 2 Byte 1: x = 4 and y = 255 a = 0 or 2 and b = SK[0] + 5 Byte 2: x = 5 and y = 255 a = 0 or 3 and b = SK[0] + SK[1] + 9 a = 1 and b = 1 or 6 + SK[0] or 5 + SK[0] a = 2 and b = 6 Byte 3: x = 6 and y = 255 a = 0 or 4 and b = SK[0] + SK[1] + SK[2] + 14 a = 1 and b = 0 or SK[0] + SK[1] + 10 or SK[0] + SK[1] + 9 a = 3 and b = 8 Byte 4: x = 7 and y = 255 a = 0 or 5 and b = SK[0] + SK[1] + SK[2] + SK[3] + 20 a = 1 and b = 255 or SK[0] + SK[1] + SK[2] + 15 or SK[0] + SK[1] + SK[2] + 14 a = 2 and b = SK[0] + SK[1] + 11 or SK[0] + SK[1] + 9 a = 3 and b = SK[0] + 11 a = 4 and b = 10This pattern can then be easily expanded into an equation that covers a rangeindependent of what SK values you have. As a result, you have distributionpattern similar to the one shown below: Secret Key Byte 0 1 2 3 4 5 6 7 8 9 a b c + + + + + + 0 8 16 16 16 16 16 16 16 16 16 16 16 16 1 8 16 16 16 16 16 16 16 16 16 16 16 2 16 8 16 16 16 16 16 16 16 16 16 a 3 16 8 16 16 16 16 16 16 16 16 4 16 8 16 16 16 16 16 16 16 V 5 16 8 16 16 16 16 16 16 a 6 16 8 16 16 16 16 16 l 7 16 8 16 16 16 16 16 u 8 16 8 16 16 16 16 e 9 16 8 16 16 16 s a 16 8 16 16 b 16 8 16 c 16 8 d 16 8 - 8-bit set of weak ivs 16 - 16-bit set of weak ivs + - 2 additional x and y dependent 8-bit weak ivsFrom this, we can determine a rough estimate of how many total weak ivs existfor each key byte. It can also be determined using the following equation: let ? : be conditional operators let MAX(x, y) be x > y ? x : y ((B mod 2 ? MAX(B - 2, 0) + 2 : B + 1) * (2 ** 16)) + (((B mod 2 ? 0 : 2) + (B > 1 ? 1 : 0) + 1) * (2 ** 8))However, our real objective is to determine an algorithm that allows us tofilter out weak ivs based on the secret key byte that they can attack, so thatwe can narrow our 2,000,000 element table down to a reasonable size that'seasier to search. This can be accomplished by using a simple algorithm similarto: let l = the amount of elements in SK i = 0 For B = 0 ... l - 1 If (((0 <= a and a < or (a = B and b = (B + 1) * 2)) and (B % 2 ? a != (B + 1) / 2 : 1)) or (a = B + 1 and (B = 0 ? b = (B + 1) * 2 : 1)) or (x = B + 3 and y = N - 1) or (B != 0 and !(B % 2) ? (x = 1 and y = (B / 2) + 1) or (x = (B / 2) + 2 and y = (N - 1) - x) : 0) Then ReportWeakIVThis algorithm results in catching the following distribution of ivs: Byte # of IVs Probability 0 768 0.00004578 1 131328 0.00782776 2 197376 0.01176453 3 197120 0.01174927 4 328703 0.01959223 5 328192 0.01956177 6 459520 0.02738953 7 459264 0.02737427 8 590592 0.03520203 9 590336 0.03518677 a 721664 0.04301453 b 721408 0.04299927 c 852736 0.05082703Which should differ slightly from the previous weak iv estimation equationsince some ivs in the pattern overlap. By sorting these IVs into tables, youcan very easily narrow down the amount of ivs to search for each crackingoperation to a maximum of 852,736 ivs, or around only 101,654 when suppliedwith a 2,000,000 packet capture file. This effectively reduces the search timefor each key by at least 1/20.4.2. FudgingWhen trying to recover keys using a capture file that doesn't statisticallyprovide enough immediate information to determine the secret key, it is commonto perform a brute force based on the most probable key bytes. Up until nowthe fudge, or breadth, has been implemented as a static number that specifiesthe range to search for each key byte. However, with > 2,000,000 samples and alarge amount of weak ivs for each byte the probability that the correct keywill be the most probable gets greater as you traverse through each byte. Aestimate of the probabilities for this are outlined below: Byte # of IVs Probability 0 768 0.00004578 1 768 0.00004578 2 2304 0.00013732 3 1792 0.00010681 4 3072 0.00018311 5 2560 0.00015259 6 4096 0.00024414 7 3584 0.00021362 8 5120 0.00030518 9 4608 0.00027466 a 6144 0.00036621 b 5632 0.00033569 c 6656 0.00039673Therefore, when attempting to brute force based on a 2,000,000 sample set,your IVs will most likely be near: Byte # of IVs # of Correct Keys 0 92 5 1 92 5 2 275 14 3 214 11 4 366 18 5 305 15 6 488 24 7 427 21 8 610 30 9 549 27 a 732 36 b 671 33 c 793 39Therefore, it's most likely that once you reach byte 2, the key that seemsmost probable, most likely is. This means that fudging is most likely notrequired, or at the least should be reduced, the farther you move through thebytes. This reduces the brute forcing time required considerably, since now itis only necessary to fudge the first few bytes of the key, and the rest is nolonger necessary. I have found in most cases, because of this property of weakivs, it requires quite less packets than 2,000,000 to recover the key, andin some cases you don't even require any statistics for the first couple bytesof the secret key to perform this attack in a very reasonable amount of time.5. ResultsUsing the outlined modifications, I've managed to crack wep using between500,000 and 2,000,000 packets in under a minute, this is mainly due to thetime required for reading in the packets. Here is an example of a successfulattack using quite less than the 60 required ivs and only ~ 500,000 packets:h1kari@balthasar ~/bsd-airtools/dweputils/dwepcrack$ ./dwepcrack -w ~/log * dwepcrack v0.3a by h1kari <h1kari@dachb0den.com> ** Copyright (c) Dachb0den Labs 2002 [http://dachb0den.com] *reading in captured ivs, snap headers, and samples... donetotal packets: 500986calculating ksa probabilities... 0: 22/768 keys (!) 1: 3535/131328 keys (!) 2: 5459/197376 keys (!) 3: 5424/197120 keys (!) 4: 9313/328703 keys (!)(!) insufficient ivs, must have > 60 for each key (!)(!) probability of success for each key with (!) < 0.5 (!)warming up the grinder... packet length: 44 init vector: 58:f7:26 default tx key: 0progress: ....................................wep keys successfully cracked! 0: xx:xx:xx:xx:xx *done.6. ConclusionsThe best solution for securing your wireless networks is using traditionalwireless security to its fullest, but not relying on it. Manually enter inyour wep keys and don't use the key generator (or use dwepkeygen ;-Q), changeyour wep keys frequently, use mac filtering and shared key authentication, andlabel your wireless network as untrusted (and no, I don't necessarily mean setyour ssid to "untrusted"). Wireless networks, just like any other networks,are proportionately insecure to the stupidity of the person managing them.References[1] Fluhrer, S. Mantin, I. and Shamir A. - Weaknesses in the Key Scheduling Algorithm of RC4.[2] Stubblefield, A. Ioannidis, J. and Rubin, A. - Using the Fluhrer, Mantin, and Shamir Attack to Break WEP[3] Newsham, T. - Cracking WEP Keys. Presented at Blackhat 2001.Sursa: http://www.dartmouth.edu/~madory/RC4/wepexp.txt Quote