Time Analysis of WPA brute-forcing

[Virchanza]

REVISION: I initially wrote this post saying that a WPA password can be between 1 and 63 characters long. Subsequently, =Tron= corrected me saying that a password must be between 8 and 63 characters. I have re-done the below calculations to take into account the minimum length of 8.

A WPA password can be between 8 and 63 characters long, and there are 95 possible characters to choose from (i.e. the 95 printable characters of ASCII). To get an idea of how long it would take to try every possible password, here's how I went about it:

1) First I worked out how many different possible passwords there are.
2) Next I said let's say we have control of every single PC in the world (and let's say there's 3 billion PC's in the world).
3) Next I considered what's the fastest rate of cracking, and I picked 4000 k/s because I hear that that's what people are getting from using graphics cards. Next I thought let's say that every machine in the world has two of these graphics cards, so that's 8000 k/s.
4) Next I expressed this figure as years.

Here's how my calculations panned out. All numbers are written in the normal decimal system everybody's used to.
1) Total amount of keys =

39919297033102270412781965613433199719545223215933635382877568640629314237842806568803331259120261378523130762379661850000000

)

2) With 3 billion machines, each machine tries the following amount of keys =

13306432344367423470927321871144399906515074405311211794292522880209771412614268856267777086373420459507710254126554

)

3) With each machine trying 8000 k/s, it will take the following amount of seconds:

1663304043045927933865915233893049988314384300663901474286565360026221426576783607033472135796677557438463781766

)

4) So altogether, it will take the following amount of years =

52743025210740992321978539887526952952637756870367246140492305936904535342997958112426183910346193475345

If I reduce the password to a maximum of 12 letters, then it works out at 722 years (still using 3 billion PC's each having 2 graphics cards).

In order to do these calculations, I used a big number library for C. The library I used is called "GNU MP", and it's the fastest and best C library for big number calculations. For anyone who's interested, here's the code I used:

#include <stdio.h>
#include <gmp.h>

void CalcAmountPasswords(mpz_t total,unsigned min,
                                     unsigned const max,
                                     unsigned const radix)
{
    mpz_t temp; mpz_init(temp);

    mpz_set_ui(total,0);

    for ( ; min <= max; ++min)
    {
        mpz_ui_pow_ui(temp,radix,min);
        mpz_add(total,total,temp);
    }

    mpz_clear(temp);
}

int main(void)
{
    char buf[1024];

    mpz_t total; mpz_init(total);

    CalcAmountPasswords(total,8,63,95);
    mpz_get_str(buf,10,total);
    printf("Total amount of keys = %s\n\n",buf);

    mpz_cdiv_q_ui(total,total,3000000000lu);
    mpz_get_str(buf,10,total);
    printf("We have control of 3 billion computers, so each computer tries %s keys\n\n",buf);

    mpz_cdiv_q_ui(total,total,8000lu);
    mpz_get_str(buf,10,total);
    printf("Each computer can try 8000 k/s, so that's %s seconds\n\n",buf);

    mpz_cdiv_q_ui(total,total,60ul * 60 * 24 * 365);
    mpz_get_str(buf,10,total);
    printf("In years, that's %s years\n\n",buf);

    mpz_clear(total);

    return 0;
}

[imported_=Tron=]

A WPA password can be between 1 and 63 characters long...

Actually it can only be between 8 and 63 characters long.

[Shatter]

Now you're making me feel very secure with my 63 character password

[Thorn]

... and there are 95 possible characters to choose from (i.e. the 95 printable characters of ASCII). ...

Plus, you can use non-printable characters in both WPA and WPA2.

[Virchanza]

Plus, you can use non-printable characters in both WPA and WPA2.

Emm... you sure about that? I read a Wikipedia article on WPA that told me it was only the 95 printable characters.

Surely, if non-printable characters were allowed, it would be really awkward?

[Revelati]

Nicely done, Ive always wanted to know the hard math behind it. Of course that is the amount of time it would take to try EVERY possible combination. Statistically however your chances of cracking the password before going through every possible combo are very high.

For instance, by knowing that your target is using a very high security password you can actually narrow the field dramatically. For instance if someone brags about their 63 character password (*cough xCPPx *cough ) then you can get rid of all combinations with 62 chars or less. While trying all combos for a 63 char password would still take a long time it is not beyond the reach of say a 16GPU tesla server or a few of them using distributed computing.

Other things you can do is have your machines compute different areas of the number line. Anyone that paranoid about their password is going to know that brute forcers start with aaaaa11111 so if you start in the middle and work your way towards the ends you can increase your chances based on human nature.

You can also get rid of any combination of words or phrases that are in the dictionary, since everyone knows that most people will try a dictionary attack first which will slim it down by a few billion.

People also use patterns even when they are trying to be random. Which means that unless the passwords are machine generated you can take the layout of a modern qwerty keyboard into account. Most people in western nations read and type from left to right, so you will normally Qs before Ps and 1s before 9s.

DARPA has been working on psycho-algorhythmic password cracking for a long time. It may take them a few thousand years to try EVERY possible combination but ill bet they could get the RIGHT combination in a relatively short period of time.

[Barry]

Nicely done, Ive always wanted to know the hard math behind it. Of course that is the amount of time it would take to try EVERY possible combination. Statistically however your chances of cracking the password before going through every possible combo are very high.

For instance, by knowing that your target is using a very high security password you can actually narrow the field dramatically. For instance if someone brags about their 63 character password (*cough xCPPx *cough ) then you can get rid of all combinations with 62 chars or less. While trying all combos for a 63 char password would still take a long time it is not beyond the reach of say a 16GPU tesla server or a few of them using distributed computing.

Other things you can do is have your machines compute different areas of the number line. Anyone that paranoid about their password is going to know that brute forcers start with aaaaa11111 so if you start in the middle and work your way towards the ends you can increase your chances based on human nature.

You can also get rid of any combination of words or phrases that are in the dictionary, since everyone knows that most people will try a dictionary attack first which will slim it down by a few billion.

People also use patterns even when they are trying to be random. Which means that unless the passwords are machine generated you can take the layout of a modern qwerty keyboard into account. Most people in western nations read and type from left to right, so you will normally Qs before Ps and 1s before 9s.

DARPA has been working on psycho-algorhythmic password cracking for a long time. It may take them a few thousand years to try EVERY possible combination but ill bet they could get the RIGHT combination in a relatively short period of time.

Which is why I tell people to use an online password generator and throw the output on a usb thumb drive for cut and paste.

[Thorn]

Emm... you sure about that? I read a Wikipedia article on WPA that told me it was only the 95 printable characters.

Surely, if non-printable characters were allowed, it would be really awkward?

Well, that's Wikipedia for you. There's a reason people don't trust that stinking pile of poo. It's great for brain-dead pop culture -something like how many lovers Paris Hilton has had this week- but if you want real information, you can't trust it.

If you search around for WPA specifications, the specs say 8-63 ASCII characters or 8-64 hexadecimal digits.* I've never seen that the ASCII character being limited to the printable ones, and the inclusion of the hexadecimal digits tends to negate that idea anyway. In fact, every reference I checked to "WPA" and "printable" seemed to lead back to the Wikipedia article, which proves nothing.

*And those numbers aren't typos. It is 63 ASCII or 64 Hex. I have no idea why an extra digit is allowed with the hex.

Why do you think it non-printable characters would be awkward?

[Virchanza]

Why do you think it non-printable characters would be awkward?

How are you supposed to type them in on your keyboard... ?

I realise you could have the passphrase stored in a binary file but most computers want you to type the password in by hand.

[Thorn]

How are you supposed to type them in on your keyboard... ?

I realise you could have the passphrase stored in a binary file but most computers want you to type the password in by hand.

I guess I'm not understanding the problem. It can be a little awkward on a laptop, but other than that, it's no big deal. You just type them in.

Uh, you do know things like hex and keycodes, don't you? Both are pretty much prerequisites if you're programming in C.