Wouldn't it be smarter to measure password entropy and reject low entropy passwords?
This would allow short passwords using the whole character set to pass, aswell as long passwords only using parts of the character set.
Is the above scheme possible or do implementation details prevent something like this to be done?
Does any site or programm already incorporate such password requirements?
After the famous XKCD strip, there were a few projects started up to deal with exactly this kind of entropy checking. One of these was the ZXCVBN password checker, made by a Dropbox employee.
It is possibly the most thorough password checker of its kind. It checks for patterns, words, and more, adding to (or subtracting from) an entropy score accordingly. It is explained in detail on their blog.
This is a great idea, in fact it is the only proper way of measuring password strength.
But how would you measure password entropy?
Entropy is an aspect of the generation process, not of the output.
For example, what would be the output of such a measurement for Tr0ub4dor&3? By any reasonable measure of possible entropy based on a given password, that would be rather decent - over 70 bits of entropy. Or maybe, taking into account a supposed password generation process, I might be smart enough to realize it is actually capped to only 28 bits, since each character is not selected randomly, but first a whole word is selected. But in reality I should junk this whole idea altogether, since I obviously just copied it directly from that comic.
Same issue would apply if the password was correct horse battery staple (one of the most popular passwords amongst a certain population).
So yeah, password requirements should be based on the password entropy, but you cannot apply this requirement to a given password after the fact.
(Btw, as I mentioned in another answer on this topic (from a different direction), it could be a good idea to implement a system where passwords / passphrases are auto-generated for a given level of entropy, and provided to the user, instead of asking the users to come up with one that meets our requirements. Of course, this is what a good password manager would do on the client, anyway...)
Static password policies are chosen for two major reasons: usability and the body of research demonstrating acceptable effectiveness. Most of my answer comes from the excellent research paper on an advanced password-strength meter, Telepathwords.
First, to summarize some of the research used to back up current password policies:
Password-composition rules date back at least to 1979, when Morris and Thompson reported on the predictability of the passwords used by users on their Unix systems; they proposed that passwords longer than four characters, or purely alphabetic passwords longer than five characters, will be “very safe indeed” [19] [However] Bonneau analyzed nearly 70 million passwords in 2012, 33 years later, to measure the impact of a six-character minimum requirement compared with no requirement [2]. He found that it made almost no difference in security...
This includes the work of Komanduri et al. [13] and Kelley et al. [12], who used similar study designs to perform comparative analyses of password composition rules. These prior studies found that increasing length requirements in passwords generally led to more usable passwords that were also less likely to be identified as weak by their guessing algorithm [13 12]. Most recently, Shay et al. studied password-composition policies requiring longer passwords, finding the best performance came from mixing a 12-character minimum with a requirement of three character sets [25].
Usability is a huge reason why more complex criteria like password entropy aren't used more frequently:
In a study of the distribution of password policies, Florencio and Herley found that usability imperatives appeared to play at least as large a role as security among the 75 websites examined [8]. ...
Ur et al. also studied the effect of password strength meters on password-creation. They found that when users became frustrated and lost confidence in the meter, more weak passwords appeared. [28] ...
While [Dropbox's] zxcvbn provides a much-needed improvement in the credibility of its strength estimates when compared to approaches relying solely on composition rules, this credibility is unlikely to be observed by users. In fact, its perceived credibility may suffer if users, who have been told that adding characters increases password strength, see scores decrease when certain characters are added. For example, when typing iatemylunch, the strength estimate decreases from the second-best score (3) to the worst score (1) when the final character is added. Even if users find zxcvbn’s strength estimates credible, they are unlikely to understand the underlying entropy-estimation mechanism and thus be unsure how to improve their scores. [30]
Finally, for sake of completeness, we have to realize that defining entropy in this example is very difficult (but far from impossible). There are lots of different assumptions we can make about the sophistication of a password cracker's guessing algorithm or dictionary, and these all lead to differing answers on the entropy of passwords like "Tr0ub4dor&3" or "correct horse battery staple". The most sophisticated password entropy measures are based off dictionaries of millions of passwords and advanced study of password patterns, and this level of sophistication is difficult to achieve for many administrators (and hackers).
Entropy is calculated based on how you create a password. In order to calculate entropy, you don't need to know the password, instead you need to know how it was created. Having the password doesn't help you in calculating entropy, it only allows you to make a very poor estimate on entropy.
Example:
If our password "Password123" was chosen from a list of the 3 most used passwords that contain letters, numbers, upper and lowercase, and are longer than 10 characters, the entropy of Password123 is ridiculously low.
If the same password "Password123" was chosen by a perfect random generator that creates 11 digit passwords with each digit chosen from 5000 possible unicode code points, the entropy of Password123 is ridiculously high.
In other words: You're on to something, but "entropy" is the wrong word - "entropy" already has a different meaning. What you're looking for is "strength" of a password. And strength of a password is hard to measure right, and even harder to communicate. The fact that strength changes whenever the attack methods change doesn't help either.
You cannot measure password entropy, you can only measure an upper bound for it. So any password strength estimator is flawed.
Using a password estimator or annoying rules have the same effect of making the user to try to meet the requirements while keeping the password as easy as possible for them to remember. So, the harder the requirement, the harder they will try to build an easy to remember password. For example by using passwords like Pa$$word1 or passwordpasswordpassword. The problem is that an easy to remember password is also an easy to guess password.
When the service you provide is optional, you also have the risk to alienate users with too strong requirements and loosing customers.
However, you can enforce a lower bound of 10 characters, because all passwords less than 10 characters are weak and the requirement is not too difficult to meet. You can also give them advises to build strong passwords.
For your last question "Does any site or program already incorporate such password requirements?", I guess you can find such sites. However, I would not recommend following their practice. It's not because someone else does it that it's a good idea to do the same.
How do you measure password "entropy"?
It's impossible.
A password like "hresda" may have 'low entropy' because it was chosen from lower case letters, but if it was randomly generated from a set of characters containing upper/lower case letters, digits and symbols and the result just happened to only contain lower case letters, then it has higher entropy. A password like "A63ba!" may have lower entropy than "hresda" if it was generated specifically as [upper case][digit][digit][lower case][lower case][symbol] rather than just randomly chosen.
Yes, there are programs that measure the entropy of a password to decide if it is good enough or not. Once such program is Wabol Talk. The feature is implemented using the estimate_quality method in the program's main module. Ultimately, the method is used in the method just above it (error) to validate password fields that are used to generate keys and initialization vectors. The estimation is only of minimal quality since it does not judge passwords based on their frequency of use, but it demonstrates one of the simplest ways to find how many bits of entropy are present in a password.
A note about the international environment. If the password is created for a website open to the whole world (not uncommon), chances are the user does not speak english as a native language, and may instead choose, say, swedish words as a basis for the xkcd password creation method.
"paraplyost" (umbrella cheese) would probably rank lower in an entropy checker that knew about the swedish dictionary than one that didn't. If an attacker knows that the user is swedish (not the most common scenario, but it may happen), he might be able to hack a user's password easier than the entropy checker was aware, unless the entropy checker is loaded with hundreds (or thousands?) of dictionaries.
One nice side effect of this is that if you speak a language that isn't one of the most common in the world, you can make even safer passwords as an anonymous user on an international web site. :)
Does any site or program already incorporate such password requirements?
Several websites do that. For example, go to https://www.dropbox.com/login and try to register with a password which is a common dictionary word of 8 characters or more (e.g. dictionary). You'll see the strength meter is showing you the lowest score. Now try to shuffle the letters randomly (e.g. ioictnadry) and use that - you'll see the strength meter going up.
The obvious downside to this method is that you need to upload a dictionary of common passwords to every client using the login form. This recently became OK but was totally unacceptable 5 or 10 years back.
My impression is that most cracks use existing word & password lists. And a few variations on those, like adding numbers or repeating a word. Exception noted below.
So a password is also weak if it appears on a list, however strong the entropy calculations (of the generation process) might show. On 'a list' meaning: if the cracker's list does not contain your password, it's strong, despite of the entropy calculation. So it's almost impossible to check the (unknown) list beforehand. Trying though, some 65 million words, does not harm, see Stanford's SUNet ID Passwords. 65M is a lot but this list contains almost 2.5 billion passwords:MySQL Passwords
A high entropy PW generation process and a tool checking that entropy, should both be complemented with a rejection step that uses lists and patterns. Even those high entropy processes can generate easy to guess passwords , such as aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (see below), and password1 .
I have asked the cracker of Ashley Madison's hashes how they could crack long passphrases they published. Just a generic answer, but after analyzing a the published ones, I found that most of those long phrases are common expressions or hash tags, see source of some cracked AM phrases
The only exception to lists as sources, is passwords that have a pattern like: capital, then lowercase followed by a number. Common patterns, with hit %, are available on the Internet. Those could indeed easily be checked beforehand.
-- edit adjusted 2.5 billion; 'aaaaaaa' part added; rephrased rejection
One word: Policy
For the past decade or so, the main drift in information security is towards compliance, control and policies. Essentially, what we do today is we build up an ISMS (Information Security Management System) based on C-Level commitment and corporate policies.
And when you get to writing the password policy, you are not at the technical level. You are writing a document that employees need to read, understand und possibly sign. You are writing a document that management has to accept and support. You cannot get too deep into mathematics, or you will not get acceptance.
Finally, when you think about how to actually implement the password policy, in almost all organisations you aren't free to invent your own rules. You will have something like Active Directory running and your implementation has to work with it, or the IDM system, or the legacy stack or whatever.
So, with tears in our eyes, we write password policies we know to be half stupid, because it's the best that we can actually get done.
