4-Way Handshake confusion

[qweasd]

From wikipedia I get: "The PTK is generated by concatenating the following attributes: PMK, AP nonce (ANonce), STA nonce (SNonce), AP MAC address, and STA MAC address. The product is then put through PBKDF2-SHA1 as the cryptographic hash function."

AFAIK in PSK mode, the PMK is the PSK.

What I don't get however is how to derive the PMK from the PTK.

What's also confusing is that rainbow tables are made for WPA2 by taking the ESSID, adding the PSK at the end, and then hashing it 4096 times. Where does that come from? I see no mention of the ESSID in the context of the four way handshake.

[atom]

What's also confusing is that rainbow tables are made for WPA2 by taking the ESSID, adding the PSK at the end, and then hashing it 4096 times. Where does that come from? I see no mention of the ESSID in the context of the four way handshake.

The ESSID is not appended. It is the data part of the HMAC. In HMAC you have two inputs, like in a cipher: The data and the key. The key is the plaintext password, the data is the ESSID. This thing is iterated 4096 just to make the process slow.

What I don't get however is how to derive the PMK from the PTK.

There is a final HMAC transformation which uses MD5 in WPA1 and SHA1 in WPA2 (its the only difference between them). This time the key is the the result of the 4096 iteration (truncated) and the data is all the stuff from above you already mentioned.

[qweasd]

Wow I never knew WPA2 used HMAC. I thought it was just a simple hash.

Still confused though.

There is a final HMAC transformation which uses MD5 in WPA1 and SHA1 in WPA2 (its the only difference between them). This time the key is the the result of the 4096 iteration (truncated) and the data is all the stuff from above you already mentioned.

What I'm getting so far is that there is an initial HMAC operation where the PMK is the key and the ESSID the data.

And another one where the previous result is used as a key and the hashed PTK as the data.

Meaning that since the hashed PTK is known(handshake capture), the key has to be guessed.

Which still begs the question. How are rainbow tables generated? the result of HMAC is a hash and AFAIK, the PTK is different each time a handshake occurs which makes the final hash different each time a handshake occurs.

Having never used rainbow tables to crack WPA2 before, it's starting to sound like they're just used to speed up the cracking process slightly.

[pragmatic]

Hi qweased, perhaps I can help. If I understand correctly the simplified flow looks like this (just after glossary):

PSK - Pre-Shared Ky, aka the password you want to break
SSID - Service Set IDentifier, wireless network's name
PMK - Pairwise Master Key, generated from PSK & SSID and not exposed directly
PRF - psuedo-random function
PTK - Pairwise Temporal Key, generated via PRK from PMK & session-specific info
PBKDF2 - Password-Based Key Derivation Function 2, a key stretching/strengthening algorithm utilizing multiple rounds of hashes. In this case the hashing algorithm is HMAC-SHA1
KCK - EAPOL-Key confirmation key
MIC - Message Integrity Codes, use KCK as only secret component
ANonce - random nonce value sent to client
SNonce - random nonce value sent to AP
AA - Authenticator Address, MAC address of AP
STA - Station Address, MAC address of client

# The PSK acts as a salt, SSID acts as the data to be hashed, and 4096 is the number of iterations of HMAC-SHA1
PMK = PBKDF2(PSK, SSID, 4096)

# The PMK becomes the PTK through the PRF (psuedo-random function) which normally performs 3-4 rounds of HMAC-SHA1 operations (3 for CCMP, 4 for TKIP), however we don't need to do the whole computation as we only need part of the PTK (the first 128 bits) called the KCK (EAPOL-Key confirmation key).

KCK = PTK[0:127] = HMAC-SHA1(PMK, “Pairwise key expansion\0”, Min(AA,SPA) || Max(AA,SPA) || Min(ANonce,SNonce) || Max(ANonce,SNonce)) || 0)

The KCK is used to verify the MIC (Message Integrity Codes) which are used in all of the handshake messages after the first one. By deriving the KCK as above we can confirm guesses just as a WPA client verifies messages against the MIC, create the expected MIC from the message using KCK and make sure it matches the one sent. If it does, you have the right KCK, therefore the right PMK, and therefore the right password. How you create a MIC depends on whether you're using CCMP or TKIP, but suffice to say it is not a particularly expensive/intensive operation.

This is probably a good point for me to mention that I have no idea if this is the route hashcat uses to verify it's got the right PMK, but it should work at least if you have the whole handshake for reference.

Finally, as to where rainbow tables come in, as you can see by far the most expensive part of this process is the 4096 HMAC rounds deriving the PMK from the PSK and SSID. Also notice that these are the only two piece of data we need to do this derivation. Because of this it is possible to build SSID-specific rainbow tables to pre-compute the most common PSKs and cut down this slowest part of the equation. As appealing as that sounds, however, because they must be SSID-dependent I have found their general utility to be rather lacking.

Anyway, hope that helps. If I screwed up anything in either the derivation flow or how its done in hashcat hopefully atom will correct me.

[gat3way]

In fact, those are not rainbow tables. Those are just precomputed tables of essid/password pairs. There is no reduction function and the check against those tables is pretty straightforward, it involves no computation.

[pragmatic]

In fact, those are not rainbow tables. Those are just precomputed tables of essid/password pairs. There is no reduction function and the check against those tables is pretty straightforward, it involves no computation.

Good point, you'd have to already have the PMK (which we don't) to compare against in order to use a rainbow table.

[NeonFlash]

@pragmatic: Well done with the description

The reason why WPA2 handshakes are so slow is due to the computationally intensive task of calculating the PMK.

If I remember correct, per the specification, the exact syntax for calculating the PMK looks like this:

PMK=PBKDF2(PSK, SSID, SSID.length, 4096, 256);

And the salt is the SSID and not the PSK (please correct me if I am wrong)

256 bits is the length of the output key.

PDBKDF2 like any other key derivation function depends on an underlying pseudo random function which in this case is HMAC SHA1.

I think time taken to compute the PTK is very less compared to PMK computation. As soon as PTK is calculated, the MIC is derived from it.

How different is HMAC SHA1 from a SHA1 cryptographic hash function?

I did not get the time to read through it.

The concept of precomputed rainbow tables is that for a specific ESSID, the PMK is already computed.

For every word in a wordlist, combine it with the ESSID according to the above syntax and calculate the PMK.

So, the rainbow tables you are referring to are precomputed PMKs which reduce the time significantly since the most computationally intensive task in WPA2 cracking is PMK computation.

[qweasd]

@pragmatic: Well done with the description

So, the rainbow tables you are referring to are precomputed PMKs which reduce the time significantly since the most computationally intensive task in WPA2 cracking is PMK computation.

After reading the explanation provided by pragmatic, this is the conclusion I came to. I verified this by using precomputed PMKs and noticing how slow the cracking process was(not a simple hash lookup).

Thank you guys for all the comments. Really helped out.

[NeonFlash]

You could post supporting benchmarks as well

It should be faster than an attack without precomputed PMKs but slower than a rainbow table attack on unsalted hashes like MD5.

[qweasd]

You could post supporting benchmarks as well

It should be faster than an attack without precomputed PMKs but slower than a rainbow table attack on unsalted hashes like MD5.

On a laptop with an AMD A6 1.6GHz CPU, Cowpatty could attempt 23,000 hashes per second with precomputed hashes.

For comparison, my GTS 450 can do 12000 hashes per second without precomputed hashes.

So yes it is faster to use precomputed hashes(keeping in mine that a CPU and a GPU are worlds apart in terms of hashing performance).