Password strength for online services

[Wuhtzu]

Hello

 

I couldn't think of where else to start of in my search for an answer to this question so here you guys go:

 

What strength is really required from password used for restricting access to online services of various nature - forum accounts, paypal accounts, webmail accounts ect.?

 

I have always been an advocate for choosing strong password but after a lot of thinking and calculating entropy of different password compositions I've begun to doubt my own (maybe soon to be old) beliefs.

 

Some numbers:

 

Set of characters and their length

 

(1) [a-z] : 26 chars

(2) [A-Z] : 26 chars

(3) [0-9] : 10 chars

(4) [!"@#¤%&/()=?{[]}+-*$,.;:_] : 25 chars

 

The four most used sets of characters from which to construct passwords arranged by popularity (and hence size) in descending order must be:

 

(1) : 26 chars

(1)+(3) : 26 + 10 = 36 chars

(1)+(2)+(3) : 26 + 26 + 10 = 62 chars

(1)+(2)+(3)+(4) : 26 + 26 + 10 + 25 = 87 chars

 

Lets consider some different length of passwords constructed from the above four sets and how many combinations they yeild: (if one can choose from m characters and the length of the password is n then there is m^n (m to the power of n) possible combinations)

 

Length       

(1)                 

(1)+(3)           

(1)+(2)+(3)   

(1)+(2)+(3)+(4)

2

6.7*10^2

1.2*10^3

3.8*10^3

7.5*10^3

3

1.7*10^4

4.6*10^4

2.3*10^5

6.5*10^5

 

4

4.5*10^5

1.6*10^6

1.4*10^7

5.7*10^7

 

5

1.1*10^7

6.0*10^7

9.1*10^8

4.9*10^9

6

3.0*10^8

2.1*10^9

5.6*10^10

4.3*10^11

7

8.0*10^9

7.8*10^10

3.5*10^12

3.7*10^13

8

2.0*10^11

2.8*10^12

2.1*10^14

3.2*10^15

9

5.4*10^12

1.0*10^14

1.3*10^16

2.8*10^17

10

1.4*10^14

3.6*10^15

8.3*10^17

2.4*10^19

 

Pretty large numbers it seems. Should an attacker decide to try and get access to some account he/she/it could systematically try all combinations of characters from one of the mentioned sets. On average the answer would be found by trying half of the combinations.

 

Should the attacker decide to try password combination using the web service's own authentication interface (an HTML form with username and password input field) he/she/it would most likely have to send POST requests (containing the username and possible password) to the web service using for example cURL. A rough estimate of the time needed to send the request to the target web service, have the server process the request and get a response back could be 1.0 second. So the attacker can check one password each second.

 

One day comprises of about 24 h/day * 60 min/h  * 60 s/min = 8.6*10^4 s. So a password picked from set (1)+(2)+(3) of length 4 with 1.4*10^7 possible combination would take: 0.5*1.4*10^7 / 1/s = 0.7 * 10^7 s = 7.0*10^6 s = 7.0*10^6 s / (8.6*10^4 s / day) =  81 days.

 

So a password from

 

Set (1) with length of 6 or greater

Set (1)+(3) with length of 5 or greater

Set (1)+(2)+(3) with length of 5 or greater

Set (1)+(2)+(3)+(4) with length of 4 or greater

 

takes more than a year to break / guess assuming 1 try per second.

 

Most web services are smart enough to restrict the number of log in attempts per time - e.g. 3 attempts per hour or something - which would cause one year of trying to become thousands of years of trying. And even if the webservice did not detect the repeated log in attempts, chances than someone notices anormalities in the webserver logs are pretty good.

 

So choosing a password from

 

set (1) of length greater than 6,

set (1)+(3) of length greater than 5,

set (1)+(2)+(3) of length greater than 5 or

set (1)+(2)+(3)+(4) of length greater than 4

 

seems like a waste of brain capacity.

 

Of course there are other scenarios. A dump of the web service's database could be stolen or leaked leaving the attacker in possession of hashed passwords. Now the attacker could generate all possible passwords, hash them and permutations, hashing them and comparing hashes) could be distributed over any number of computers and would not take long with the above mentioned password lengths. A person studying computer science at 2nd year or so should be able to do this within reasonable time.

 

But take for example set (1) + (2) + (3) + (4) = 87 chars. Choose a 10 char password from that set which yields 2.4*10^19 possibilities. To compute all possibilities (not to speak of hashing too) in 1 year you need to compute 2.4*10^19 / (356*24*60*60)  = 7.8*10^11 combinations per second or 4.1*10^13 combinations per second if you want to do it in a week. I think it's fair to say that you should have quite few CPU's at your disposal to pull of such computation rates. This can only be possible for large organizations with considerable know how and budget.

 

On top of that most services hopefully use a salt for their hashes which may or may not be stolen with password hashes. If stolen with the password hashes it's of little use, but if is kept separately and not compromised it renders a dictionary attack completely useless.

 

So, if you also want to be almost completely safe from dictionary attacks on stolen database entries, you could go with a password from

 

set (1) of length greater than or equal to 10,

set (1)+(3) of length greater than equal to 9,

set (1)+(2)+(3) of length greater than or equal to8 or

set (1)+(2)+(3)+(4) of length greater than or equal to 7

 

based on the assumption that computing 10^6 = 1000000 = 1 million combination per second is an expensive task.

 

What do you guys think - I'm I right?

 

Most people would be of with random password of 6 chars and paranoid people who _really_ do not want anyone else to post silly stuff on their behalf could go with 10 chars.

 

 

Best regards and sorry for long boring post in the Miscellaneous sub forum

Wuhtzu

 

 

 

 

[xcoderx]

lol  TLDR.

[Garethp]

http://lastbit.com/pswcalc.asp

 

I use (1) + (3) at 15 legnth, but it's not random, it's just A) Not spelled right, B) A sentance and C)In L33T. It would take 7107572007482425 years to crack it at 1 attempt per second. At 500 attempts a second, it would take 14215144014965 years.

 

If you had 1000000 computers that could each process 100000000 attempts per second, it would STILL take 72 years.

 

Too bad the program doesn't allow more than that in it's calculation

[cags]

You mean it could still take 72 years. It might guess right first time

[Garethp]

True, true. That is, if it randomly selected passwords. If it used typical  brute force methods that go through each possible character, then it would take, not 73 years, but certainly a long fucking time

[Daniel0]

You mean it could still take 72 years. It might guess right first time

 

Well, yeah, but that's pretty useless. For instance, best-case running time of path finding algorithms is also Θ(1) because if you already are at your destination you don't have to move anywhere.

 

Even when using a randomized algorithm, it's still highly unlikely that you'll guess it the first time (assuming the password is selected randomly). Plus you'll now have the extra overhead of needing to keep track of all the passwords you've already tried. That problem doesn't exist when you're checking sequentially.

[cags]

You mean it could still take 72 years. It might guess right first time

 

Well, yeah, but that's pretty useless. For instance, best-case running time of path finding algorithms is also Θ(1) because if you already are at your destination you don't have to move anywhere.

 

Even when using a randomized algorithm, it's still highly unlikely that you'll guess it the first time (assuming the password is selected randomly). Plus you'll now have the extra overhead of needing to keep track of all the passwords you've already tried. That problem doesn't exist when you're checking sequentially.

Doesn't change the point that stating it will take 72 years to crack purely because that's how long it would take you to check every combination is misleading. It's not like I actual expect it to find it first time, I was being 'tongue-in-cheek' hence the smiley. But it finding it first time is just as likely as it being the last combination checked if the password is randomly generated. Therefore it's just as like to take one attempt as it is to take the full amount of time.

 

Was I being pedantic? Yes. Was I being entirely serious? No.

[Wuhtzu]

I personally like http://world.std.com/~reinhold/diceware.html 's method of generating pass phrases a lot. It's easy to remember since it's normal short English words, but it still has a great entropy due to the amount of words in the word list.

 

Could any of you comment on my points (I know they were buried deep beneath numbers and talking back and forth)?

 

With the numbers being astronomically large, even for very short random passwords, is there any point in choosing "long" (8 chars and longer) passwords besides protecting one self from compromised user databases?

 

Best regards

Wuhtzu