A new feature now completely implemented in Pyrit can boost the performance of database-driven attacks against WPA2-PSK by about fifty percent. As far as I know, Pyrit is the first and only tool that implements this new approach of attacking WPA2-PSK.
The idea, originally pitched to me by Domonkos Tomcsányi, is to leverage the knowledge of the plaintext for the first few bytes of an encrypted packet to find the correct Temporal Key. This is the key which is used by WPA2 in conjunction with CCMP and AES to encrypt and authenticate the data-stream. The performance-gain comes from the fact that computing the Temporal Key and one encryption-round via AES to prove it’s validity is faster than the classic approach of computing the Key Confirmation Key and HMAC-SHA1 over one entire packet.
The first important insight is that we know what the first six bytes of an encrypted message should be as there is always a LLC- and a SNAP-header. There is only a minuscule chance that a guessed key was incorrect after we try a possible CCMP-key and the first six bytes of the decrypted plaintext turn out to read AAAA03000000. After the Temporal Key has been computed, this check can be done with just one AES key-setup and one encryption-round.
The Temporal Key is a part of the Pairwise Transient Key which in turn is derived from the Pairwise Master Key using PRF-384. Technically spoken, PRF-384 is HMAC-SHA1 computed over the Pairwise Key Expansion and keyed by the Pairwise Master Key. As the function’s output is always 20 bytes per iteration (the length of a SHA1-digest) and the Temporal Key is 32 bytes into the function’s stream, we need the last eight bytes of the second and the first eight bytes of the third iteration. At first sight this makes it actually more difficult to compute the Temporal Key compared to the Key Confirmation Key which only requires one iteration of PRF-384. While implementing Domonkos’ idea I came to realize that there are two important (and afaik not previously discussed) weaknesses in the design of PRF-384 that we can exploit in order to lessen this disadvantage:
The PRF-384 function is – in essence – like a stream-cipher that produces a large number of output bits using a smaller number of secret input bits. Real stream-ciphers or strong PRNG feed the output of iteration N back as an input to iteration N+1; this makes it impossible to compute the state of the algorithm at iteration N without knowing it’s state at iteration N-1. However, PRF-384 does not do that: We can compute the second iteration (for the first eight bytes of the Temporal Key) without having to compute the first iteration. Second, the counter used in every iteration is placed at the end of the Pairwise Key Expansion instead of the beginning. We can therefor re-use the state of the SHA1-algorithm between iteration two and three as the HMAC-key and the first block of the message are the same.
Combining these two completely unnecessary weaknesses allows us to reduce the number of SHA1-rounds required to compute the Temporal Key from fifteen to seven. This is still more than the five rounds of SHA1 required to compute the Key Confirmation Key but in fact is more than fast enough: The one key-setup plus one AES-round required to confirm the Temporal Key can be done much faster than the four to six rounds of SHA1 required to check the Key Confirmation Key. This is especially true as we can utilize hardware-based implementations of AES with the new AES-NI instruction-set found in recent processors.
Putting this all together, the number of passwords Pyrit can check on my Intel i7 4×3.4Ghz increases from 5.4 million to 7.9 million per second, a straight 50% increase. I will post more details about how to use this new feature in the next blog-entry.