Wi-Fi Security: Cracking WPA With CPUs, GPUs, And The Cloud

Understanding WPA/WPA2: Hashes, Salting, And Transformations

WPA/WPA2, WinZip, WinRAR, Microsoft's native Data Encryption API, Apple's FileVault, TruCrypt, and OpenOffice all use PBKDF2 (Password-Based Key Derivation Function 2.0). The critical element here is that a password won’t directly grant access to whatever it's protecting. You need to generate a key (decryption code) from the password.

This is one of the most critical differentiators separating WEP and WPA. WEP doesn't obscure your password in an effective way. That is a huge security risk because hackers can directly extract it from packets sent during authentication. This makes it easy for those same folks to sit in parking lot or lounge around in a mall and break into networks. Once enough packets are gathered, extracting the key and connecting to the network is easy. WPA is different because the password is hidden in a code (in other words, it's hashed), forcing hackers to adopt a different tactic: brute-force cracking. 

In one of our last security-oriented pieces, we noticed some confusion in the comments section where readers were asking for more clarification on concepts like rainbow tables, hashes, salting, and transformations.

There are two major parts to converting a password value to a decryption key. The first is called salting. It's possible you've heard this term used once or twice. This is a method in cryptography that prevents two systems from using the same key, even though they may share the same password. Without salting, a pair of machines using the same password, even coincidentally, end up with the same key. This is a vulnerability for rainbow tables, which are huge spreadsheets that allow you to look up the original password (provided you know the key). Salting largely nullifies the use of rainbow tables, because every password uses a random value to generate a different key. It also effectively renders password derivation a one-way function, because you can't backwards-generate passwords from keys. For example, SSIDs are used to salt WPA passwords. So, even if your neighbor uses the same password, he's going to have a different key if his router has a different name.

PBKDF2 takes things one step further by using a key derivation function (KDF). The idea itself is pretty simple, but it's a little math-heavy. There are two steps:

  1. Generate data1 & data2 from password and salt.
  2. Calculate key using transformation invocations using a loop, which looks like:

        for (int i=0; i<iteration_count; i++)
                data1 = SHA1_Transform(data1, data2);
                data2 = SHA1_Transform(data2, data1);

Basically, you input the password and salt (the random bits) in order to generate the first data parameter. This represents the key in it's non-final form. From there, the key is continuously hashed in a cycle, where the next calculation relies on the previous one in order to continue. For every interval, the value of the key changes. Repeat this a couple thousand times and you have the final decryption key. And because you can't go backwards, brute-force cracking requires you to "recreate" the key on every password attempt.

This process accounts for 99% of the computational overhead required in brute-force cracking, so throwing copious compute muscle at that wall is really the only way to chisel it down. Hash cracking lets you to try multiple passwords at a time because the process doesn't employ a key derivation function or salt, making it magnitudes faster. As a practical matter, the impressive speeds you see from hash cracking shouldn't scare you. This form of brute-force hacking is limited in scope, since just about everything secure utilizes salting and a key derivation function. 

To give you a sense of scale, WinZip uses 2002 SHA-1 transformation invocations to generate a key. This value is constant for any password length, up to 64 characters. That's why a 10-character password is just as easy to defeat with AES-256 as it is with AES-128. WPA, on the other hand, uses 16 388 transformations to convert a master key (MK) into what's known as a Pairwise Master Key (PMK). That makes brute-force cracking in WPA 8x slower than it does with WinZip/AES.

WPA relies on a Pre-Shared Key (PSK) scheme. You may enter in a master key (the value that you see in the password field on the router), but you can only "sniff out" the Pairwise Transient Key (PTK) during what is known as a "four-way handshake."

Authentication relies on deriving the PTK from a Pairwise Master Key, which is in turn derived from a master key. It takes about five or six more transformations to go from the PMK to PTK, but WPA cracking speeds are often presented in PMK units, the most computationally-intensive portion of the brute-force attack.

  • fstrthnu
    Well it's good to see that WPA(2) is still going to hold out as a reliable security measure for years to come.
  • runswindows95
    The 12 pack of Newcastles works for me! Give that to me, and I will set you up on my wifi! Free beer for free wifi!
  • Soma42
    I think I'm going to go change my password right now...
  • Pyree
    runswindows95The 12 pack of Newcastles works for me! Give that to me, and I will set you up on my wifi! Free beer for free wifi!
    Then either beer at your place is really expensive or internet is really cheap. Need 6x12 pack for me.
  • compton
    Thanks for another article that obviously took a lot of work to put together. The last couple of articles on WiFi and archive cracking were all excellent reads, and this is a welcome addition.
  • mikaelgrev
    "Why? Because an entire word is functionally the same as a single letter, like "a." So searching for "thematrix" is treated the same as "12" in a brute-force attack."

    This is an extremely wrong conclusion. Extremely wrong.
  • What about the permutations of the words?
    i.e ape can be written:
    ape, Ape, aPe, apE, APe, aPE, ApE, APE.
    Thats 2^3=8 permutations. Add a number after and you get (2^3)*(10^1)=80 permutations.
    You can write PasswordPassword in 2^16=65536 ways.
    How about using a long sentence as a password?
    i.e MyCatIsSuperCuteAndCuddly, thats 2^25 permutations :)
  • molo9000
    Any word on MAC address filtering?
    Can you scan for the MAC addresses? It's probably easy to get and fake MAC adresses, or it would have been mentioned.

    *scans networks*
    12 networks here,
    1 still using WEP
    10 allowing WPA with TKIP
    only 1 using WPA2 with AES only (my network)
  • agnickolov
    Considering my WPA password is over 20 characters long I should be safe for the foreseeable future...
  • aaron88_7
    "12345, that's amazing, I've got the same combination on my luggage!"Still makes me laugh every time!