Wednesday, September 26, 2012

A note on password math

The number of possible passwords with a character set of size C and a password length x is Cx.  For instance, with mixed case alphanumeric passwords we have a character set that has 62 possible characters: 26 lower case letters, 26 upper case letters and 10 numbers (26 + 26 + 10 = 62).  If a password is 8 characters long, there are 628 = 62 ∙ 62 ∙ 62 ∙ 62 ∙ 62 ∙ 62 ∙ 62 ∙ 62 possible combinations.

If there are P possible passwords and we can guess G passwords per second, then it will take us P ÷ G seconds to guess all possible passwords.  Since there are 86,400 seconds in a day, the number of days that it will take us is P ÷ (G ∙ 86,400) and the number of years is P ÷ (G ∙ 86,400 ∙ 365).

The number of guesses that an attacker can make per second depends mostly on the password hashing algorithm.  For a fast algorithm like MD5, a reasonable cracking speed is several billion guesses per second.  For bcrypt or scrypt, a reasonable speed might be from a few hundred to a few thousand guesses per second. 

Example:

Number of possible 8 character mixed-case alphanumeric passwords = 628 = 218,340,105,584,896
Seconds to guess all possible passwords (1 billion per second) = 628 ÷ 1,000,000,000 = 218,340 seconds.
Days to guess all possible passwords = 218,340 ÷  86400 = 2.523 days.
Years to guess all possible = 2.523 ÷ 365 = .007 years

7 comments:

  1. what if you are forced to use 3 charsets in a password of 8? how many passwords would then be? i'm having some problems on that.....thanks.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. no, my questions is like this:
    what if you're forced to use 1 digit, 1 lower, 1 upper, the other 5 are not restricted
    so the final number would be smth. like:

    10 x 26 x 26 x 95 x 95 x 95 x 95 x 95 .....is this correct?

    ReplyDelete
  4. That's actually a complicated question. To start, let's be clear that there are 95^8 possible 8 character passwords using all printable ASCII characters. To get the answer you are looking for, we need to subtract out the passwords that contain no digits, no upper case, or no lower case letters.

    If any readers with a good understanding of probability want to double-check my math here, I'd appreciate it.

    There are 85^8 passwords with no digits. There are 69^8 passwords with no upper case letters and, similarly, 69^8 passwords with no lower case letters.

    The naive (and wrong) way to calculate the number of passwords with at least 1 digit, at least 1 upper case, and at least 1 lower case letters would be:

    95^8 - 85^8 - 69^8 - 69^8 = 2,881,702,313,642,720

    The problem is that there is some overlap between the groups. For instance, some of the passwords with no digits also contain no lower case letters. So, among the 85^8 passwords with no digits and the 69^8 passwords with no lower case letters, there are 59^8 passwords with no lower case or digits and we counted them twice.

    So, taking the initial (wrong) answer, we need to add back the number of passwords with no digits or lower case, no digits or upper case and no upper or lower case.

    There are 59^8 passwords with no digits or lower case
    There are 59^8 passwords with no digits or upper case
    There are 43^8 passwords with no upper or lower case

    This gets us to 95^8 - 85^8 - 69^8 - 69^8 + 59^8 + 59^8 + 43^8.

    We're still not done, every one of the three groups we added or subtracted from 95^8 includes the 33^8 passwords that consist of no upper or lower case or digits (only special characters) and all three of the groups we added back also included them so we need to subtract them again:

    We now have:

    95^8 - 85^8 - 69^8 - 69^8 + 59^8 + 59^8 + 43^8 - 33^8 = 3,185,644,980,510,720.

    There are some notes on password math worth reading here:

    http://people.math.gatech.edu/~heitsch/Teaching/F06/passwd.pdf



    ReplyDelete
  5. i'm glad you like my question, it is indeed a tough one i think...i thought about it after reading some stuff on passwords math, including this post.....
    I think you're wrong with something though. You've started by substracting 85^8 ,meaning passwords with no digits.

    Instead i think you should have substracted

    85 x 95^7, meaning passwords with no digits in just one position, or better yet, what if you subtract from the start like this:

    95^8 - 85 x 69 x 69 x 95 ^ 5 (this would be the "complementary of 10 x 26 x 26 x 95^5 we have started with") = final answer ?

    ReplyDelete
  6. You definitely need to subtract 85^8. The 85^8 comes about because there are 85^8 passwords that contain no digits in any of the 8 positions. You need to remove these to ensure that the remaining passwords all contain at least one digit. If you look at the link in the previous comment, it shows how to calculate a similar problem where there are 36^6 possible 6 character alphanumeric passwords and 26^6 of those contain no digits so that (36^6 - 26^6) contain at least one digit.

    ReplyDelete
  7. that was an excellent pdf, thanks, only now i found the time to read it....if you got more like that, shoot!:)

    ReplyDelete