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

  1. Very well put. In response to your paragraph about hardware needed I would say however that the risk vectors come from commodity hardware tasked unknowingly or specialized hardware. It would be nice to know if there was much benefit using FPGA hardware or such do you know ?

    regards

    John Jones
    http://www.johnjones.me.uk

  2. That has always been and will ever be a risk. However the group of people that have access to either a botnet or specialized hardware is rather small.

    What we see now is how the billions and billions of money made by the computer-gaming-industry lead to giving people access to such hardware basically for free. The gaming industry becomes the unwilling / not caring fundraiser to put a terraflop of power beneath every computer desk.

  3. its like 2001 all over again!! hehehehe!! here we come guys…

    lock up your cc info!! all those merchants that spent millions upgrading there networks to WPA are crying right now!!.. They better really have there CC data encrypted this time.. its TJx all over again!

  4. If I understand correctly, those entropy estimates are only valid for 8 char. passwords chosen non-randomly (i.e by a user) under certain conditions?

    • as 8 chars is the minimum dependency for most wireless routing devices, it is likely that people will use exactly 8 chars. You can also guess, that if they use a shorter password, they will probably fill it with zeroes or ones to achieve the minimum password length of 8.

      In fact, as it comes to wireless, I have realized that peoples network PSKs are usually much worse than those 30-32 bits of entropy. In fact, from what I saw in real-world conditions, theres a good chance that about 5% of all WPA PSKs can be found in a unix default dictionary, salted with some zeroes or ones to match minimum psk length.

  5. Yes, thats basically true. Thereby the entropy is that of a dictionary word.

  6. Thanks, well written! can’t wait for SLI/X-FIRE support to speed up the process :-D

  7. Hello!
    Very Interesting post! Thank you for such interesting resource!
    PS: Sorry for my bad english, I’v just started to learn this language ;)
    See you!
    Your, Raiul Baztepo

  8. Too bad you can’t combine the hardware of multiple computers to target the same node… basically reverse the concept of LimeWire…. instead of a bit-torrent to download… bit-torrent to hack a node…

    Multiple uses log on to the same client software… allowing their hardware to be used to hack the same node… instantly allowing hundreds of thousands of computers working towards the same node to be hacked…

    Possible?

  9. Interesting, I did see a similar concept where thousands of ps3′s were used for a single brute force attack. I never did get the final outcome though, Dam now you guys have me thinking about two things at the same time…… I wonder how a fork goes from one path to five all at once ?

  10. Just a few practical questions, since WPA/WPA2 is generally what’s available in the SOHO setting… Basically I’m asking about best practices on a typical (ie WRT54G) router.

    I’m using a non-default SSID, and a 63-character (the max, I believe) program-generated pseudorandom password. I’ve got the router set to WPA2/WPA-CCMP, which appears to be the strongest it offered.

    Even in light of what you’ve written, the non-default SSID makes me think that no pre-computed tables are useful against me, someone would have to start pre-computing a set of tables with my SSID to even get started. Then I have a full-length password with presumably no dictionary attacks available. This leaves me still feeling fairly safe.

    It sounds as if I could improve things by periodically changing the SSID, just to invalidate any table precompilation, and perhaps the same with the password. The former is obviously easier, since it’s human-readable and sensible.

  11. A non-dictionary password longer than 10 characters (upper- and lowercase, digits and special characters) is usually strong enough to resist brute-force attempts. In that case, you do not have to take the SSID into account, because the password can’t be guessed; precomputed tables against a password that strong can’t be stored of affordable hardware.

  12. I hope that I’ll still be safe by using a custom SSID and a password generated by a random string generator.

    At least for some time.

  13. [...] Pyrit’s implementation allows to create massive databases, pre-computing part of the WPA/WPA2-PSK authentication phase in a space-time-tradeoff. The performance gain for real-world-attacks is in the range of three orders of magnitude which urges for re-consideration of the protocol’s security. Exploiting the computational power of Many-Core- and other platforms through ATI-Stream, Nvidia CUDA, OpenCL and VIA Padlock, it is currently by far the most powerful attack against one of the world’s most used security-protocols. For more background also seehttp://pyrit.wordpress.com/the-twilight-of-wi-fi-protected-access/ [...]

  14. [...] that processor power isn’t realistically limited anymore.  From the pyrit blog itself, it appears PSK values longer than 10 ASCII characters cannot affordably be stored on current hard drives, even though it is definitely possible to [...]

  15. [...] protected wireless network. This article is fairly interesting, but also fairly technical: The twilight of Wi-Fi Protected Access Pyrit __________________ E8400 — Gigabyte GA-EP35-DS3R — 2x2GB Crucial Ballistix – Asus EN8600GTS — [...]

  16. [...] attack against one of the world’s most used security-protocols. For more background see this article on the project’s [...]

  17. I wonder how much it takes to crack my WPA2 given the fact that I have a 28 character password with plenty of special characters and no dictionary word :)

  18. Get a WiFi overlay security system. Encryption and decryption is statistical and any encryption will be forced open some day or the other.It is the cop-robber game.

  19. Amazing post definitely gives people something to think about. Thinking about borrowing a few of my buddies towers because as stated before the gaming industry is ever uncaring about giving base users “teraflops” of power. So x8 295′s should post a good benchmark.

  20. wonder if we should re-visit “chaocipher” … by John Byrne

  21. Can this method be used against bluetooth?

    • I know almost nothing about bluetooth. AFAIR you can bruteforce-attack the authentication phase (guess the correct PIN). That should be easily doable on GPUs. I don’t know if it is possible to pre-compute anything…

      • Thanks for the reply. I think the main problem with bluetooth is capturing data easily and cheaply. I believe the software radio guy’s can do it, but it can be costly and have a too-steep a learning curve to justify the efforts of a casual tinkerer. Thanks again.

  22. [...] The twilight of Wi-Fi Protected Access [...]

  23. [...] making simple brute-force-attacks even more alluring to the attacker. For more background see this article on the project’s [...]

  24. [...] making simple brute-force-attacks even more alluring to the attacker. For more background see this article on the [...]

  25. [...] making simple brute-force-attacks even more alluring to the attacker. For more background see this article on the project’s [...]

  26. First,
    Thank you very much for the work done, and this wonderful blog.

    Assumption:
    The bear will eat you if you don’t run faster than the bear!

    False!

    You only need to run faster than the slower guy. He’ll be the bear’s breakfast, not you.

    I have compiled about 50m real passwords from different hacks, from the Rockyou heist, gawker, Lulz sec , etc and sorted them statistically. The results are really scary!
    Hence I can absolutely confirm that “People are stupid. They choose bad passwords all over the place”
    The average length is 10ch and the clear winner is … “123456789″ with over 250,000 occurrences. Surprise!

    When explaining WPA and Password Recovery, I have stopped calculating the probabilities, time needed or CP needed some time ago. I now explain to people the difficulty, not in time, but simply in energy cost: Telling someone that he may need to cough up few dozen million dollars for the electrical bill is more efficient than mentioning 63^127.

    As for my 2 cents, here is what I suggest:

    - Stop using “password” , think PassPhrase. You’ll automatically create a longer, more secure “password”
    - Friends don’t let friends use words.
    - Don’t use 8 or 63 ch long, Extremes are too easy (well..63 ..maybe not, but trying every 63 only would be faster than trying all 63^127)
    - Use a GRC generated passphrase. it’s free..fast..and theoretically unbreakable in a life span. make it 50ch +
    Don’t use generic ESSID. Make your own!
    - Because you’ve used GRC, you can create a new unique randomly generated PassPhrase in 1 second. Okey then, use your calendar: put a reminder and change your password every month or so.
    - Ah, while at it, increment your ESSID too, it takes an extra 2 seconds.
    Using those simple simple steps would make the NSA and the CIA combined break a serious sweat, for a long time …

    @ one hundred trillion guesses per seconds, a Passphrase of 59 RND ch long would take 1.56 billion trillion trillion trillion trillion trillion trillion trillion centuries.

    https://www.grc.com/passwords.htm

    Once again,
    Thank you for the wonderful work on Pyrit

  27. Or dont use PSKs? Use a radius server like FreeRADIUS


Comments RSS TrackBack Identifier URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.