Randomly-generated passwords still have to be legal strings(blogs.msdn.microsoft.com)
blogs.msdn.microsoft.com
Randomly-generated passwords still have to be legal strings
https://blogs.msdn.microsoft.com/oldnewthing/20160316-00/?p=93163
13 comments
Unicode mystifies a lot of people. Many people don't even realize that a sequence of 16-bit unicode value is UTF-16 (or UCS-2), let alone that not all sequences of 16-bit values are valid UTF-16.
The password bit is really just the hook, the main info in this article is the fact that these values are interpreted as UTF-16, and that UTF-16 has requirements beyond "sequence of 16-bit values."
Which is kind of obvious, but still not well known for many.
The password bit is really just the hook, the main info in this article is the fact that these values are interpreted as UTF-16, and that UTF-16 has requirements beyond "sequence of 16-bit values."
Which is kind of obvious, but still not well known for many.
I'll freely admit to being one of those mystified folk. As an easy example of which, can you roughly outline which n-bit values are not valid UTF-n? (are they reserved for shifting to other systems? and if so, isn't that still a valid, even an important value, within UTF-n?)
The article covers this for the case of UTF-16. To recap, UTF-16 has surrogate pairs, which are a sequence of two 16-bit values in certain ranges. A high surrogate is in the range 0xD800–0xDBFF and a low surrogate is in the range 0xDC00–0xDFFF. This is used to encode values beyond 65,535. If a high surrogate appears without a following low surrogate, or a low surrogate appears without a leading high surrogate, the sequence is not valid UTF-16.
For UTF-32, only valid code points are allowed. Values above 0x10FFFF are not allowed, nor are values in the range used for UTF-16 surrogates.
UTF-8 is more complex. It's ASCII compatible, which means all values with the top bit set to 0 are allowed. Bytes with the top bit set to 1 must exist as part of a multi-byte sequence. The first byte in such a sequence must contain 2-4 leading 1s followed by a 0. Subsequent bytes must be of the form 10xxxxxx. The total length of the sequence is equal to the number of leading 1s in the first byte. Any deviation from this is invalid UTF-8. Further, any sequence must be minimal, meaning that the value it encodes can't be one that would fit into a smaller sequence.
For UTF-32, only valid code points are allowed. Values above 0x10FFFF are not allowed, nor are values in the range used for UTF-16 surrogates.
UTF-8 is more complex. It's ASCII compatible, which means all values with the top bit set to 0 are allowed. Bytes with the top bit set to 1 must exist as part of a multi-byte sequence. The first byte in such a sequence must contain 2-4 leading 1s followed by a 0. Subsequent bytes must be of the form 10xxxxxx. The total length of the sequence is equal to the number of leading 1s in the first byte. Any deviation from this is invalid UTF-8. Further, any sequence must be minimal, meaning that the value it encodes can't be one that would fit into a smaller sequence.
In the vein of "unicode mystifies people", one interesting fact is that converting a unicode string to lower-case is not length-preserving - whether you're counting bytes (in any of the standard encodings) or characters!
What doesn't make sense though is why the password's bits MUST be a valid UTF-16 string. Password comparison should just be comparing bits and checking if they're equal.
Whether it may just so happen to represent real, correctly typed, English words, or be a valid ASCII string, or UTF-16 string, or whether it was typed it from your keyboard, or generated from a program, these should also be incidental.
Whether it may just so happen to represent real, correctly typed, English words, or be a valid ASCII string, or UTF-16 string, or whether it was typed it from your keyboard, or generated from a program, these should also be incidental.
If your passwords are entered by humans (which is usually what "password" means) then you want to treat it as a real Unicode string so that you can normalize it before you do the dirty work on it. Otherwise you could end up with a situation where, for example, a user's password contains "é" and fails when entered on certain systems because that system composes é differently from the system on which the password was set.
And how do you suppose to deal for example cases where some login forms have different character encodings than others but use same authentication backend? Or cases where user agents use inconsistent character composition? Or some other fun edge case?
> We found that sometimes (no predictable pattern), we have interoperability problems between systems. The password produced by one system is not recognized by the other.
I second the "hex encode it" solution, 256 bit of generated hex looks something like this:
232e2252b8d5a294dd8564020f0cf609f511b3d196ed83030ce9615c6737f578
That's readable, typable, copy-pastable. Not very memorable but 256 bits is rarely memorable.
It's still short enough to send around by normal messaging.
This is specifically about randomly generated passwords, this is not about dealing with human generated "must have capitals, not start or end with a number" etc rules.
232e2252b8d5a294dd8564020f0cf609f511b3d196ed83030ce9615c6737f578
That's readable, typable, copy-pastable. Not very memorable but 256 bits is rarely memorable.
It's still short enough to send around by normal messaging.
This is specifically about randomly generated passwords, this is not about dealing with human generated "must have capitals, not start or end with a number" etc rules.
Remember on windows you are effectively stuck with a maximum password length of 15 characters in many scenarios.
And before you Google and say "No! It changed to 127 in Windows XP!", remember:
- Somewhere on your network, NTLM is being used.
- Office 365 supports 16 max.
- Lots of random apps won't work.
And before you Google and say "No! It changed to 127 in Windows XP!", remember:
- Somewhere on your network, NTLM is being used.
- Office 365 supports 16 max.
- Lots of random apps won't work.
Dangerously incorrect (also, the two magic #s are 14 for ntlm and 16 for o365; where did you get 15 from?)
1 - if you have ntlm (non-v2) on your network, you're fucked anyway and this debate is academic. 2 - even if you do, having a password of 15 or more characters will cause your legacy hash to be set to "AAD3B435B51404EEAAD3B435B51404EE" and will protect you against having your hash cracked if it's stolen from the non-v2 service. 3 - the office 365 limits can be worked around with dirsync or federation (source: I've done both)(note: outlook does weird things with leading/trailing spaces) 4 - those apps should be kerberized or similar
1 - if you have ntlm (non-v2) on your network, you're fucked anyway and this debate is academic. 2 - even if you do, having a password of 15 or more characters will cause your legacy hash to be set to "AAD3B435B51404EEAAD3B435B51404EE" and will protect you against having your hash cracked if it's stolen from the non-v2 service. 3 - the office 365 limits can be worked around with dirsync or federation (source: I've done both)(note: outlook does weird things with leading/trailing spaces) 4 - those apps should be kerberized or similar
My bad on the 15 -- I did a very large O365 migration 3 years ago and haven't been in the weeds for a couple of years. I got my head wrapped around Azure MFA app passwords and the samaccountname limits.
In any case, the point is as a user, especially on a big network, you have no idea what your actual effective password strength is. Plenty of places do lots of dumb things with AD -- one example that comes to mine was an inter forest trust between two good sized domains where bad DNS implementation and... Misguided security interpretations basically made it impossible to use Kerberos.
In any case, the point is as a user, especially on a big network, you have no idea what your actual effective password strength is. Plenty of places do lots of dumb things with AD -- one example that comes to mine was an inter forest trust between two good sized domains where bad DNS implementation and... Misguided security interpretations basically made it impossible to use Kerberos.
I think you're wrong.
I login to Office 365 with a password that has over 16 characters. I have similar length passwords in Windows networks that use NTLM. Clearly it works just fine.
I login to Office 365 with a password that has over 16 characters. I have similar length passwords in Windows networks that use NTLM. Clearly it works just fine.
Just a guess, but I've seen systems that just ignore the extra characters. VNC is one, and there's others.
Example:
Your password is 12 characters on a system that says make it 8 characters or longer. If you type only the first 8 characters of your password, it lets you in. As someone else said, "silent truncation".
Example:
Your password is 12 characters on a system that says make it 8 characters or longer. If you type only the first 8 characters of your password, it lets you in. As someone else said, "silent truncation".
I think you're correct now, but I believe this changed relatively recently (maybe around a year or so?) In fact, in some Microsoft Account password setting pages, there are warnings that say setting the password longer than 16 can cause XBox logins to fail (I think this is in Windows 10 for example).
All of this is anecdote from personal experience so take it with a grain of salt. I haven't researched it.
All of this is anecdote from personal experience so take it with a grain of salt. I haven't researched it.
I've been using 20+ character Windows passwords for years and have literally never had a single problem with it.
Silent password truncation isn't a problem that reveals itself until someone cracks the shorter NTLM hash.
someone cracks the shorter NTLM hash.
There are only two possible hashes stored in the SAM database. You mention the 'shorter' one, which would be the 'LM hash' which is restricted to 14 character passwords. However, LM hash storage has been disabled by default for all windows system since Vista / Windows Server 2008 (and ability to not store them was available, but not disabled by default since at least Windows 2000). Even Samba has had the ability to not generate or store the LM hash since at least 2002 (earliest search reference I could find).
There are only two possible hashes stored in the SAM database. You mention the 'shorter' one, which would be the 'LM hash' which is restricted to 14 character passwords. However, LM hash storage has been disabled by default for all windows system since Vista / Windows Server 2008 (and ability to not store them was available, but not disabled by default since at least Windows 2000). Even Samba has had the ability to not generate or store the LM hash since at least 2002 (earliest search reference I could find).
Try pointing something like L0phtCrack at your SAM database and see how quickly it shreds through all but the most complex NTLM and LM password hashes.
Using something like john [the ripper] with a decent dictionary and applying mangling rules will shred through the rest.
Not to mention, there's rainbow tables built and freely downloadable that contain every possible LM and NTLM hash (they're huge files, 30+ GB's, but if you need to crack in a hurry...).
Using something like john [the ripper] with a decent dictionary and applying mangling rules will shred through the rest.
Not to mention, there's rainbow tables built and freely downloadable that contain every possible LM and NTLM hash (they're huge files, 30+ GB's, but if you need to crack in a hurry...).
> ...but the most complex...
Those would be the passwords that we're talking about here. Next time you run either, take a look at the count of uncracked passwords. There are always some, which should tell you something.
Also, I couldn't reply to you before so see my reply to parent WRT rainbow table size. They're not the panacea you're implying.
Those would be the passwords that we're talking about here. Next time you run either, take a look at the count of uncracked passwords. There are always some, which should tell you something.
Also, I couldn't reply to you before so see my reply to parent WRT rainbow table size. They're not the panacea you're implying.
> They're not the panacea you're implying.
But they are - we have a hard-limited keyspace, with a fixed well-known and understood algorithm, which means, regardless of disk size, a rainbow table can (and has been) generated to cover the entire LM/NTLM space.
This place just has a few for starters[1]
[1] http://project-rainbowcrack.com/table.htm
But they are - we have a hard-limited keyspace, with a fixed well-known and understood algorithm, which means, regardless of disk size, a rainbow table can (and has been) generated to cover the entire LM/NTLM space.
This place just has a few for starters[1]
[1] http://project-rainbowcrack.com/table.htm
The limited key-space is the full set of unicode characters which have alt-codes and can thus be typed into a password prompt. This is a much larger key-space than the traditional a-zA-Z1-9 space most people use in their tables. Anecdotally (insert usual HN isn't real life quote) I polled the people I work with and roughly 1/3 of us paranoiacs have at least one such character.
What you're saying is akin to saying you can defeat AES by generating all possible keys and trying them. Possible? Totally. Realistic? No.
You have repeatedly now said that such a table exists. Source? How big was it, and at what work factor was it created? Keep in mind that the full space is all alt-codes and must cover passwords up to length 127. The site we have now both linked to does not have such a table.
What you're saying is akin to saying you can defeat AES by generating all possible keys and trying them. Possible? Totally. Realistic? No.
You have repeatedly now said that such a table exists. Source? How big was it, and at what work factor was it created? Keep in mind that the full space is all alt-codes and must cover passwords up to length 127. The site we have now both linked to does not have such a table.
(and has been) generated to cover the entire LM/NTLM space
I don't think this is true. Certainly true for the LM space of 7 characters, but the size of the NTML rainbow table for all passwords of length 1-9 with "only" mixed alphanumeric is 690GB with a key space of 13,759,005,997,841,642. This doesn't include the fact that a windows password can use any unicode character. So while there is could be some sort of collision with a shorter password, it's not really likely. Note that windows passwords can be up to 127 unicode characters, but that in win2k/2k3 the actual dialog box would only allow 32. So we're talking quite a bit more space to have each combination stored.
Additionally, unless I'm doing some bad math here, it's just not currently possible to have a rainbow table that includes all possible MD4 hash values. An MD4 hash is 16 bytes, which is 128 bits. In order to just list each hash would take 16 bytes * 2^128 = 5 * 10^39 bytes, which is something like 5 * 10^27 terabytes, 5 * 10^13 yottabytes, etc. This doesn't include any space to list whatever password caused that hash to be calculated.
And directly 'reversing' an MD4/NTLM hash still requires a preimage attack on MD4 and the current best known is still at a complexity of 2^121 [0], which would likely still be more feasible than having access to an MD4 rainbow table with all possible hash values.
[0] - https://who.rocq.inria.fr/Gaetan.Leurent/files/MD4_FSE08.pdf
I don't think this is true. Certainly true for the LM space of 7 characters, but the size of the NTML rainbow table for all passwords of length 1-9 with "only" mixed alphanumeric is 690GB with a key space of 13,759,005,997,841,642. This doesn't include the fact that a windows password can use any unicode character. So while there is could be some sort of collision with a shorter password, it's not really likely. Note that windows passwords can be up to 127 unicode characters, but that in win2k/2k3 the actual dialog box would only allow 32. So we're talking quite a bit more space to have each combination stored.
Additionally, unless I'm doing some bad math here, it's just not currently possible to have a rainbow table that includes all possible MD4 hash values. An MD4 hash is 16 bytes, which is 128 bits. In order to just list each hash would take 16 bytes * 2^128 = 5 * 10^39 bytes, which is something like 5 * 10^27 terabytes, 5 * 10^13 yottabytes, etc. This doesn't include any space to list whatever password caused that hash to be calculated.
And directly 'reversing' an MD4/NTLM hash still requires a preimage attack on MD4 and the current best known is still at a complexity of 2^121 [0], which would likely still be more feasible than having access to an MD4 rainbow table with all possible hash values.
[0] - https://who.rocq.inria.fr/Gaetan.Leurent/files/MD4_FSE08.pdf
Indeed, the LM hash was easily cracked by l0pht back in the day since the lanman hash could be split in two and cracked separately, meaning it only needed to consider all 7 character combinations.
Also, note that with the rainbow tables (for both NTLM and LM hashes), it will give you a password that hashes to the same exact value, but not necessarily the same exact password. This is kind of obvious once you understand that the NTLM (as compared to LM) hash is just md4(password) and is just 16 bytes long.
So that's valuable as it will let you log in to the machine, but since it's not actually giving you the actual password back, it's not helpful for logging in to other non-windows systems that may have the same password. Also, it requires administrator level access, a local privilege escalation exploit or a physical copy of the disk, to the SAM database, any of which likely mean that cracking the password is irrelevant.
Also, note that with the rainbow tables (for both NTLM and LM hashes), it will give you a password that hashes to the same exact value, but not necessarily the same exact password. This is kind of obvious once you understand that the NTLM (as compared to LM) hash is just md4(password) and is just 16 bytes long.
So that's valuable as it will let you log in to the machine, but since it's not actually giving you the actual password back, it's not helpful for logging in to other non-windows systems that may have the same password. Also, it requires administrator level access, a local privilege escalation exploit or a physical copy of the disk, to the SAM database, any of which likely mean that cracking the password is irrelevant.
In response to the existence of a rainbow table for "all possible hashes", consider that a rainbow table over all possible (ascii printable) characters with a maximum length of 8 characters is well over 400GB. These sizes grow factorially as the password length increases.
[1] http://project-rainbowcrack.com/table.htm
[1] http://project-rainbowcrack.com/table.htm
Try logging in with only the first 16 characters of your password rather than the full password.
"the username or password is incorrect."
Why not base64? Even shorter, readable, typable, copy-pastable (why are you copy-pastung passwords?), and pehaps even memorable.
Indeed.
$ dd if=/dev/random bs=1 count=32 | base64
ca2ktYYvppr1/HwwGYrg01udQX1cP4Ek5VmyzQydT+8=My mother was a saint!!
... when I just still wet behind the ears I was studying the codebase of my first job, and came across a quite extensive badwords.txt . On asking why we had a the dictionary of cussing in our project, I found out that the randomly generated passwords that we sent to our clients, apparently managed to get a customer quite angry when one of the words produced started with a slur, and this was a filter to prevent that from happening again
Generating random passwords isn't quite as straightforward as it would seem to be...
... when I just still wet behind the ears I was studying the codebase of my first job, and came across a quite extensive badwords.txt . On asking why we had a the dictionary of cussing in our project, I found out that the randomly generated passwords that we sent to our clients, apparently managed to get a customer quite angry when one of the words produced started with a slur, and this was a filter to prevent that from happening again
Generating random passwords isn't quite as straightforward as it would seem to be...
> randomly generated passwords
> we sent to our clients
I'm making the assumption that these are one-time passwords for initial account setup. But no, no one scheme will work for everything, obviously. The hex version will fail for schemes which have an upper limit, or when there's a requirement for upper/lower/symbols. The base64 encoding will fail other validations due to the '/' character, or for particularly restrictive upper size limits.
I wish all of them would simply accept a string and put in an upper limit of 1k to limit DOS by password. Call it good.
> we sent to our clients
I'm making the assumption that these are one-time passwords for initial account setup. But no, no one scheme will work for everything, obviously. The hex version will fail for schemes which have an upper limit, or when there's a requirement for upper/lower/symbols. The base64 encoding will fail other validations due to the '/' character, or for particularly restrictive upper size limits.
I wish all of them would simply accept a string and put in an upper limit of 1k to limit DOS by password. Call it good.
This approach requires that your badwords.txt is not just extensive, but supports all languages.
Isn't it easier to just generate words without vowels? This is the more common solution to that problem, IIRC.
Isn't it easier to just generate words without vowels? This is the more common solution to that problem, IIRC.
Yeah I thought about that as well when I wrote down the above. Doing general localization is really hard if you want to do it well. If you know your approximate audience, you probably have to tailor your localization to them, instead of everybody.
Case in point: Not all scripts even have vowels.
Case in point: Not all scripts even have vowels.
That would fail if you tried using it as a password with JetBlue, which does not allow the letters Q or Z: http://security.stackexchange.com/questions/57909/why-would-...
And the hex encoding fails if they require a symbol. No single passphrase generation tool works for all sites... but that's more a problem with the sites' requirements for passwords.
[deleted]
I copy-paste passwords from a password manager. Usually it puts it right in the clipboard for me though, so I don't have to highlight it manually.
I always loved hex encoding because you can always click it twice to highlight the entire string. It's a simple thing, but always saves time and reduces errors.
Different systems have different characters that will be included/discluded from "twice click highlighting" (I have no idea what the term is called). Hex works on virtually all systems.
The article does mention it's not very space efficient.
Different systems have different characters that will be included/discluded from "twice click highlighting" (I have no idea what the term is called). Hex works on virtually all systems.
The article does mention it's not very space efficient.
I argue with 'typable.' If I'm reading this from my smartphone and typing it on my computer (or vice versa), I'm going to lose my place. Maybe formatting could fix that, but it's still a pretty long chunk of text to get lost in.
Two bytes at a time is not so bad, especially with some friendly newlines:
232e 2252 b8d5 a294
dd85 6402 0f0c f609
f511 b3d1 96ed 8303
0ce9 615c 6737 f578
In fact I find it MUCH more typable than my usual generated password, which are like ,X,=a&ny.Qz{?Uif@0q( and are a real pain to type on mobile due to the special characters.
That might be ameliorated by choosing a touch keyboard optimized for character-by-character input rather than english text. MessagEase works well for me for that.
Is there really any need to generate non-alphanumeric passwords as long as they are of sufficient length? Sticking with plain old A-Za-z0-9 seems like it avoids a lot of interop issues.
Every extra supported character makes the solution space much bigger. with 2 character passwords, your set is 3844 combinations. If you can manage to add in "!@#$%^&*()", that goes up to 5184, a 16% increase in options leads to a 34% increase in search space.
No, it's not necessary, unbounded length is probably better. But it's pretty nice to have a lot more characters, and ought to be an easy win.
No, it's not necessary, unbounded length is probably better. But it's pretty nice to have a lot more characters, and ought to be an easy win.
Every required charter type makes the search space dramatically smaller. https://xkcd.com/936/
The goal should be long easy to type and remember passwords, adding an extra few digit is worth far more than forcing passwords to look like: 2K#@1j*
Compare say a 20 digit numeric password vs an 9 digit [0-9] [a-z] [A-Z] and special.
The goal should be long easy to type and remember passwords, adding an extra few digit is worth far more than forcing passwords to look like: 2K#@1j*
Compare say a 20 digit numeric password vs an 9 digit [0-9] [a-z] [A-Z] and special.
> Every required charter type makes the search space dramatically smaller.
That is neither what the parent suggested nor really true. The space of, say, 8 character passwords A-Za-z0-9 that DO have at least one digit is very similar in size to the space of passwords maybe not containing digits. (The latter is 36^8 the former is 36^8-26^8, a reduction by less than 8% of the password space. The difference is even less important for longer passwords)
That is neither what the parent suggested nor really true. The space of, say, 8 character passwords A-Za-z0-9 that DO have at least one digit is very similar in size to the space of passwords maybe not containing digits. (The latter is 36^8 the former is 36^8-26^8, a reduction by less than 8% of the password space. The difference is even less important for longer passwords)
People have a huge bias to add digits and special Characters at the end of a password and start a password with an upper case letter. 1! is also really common. So, the rules often end up with something like a ~90% reduction in search space.
PS: You also forgot about the special character.
PS: You also forgot about the special character.
What rule am i proposing? when am i "requiring" a special character?
"correcthorsebatterystaple" is ok, "correct! horse battery Σtaple" is better.
Why are you arguing i shouldn't be allowed to use any key on my keyboard?
There is no reason to disallow any character in a password. let me use them all. limiting to A-Za-z0-9 is goofy and antiquated.
"correcthorsebatterystaple" is ok, "correct! horse battery Σtaple" is better.
Why are you arguing i shouldn't be allowed to use any key on my keyboard?
There is no reason to disallow any character in a password. let me use them all. limiting to A-Za-z0-9 is goofy and antiquated.
> "correcthorsebatterystaple" is ok, "correct! horse battery Σtaple" is better.
"better" is a dangerous term. Better as for bruteforce guessing resilience? Sure. Better for security? That would be much less certain. Once you discover the users can't enter it on mobile (no Σ on default keyboard) you'd have to provide replacement mechanism for them or allow them to easily reset passwords. Which probably would be the way your security will be compromised soon. And, of course, the users will be losing such fancy passwords at incredible rates, which would generate a lot of noise on "password reset" system which would make it harder for you to detect abuse there. And that not even considering that humans are very bad at avoiding biases and choosing "random" character replacements - they probably would do the same thing in 90% of cases (yes, you are in the 10% of course, but that doesn't change the statistics), like replacing o with 0 and adding ! at the end. Which robots would defeat instantly.
So it's not about forbidding you from using your special characters. It's that using them - on the whole, not for you personally - may not make any improvement, and if you force it, might actually make the matters worse. Encouraging long passwords that one can remember would seems to be actually better. Or doing away with passwords and using something else :)
"better" is a dangerous term. Better as for bruteforce guessing resilience? Sure. Better for security? That would be much less certain. Once you discover the users can't enter it on mobile (no Σ on default keyboard) you'd have to provide replacement mechanism for them or allow them to easily reset passwords. Which probably would be the way your security will be compromised soon. And, of course, the users will be losing such fancy passwords at incredible rates, which would generate a lot of noise on "password reset" system which would make it harder for you to detect abuse there. And that not even considering that humans are very bad at avoiding biases and choosing "random" character replacements - they probably would do the same thing in 90% of cases (yes, you are in the 10% of course, but that doesn't change the statistics), like replacing o with 0 and adding ! at the end. Which robots would defeat instantly.
So it's not about forbidding you from using your special characters. It's that using them - on the whole, not for you personally - may not make any improvement, and if you force it, might actually make the matters worse. Encouraging long passwords that one can remember would seems to be actually better. Or doing away with passwords and using something else :)
Not accepting all of unicode is mystifying to me. I've had to localize with code pages in the past. i'm probably scarred in horrible ways which causes a strong bias against the kinds of arbitrary limits people seem to be supporting.
Anyway.
Yeah, hopefully we'll come up with something other than passwords.
Anyway.
Yeah, hopefully we'll come up with something other than passwords.
For requiring both a number and a special character (out of 10 possibilities): reduces passwords from 46^8 to 46^8 - (36^8 + 36^8-26^8) which is a 27% reduction in password space. I wouldn't call that dramatic and it reduces in importance as the password length grows and, as you bring up biases, it eliminates the most abused password types.
I don't understand your comments about adding digits and special characters at the end of the password. password + digit + special character is strictly harder to guess than just password (we've added two extra characters, after all). Do you mean that people routinely delete the last two letters of their alphabetic password and replace them with 1! ? I find that implausible. The key point is that if you don't require numbers and special characters then no one uses them at all so the possibility space becomes 26^8.
I don't understand your comments about adding digits and special characters at the end of the password. password + digit + special character is strictly harder to guess than just password (we've added two extra characters, after all). Do you mean that people routinely delete the last two letters of their alphabetic password and replace them with 1! ? I find that implausible. The key point is that if you don't require numbers and special characters then no one uses them at all so the possibility space becomes 26^8.
> (we've added two extra characters, after all)
No, the same length just with more restrictions. Your suggesting you replace a min 8 digit password with a minimum 10 digit password but the gain is from adding length not restrictions.
Sadly plenty of passwords are fixed at 8 digits and they reduce the search space below that. So you go from 26^8 to 26^1 x 26^5 and 1! which effectively is just 26^6.
IMO it's reasonable to remove the top 100 or so passwords. But, after that your just reducing the search space.
No, the same length just with more restrictions. Your suggesting you replace a min 8 digit password with a minimum 10 digit password but the gain is from adding length not restrictions.
Sadly plenty of passwords are fixed at 8 digits and they reduce the search space below that. So you go from 26^8 to 26^1 x 26^5 and 1! which effectively is just 26^6.
IMO it's reasonable to remove the top 100 or so passwords. But, after that your just reducing the search space.
Do you honestly think that people pick MORE predictable passwords when required to include digits and symbols? I agree that few are very creative with how they use the digits and symbols, but in no way is this lack of creativity greater than the lack of creativity that is exercised when given no constraints. People just love to use a dictionary word or common phrase or ncc1701 as their password and call it done.
100 passwords is nothing compared to a state space of 36^8 = 2.8x10^12. Remove a million or ten if you want. I think you're strongly underestimating how large this space is. Almost any change you can imagine pushes people out of the relatively minuscule space of actually-used-passwords and into the vast barren lands of all-possible-passwords and thereby increases time taken to crack. If you think requiring a number and special character are damaging (since people just have them at the end), then how about the requirement that they have numbers and special characters that are NOT at the end? I've seen this before and it forced me to invent a new password instead of reusing one. It's technically reducing the state space, but it increases the space of passwords that are actually used.
Sure, those 27% of people who actually generated a random password and then happened to get no numbers or special characters are annoyed that they have to generate a new password, but everyone else is picking better passwords.
100 passwords is nothing compared to a state space of 36^8 = 2.8x10^12. Remove a million or ten if you want. I think you're strongly underestimating how large this space is. Almost any change you can imagine pushes people out of the relatively minuscule space of actually-used-passwords and into the vast barren lands of all-possible-passwords and thereby increases time taken to crack. If you think requiring a number and special character are damaging (since people just have them at the end), then how about the requirement that they have numbers and special characters that are NOT at the end? I've seen this before and it forced me to invent a new password instead of reusing one. It's technically reducing the state space, but it increases the space of passwords that are actually used.
Sure, those 27% of people who actually generated a random password and then happened to get no numbers or special characters are annoyed that they have to generate a new password, but everyone else is picking better passwords.
>Do you honestly think that people pick MORE predictable passwords when required to include digits and symbols?
After looking at lists of user passwords <yes>.
User chosen passwords are generally terrible. If you want users to use secure passwords the correct solution is to generate them and send them to users. Granted, users are going to just write them down at that point.
After looking at lists of user passwords <yes>.
User chosen passwords are generally terrible. If you want users to use secure passwords the correct solution is to generate them and send them to users. Granted, users are going to just write them down at that point.
I really really think you're mistaken. I completely agree that users choose passwords from a tiny subset of the possibilities and that counting the whole state space is a nearly useless measure. But there just HAS to be more variability when users are forced to do something different. Like trying to find someone, or trying to find someone who has been disallowed from being at their home or work that day. The second person is going to be much harder to find, even if they're still really predictable and just end up at the coffee shop across the street.
What lists of user passwords were you looking at? I looked through the default one used by John the Ripper (though they recommend using a larger one for any real purpose) and there were hardly any uses of punctuation at all (exceptions "iloveyou!" and "!@#$%^&*") so I can't make the least bit of conclusions. Reading the list of rules it uses to modify passwords, it prepends and appends digits and punctuation but doesn't seem to delete two characters and then replace them with 1!, or anything similar to that. (Though I'll admit to being inexpert at reading the rule formats and not understanding some). That's as close to empirical data as I've got this side of thinking about how I incorporate symbols and numbers.
What lists of user passwords were you looking at? I looked through the default one used by John the Ripper (though they recommend using a larger one for any real purpose) and there were hardly any uses of punctuation at all (exceptions "iloveyou!" and "!@#$%^&*") so I can't make the least bit of conclusions. Reading the list of rules it uses to modify passwords, it prepends and appends digits and punctuation but doesn't seem to delete two characters and then replace them with 1!, or anything similar to that. (Though I'll admit to being inexpert at reading the rule formats and not understanding some). That's as close to empirical data as I've got this side of thinking about how I incorporate symbols and numbers.
I'm not saying require *, I'm saying allow the option.
Usability is key.
Once you hit 12+ characters it is extremely likely that the password is vulnerable to dictionary/phrase attacks combining whole words - or you're using a password manager.
The xkcd is funny - but it's also a terrible password suggestion.
Once you hit 12+ characters it is extremely likely that the password is vulnerable to dictionary/phrase attacks combining whole words - or you're using a password manager.
The xkcd is funny - but it's also a terrible password suggestion.
Why is it terrible?
Certainly a passphrase consisting of 4 English words is going to be easier to attack than a password consisting of a similar number of random letters. But as long as you judge a password or passphrase by its information content rather than by its length, xkcd-style passphrases can be just as good as random letters, but are likely to be easier to remember.
Plug: I've written a random passphrase generator, inspired by xkcd's https://xkcd.com/936/ ("correct horse battery staple") that picks random words from a dictionary, subject to requirements you can give on the command line. It optionally tells you how much randomness is contained in the generated passphrase (assuming the attacker knows the parameters you used). Sample output (picking 4 words of 6 to 8 letters):
https://github.com/Keith-S-Thompson/random-passwords
Of course this won't work for sites that restrict the length of a password, or that require special characters.
Certainly a passphrase consisting of 4 English words is going to be easier to attack than a password consisting of a similar number of random letters. But as long as you judge a password or passphrase by its information content rather than by its length, xkcd-style passphrases can be just as good as random letters, but are likely to be easier to remember.
Plug: I've written a random passphrase generator, inspired by xkcd's https://xkcd.com/936/ ("correct horse battery staple") that picks random words from a dictionary, subject to requirements you can give on the command line. It optionally tells you how much randomness is contained in the generated passphrase (assuming the attacker knows the parameters you used). Sample output (picking 4 words of 6 to 8 letters):
$ gen-passphrase -v 4 6 8
verity nonfat shunted specking
27405**4
5.6405e17 possibilities, equivalent to:
58.97 random bits
12.55 random lowercase letters
9.90 random mixed-case alphanumerics
9.00 random printable ASCII characters
https://github.com/Keith-S-Thompson/random-passwords
Of course this won't work for sites that restrict the length of a password, or that require special characters.
> Why is it terrible?
Ars Technica published an article a few years ago about password crackers, and one of the subjects they interviewed mentioned the XKCD strip in an offhand remark that was flawed and hinted towards what was probably a poor understanding of the subject matter.
Now whenever the XKCD strip is brought up, people who've been shown the article make an appearance and and talk about the scheme being vulnerable while using the phrase "dictionary attack" in a non-specific sort of way.
That's probably what's going on in the GP comment.
http://arstechnica.com/security/2013/05/how-crackers-make-mi...
Ars Technica published an article a few years ago about password crackers, and one of the subjects they interviewed mentioned the XKCD strip in an offhand remark that was flawed and hinted towards what was probably a poor understanding of the subject matter.
Now whenever the XKCD strip is brought up, people who've been shown the article make an appearance and and talk about the scheme being vulnerable while using the phrase "dictionary attack" in a non-specific sort of way.
That's probably what's going on in the GP comment.
http://arstechnica.com/security/2013/05/how-crackers-make-mi...
Nothing is wrong with a good password manager.
Don't forget having lot's of passwords written down in an office setting is terrible for different reasons. &$RGJL__"LKHF#3fghu seems great until it's an a sticky or notepad file.
Don't forget having lot's of passwords written down in an office setting is terrible for different reasons. &$RGJL__"LKHF#3fghu seems great until it's an a sticky or notepad file.
I just wish the managers would really manage. Instead of just being a sticky-note substitute, if they'd take passwords out of my way (by automatically providing them when needed, once I'm authenticated to the password manager).
[deleted]
It's not an easy win compared to just adding more length. Yes adding those characters to the set would increase the search space by 34%, but going from 2 characters to 3 (with the original set) would increase it by 6100%.
Easy is relative to the experience. If we're talking (26+26+10)^100 versus (26+26+10+10)^100, the difference is moot in terms of brute-forcing the password. However, the inability to double click select, to paste in to chat rooms, etc may change based on which characters are allowed. These properties may be desired (or not) for your organization.
I quite agree. However I have seen a great many registration forms that only accept a short password. If passwords are handled properly there's no reason to limit password length because a password will get converted to a fixed-length string due to hashing before storing it to a database. So I suspect many people prefer storing passwords in plaintext.
True, but I'm also pretty sure that there's no brute force password guess-o-matic that tries every possible UTF-16 character; they too will stick to the default keyboard-entered combinations because there's very few passwords outside of those.
A-Za-z0-9 != alphanumeric.
My alphabet last letter is "ż" not "z".
\w = alphanumeric
Some people don't even have latin letters on their keyboards by default. And "latin letters" aren't well defined anyway. For one thing technicaly "w" isn't a latin letter.
I'm of the opinion that all restrictions on character set in password are unnesessary and harmful. You shouldn't store plain passwords anyway. You shouldn't even pass the plain password from client to server. Why do you care what character set your customer uses?
IMHO the main reason to restrict passwords' character set is to annoy users by forcing them to make another variation of their favorite throwaway password for your criticaly important blog comment section.
My alphabet last letter is "ż" not "z".
\w = alphanumeric
Some people don't even have latin letters on their keyboards by default. And "latin letters" aren't well defined anyway. For one thing technicaly "w" isn't a latin letter.
I'm of the opinion that all restrictions on character set in password are unnesessary and harmful. You shouldn't store plain passwords anyway. You shouldn't even pass the plain password from client to server. Why do you care what character set your customer uses?
IMHO the main reason to restrict passwords' character set is to annoy users by forcing them to make another variation of their favorite throwaway password for your criticaly important blog comment section.
> For one thing technicaly "w" isn't a latin letter.
[deleted]
> We generate our password from a cryptographically secure random number generator. ... We found that sometimes (no predictable pattern), we have interoperability problems between systems.
If there was a predictable pattern, that would be even worse!
If there was a predictable pattern, that would be even worse!
well, no. a predictable pattern would be "every time the password starts with 0100101 they are not compatible". its not about the number having a pattern
It has happened to me that a registration form would not allow characters like '<' which any keyboard will most likely have, while it allowed unicode characters like (ಠ_ಠ)
Sounds like a clumsy attempt to guard against HTML injection.
It has occurred to me recently that 12 random words from a 2000 word dictionary will give you 132 bits on entropy. More that you will ever need.
There's a number of advantages to this scheme:
- It's easy to write down and put in a safe.
- No funny characters required.
- Not case-sensitive.
- If a user makes a spelling error, we can correct it for him without any compromise in security.
- Guaranteed to be free from offensive words, unlike a randomly generated password.
- People are using words anyways, misspelled if necessary, whether we like it or not.
We can also make it even more user-friendly by carefully degrading security, such as trying common word substitutions for the forgetful users, or doing some kind of middle-ground "remember me" that does not let you straight in, but only demands first three words (to keep the family members at bay). Like I said, this required careful calculations as to how much security is sacrificed when we do that.
There's a number of advantages to this scheme:
- It's easy to write down and put in a safe.
- No funny characters required.
- Not case-sensitive.
- If a user makes a spelling error, we can correct it for him without any compromise in security.
- Guaranteed to be free from offensive words, unlike a randomly generated password.
- People are using words anyways, misspelled if necessary, whether we like it or not.
We can also make it even more user-friendly by carefully degrading security, such as trying common word substitutions for the forgetful users, or doing some kind of middle-ground "remember me" that does not let you straight in, but only demands first three words (to keep the family members at bay). Like I said, this required careful calculations as to how much security is sacrificed when we do that.
This was made clear many moons ago by the now famous xkcd strip https://www.xkcd.com/936/
My innovation :) is to prevent users from selecting their own words, so that we can actually guarantee the entropy required. Otherwise a Markov chain will tear it to pieces.
You mean like Diceware[1], which has been around since at least 2000?
[1] http://world.std.com/~reinhold/diceware.html
[1] http://world.std.com/~reinhold/diceware.html
Good stuff. All we need now is to marry it with a password manager so that it generates random passwords based on this one passphrase and then autofills the web forms for you.
Also done frequently in the past, see:
http://world.std.com/~reinhold/diceware.html
Some intrepid child got internet famous recently for making some money by doing this for you.
http://world.std.com/~reinhold/diceware.html
Some intrepid child got internet famous recently for making some money by doing this for you.
Alas, many many many sites have inanely short password length limitations.
The article mentions that hex encoding solves most of the problems but isn't very space efficient. A good alternative may be base64k encoding, which was proposed here on hacker news[0].
This gives you safe strings as well as space-efficient encoding. As a bonus virtually all systems support unicode without any tweaking necessary.
I hope the author of base64k gets around to writing an RFC because it would be a great standard to use.
[0] https://www.npmjs.com/package/base65536
This gives you safe strings as well as space-efficient encoding. As a bonus virtually all systems support unicode without any tweaking necessary.
I hope the author of base64k gets around to writing an RFC because it would be a great standard to use.
[0] https://www.npmjs.com/package/base65536
All of these systems suffer from the differing password restrictions imposed by the various services you need to register for.
• Some services require both upper and loweracase characters.
• Some services require punctuation characters whilst others prohibit them.
• Some services prohibit repeated characters.
• Some services impose a minimum password length; some impose a maximum password length; some impose both.
Covering all these situations is nearly impossible.
• Some services require both upper and loweracase characters.
• Some services require punctuation characters whilst others prohibit them.
• Some services prohibit repeated characters.
• Some services impose a minimum password length; some impose a maximum password length; some impose both.
Covering all these situations is nearly impossible.
The first line of the article makes it clear this is for passwords used in programmatic use.
These restrictions exist for when humans are allowed to generate passwords. This article is discussing systems where humans don't generate passwords and don't in regular operation enter them.
Think of automatic password generation for a secure API endpoint, or automatic generation of private keys secured by a password that typically will be used in a system with it on the keychain but where the backup copies will be stored offsite.
In that case it's acceptable to have a password which is both secure but it has to be easy to type when required but doesn't have to be easy to type (i.e. short) for regular use.
The internet of things means that more and more devices will be creating "users" which are actually just other IoT devices. Those devices/device-users require these sorts of passwords.
These restrictions exist for when humans are allowed to generate passwords. This article is discussing systems where humans don't generate passwords and don't in regular operation enter them.
Think of automatic password generation for a secure API endpoint, or automatic generation of private keys secured by a password that typically will be used in a system with it on the keychain but where the backup copies will be stored offsite.
In that case it's acceptable to have a password which is both secure but it has to be easy to type when required but doesn't have to be easy to type (i.e. short) for regular use.
The internet of things means that more and more devices will be creating "users" which are actually just other IoT devices. Those devices/device-users require these sorts of passwords.
By just looking at the title and before reading the article, I though they meant that they are checking for illegal strings that are illegal to transmit. https://en.wikipedia.org/wiki/Illegal_number
Throw in the complexity requirements a Windows domain imposes on the password, and this turns into even more of a headache. Of course you can just append A1! to an otherwise sufficiently complex password to meet the requirements, but it will make people freak out in the code review.
Ascii85 is a great compromise between binary and base64, which works well for passwords.
Another solution is to treat every password as binary. Text works. UUIDs work. Everything works. But folks went down the text-password road a long time ago, so we're stuck with this for now.
Passwords-based systems assume input, and most UI frameworks use text strings for inputs.
Binary password is usually not called a password, it's a key.
Binary password is usually not called a password, it's a key.
Exactly, so if they are not meant to be input, as the article claims, why are they passwords and not keys? Why they are even checked to be valid unicode strings? I know of no encryption algorithm that cares about key being a valid unicode string. Looks like just laziness in distinguishing which data should be binary and which should be Unicode string.
I hope the developers of those sites that insist that passwords must be, let's say, between 6 and 18 characters are reading this.
This is like saying "Why isn't this random sequence of bytes a valid JPEG file?" If you want a random image, you generate the image randomly, then you encode it. Strings are no different — though the encoding is simpler.