Brute-forcing WEP Keys

Some people wonder why anyone would bother brute-forcing a 40-bit key when so many other attacks can be leveled against WEP. There are two compelling reasons to try to brute-force a WEP key. One reason is that brute-forcing a WEP key takes a fixed amount of work. Depending on the resources you can muster, you can realistically crack a 40-bit key in 24 hours, worst case. Using statistical attacks, the amount of time can vary wildly as a function of your luck and the data collected.

The other compelling reason to brute-force a WEP key is that it is the only way to know if, in fact, the target is using a 40-bit key. Networks don't advertise the key size they are using. If you know the secret key, you obviously don't need to have someone tell you the size. Attempting to brute-force a 40-bit key and failing is currently the only way to know you have a 104-bit key on your hands.

Brute-forcing WEP Keys on Linux and OS X

If you are going to brute-force WEP keys, you will want some sort of distributed solution. Such a solution lets you use all the computers that you control to do the job in parallel. There is currently only one distributed WEP brute-forcer, jc-wepcrack.

jc-wepcrack is included as part of Airbase. You can think of jc-wepcrack as a sort of SETI at home for cracking WEP keys. jc-wepcrack is broken into two parts, a client and a server. To use jc-wepcrack, launch the server by telling it the key size you think the network is using, pass it a pcap file, and stand back. Once jc-wepcrackd is under way, you can run a client program on any computer you have access to. The client program talks to the server, checks out a chunk of the keyspace, and starts cracking. The client will either find the key or tell the server it's not there and ask for another.

jc-wepcrack was designed with portability in mind. It is known to compile and run on x86-based Linux distributions and both Intel-and PowerPC-based Macs. jc-wepcrack allows PowerPC-based clients to talk to x86 servers and vice versa. It also supports saving the state on the server so a cracking job can be stopped and started up again later.

To run the server, jc-wepcrackd, you need to tell it the key size and pass it a pcap file with at least two packets from the network you are interested in. After that, start up as many jc-wepcrack-clients on as many computers as you can. The example here shows a typical setup:

[ johnnycache@galadriel:~/airbase/jc-wepcrack/jcwepcrackd ]$ ./jc-wepcrackd
 -k 40 -f ./path/to/pcapfile.pcap

Once some debugging output flies by, you'll see a screen that looks like the following.

When the server is up and running, it's time to launch some clients. To run a client on the same computer that the server is running on, execute the following command:

[ johnnycache@galadriel:~/airbase/jc-wepcrack/clients/jc-wepcrack-client ]$
./jc-wepcrack-client -s localhost

You will see some debugging output on the client's display, and if you check the jcwepcrackd display, it will show a keyspace chunk checked out. If you are running the client on a remote machine, type in the IP address of the server for the argument to -s.

Hardware-accelerated WEP Cracking

One feature that jc-wepcrack recently gained is the ability to offload the key-cracking work to an external card. In particular, jc-wepcrack has support to use a Field Programmable Gate Array (FPGA)-based board developed by Pico Computing. jc-wepcrack includes a special client, called the pico-client, that instead of brute-forcing the keyspace using the CPU, will use the pico card instead.

FPGAs are little chips that contain an assortment of gates on them. The magic is that the gates aren't connected to anything by default. You can write a program, typically in Verilog or VHDL, that gets synthesized (analogous to compiling) into a .bit image. This image is then written to the card and acts like a program. The FPGA interprets the .bit file as a pattern to connect the gates together. Because the gates can be connected in any way you want, they can do anything that software can do, only typically much faster and in parallel.

Programming FPGAs takes a different mindset than most software developers have. Fortunately, David Hulton (aka h1kari) was kind enough to write the code to make the hardware go, which means that C programs can use the FPGA to do the WEP brute-forcing without knowing all the details of how it works.

To use the hardware-accelerated pico jc-wepcrack-client, you will need a card from Pico Computing. These currently cost somewhere around $2K, placing them well outside the budget of most hackers. It is possible that jc-wepcrack will get support for other, less expensive FPGA boards in the future, however, so hope is not lost.

Assuming you have obtained a card from Pico Computing and have booted it successfully with the appropriate RC4 image file, you can run the pico-client as follows:

[root@phoenix:/home/johnycsh/airbase/jc-wepcrack/clients/pico-client]$
./jc-wepcrack-pico-client -s localhost -d 0 -F ./matrix-blue

Assuming everything went well, you will be greeted with a screen similar to the one shown next. The matrix screensaver in the background is optional.

Other than hardware acceleration, the pico-client behaves just like the normal client. The jc-wepcrackd server gets to remain happily unaware that it has hardware-accelerated clients doing its bidding.

Using Your PS3 to Crack WEP Keys

HD Moore recently contributed a client for jc-wepcrack optimized for running on the Cell Broadband Engine (CBE) CPU. The most likely place to find this processor is in your Playstation 3.

The cell processor is unique because it bundles a handful of vector processing units (called Synergistic Processing Units, or SPUs in Sony marketing speak) with the processor. The way the CBE client works on your PS3 is by checking out six keyspace chunks from the server and running them in parallel on the SPUs. By doing this, you can try WEP keys approximately ten times as fast you could on an unaccelerated software-only client.

In order to run the CBE client on your PS3, you will first need to get Linux installed. Development was done on the gentoo port, but the code is not tightly tied to one particular distribution. You'll also need the spu-elf cross-compiling tools and the SDK (at least, libspe, libspe2) from IBM. Once you have completed that, you can compile and run the cbe-client just like any other jc-wepcrack client. The cbe-client is included inside the clients' directory in jc-wepcrack.

Brute-forcing WEP Keys on a Windows Machine

Currently, there are no known WEP key brute-forcers available on Windows. It may be possible to compile the jc-wepcrack client on Windows under cygwin, however.

Countermeasures for Brute-forcing WEP Keys

Protecting against brute-forcing WEP keys is simple. Use a 104-bit key. Brute-forcing a 104-bit key would take longer than the expected life of the universe. The only way anyone could realistically brute-force a 104-bit key is if it happened to start with 00:00:00:00:00:00:00.

Really though, you shouldn't be using WEP at all. While a randomly generated 104-bit key may be impossible to brute-force, there are still plenty of other attacks possible against WEP.

Dictionary Attacks Against WEP

When the IEEE specified the standard for WEP, they decided not to describe how to convert a passphrase into a WEP key. They might have thought it would be a good idea to leave it unspecified so newer algorithms could be dropped in without modifying the standard. Maybe they thought it would be better to let vendors differentiate themselves. In hindsight, this was a bad idea. Vendors certainly did differentiate themselves-just not in the way people had hoped.

Because the standard doesn't say how to convert a passphrase to a WEP key, there are quite a few different implementations. Two popular techniques are MD5 and the infamous Neesus Datacom technique. There are other possibilities, however. Apple, for example, has its own algorithm. When attempting a dictionary attack against a WEP key, you need to know what algorithm that vendor implements and use the corresponding tool.

Regardless of the algorithm used, all dictionary attacks use the same approach. Read in a list of dictionary words, hash them, and check to see if the created key is correct. When dealing with WEP, tools can verify if the key is correct by checking the ICV field on a WEP-encrypted data packet. Another faster technique is to see if the key creates 8 bytes of cipher-stream that will decrypt the SNAP header of a few packets successfully.

Vulnerabilities in the Neesus Datacom Passphrase Algorithm

Neesus Datacom created one of the first algorithms used to transform passphrases into WEP keys. This algorithm is widely known by the attack launched against it, the Newsham-21-bit attack, which was discovered by Tim Newsham. It is hard to determine what is the most surprising aspect of this algorithm: that it was ever created, that it received such widespread adoption, or that people are still using it.

Basically, the Neesus Datacom algorithm takes the user input passphrase and starts XORing the individual ASCII bytes together to generate a WEP key (this is a simplification of the process, but you get the idea). The attack against it is famous because it can reduce the keyspace of an allegedly 40-bit key down to 21 bits, which can be brute-forced in seconds.

The algorithm has other problems, too. Though commonly referred to as the Newsham-21-bit attack, this same attack, when applied to 104-bit keys, also reduces their size significantly. This smaller key, however, is still beyond the realm of brute-force. When using this algorithm to generate a 104-bit key though, the biggest problem is the number of collisions it generates.

For example, to check if an AP you own uses this algorithm, generate a 40-bit WEP key using the passphrase cat, and then try catt. An AP using the Neesus Datacom algorithm will create the same key. When using 104-bit mode, the problem is still present; it's just not as easy to pick words that collide by hand.

As mentioned earlier, the number of APs that still employ this algorithm is surprising. Personally, I don't even feel that offering the user the ability to generate a key from a passphrase with WEP is useful. Since there is no standard, most of the time users can't enter the passphrase on the client machines anyway, and they still have to enter the "random" hex digits. A quick test of some nearby APs yielded the following results:

Brute-forcing 40-bit Keys Created with the Neesus Datacom Algorithm

As mentioned previously, this is commonly referred to as the Newsham-21-bit attack. A few tools implement this attack, but we are going to use the code originally released by Tim Newsham, wep_crack, because it is easy to compile and is cross-platform. The only downside to using wep_crack is that it doesn't handle pcap files with more than one network in them intelligently. If you have a capture with more than network in it (and you probably do), you will need to provide filtered input to wep_crack. If you don't do this, you won't know which network wep_crack is attacking. Using Wireshark is one easy way to clean up an input file for wep_crack. wep_crack requires at least two encrypted data packets from the network to run.

To perform a brute-force attack using wep_crack, download and compile wep_tools. Once wep_crack has built, run it and pass it the path to the pcap file. The example here illustrates successfully attacking a network that was using a 40-bit key generated with the Neesus Datacom algorithm:

[ johnnycache@galadriel:~/wep_tools ]$ ./wep_crack -b ./cat.pcap
success: seed 0x00746163,  [generated by AAAa" 5a]
wep key 1: d0 43 c5 63 0a
wep key 2: bf 15 5f 8f 03
wep key 3: 08 87 50 54 9f
wep key 4: 6b ef d7 38 7c
1913060 guesses in 9.65 seconds:  198161.11 guesses/second

Dictionary Attacks Against 104-bit Keys Created with the Neesus Datacom Algorithm

If, on the other hand, you want to perform a dictionary attack against what you think is a 104-bit key, you must pass wep_crack the -s flag (s is for strong) and give it a path to a dictionary file. Remember, the nice thing about dictionary attacks against this algorithm is that you don't need to have the exact word in your dictionary file, just something similar that will create the same key. The following example shows the recovery of a 104-bit key:

[johnycsh@phoenix:~/wep_tools]$ ./wep_crack -s ../dictionary-pcaps/
dolphin-104bit-newsham.pcap ../dictionary-pcaps/dict
success: genword dolphin
wep key 1: 26 e3 c9 b2 6e
wep key 2: c8 38 7b 96 dc
wep key 3: d0 ff b3 00 00
wep key 4: 00 00 00 00 00
6 guesses in 0.00 seconds:  17699.12 guesses/second

Dictionary Attacks Against Other Algorithms

As mentioned earlier, the other popular passphrase-to-WEP-key algorithm is MD5. There are many tools that can perform dictionary attacks. Currently, these include weplab, WepAttack, and Kismac. Though the details of these tools differ, the idea is the same as wep_crack. Input a pcap file and a dictionary and hope for the best. Don't think that because your AP employs MD5 to create a WEP key it is secure. Passphrase-generated WEP keys will always be worse than random keys.

Preventing Neesus Datacom and Generic Dictionary Attacks

The moral of this section is simple. Don't let your AP generate a WEP key for you. It is remarkable that the most popular algorithm for this still seems to be Neesus Datacom, despite all the flaws found in 2001. If you are absolutely forced to use WEP for some reason, use a random 104-bit key, change it often, and don't let your AP help you generate it.

Statistical Attacks Against WEP

In 2001, Fluhrer Mantin and Shamir (FMS) released a paper describing a vulnerability in the key scheduling algorithm in RC4. RC4 (Ron's Code version 4) is the stream cipher used by WEP. As it turns out, WEP uses RC4 in a manner that makes it a perfect target for this vulnerability.

The problem is how WEP uses the initialization vectors (IVs) in each packet. When WEP uses RC4 to encrypt a packet, it prepends the IV to the secret key before feeding the key into RC4. This means that the attacker has the first three bytes of an allegedly "secret" key used on every packet. A few equations later and you now have a better than random chance at guessing the rest of the key based on the output of RC4. Once this is accomplished, it is just a matter of collecting enough data and the key falls out of thin air.

The original FMS paper specified IVs with a specific pattern that set up the attack. The paper called these "weak" IVs. Later another class of weak IVs was found by h1kari. After this, KoreK found another 15 attacks. This means that there are 17 different types of "weak" IVs, something few people realize.

Using aircrack to Break WEP on Linux

There are quite a few tools that implement this attack. The two most popular are airsnort and various incarnations of aircrack. The first publicly available implementation of this attack was a set of perl scripts called WEPCrack by Anton Regar. Airsnort, with an easy-to-use GUI, was released later by the Shmoo group.

Later Christophe Devine implemented aircrack, which advanced the speed of statistical attacks against WEP significantly. Ultimately aircrack spawned two new versions, aircrack-ng and jc-aircrack. aircrack-ng focuses on adding features and updating the aircrack codebase. jc-aircrack is based loosely on aircrack, but it is a total rewrite in C++, with an emphasis on readability and ease of experimentation.

aircrack can be used on Linux, OS X, and Windows; however, the platform of choice is Linux. Injecting packets on Linux is easier than on any other OS, and injecting packets significantly speeds up the attack.

In order to launch this attack, you need a lot of packets from the target. To recover a 40-bit key, you need around 300,000 packets. For a 104-bit key, 1,000,000 packets is a good guess. Remember, this attack depends quite a bit on your luck and the amount of data you have available. aircrack can take its input in two forms: pcap files and IV files. IV files are generated from packets and contain only the information relevant to cracking. IV files are also much smaller than pcap files.

In the following example, instead of using aircrack-ng (the latest version of aircrack), aircrack 2.4 was used to prevent the command-line arguments from changing. This example shows how to crack networks in real time. If you've already collected all the packets you need, you can skip the airodump and aireplay commands.

For this example, let's assume you have a network named AirPlus on channel 11 with BSSID 00:13:46:A1:62:C4:

[root@phoenix:/home/johnycsh/Airplus]$ airmon.sh start ath0 11
[root@phoenix:/home/johnycsh/Airplus]$ airodump ath0 AirPlus 11
00:13:46:A1:62:C4   44      167       133  11  54. WEP   AirPlus

At this point, airodump is writing out all the packets it sees to the file AirPlus-01.pcap. You could proceed straight to running aircrack on it at this point, but let's try to generate some more traffic on the network with aireplay.

The first thing you are going to do with aireplay is fake an association. This allows you to set the source address of packets to this address without causing any strange quirks in network behavior. If this doesn't work, it's okay; you can still inject packets as another MAC on the network without causing too much trouble. This technique prevents any strange hiccups from happening, however.

[root@phoenix:/home/johnycsh/Airplus]$ aireplay -1 0 -e AirPlus -a
 00:13:46:A1:62:C4 -h 00:01:BA:DC:0D:ED ath0
22:59:35  Sending Authentication Request
22:59:35  Authentication successful
22:59:35  Sending Association Request
22:59:35  Association successful :-)

Notice how you need to tell aireplay the SSID of the network you are interested in. This is so aireplay can fill in the SSID field of the association request. Next, you are going to tell aireplay to start replaying all the ARP packets it sees. aireplay can pick out ARP traffic even though it's encrypted, because it has a unique size.

[root@phoenix:/home/johnycsh/Airplus]$ aireplay -3 -b 00:13:46:A1:62:C4 -h
 00:01:BA:DC:0D:ED ath0
Saving ARP requests in replay_arp-0423-230522.cap

You must also start airodump to capture replies.
Read 90788 packets (got 8 ARP requests), sent 45705 packets

If all went well, you are now re-injecting ARP packets into the network with the source address of 00:01:BA:DC:0D:ED. This will hopefully generate many ARP responses, creating more network traffic. At this point, you can go ahead and start aircrack on the file being generated by airodump:

[johnycsh@phoenix:~/Airplus]$ aircrack -0 -x ./AirPlus-01.cap
Opening ./AirPlus-01.cap
Read 84836 packets.

The -0 flag to aircrack tells it to enable pretty colorized output (very intuitive). The -x flag tells aircrack to brute-force the bottom two key bytes. Once aircrack starts, you are greeted with a screen similar to the one shown in Figure 6-1.

Figure 6-1: aircrack's main display. The low numbers for the votes means that aircrack doesn't have a good idea what the key is yet.

Using aircrack to Break WEP on Windows

Running aircrack on Windows is similar to running it on Linux. The biggest difference is that on Windows there is no easy way to generate traffic. You can attempt to get creative using AiroPeek; however, it's probably easier to use Linux.

Using aircrack to Break WEP on OS X

You can use aircrack on OS X as well. Unfortunately the aireplay tool doesn't work, so if you want to inject packets, you will have to use Kismac. Also, the bundled airodump tool doesn't run on OS X, which means collecting packets in real time can be tricky. Fortunately, the version of airodump bundled with jc-aircrack works on OS X.

In order to use the version of airodump bundled with jc-aircrack, you will need to load the passive Airport Extreme driver. The easiest way to do this is to let Kismac handle it. Once Kismac is running, you will have an interface named wlt1. To run airodump once wlt1 has been enabled, do the following:

galadriel:~/airbase/jc-aircrack root# ./jc-airodump -i wlt1 -p AirPlus

Once jc-airodump is running, you can use either aircrack or jc-aircrack to crack the pcap or IV file generated.

Kismac also has an integrated FMS attack. It probably doesn't implement as many of the attacks as aircrack, however. You can also use Kismac to replay traffic, similar to aireplay on Linux.

Defending Against Statistical Attacks

Quite a few countermeasures to this attack exist. The most popular (and probably most misunderstood) is weak IV avoidance. To successfully launch the attack, an attacker needs to gather packets encrypted with IVs that follow a specific pattern. Many vendors say that their products employ weak IV avoidance. There are two major problems with this claim.

The first problem is that the AP cannot stop a client from transmitting with a weak IV. By the time an AP sees a packet from a client that was encrypted with a weak IV, it's too late. The client has clearly already transmitted the packet. Weak IV avoidance simply means that the AP itself will not use the bad IVs. This is one of those security problems where one bad apple can spoil the whole barrel.

The second problem is that there are 17 unique statistical attacks implemented widely. Each one uses IVs with a different pattern. When vendors talk about weak IV avoidance, they are probably referring only to the very first attack discovered. These IVs are easy to detect. Even without "classically" weak IVs, an attacker can still recover the WEP key; it just takes more time.

A better countermeasure than avoiding weak IVs is dynamic WEP keys. The reason a statistical attack works in the first place is because the attacker can gather a lot of data encrypted with the same secret key. If that key changed fairly often, or if different clients used different WEP keys, it would make this attack much more difficult.

However, there aren't any dynamic WEP products that I know of that actually employ key rotation. Once a user creates a dynamic WEP key, they use it until they disconnect. This means that statistical attacks can be used against a single user instead of the entire network, which is clearly not desirable. The most widely used implementations of dynamic WEP keys is Cisco's pre-WPA LEAP.

Later, you'll see that this attack can be sped up greatly if the attacker can create traffic on the network. If WEP had some mechanism to prevent attackers from replaying old packets, this countermeasure would slow down attackers significantly. By far, the best solution to this problem is to use WPA or 802.11i.