In Which Jarrett Builds

Hell yeah, acronyms.

Restartin’ dis.

I’ve got the old working SHA1 encryption algorithm going. It’s up on GitHub, here. I was waffling between parallel and serial loads and outputs. SHA1 takes a 512 bit input and outputs 160 bits, and no FPGA that I have access to will have that many pins.

Here’s a fallacy I got stuck on for a while:

If I use completely parallel I/O, it’s faster. Therefore, I should try to use as much parallel communication as possible to maximise speeds.

 

The truth is, though, that most modern high-speed circuits use serial data. When you’re clocking at very high frequencies, propagation errors become very difficult to mitigate. With many data lines, you have no way of knowing when exactly data arrives at the lines. It’s better, easier, more reliable to just send one bit at a time and pump them through really fast. That’s a core principle of pipelining; you don’t even need to wait for a signal to reach its destination before you’re sending the next one.

 

With this project, I don’t think I can go faster than 100MHz with the FPGAs I have. That’s right on the edge of where efficient pipelining starts to matter, so I’ll be experimenting with a mix of serial and parallel interfaces to see how far I can stretch it.

 

Right now at this moment, though, I want to get the computationally-intensive parts of the WPA2 protocol offloaded to the FPGA. I won’t worry about speed juuust yet.

 

 

Here’s how WPA2 works, from a security analysis perspective:

 

 

Some definitions

 

• Access Point (AP) – Usually the router, in these systems
• SSID – AP name. This is the router name that you connect to
• Master Key (MK) – AP password. This is the key we ultimately want to find
• Pairwise Master Key (PMK) – This is the cryptographically hard part of the whole transaction. It’s derived from the MK and SSID
• Pairwise Transient Key (PTK) – The cleartext portion of the authentication to verify the correct PMK
• PBKDF2 (wiki, RFC) – Password-Based Key Derivation Function 2 – A cryptographic function, used like PBKDF2(PRF, Password, Salt, c, dkLen) where PRF is any given hash function, c is the quantity of iterations, and dkLen is the output length
• HMAC (RFC) – Hash-based message authentication code – Intermediate function applied to the SHA1 hash
• SHA1 (RFC) – Standard hashing function. Uses a one-way algorithm to generate non-reversible output

 

The AP has the password, from which it can derive the Pairwise Master Key (PMK). To verify that both sides of the transaction have this, a PTK is generated using the PMK and nonces (randomly generated, one-time-use numbers).

This PTK is transmitted over cleartext, and is part of the 4-way handshake.

 

So, in short, if you combine the proper PMK with the proper PTK, the whole conversation breaks wide open and you can associate with the AP.

If you’re watching the WPA traffic, then you can easily capture the 4-way handshake and therefore the PTK.

 

That means that, for my purposes anyway, the PMK is the important unknown variable, and the computationally hard part. Here‘s how you calculate it, from top to bottom:

PBKDF2:

x1 = HMAC_SHA1(MK, SSID + "1");
x2 = HMAC_SHA1(MK, SSID + "2");
f1 = x1
f2 = x2
for(i = 1; i < 4096; i++) {
    x1 = HMAC_SHA1(MK, x1);
    x2 = HMAC_SHA1(MK, x2);
    f1 ^= x1
    f2 ^= x2
}
return f1 + f2;

 

HMAC:

This is more complicated. Given HMAC(secret, value)

•  Initialise two 64-byte variables, Bi and Bo with secret, padded with zeros on the end
• XOR each of byte of Bi with 0x36, and XOR each of byte of Bo with 0x5C
• Append value to Bi
• Append SHA1(Bi) (in Ascii!) to Bo
• Return SHA1(Bo)

In short:

HMAC_SHA1(s, v) = SHA1((s ⊕ 0x5c)||SHA1((s ⊕ 0x36)||v))

 

And finally, with the SHA1 function, I have covered it in previous posts. This portion is already done.