![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
handslive[Edited: To fix the math errors. Not that anyone will notice, I suppose. And it took me 2 weeks to get around to doing it. Procrastinate much?]
Two things happened in the last month to make me think about passwords. The first was an issue at work where I was asked to describe in some technical detail how hard or easy it would be to guess a single person's password if I had access to the password hash stored in the application's database. The second was that I screwed up when changing my password in KeePass and had to give some thought to whether I could recover it and how.
I've had a few arguments with other people at work over the years about passwords and password policy. So here's some slightly more mathematical thoughts about passwords. We use passwords for a lot of things these days, including as a kind of source for encryption keys. KeePass does this when it protects the password database. If you've ever password protected a ZIP file with a current version of WinZip (which uses AES by default), then you've done this. In this context password strength is actually better described as key strength. NIST in conjunction with the NSA has guidelines for measuring the level of entropy in password-based keys and KeePass actually uses a version of this to calculate a password strength that gives a relative key strength. Depending on character choices, an eight character password might be equivalent to a 36-bit key or even a 53-bit key.
This is, frankly, a crappy way to consider password security except in very narrow circumstances. In cryptography, the strength of a key is generally considered on the basis of how many operations an attacker would have to perform in order to break it. My thinking is that password strength should be considered the same way.
A single character password containing letters and numbers has 62 possible values (a-z, A-Z, 0-9). If we add common North American punctuation (~`!@#$%^&*()_+-=[]\{}|;':",./<>?), we add another 32 characters for a total of 94. So, 62 and 94 will be our magic numbers for most of what follows. My first point is about common password policies and what they mean from a "number of operations" point of view in the ideal case, meaning that we forced the person guessing the password to do a brute force search through all the combinations (which will average out to n/2 where n is the total number of possible guesses).
I've dealt with some older systems that had a default rule requiring that passwords be at least 3 characters, so that's a good starting point. A 3 character, alphanumeric password has (62^3) possible values (you have to eliminate the 1 character and 2 character possibilities since the password has to be at least 3 characters) or 238,328. This is not very many. A modern desktop computer can try all of these in under an hour on a single password entry. [citation needed -- like seriously; digression at the bottom] :-) If we add in punctuation, we only increase the total size to 830,584. Using the earlier result as a guide, this might take a few hours.
So, let's bump up the length. There are still quite a few systems in use that won't support a password longer than 8 characters. Traditional Unix flavours, including most vendor implementations today, still support the crypt(3) function for protecting passwords. This is a hash-like function based on DES, but it only uses the first 8 characters of the input string. It's possible to pick better schemes like MD5 or SHA-1 (or even SHA-256 or SHA-512), but a lot of Unix systems default to crypt().
I argued with one co-worker that we should bump our minimum password length up to support the shortest maximum password length. This would mean we had systems where the password would be known to be exactly 8 characters for every single user. He claimed that a significant chunk of search space would be lost as a result. In the ideal case, this isn't so. Again, just looking at alphanumeric passwords, a 6 to 8 character passwords has 221,918,520,426,688 (62^8 + 62^7 + 62^6) possible values. An 8 character password alone has 218,340,105,584,896. The size of this set is smaller, but not significantly smaller (less than 2%). This isn't a reasonable counter to his argument though because this is the ideal case. For comparison, if the 8 character password includes punctuation, there are 6,095,689,385,410,816 possible values, an order of magnitude more at this length.
So, the real question is how many guesses does it reasonably take? If you tell people to select mixed-case, alphanumeric, 8 character passwords, they will not generate ideal passwords like Z6Foy0jR (generated specifically for this example). They'll select things like Ssssss55 or 67vikinG. And if you ask them to change these passwords periodically, they'll produce new ones like Ssssss66 or Viking68.
There are password breaking programs out there that will take a set of words you supply and apply rules to them to generate possible alternate passwords. Similar programs have been around since the early 90s, when I first got involved in looking at password security as a system administrator. This kind of approach is called a "hybrid" attack because it combines an iterative set of rules with a dictionary. The program I'm referring to is John the Ripper, but Crack, the first program I used, had a similar capability. John ships with a default password list that the developer claims has a high success rate. There are roughly 3,000 words in this file. On Unix you could use the /usr/dict/words file, too. If you restrict to words that are roughly in the right length range, you'll have 3,000 - 8,000 words. A little further afield you can download dictionary files specifically for password guessing that have millions of words, some of them, like Galadriel or Romulan, outside of the usual English lexicon used by spell checkers.
To give an idea what the mangling does to the number of guesses, the default rule set and default password list for John will produce a new password list of around 126,000 from the 3,000 value source file. John also includes some additional rules that use user proifle information instead of password files. If these rules are also added to the mix, then roughly 1,800,000 words are generated. That's a sizeable jump and includes passwords that are too short for what we're doing (I asked for 8 character passwords, so it went up to 8 characters) but gives us a ballpark. 1,800,000 guesses is still significantly less than 10^15 (or 62^8, whatever gets you in the ballpark). These rules aren't exhaustive (Ssssss55, Ssssss66, and Viking68 would be caught, but not 67vikinG), but the rules are configurable and can easily be expanded. The trick really is to keep the number of variations to within a reasonable fraction of the total search space. Almost any reasonable number of operations below (62^8)/2 is cheaper than brute force. Almost any time scale that's within a month or two is feasible.
These rules do have short comings if you're trying to target a single password as opposed to simply catching the low hanging fruit in a password database. They're essentially substitution and permutation rules so even a little variation can produce a password that's outside the generated set of guesses. It's easy to write a rule, for example, that replaces all e's with 3's, but harder to write a rule that tries all the possibilities for replacing only some e's with 3's. It will only catch misspellings if they're common enough to make it into a source password list or to be caught by a simple rule, like switching ie for ei or substituting k for c.
So, a rough guess is that something on the order of 10^6 or maybe 10^8 dictionary based hybrid attacks on the password is a reasonable search space for 8 character alphanumeric passwords depending on the rules and the choice of dictionary. Password expiry is of little help here. The length of time to work in this space gets less and your policy only moves towards something unreasonable. While it's possible to use a dictionary based password and still avoid this search space, you're putting yourself in the path of the attack and betting it will miss you. There are better ways.
In any case, here are some things to think about from a system designer and policy setting point of view. It's extraordinarily difficult to set policies on your passwords that protect users from themselves. You'd need to duplicate the rules your attackers are using in order to push users outside that search space. What you want to do is not avoid the attack (that's impossible) but increase the number of operations that are needed to guess the password. The easiest thing to do is increase the size of the search space.
Where we're limited to 8 characters, our only choice is to add punctuation to our password policy. This increases the ideal space from 10^14 to 10^15. If we were able to increase the length of the password by a single character and keep the old alphanumeric policy, then it would increase to 10^16. Simple increases in length trump complexity. John's generated list from the same old source dictionary and using the extended ruleset only jumps up to 2,000,000. Bumping the length up higher quickly runs into the upper limit for possible passwords that can be generated from this combination of rules and dictionary, which is around 2,500,000. We would need a different dictionary in order to keep pace.
One of the things to keep in mind is that newer systems for storing passwords are not restricted by the length of the password. An MD5 or SHA-1 hash of a password will take an arbitrary length piece of text and produce a fixed length result. This means you could have a 100 character password if you wanted and the system would not care. I've had this discussion with folks building login pages for web sites. From an implementation viewpoint, there should be a reasonable fixed size to the text that can be provided, but we should stop telling users that there's a maximum length for their passwords. As one LDAP support person I spoke to years ago said, as long as it's under 1 MB why should we care? A minimum length is a must, but the maximum length can afford to be pretty open ended.
This argument gets some criticism from useability folks, though, who claim that users have enough trouble remembering their 6 or 8 character passwords. I think they might be more creative if we gave them more space and a little advice. Imagine full sentences or sets of interesting dictionary words. The usual argument against this in security circles is that users will pick movie quotes and bits of song lyrics in the same way that they pick dictionary words. There's a lot of truth to that, but there's more content and more complex content in the language than in individual words or small sets of letters. The objective is to increase the number of operations needed to gain the password or passphrase.
You can implement this kind of password today. Windows XP Home supports arbitrary length passwords, for example.
* I said I needed a citation. And I do. I was going to try cracking a random, 3 character, mixed case, alphanumeric password with John the Ripper and see how long it took. But John assumes that no sane sysadmin would ever allow this length of password (and convincing RedHat to let me make one involved turning several things off) and it doesn't find it. I think it would be possible to configure John, or even extend its functionality using the scripting capability, to try guessing this password, but frankly I can't be bothered. I'd be shocked if it took a whole hour though.
Two things happened in the last month to make me think about passwords. The first was an issue at work where I was asked to describe in some technical detail how hard or easy it would be to guess a single person's password if I had access to the password hash stored in the application's database. The second was that I screwed up when changing my password in KeePass and had to give some thought to whether I could recover it and how.
I've had a few arguments with other people at work over the years about passwords and password policy. So here's some slightly more mathematical thoughts about passwords. We use passwords for a lot of things these days, including as a kind of source for encryption keys. KeePass does this when it protects the password database. If you've ever password protected a ZIP file with a current version of WinZip (which uses AES by default), then you've done this. In this context password strength is actually better described as key strength. NIST in conjunction with the NSA has guidelines for measuring the level of entropy in password-based keys and KeePass actually uses a version of this to calculate a password strength that gives a relative key strength. Depending on character choices, an eight character password might be equivalent to a 36-bit key or even a 53-bit key.
This is, frankly, a crappy way to consider password security except in very narrow circumstances. In cryptography, the strength of a key is generally considered on the basis of how many operations an attacker would have to perform in order to break it. My thinking is that password strength should be considered the same way.
A single character password containing letters and numbers has 62 possible values (a-z, A-Z, 0-9). If we add common North American punctuation (~`!@#$%^&*()_+-=[]\{}|;':",./<>?), we add another 32 characters for a total of 94. So, 62 and 94 will be our magic numbers for most of what follows. My first point is about common password policies and what they mean from a "number of operations" point of view in the ideal case, meaning that we forced the person guessing the password to do a brute force search through all the combinations (which will average out to n/2 where n is the total number of possible guesses).
I've dealt with some older systems that had a default rule requiring that passwords be at least 3 characters, so that's a good starting point. A 3 character, alphanumeric password has (62^3) possible values (you have to eliminate the 1 character and 2 character possibilities since the password has to be at least 3 characters) or 238,328. This is not very many. A modern desktop computer can try all of these in under an hour on a single password entry. [citation needed -- like seriously; digression at the bottom] :-) If we add in punctuation, we only increase the total size to 830,584. Using the earlier result as a guide, this might take a few hours.
So, let's bump up the length. There are still quite a few systems in use that won't support a password longer than 8 characters. Traditional Unix flavours, including most vendor implementations today, still support the crypt(3) function for protecting passwords. This is a hash-like function based on DES, but it only uses the first 8 characters of the input string. It's possible to pick better schemes like MD5 or SHA-1 (or even SHA-256 or SHA-512), but a lot of Unix systems default to crypt().
I argued with one co-worker that we should bump our minimum password length up to support the shortest maximum password length. This would mean we had systems where the password would be known to be exactly 8 characters for every single user. He claimed that a significant chunk of search space would be lost as a result. In the ideal case, this isn't so. Again, just looking at alphanumeric passwords, a 6 to 8 character passwords has 221,918,520,426,688 (62^8 + 62^7 + 62^6) possible values. An 8 character password alone has 218,340,105,584,896. The size of this set is smaller, but not significantly smaller (less than 2%). This isn't a reasonable counter to his argument though because this is the ideal case. For comparison, if the 8 character password includes punctuation, there are 6,095,689,385,410,816 possible values, an order of magnitude more at this length.
So, the real question is how many guesses does it reasonably take? If you tell people to select mixed-case, alphanumeric, 8 character passwords, they will not generate ideal passwords like Z6Foy0jR (generated specifically for this example). They'll select things like Ssssss55 or 67vikinG. And if you ask them to change these passwords periodically, they'll produce new ones like Ssssss66 or Viking68.
There are password breaking programs out there that will take a set of words you supply and apply rules to them to generate possible alternate passwords. Similar programs have been around since the early 90s, when I first got involved in looking at password security as a system administrator. This kind of approach is called a "hybrid" attack because it combines an iterative set of rules with a dictionary. The program I'm referring to is John the Ripper, but Crack, the first program I used, had a similar capability. John ships with a default password list that the developer claims has a high success rate. There are roughly 3,000 words in this file. On Unix you could use the /usr/dict/words file, too. If you restrict to words that are roughly in the right length range, you'll have 3,000 - 8,000 words. A little further afield you can download dictionary files specifically for password guessing that have millions of words, some of them, like Galadriel or Romulan, outside of the usual English lexicon used by spell checkers.
To give an idea what the mangling does to the number of guesses, the default rule set and default password list for John will produce a new password list of around 126,000 from the 3,000 value source file. John also includes some additional rules that use user proifle information instead of password files. If these rules are also added to the mix, then roughly 1,800,000 words are generated. That's a sizeable jump and includes passwords that are too short for what we're doing (I asked for 8 character passwords, so it went up to 8 characters) but gives us a ballpark. 1,800,000 guesses is still significantly less than 10^15 (or 62^8, whatever gets you in the ballpark). These rules aren't exhaustive (Ssssss55, Ssssss66, and Viking68 would be caught, but not 67vikinG), but the rules are configurable and can easily be expanded. The trick really is to keep the number of variations to within a reasonable fraction of the total search space. Almost any reasonable number of operations below (62^8)/2 is cheaper than brute force. Almost any time scale that's within a month or two is feasible.
These rules do have short comings if you're trying to target a single password as opposed to simply catching the low hanging fruit in a password database. They're essentially substitution and permutation rules so even a little variation can produce a password that's outside the generated set of guesses. It's easy to write a rule, for example, that replaces all e's with 3's, but harder to write a rule that tries all the possibilities for replacing only some e's with 3's. It will only catch misspellings if they're common enough to make it into a source password list or to be caught by a simple rule, like switching ie for ei or substituting k for c.
So, a rough guess is that something on the order of 10^6 or maybe 10^8 dictionary based hybrid attacks on the password is a reasonable search space for 8 character alphanumeric passwords depending on the rules and the choice of dictionary. Password expiry is of little help here. The length of time to work in this space gets less and your policy only moves towards something unreasonable. While it's possible to use a dictionary based password and still avoid this search space, you're putting yourself in the path of the attack and betting it will miss you. There are better ways.
In any case, here are some things to think about from a system designer and policy setting point of view. It's extraordinarily difficult to set policies on your passwords that protect users from themselves. You'd need to duplicate the rules your attackers are using in order to push users outside that search space. What you want to do is not avoid the attack (that's impossible) but increase the number of operations that are needed to guess the password. The easiest thing to do is increase the size of the search space.
Where we're limited to 8 characters, our only choice is to add punctuation to our password policy. This increases the ideal space from 10^14 to 10^15. If we were able to increase the length of the password by a single character and keep the old alphanumeric policy, then it would increase to 10^16. Simple increases in length trump complexity. John's generated list from the same old source dictionary and using the extended ruleset only jumps up to 2,000,000. Bumping the length up higher quickly runs into the upper limit for possible passwords that can be generated from this combination of rules and dictionary, which is around 2,500,000. We would need a different dictionary in order to keep pace.
One of the things to keep in mind is that newer systems for storing passwords are not restricted by the length of the password. An MD5 or SHA-1 hash of a password will take an arbitrary length piece of text and produce a fixed length result. This means you could have a 100 character password if you wanted and the system would not care. I've had this discussion with folks building login pages for web sites. From an implementation viewpoint, there should be a reasonable fixed size to the text that can be provided, but we should stop telling users that there's a maximum length for their passwords. As one LDAP support person I spoke to years ago said, as long as it's under 1 MB why should we care? A minimum length is a must, but the maximum length can afford to be pretty open ended.
This argument gets some criticism from useability folks, though, who claim that users have enough trouble remembering their 6 or 8 character passwords. I think they might be more creative if we gave them more space and a little advice. Imagine full sentences or sets of interesting dictionary words. The usual argument against this in security circles is that users will pick movie quotes and bits of song lyrics in the same way that they pick dictionary words. There's a lot of truth to that, but there's more content and more complex content in the language than in individual words or small sets of letters. The objective is to increase the number of operations needed to gain the password or passphrase.
You can implement this kind of password today. Windows XP Home supports arbitrary length passwords, for example.
* I said I needed a citation. And I do. I was going to try cracking a random, 3 character, mixed case, alphanumeric password with John the Ripper and see how long it took. But John assumes that no sane sysadmin would ever allow this length of password (and convincing RedHat to let me make one involved turning several things off) and it doesn't find it. I think it would be possible to configure John, or even extend its functionality using the scripting capability, to try guessing this password, but frankly I can't be bothered. I'd be shocked if it took a whole hour though.
no subject
Date: 2008-10-30 06:58 pm (UTC)I've dropped the (- 1) part of this calculation as being nearly insignificant, but that's where the reasoning stems from.
no subject
Date: 2008-10-30 06:59 pm (UTC)In case, my argument needs further clarification, assume my ordering looks like a-zA-Z0-9, where a is the smallest value and 9 is the largest. Then 62^2 starts at 'a' and proceeds to '99'. Maybe I need to actually count a list this size to confirm that the value I'm giving it is correct?
no subject
Date: 2008-10-30 07:05 pm (UTC)no. if it were a 3-character numeric pin, then it would have potentially 10^3 values, including 000, which is still a (as far as i know, valid - correct me on that if i'm missing the point) 3-digit pin. i think one of us is missing something here. it might be me...
no subject
Date: 2008-10-31 02:25 am (UTC)no subject
Date: 2008-10-31 03:25 am (UTC)no subject
Date: 2008-11-01 05:55 pm (UTC)I think this means that calculating the actual size of the search space for alphanumeric passwords between, say, 6 characters and 8 characters in length would be 62^8 + 62^7 + 62^6.
I'll have to rewrite this post now. :-P
no subject
Date: 2008-11-01 06:32 pm (UTC)that looks more like it, yup