How is the Pixie dust attack different from other WPS attacks?
I have been studying about the brute-force attack on the WPS PIN, and I understand that because the last digit is the check digit, and that the PIN is divided into two halves in M4 and M6 messages, one can brute-force the WPS PIN in 11.000 attempts.
However, I recently heard about the Pixie attack on WPS, and it said something like it takes advantage of the low entropy in some routers. What exactly is the Pixie attack, and how does it affect WPS? One more question, how can one find the WPA key from brute-force WPS PIN?
Pixie works by exploiting weaknesses in the generation of the E-S1 and E-S2 nonces which are used to produce the enrollee hash, as described in the Pixie Dust Attack. Traditional attacks attack the two halves of the WPS PIN (PSK1, PSK2) in an online attack, essentially brute-forcing all possible options for the PIN until it is found. This has to be done online against the target, so it takes a long time.
The WPS exchange involves computing two hashes (E-Hash1, E-Hash2) which are derived from two nonces (E-S1, E-S2), the public keys of the enrollee and registrar (PKE, PKR), the authkey (a value derived from the Key Derivation Key / KDK), and two halves of the WPS PIN (PSK1, PSK2). The values PKE, PKR, E-Hash1 and E-Hash2 are known by an attacker since the router will give you them (or you're providing them as a client) and you need to find the correct combination of E-S1, E-S2, PSK1, and PSK2 in order to break the hash offline.
Cracking the PSK1 and PSK2 parts is relatively easy; there are only 10,000 possible values for PSK1 and 1,000 for PSK2 (the last number is a checksum) and each hash is separate so you only need to compute 11,000 hashes. This doesn't take a lot of time on a modern system. However, the problem is that you need to know the two nonce values E-S1 and E-S2. This makes the offline brute force approach untenable, as these are 128-bit values.
The crux of the Pixie Dust Attack is that the E-S1 and E-S2 nonces are not generated securely in many routers. As an example, MediaTek routers are known to just use zero for both values. In some Broadcom routers, the PRNG used is a weak one (likely an LFSR or something like Mersenne Twister) and it is also used to generate the PKE. By guessing the possible PRNG seed values until you find one which generates the same PKE as the router gave, you can then generate the E-S1 and E-S2 values trivially. Realtek routers use the Unix timestamp in seconds to generate the PKE, E-S1, and E-S2 values, but since the generation is fast it's usually the case that E-S1 = E-S2 = PKE (or E-S1 = E-S2 = PKE+1 in the case that it did tick over a second boundary) and since we know PKE, we now know E-S1 and E-S2. This is why the Pixie attack is so fast. Instead of trying 11,000 possible PINs against the live router (which is slow and might result in the router blocking you), it captures the WPS hash values and cracks them offline, utilising weaknesses in nonce generation so that it only has to try 11,000 PIN values against each possible guessed E-S1 and E-S2 value pair.