Page 1 of 5 123 ... LastLast
Results 1 to 10 of 47

Thread: Time Analysis of WPA brute-forcing

  1. #1
    Very good friend of the forum Virchanza's Avatar
    Join Date
    Jan 2010
    Posts
    863

    Default Time Analysis of WPA brute-forcing

    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 =
    Code:
    39919297033102270412781965613433199719545223215933635382877568640629314237842806568803331259120261378523130762379661850000000
    )

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

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

    4) So altogether, it will take the following amount of years =
    Code:
    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:

    Code:
    #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;
    }

  2. #2
    Senior Member
    Join Date
    Apr 2008
    Posts
    2,008

    Default

    Quote Originally Posted by Virchanza View Post
    A WPA password can be between 1 and 63 characters long...
    Actually it can only be between 8 and 63 characters long.
    -Monkeys are like nature's humans.

  3. #3
    Senior Member Shatter's Avatar
    Join Date
    Jan 2010
    Posts
    192

    Default

    Now you're making me feel very secure with my 63 character password
    I have the card in me head, but you have the memory problems?

  4. #4
    Senior Member Thorn's Avatar
    Join Date
    Jan 2010
    Location
    The Green Dome
    Posts
    1,509

    Default

    Quote Originally Posted by Virchanza View Post
    ... 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.
    Thorn
    Stop the TSA now! Boycott the airlines.

  5. #5
    Very good friend of the forum Virchanza's Avatar
    Join Date
    Jan 2010
    Posts
    863

    Default

    Quote Originally Posted by Thorn View Post
    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?

  6. #6
    Member
    Join Date
    Sep 2008
    Posts
    146

    Default

    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.
    Morpheus: "You take the blue pill - the story ends, you wake up in your bed and believe whatever you want to believe. You take the red pill - you stay in Wonderland and I show you how deep the rabbit-hole goes."

    Neo: "What if I take both?"

    Morpheus: "Don't do that! You end up like Nick Nolte!"

  7. #7
    My life is this forum Barry's Avatar
    Join Date
    Jan 2010
    Posts
    3,817

    Default

    Quote Originally Posted by Revelati View Post
    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.
    Of course, if you really wanted to have some fun, go to Wal-Mart late at night and ask the greeter if they could help you find trashbags, roll of carpet, rope, quicklime, clorox and a shovel. See if they give you any strange looks. --Streaker69

  8. #8
    Senior Member Thorn's Avatar
    Join Date
    Jan 2010
    Location
    The Green Dome
    Posts
    1,509

    Default

    Quote Originally Posted by Virchanza View Post
    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?
    Thorn
    Stop the TSA now! Boycott the airlines.

  9. #9
    Very good friend of the forum Virchanza's Avatar
    Join Date
    Jan 2010
    Posts
    863

    Default

    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.

  10. #10
    Senior Member Thorn's Avatar
    Join Date
    Jan 2010
    Location
    The Green Dome
    Posts
    1,509

    Default

    Quote Originally Posted by Virchanza View Post
    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.
    Thorn
    Stop the TSA now! Boycott the airlines.

Page 1 of 5 123 ... LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •