The twilight of Wi-Fi Protected Access

The “Wi-Fi Protected Access” protocol (in it’s revisions WPA and WPA2) is one of today’s most important security related protocols. Wigle.net counts about fifteen million wireless networks worldwide and the numbers keep climbing dramatically. After the catastrophic failure of WEP, the all new and shiny WPA now almost completely took over protecting the public airspace.

WPA was designed with the small-office/home user in focus; while the protocol allows a sophisticated key-exchange to take place, most implementations like DSL/Cable/LAN-routers prefer the “Pre-Shared Key” mode. Exchange of the Pairwise Master Key (we will hear that term a lot) is simplified by using a common password that is known to all communicating parties. Without going into too much detail, here is how the authentication-phase for WPA-PSK works:

1. The client station (“STA“) wants to connect to a protected Wi-Fi network. The user has typed in a password which the STA uses in conjunction with the network name to compute the Pairwise Master Key. The STA tells the Access Point (AP) that it wants to communicate and the AP starts the authentication-phase by sending a random number, the ANonce, to the STA.
2. After receiving a ANonce from the AP, the STA itself also picks a random number, the SNonce. It takes the Pairwise Master Key, the ANonce, the SNonce and other elements to compute the Pairwise Transient Key. It then sends the SNonce to the AP within a message that is signed (but not encrypted) by the Pairwise Transient Key.
3. The AP receives the SNonce from the STA. It knows the password and therefor the Pairwise Master Key and can now also compute the Pairwise Transient Key from the ANonce it picked itself and the SNonce it just received. The AP checks the Integrity Code on the SNonce-message to see if the STA used the correct key to sign that message. If the Integrity Code is correct, the AP can assume that the STA knew the correct Pairwise Master Key. It sends an acknowledgement to the STA that is also signed with the Pairwise Transient Key and includes information for further communication.
4. The STA receives the acknowledgement and checks the Integrity Code on that message. If it is correct, the STA can assume that the AP knows the correct Pairwise Master Key. Both parties now derived the Pairwise Transient Key and checked their counterpart’s integrity without revealing the password or the Pairwise Master Key over an unsecure channel. They use the Pairwise Transient Key to derive a unique session key and start communicating over a secure channel.

As you may have noticed, everything here depends on the password. The way this works creates some deep concerns:

• People are stupid. They choose bad passwords all over the place, especially when they are not forced to do otherwise. Even when there are requirements on the password, people tend to trick themselves: MySpace requires for passwords to include at least one digit; a hack of 34.000 user accounts (that got accidentily public) revealed that the by far most common case is a single “1” appended to a dictionary-word…
• Everyone in the network uses the same key to create session keys; the chosen password is used to compute the Pairwise Master Key from which the Pairwise Transient Key is derived which leads to the session keys. If a user who knows the password – legally or not – sniffs on other users’ authentication-phase, he may use the Pairwise Master Key to compute the other users’ Pairwise Transient Keys. As from that point the session keys are virtually unprotected, there is in fact no authenticity,  no privacy and no integrity between users of a network protected by WPA-PSK.
  Everyone within the network can fake to be any station, can decrypt every users’ traffic and can forge and inject traffic into other users’ sessions.
• WPA-PSK is badly implemented. The PBKDF2-algorithm is used to derive the Pairwise Master Key from the password. That’s a good choice and in reality forces us to compute more than 16.000 rounds of SHA-1 to compute the Pairwise Master Key from a given password; this seriously slows down any brute-force attempt. However the computational stress is put solely upon that one Pairwise Master Key. Once it is known, deriving the Pairwise Transient Key is virtually free. However since unique session elements are only used in computing the Pairwise Transient Key, we can pre-compute the toughest part – the Pairwise Master Key – and later on use that data as often as we want.
  More seriously the Pairwise Master Key is derived only from the password and the network’s name. Ruling out the name as a variable, all networks of the same name share the exact same “password to key” function.
• Having precomputed a set of Pairwise Master Keys, a fail-fast-attack becomes possible. When on-site, it is a matter of minutes to tell if a set of Pairwise Master Keys – which may have taken weeks to compute – includes the correct key. It is extremely valuable to an attacker if he can tell possible and impossible targets apart.

Let’s do some number-crushing. The NIST estimates the guessing entropy of an 8 character password with certain rules to be about 30bit. We can assume that a lot of people somehow got smarter over night and use passwords with a guessing entropy of 32 bit. In order to crack a password of that strength with a chance of at least 50% we need about 3 billion guesses.

At the time WPA/WPA2 was created, then-current x86-hardware was able to  compute less than 100 Pairwise Master Keys per second. In theory it took about two years to crack a password used for WPA-PSK with a chance of at least 50%. Compared to that hardware, Pyrit increases the number of keys we can compute per second by a factor of x100 and therefore reduces the time we need to crack a network with a chance of at least 50% to 2-3 days. But it get’s worse.

In a small scenario we assume to attack 30 (out of hundreds) networks with the following distribution of network names:

• 17 times “linksys”
• 7 times “NETGEAR”
• 3 times “default”
• 2 times “wlan”
• Once “WiFI”

Looking at the ESSID toplist at wigle.net we can see this distribution is not unrealistic. Our mission is to crack every network listed above with a chance of at least 50% each within 7 days.

On traditional x86 hardware and in a naive solution we had to compute 3 billionen Pairwise Master Keys for every network on the list which accumulates to 90 billionen guesses; this takes around 28 years to compute or (at 800 US$ a box) about 1.2 million US$ to do within 7 days.

As we’ve seen above, the computational stress to guess a WPA-PSK password is solely put on computing the Pairwise Master Key; we can neglect computing further keys and verifying the decrypted message performance-wise. We’ve also seen that all networks with the same ESSID share the same “password to key” function and that there is no session-unique element in that function. That means we only have to compute a Pairwise Master Key once and can re-use it 16 times at best in our scenario. Overall this reduces the number of keys we have to compute to around 15 billion which we can do on a single GPU in a little more than two weeks.

Given a cost of 1.300 US $ for a box with CUDA-capable hardware and decent storage (15 billion PMKs require about 600gb) this solution costs less than 3.000 US $ to succeed in 7 days. Not only are we about 660 times faster – we are still about 400 times more cost-effective. If we focus on the two most common network names – cracking only 24 out of 30 networks but maximizing the value of the precomputed data – we are more than 1.300 times faster and even 800 times more cost-effective than what was thought of when WPA was designed.
In order to increase the chance to succeed in the above scenario from 50% to 99% a six-fold increase in computational power and cost is required; that is still less than 20.000 US$ (compared to around 8 million US$ on traditional hardware) which is well within the reach of most people – not even speaking of groups, corporations or governments.

Using pre-computed tables of Pairwise Master Keys to create fail-fast-attack on WPA-PSK networks has been shown before, most noticable by the people of coWPAtty. But let me stress this point: The problem is not only raw speed; the problem is how cost-effectivness scales by that. Attacking WPA-PSK with GPGPU-capable hardware puts very little financial requirements to the attacker which leaves us within the twilight of a “can be done” scenario.

30 Comments

Comments RSS TrackBack Identifier URI