Wireless Insecurities - Advances in Computers - page 231

2 . 2 B r u t e F o r c e / D i c t i o n a r y W E P C r a c k i n g
The secret key can usually be entered in hex format or ASCII format. Since a
number of hexadecimal characters are much harder to remember then half as many
ASCII characters, most people will choose a word or phrase that they can easily
remember. This might make the key management much easier, but it also facilitates
a brute force attack. There are utilities that try to decrypt WEP encrypted packets.
decrypt, a utility that comes with AirSnort, is one such tool. It tries a list of words
from a wordlist (aka dictionary) against a saved encrypted packet capture. With each
possible key, it decrypts a packet using that key and computes a checksum on the
newly decrypted data. If the checksum matches the checksum that was transmitted
with the packet, a potential secret key has been found. If that same potential key
works with another packet, the correct secret key has been revealed.
Brute force cracking requires more time and resources to find the correct key than
dictionary attacks. This is the process of trying all possible combinations of values
until the correct key is found. With a 40-bit secret key, there are a total of 2 40 =
1 , 099 , 511 , 627 , 776 possible secret keys. If a computer could check 50,000 different
secret keys per second, it would take over 250 days to find the correct key. The
amount of time that would be required to brute force a 104-bit key is measured in
centuries.
The time required to brute force a 40-bit secret key can be brought down to un-
der a minute due to a flaw in the random WEP key generation programs that was
discovered by Tim Newsham [11] . Unfortunately, this flaw has been implemented in
firmware by many wireless vendors.
These programs are supposed to create a set of random keys based upon ASCII
input. The algorithm that is often used by these programs is the Neesus Datacom
key generation algorithm. This algorithm takes a string of ASCII characters as input,
arranges them in a two dimensional array with four characters in a row, and then
XORs all of the column values together in sequence to get a 32-bit output value. The
4 byte (32-bit) output value is then fed through a PRGA which generates the 40-bit
secret keys. See Fig. 3 for a visual representation.
Note that the most significant bit of each ASCII character is always zero and there-
fore the resulting bytes from the XOR operation also have a most significant bit of
zero. This, combined with the PRGA algorithm that is used, only produces unique
keys for seeds 00:00:00:00 through 00:7F:7F:7F. This greatly reduces the amount of
effort required for a brute force attack. To prove this concept, Newsham created the
toolkit wep_tools which will brute force keys that have been generated by this type
of “random” WEP key generation utility.
A utility called WEPAttack also makes claims to WEP cracking efficiency using
both brute-forcing and dictionary attacks against the key. The claim is that only one
WEP encrypted data packet is necessary to start the attack. This is possible because