Picking a Trivial Lock: Various Means of Cracking WEP

The next step on your way to complete WLAN control is cracking WEP. As mentioned, wireless attacks do not start and end with cracking WEP, as many security experts might tell you. However, if the attacker cannot break WEP (if present), all he or she can do is disrupt the network operations by DoS attacks on layers below the protocol WEP implementation.

From the section dealing with WEP cracking tools, you have probably gathered that there are three major ways of attacking WEP:

Because this book is a down-to-earth guide to wireless security and hundreds of pages have already been written on WEP weaknesses and cracking mathematics, we do not aim to provide a comprehensive guide to the mathematical internals of WEP cracking attacks. Nevertheless, we believe it is important to present some cryptological data on WEP as an act of homage to all researchers who contributed to the WEP analysis and flaw enumeration.

WEP Brute-Forcing

Pure WEP keyspace brute-forcing with tools such as wep_tools or dwepcrack brute-forcing options is realistic only against 40-bit WEP keys. Even with this limited key size, it might take about 50 days on a single average Pentium III host. Nevertheless, an efficient distributed attack against 40-bit WEP is possible and one should never underestimate the potential of dictionary attacks, which are also applicable to 128-bit and higher WEP key size. In particular, it applies to the use of the newer Wepattack tool that can run dictionary attacks against a single captured data packet encrypted using WEP.

Tim Newsham has pointed out that the algorithm accepted as the de facto standard for 40-bit WEP key generation by many wireless equipment vendors is extremely flawed. It starts from folding a password string into a 32-bit number that reduces the keyspace from 2⁴⁰ to 2³² bits. This number is employed to seed a pseudorandom number generator (PRNG; see Chapter 11), which is used to derive all four 40-bit WEP keys used on the network. Although the PRNG-generated keyspace has a cycle length of 2³² bits, because of the way the values are derived from the PRNG, the actual cycle length of drawn values is only 2²⁴ bits. To be more specific, a seed x produces the same keys as a seed x + 2²⁴. To make the situation even worse, the method chosen to fold a password string into a 32-bit seed ensures that the high bit of each of the four bytes always equals zero. The effect of these weaknesses combined is that the algorithm can only generate 2²¹ unique sets of WEP keys, corresponding to seeds between 0 and 0x1000000, which do not have bits 0x80, 0x8000, or 0x800000 set. Thus, it takes 2²¹ operations or less to crack any set of WEP keys generated from a password processed with such an algorithm. In Newsham's observations, this corresponds roughly to 90 seconds of cracking time on a 233-MHz PII or 35 seconds on a 500-MHz PIII; this is quite a difference if compared to 50 days of brute-forcing without this flaw.

However, not all vendors used the vulnerable key generation algorithm (to our knowledge, 3Com never did), 40-bit keys aren't used much anymore, and there are tools that ensure proper 40-bit key generation. An example of such a tool is dwepkeygen, included as part of BSD-airtools. In addition, to crack WEP using wep_tools, a large (about 24 Gb) pcap-format dump file is required. Thus, although Newsham's comments are interesting and have their place in the history of wireless cryptanalysis, we do not recommend trying the attack he developed or using brute-forcing in general against 128/104-bit WEP keys used by modern wireless networks.

However if you have truly massive traffic dump files, trying a dictionary attack using wep_tools or dwepcrack could bring success. Even better, you can try your luck with a dictionary attack against a single captured data packet or limited-size traffic dumps using Wepattack.

The FMS Attack

The most common attack against WEP is Scott Fluhrer, Itsik Mantin, and Adi Shamir's (FMS) key recovery methodology discovered in 2001 (the original paper entitled "Weaknesses in the Key Scheduling Algorithm of RC4" is available from http://www.cs.umd.edu/~waa/class-pubs/rc4_ksaproc.ps). As you already know, this attack was implemented first by the Wep_crack and then by AirSnort. For those interested in how the attack algorithms work, we present a brief explanation here. If you are already familiar with the FMS attack or aren't interested in the "theoretical" cryptanalysis, feel free to skip this section and move forward.

Some IVs set up RC4 cipher (see Chapter 11) the way it can reveal key information in its output bytes.
Invariance weakness allows use of the output bytes to determine the most probable key bytes.
The first output bytes are always predictable because they contain the SNAP header defined by the IEEE specification.

A WEP key can be defined as K=IV.SK where SK is the secret key. The RC4 operation in a nutshell is K=IV.SK ---> KSA(K) ---> PRNG(K) XOR data stream. The scheduling algorithm KSA(K) works in the following way:

Some IVs initialize the PRNG the way the first byte in the stream is generated using a byte from the secret key. Because the first data byte that the PRNG output is XORed with is predictable (SNAP header), it is easy to derive the first PRNG byte. The values we can get from weak IVs are only true about 5 percent of the time; some are true about 13 percent of the time. Taking into account the key size, it takes six to eight million packets of analysis to determine the correct WEP key. The theoretical packets throughput maximum ("wire speed") on the throughput-comparable to 802.11b LAN 10Base-T shared Ethernet is 812 frames per second (frame size of 1,518 bits). If we divide 6,000,000 by 812 we will get about 7,389 seconds or just above 2 hours necessary to accumulate enough packets for efficient WEP cracking. However, as we will see, the reality is different.

The basic FMS attack comes down to searching for IVs that conform to the (A + 3, N - 1, X) rule, where A is the byte in the secret key you are cracking, N is the size of the S-box (256) and X is a random number. It is advised that the following equations are applied right after the KSA:

The main problem is that such an equation is dependent on the previous key bytes, so it must be applied to the entire packet dump for every key byte that is tested. In its classical form, the FMS attack tests only the first byte of the output because it is very reliable; we know that the first byte of the SNAP header is nearly always 0xAA.

An Improved FMS Attack

To bypass this problem and optimize the FMS attack, H1kari of Dasb0den Labs has analyzed the patterns of weak Ivs appearance and how they relate to the key bytes they rely on. As he pointed out in the "Practical Exploitation of RC4 Weaknesses in WEP Environments" article (a must-read for any serious wireless security professional; available at http://www.dachb0den.com/projects/bsd-airtools/wepexp.txt), a basic pattern present can be defined as follows:

From this distribution a rough estimate of weak IVs per key byte can be derived. There are other means of deriving this value as outlined in the referenced article. However, the real catch is to find an algorithm that will allow filtering out weak IVs based on the secret key byte that they can attack. This can be done with an algorithm similar to this:

Such methodology effectively reduces the search time for each key by at least 1/20, thus giving us the time necessary to crack WEP. Now you don't need to collect 6,000,000 packets or more; half a million packets could be sufficient! This is the improved FMS attack as implemented by BSD-airtools dwepcrack; read its source code to discover and learn more.

The practicality of WEP cracking attacks is still denied by many. There are statements that, for example, a home or SOHO WLAN will not generate enough traffic to collect a sufficient amount of weak or interesting IVs for the key compromise in a reasonable time period. You just saw a methodology that can significantly cut the necessary data collected and this methodology has been implemented in a security auditing tool since the year 2001! However, even if the most commonly used WEP cracking tool, AirSnort, is employed, the results can be less than encouraging for the few remaining WEP enthusiasts. In our experience it takes only 3,000 to 3,500 interesting IVs frames to break the WEP key for either 64-bit or 128-bit WEP keys using AirSnort. The only difference mentioned between cracking the keys of both sizes is the amount of time necessary to collect these frames. It took 10 to 20 percent more time to collect the necessary amount of interesting IVs frames to obtain a 128-bit key on a testing wireless network. Our record of breaking a 64-bit WEP with AirSnort is 1 hour 47 minutes on a point-to-point 802.11b link with one of the hosts flood pinging the other (approximately 300 packets per second). Such an attack required 107 minutes * 300 packets/second = 1,926,000 packets, much less than the 6,000,000 packets estimated theoretically. It could've been sheer luck, but would you base your network security on guesswork considering how lucky or unlucky an attacker might be?

On a large, corporate wireless network, 300 packets per second is neither unusual nor unexpected, especially with 802.11a and 802.11g standards offering higher bandwidth and network throughput. The presence of "chatty" network protocols (RIP, link-state routing protocols "hello" packets, spanning tree, HSRP, VRRP, NetBIOS, IPX RIP and SAP, AppleTalk, etc.) might dramatically decrease the time needed to crack WEP. It also generates wireless traffic even when no user activity is present. Imagine a large wireless Novell-based network running NetBIOS over IPX and using three Cisco routers with turned-on hot standby for failover resilience and enabled CDP (we have seen networks like this in the United Kingdom on several occasions). Such a network does not have to be the WLAN itself; leaking wired traffic on the wireless side is sufficient and we have frequently seen access points plugged directly into the switch or hub. Let's say there are 100 hosts on the network and no user activity present. In one hour, every host will generate approximately 1,200 NetBIOS keep-alives, 40 IPX RIPs, and 40 SAPs, and each router will send 1,200 HSRP Hello packets and 60 CDP frames if the defaults aren't changed (they rarely are), as well as the obvious 40 RIPs. Thus, the number of generated packets will be 100x(1,200+40+40) + 3x(1,200+60+40) = 131,900 packets per hour. Thus, accumulating the 2,000,000 packets necessary to crack WEP with AirSnort in our example will take approximately 15 hours. With dwepcrack as few as 500,000 packets might be needed, which translates into approximately 3 hours, 47 minutes, without a single user logged in! Remember that this network is both perfect and hypothetical. In reality, a Novell server might send more than one SAP in 90 seconds because a single SAP packet can advertise up to seven services and the server might run more. NLSP might be running and STP traffic could be present. We frequently find networks with system administrators completely unaware of the unnecessary and unused STP traffic on the network and some higher end switches and even wireless access points have STP enabled by default. Mind the traffic!

Finally, in some cases, old 802.11b cards use the same IV value or start counting IV numbers from 0 each time the card is initialized and increments these numbers by one. This also significantly cuts the time necessary to crack WEP.

How about cracking WEP on 802.11a networks? It is essentially the same. The only difference is that we aren't aware of decent 802.11a support on BSD and AirSnort will not work with ark_5k. However, you can save a pcap-format 802.11a traffic dump file obtained using an Atheros chipset card in the RFMON mode and tcpdump (or Kismet) and feed it to AirSnort or even dwepcrack (after booting into BSD). If you want real-time WEP cracking on an 802.11a network, use wepcrack and the power of at/crond as we have described. For example, you can pipe tcpdump output into prism-getIV.pl and then process the IVFile.log file with WEPCrack.pl.