Home > Articles

This chapter is from the book

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:

  • 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 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 240 to 232 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 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" 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.

The FMS attack is based on three main principles:

  1. Some IVs set up RC4 cipher (see Chapter 11) the way it can reveal key information in its output bytes.

  2. Invariance weakness allows use of the output bytes to determine the most probable key bytes.

  3. 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 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:

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.

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

Overview


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information


To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information


Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.

Security


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

Children


This site is not directed to children under the age of 13.

Marketing


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information


If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

Choice/Opt-out


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information


Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents


California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure


Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

Links


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact


Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice


We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020