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:
-
Brute-forcing and improved brute-forcing
-
FMS attack
-
Improved FMS attack
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 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 240 to 232
bits. This number is employed to seed a pseudorandom number generator (PRNG 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 232 bits, because of the way the
values are derived from the PRNG, the actual cycle length of drawn values is
only 224 bits. To be more specific, a seed x produces the same keys as a seed x + 224. 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 221
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 221
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" ). 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.
The FMS attack is based on three main principles:
-
Some IVs set up RC4 cipher 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:
Initialization:
For i = 0 \x{2026} N - 1
S[i] = i
j = 0
Scrambling:
For i = 0 \x{2026} N - 1
j = j + S[i] + K[i mod l]
Swap(S[i], S[j])
The PRNG works as:
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]]
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:
X = SB+3[1] < B+3 X + SB+3[X] = B+3
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
basic pattern present can be defined as follows:
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 = 10
The resulting distribution pattern would be similar to
this:
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 ivs
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:
let l = the amount of elements in SK
i = 0
For B = 0 ... l - 1
If (((0 <= a and a < B) 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 ReportWeakIV
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.
