Password Algorithms
penguindreams.org
penguindreams.org
This is one of the big problems with an algorithm. You'll eventually come across a site that -- for whatever reason -- doesn't allow that particular special character (or has a length restriction, or something else that makes your algorithm break). Now what do you do?
I use a password manager and generate 30-ish character long passwords, and I still occasionally run into sites that tell me it's too long. No big deal, I just generate one at the max length they support, save it, and move on. It literally makes no difference to me, other than I scoff at the ineptitude of the people that built the site and have to click a couple more times to get a new shorter password.
Do note that you don't need anything more than 22 random mixed-case letters & digits: 26 lower-case letters plus 26 upper-case letters plus ten digits is 62, and 62²² ≈ 2¹²⁸.
Completely agree re. the ineptitude of the developers of sites that try to limit one to less than that.
Here's a direct link: https://www.eff.org/files/2016/07/18/eff_large_wordlist.txt
It is awful for actual third-party passwords.
* Your password must be between 7 and 20 characters
* Your password must contain
* At least one number
* At least one upper-case letter
* At least one symbol from this list (!@#$%*)
* Your password must be changed every 30 days
- password must be between 7 and 8 characters long
- has to include one number
- has to include one of the following: $#!*, no other special characters are allowed
It was so horrendously bad it's not even funny.
The NHS online booking system my GP uses has rules like this. Pretty much guaranteed to prevent old people from being able to login.
How do you enter a fractional character?
A system I use not only has that requirement (along with a very insane set of requirements like "no patterns like 123 or ABC"), but they also NEVER let you reuse a password.
Which means they have a database of every password I've ever used on a machine somewhere, hashed or otherwise.
So the annoying workaround is to append year+month on the end of each password (which I was basically told to do when first setting up my account). So combined with a "maximum 10 characters" leaves 6 for my actual password...
Or do <password>, <password>1, <password>2, ...
(╯°□°）╯︵ ┻━┻
I don't know how people who don't use password managers are able to deal with this kind of crap at all.
┬─┬ノ(º_ºノ) calm down, take it easy.
I do use a password manager however, so I don’t really notice.
I don't think so... So are your old passwords stored in plain text somewhere so they can compare ?
Scary...
Yes, maybe: https://en.wikipedia.org/wiki/Locality-preserving_hashing
> So are your old passwords stored in plain text somewhere so they can compare?
You betcha!
Or did I misunderstand you?
But now that Im writing it out, I was clearly wrong anyways
I thinking something along the lines of taking every substring of 4 characters, and then for all permutations of those 4-tuples, plug it back into the string hash and store. Assuming the goal is to not share any 4-substring with the new string
So I think (N-4) + 1 gives you the number of 4-character windows
4! for the number of permutations of that 4-char window
So 4!*(n-3) total hashes
Which I guess is actually the same work you'd have to do anyways if you stored the plaintext; just without storing each variant
But I would guess they use plain text :-(
Previous Password:
New Password:
Confirm New Password:
Algorithms have their downside, sure, but for someone like me who is often working on other computers that aren't mine, managers are a non starter.
You can even use something like InputStick to auto-type the password into the other computer if you'd rather not do it manually.
I would recommend you to use any password, but rotate the credentials every time you enter them in one of these.
Copying over a really long generated password is much harder than an algo you can perform in your head.
For the couple passwords I have to enter on other devices (like Netflix) I often just create them by hand, and choose something easy to type on an on-screen keyboard, and then store it in my password manager. For example: "assdeeeerffghhhjuiop". If the keyboard is sorted alphabetically instead of QWERTY, I'll adapt to that.
I generally only have to type this in once or twice a year so it's not a huge deal.
It's free, fast and secure. Try ANPM:
Of course passwords would be case sensitive, why wouldn't they be?
Apparently everyone thinks I'm a fuckin' retard over that of a typo.
Great audience. 10/10, would post again.
I wrote this page to be a guide to friends and family, but I feel like I end up linking to the refutation of PA's more than anything else:
They "don't work" in theory, but in practice hardly anyone is individually targeted by attackers. 99.9% of compromised accounts are due to automated attacks churning through compromised databases looking for low hanging fruit. People who use algorithms are not low hanging fruit.
It's the forced rotation of passwords due to breaches that throw a wrench into the algorithm scheme. Even assuming no one ever actually figures out your leaked password because it was properly hashed and salted, if you as a good citizen are rotating your passwords with every breach, your Yahoo password should now be in its fourth iteration, while your other accounts may only be on your first or second. Trying to keep track of that, in practice, is unmaintainable.
So I agree, in principle, that the idea of letting your document be public is a good one. Then it could work like public-key cryptography. Even still, my concerns would be the following:
1. You are still guarding the "secret" of how you generate those passwords. That cannot be known, or your security breaks down. Is your algorithm sufficiently resilient to reverse-engineering that it won't be obvious to an attacker who sees a password that is compromised during a breach? If so, great! Personally, I can't see myself coming up with a one-way hash in my head that would not be trivial for someone else to figure out. I don't think the average person can, either.
2. You mentioned non-uniform password complexity requirements, which means that your algorithm (or algorithms) need to be able to accommodate that. I, again, feel like that would be very difficult to juggle. You're now remembering not just one algorithm, but several, and possibly several variants within.
3. Based on what you have to track just to know what algorithm to use, it sounds like your spreadsheet already has four or five columns: the site, the username, the password rules (which I assume is the "hint" that you use to tell you to use Algorithm A/B/C or Algorithm A var. 2, etc.), and the number of times compromised. At that point, I don't feel like the convenience of a "secret-free" document that doesn't need to be kept hidden outweighs the mental effort required to maintain the sheet and keep all processing within one's brain.
4. Your algorithm may be tweaked for the "max" the site will allow, but I imagine most people's are tweaked only to the minimum. What is nice about the password manager is that since I don't have to remember it, I can make the password arbitrary long. If the site allows your passwords to be up to 50 characters, I make it 50 characters. Always. I could never do that if I were forced to memorize it (unless it were a password phrase with some vowel-to-number/special char substitutions, but crackers have shown that rainbow tables already account for those).
You should be able to publish your password algorithm without people being able to compromise your accounts. Here's mine:
Pick 20-30 characters from the set of alphanumerics and special characters. Adjust length and character set to match site requirements.
With the given example, if your password is leaked plaintext on two sites, someone can reduce their brute force space from 100^30 to [A-Z][a-z][A-Z]B1a3k#[0-9]{1,2}.3 or 26^3*10^2 which is roughly 100^3
My problem of 4 years of algorithm use was that it would slowly change over time. I began to add mechanisms to predictably rotate the passwords. I began to add mechanisms that dealt with arcane dumb password requirements. Encountering a login from 3 years ago usually had me trying 3 different variants before getting it.
Furthermore, my algorithm still produces passwords that have considerably less entropy than a password generator will do for you.
The other advantage of password managers are for those damn security questions. I now routinely use 4-word diceware generated password as my security question answers and can store those in 1Password as well. The number of websites that let you bypass login with just a security question is mind blowing.
Everytime I go to an obscure website I rarely visit and I have to log in, I hope it's in my 1password account, and when it is I feel so releived I dont have to worry about what my damn password is for that one site.
Obscure password requirements are what drove me to 1password.
Just click "Forgot password"?
My bank recently reduced it's max password length from 20 characters to 15, so in an E-mail I was writing to the CEO demanding they fix it, I was recommending improvements and I realize that an 18 character password SHOULD be minimum, however...
If an 18 character password is minimum that actually reduces the length of brute force attacks. If the minimum length is 8 characters and the maximum something ridiculous like 64, then people with 32-64 characters will have the strongest passwords.
However, this relies on the assumption that lots of people will be using weak passwords, the brute forcers are going to target and exploit those people first. The number of possible permutations are increased by allowing weaker passwords, but that isn't enough. If everyone uses 18 char or greater passwords then brute forcers will start their searches at 18 characters so it would matter if 8 characters are allowed.
Just some food for thought, and reason to encourage the use of stronger passwords than the recommended 180 bits. If the system supports 64 characters, might as well use 64 characters. And if it doesn't support 64 characters, fix it.
This means that if you allow at least uppercase and lowercase letters in the password, setting a minimum decreases the search space by less than 2%, assuming the minimum equals the maximum.
If we even increase the maximum a tiny bit above the minimum, this decreases exponentially. Allowing a length of 8-20 instead of 18-20 only increases the search space by 0.0007%.
So you have to ask yourself whether that tiny fraction of a percent more security for you against brute force attackers (which a proper password of that length is already secure enough against) is really worth having your money in a bank with easy to hack accounts. As a customer, part of the cost of all those hacked accounts is going to find its way to you eventually.
Yahoo, Disqus, Experian, Tumblr, Adobe, LinkedIn, Dropbox, MySpace, Avast, DaniWeb, YouPorn, Trillian, Brazzers, Unreal Engine, PlayStation Network, Warframe, etc, etc, etc.
Here's a list of even more sites that have had passwords stolen: https://haveibeenpwned.com/PwnedWebsites
If you are being specifically targeted to that extent, a password manager may not be as helpful as you think .. and you probably have much bigger problems to worry about.
My startup is working on killing the password. What if we don't need passwords EVER? No need to argue about algorithm, strength, reset, lost, stolen, forgotten and expired passwords.
This is the problem I'm currently working on. Oh yeah, I did apply to YC and got rejected. Anyways, I'm in the early stages but plan to be shipping within the next 4 months. If anyone is interested in beta testing when I reach that stage please ping me.
Good luck with legacy systems. Bad passwords will be around forever because of ancient software.
Oh, and
1. They have to have multiple passwords to have a chance to derive the algorithm.
2. They also need to somehow think it's worth their time to reverse the algorithm instead of just going with lower-hanging fruit.
Even if it only applies to dedicated attackers, think about the consequence, once the attacker cracks your password, he knows your algorithm, all your passwords will be exposed.
And the point is the method is not more secure than using the same password for multiple sites.
I'm not ruling out that there will be attackers that try to harvest passwords from multiple sites, join those sites by username or email, then try some ML to derive people's password algorithms. But there is a whole class of attackers that just won't bother with that level of sophistication.
If your algorithm is any good, you're already not the slowest person running from the bear (cf. easy passwords or exact-password-reuse).
If password can be cracked, they are insecure, no matter it takes the hacker 10 minutes or 10 hours.
And it does not take ML to derive these simple algorithms at all. People may think their password algorithm is good, but it lacks the fundamentals of cryptography. It's really just a puzzle you play with the attacker.
4. Someone makes a John the Ripper/Hashcat plugin that searches password dumps for common usernames/email addresses and attempts to determine if the password is based on an algorithm.
5. With advances in NLP AI, this will just get easier in the future.
How is it going to do that? Especially since every website has different length and character requirements?
If. Depends a lot on how easy that attacker can identify those accounts as belonging to one set. Easy when they all go to the same email, but deep in the realm of individually targeted attacks if there is a layer of redirection. It's a tradeoff, password managers come at the cost of making their users part of a very high value dragnet target. I guess the proper way to do it would be to augment managed passwords with a brain-based component. That, and stuffing the password manager with a few canary accounts on high-value sites that send out login notifications.
The point of password managers are to have true different password for different site and users don't need to remember it. For the inconvenience the author has, there are other secure ways to handle that, no need to sacrifice security for convenience. For example, to have a usb drive with portable password manager installed.
If this simple modification which I have to do one time costs me a minute, how many years of my life will it take to go through some algorithm, and this every single time I log in?
Besides any security considerations, its just too much of a hassle for me to use some password algorithm technique.
It's free and you won't loose a minute again :-)
Unless the sites password policy won’t accept it..
For that reason, I think that a secure password manager (e.g. password-store, KeePass or Password Safe, not something like LastPass) is generally preferable.
Why? Friends have found LastPass to be pretty reliable and user friendly so far.
Also, they're proprietary software. Password security is too important to entrust to proprietary software.
Is LastPass going to protect you against sophisticated State, or even potentially Corporate attackers? Maybe not. Will it protect you against random hacks and insecure sites better than just reusing the same password that you can remember? Yes.
I generally agree though that this is an area where open source software is preferable. I'm also really intrigued by the work Keybase is doing and hope that it might spur some interesting solutions for web auth as well.
but using keepass does protect you in the case that lastpass' servers get compromised into serving malicious javascript.
If you like terminal commands, here's one way:
LC_ALL=C < /dev/urandom tr -dc "abcdefghijklmnop" | head -c32 && echo
(Choose the character set and length as you like. We like to use 32 characters picked from 16 lowercase letters. This is because it's a good balance of bit strength, fast typing for mobile devices, and full mappability to hexdecimal when we need it e.g. to prove exactly 2^128 bit strength or for compliance with HIPAA, FERPA, etc.)
Okay.
I believe my algorithm is strong enough that it puts me completely out of reach against automated attacks. If one password is compromised to plaintext, will an attacker even recognize it was generated by an algorithm? Unlikely. If two of my passwords are compromised to plaintext somehow will a determined attacker specifically targeting me be able to recognize and determine my algorithm? Possibly yes. But in my mind, the risk of being individually targetted and having two different passwords compromised to plaintext is not high enough to outweigh the convenience factor of password algorithms.
For all those 90% of places where the data protected by the password isn't valuable, I just use a crap password. Usually the same password everywhere suffix with with something from the domain or whatever.
All those forums I needed to register just to use the search, or the mandatory registration to download a software trial.
Same with all those passwords that I need to enter on a TV remote or console controller: I just use a crap (short lowercase) pass and hope for the best. I don't consider the account worth protecting so long as I can reset the password with my (well protected) email account.
I must have 100+ accounts registered but maybe 4 that I really would worth about being stolen.
But if the goal was for it to be universal enough to work anywhere without the password manager installed then these crypto primitives would work.
You'd still be relying on the strength of those primitives and your secret key so it's not nearly as secure as randomly generated password.
So, yeah, use a password manager.
Having a spreadsheet matching sites and algorithms may be another weak spot depending on how it is stored. Password managers usually keeps metadata about sites, not just the password, and it is stored encrypted.