An alternative to traditional passwords: is there some merit to this idea?

Question

If you've got a website aimed at people that are not necessarily technically proficient, letting new users choose their own password isn't very secure because of the simple fact that a lot of people don't choose secure passwords. Some methods of dealing with this problem are:

• Most common: have a 'password strength checker' or demand that the password contains a certain number and different kinds of characters. These often aren't very good and result in passwords that are not actually very secure and/or difficult to remember (of course this doesn't mean you can make a very good password checker, although that is pretty difficult).
• Generate a random sequence of characters: very impractical and insecure because people tend to write these down because they can't remember them.
• Two phase authentication through SMS or e-mail: not very convenient for the user.

I've thought of a different approach that is inspired by this XKCD comic. It works like this:

When a new user registers, they are presented with 20 randomly picked dictionary words. They are asked to make a secret sentence (let's call it a passphrase) that contains at least five of these words. They are encouraged to create a nonsensical sentence that is hard to guess but easy for them to remember. They have an option to refresh the 20 random words multiple times if they can't think of anything.

This passphrase will simply function as their passwords. You only have to check they use at least five of the provided words and take the usual security measures you would for regular passwords.

I personally think this is a pretty user-friendly way of letting people choose strong passwords; and the problems I mentioned for the other methods appear to be avoided. Of course I could be completely wrong and might be overseeing something important. So I'd really like to hear what the smart people here think about this system.

Answer 1

That sounds great to me.

The entire point of generating passwords is to pick one that is extremely hard for an attacker to guess, and easy for the authorized users to remember and type in. Ideally a password generating process should generate such extremely hard-to-guess passwords even if the attacker knows exactly which password generating process you used ( Kerckhoffs's principle ). If the "perfect knowledge" attacker finds it hard to guess the password, then other attackers will find it even harder.

I'm going to assume that you use a /dev/random that is not broken (it's connected to a hardware random number generator or a cryptographically secure pseudorandom number generator).

Many people seem to feel that a so-called "10-random-character password" formed from a randomly selected uppercase letter, randomly selected lowercase letters, followed by a randomly-chosen digit, a total of 10 characters long, is more than adequate for many purposes. That gives ln2( 26^9 * 10 ) = 45.6 bits of password strength.

If you completely randomly pick words from any list of 7776 words ( 6^5 words ), such as the the standard Diceware list or the easier-to-type-on-a-phone Dialdice list, and the attacker knows exactly what wordlist you use, and your user chooses the first 4 words you select, in the order you select them, the user gets ln2( (6^5)^4 ) = 51.7 bits of password strength.

increasing randomness?

If the user hits the refresh key a random number of times, and then rolls the dice to randomly selects 4 words from among the ones you present, and then rolls the dice to shuffle those words into a random order to generate the 4-word Diceware passphrase, then (again assuming /dev/random is not broken) I can a priori calculate that it has no effect -- the user still has 51.7 bits of password strength.

If the user thinks that's not enough password strength, then I think your system should allow the user to add additional letters, symbols, words, etc.

effects of non-random selection

Your user is unlikely to make a completely random selection, but that's OK. In the worst case -- your user puts things in alphabetical order or chooses some other order, and the attacker somehow knows exactly what order that is, you've lost -ln2( 4! ) = -4.6 bits of password strength from a 4-word Dialdice passphrase.

If we assume the user always rejects certain words, and keeps refreshing until he can make a passphrase without those words, and those words make up about 1/6 of the dictionary, and somehow the attacker knows which words those are, then for a 4-word Dialdice passphrase we've lost about -1 total bit of password strength. (The worst case is a loss of N bits of password strength for every 2^N times the user pushes the refresh button -- but that doesn't seem to be realistic to me).

The combination of these two effects results in your users having 46.1 bits of password strength with a 4-word Dialdice passphrase -- stronger than the 10-random-character password, and much easier to memorize.

If you later think that's not enough password strength, it's pretty straightforward to increase the minimum number of words in the passphrase, or switch to a wordlist with more words in it, or both. (You could use the approach in "Migrate old md5 passwords to bcrypt passwords" to force everyone with old, low-strength passwords to upgrade to new, higher-strength passwords).

That sounds great to me.

Answer 2

The idea of the xkcd comic is to generate a passphrase based on 4 words from a small dictionary of about 2000 to 3000 extremely common words.

If you let users pick words from a refreshable list, you significantly reduce entropy. The same is true for letting them change the order. Have a look at XKCD #936: Short complex password, or long dictionary passphrase?

Therefore you need to provide a much larger dictionary with less common words to compensate.

On the practical side: Users don't like typing in long passwords, especially on devices without a proper keyboard.

Answer 3

While I like the idea of assisting users with a strong password (especially inspired by the XKCD comic), I see a problem. Your dictionary. How big of a problem this is, depends on what your site is for obviously.

First of all your dictionary has to be huge, and needs to contain uncommon words. Still you should assume that whatever dictionary you have, someone else will too. I'm not a cryptographer, but you really need a lot of words because those five picks are all that makes the password. The other part of the problem is quite obvious; you have to secure it really well. If some evil genius gets hold of your exact dictionary cracking the hashes or trying to gain access to the account, will be a lot more easy.

That's where the importance of your site comes in. Since you provide the password for the user, it is unlikely (but not impossible) that the user will choose to use the same password somewhere else. So should someone obtain your DB, brute forcing the hashes won't provide them with something really useful.

Apart from that making sure that you block accounts after X failed login attempts (and making login attempts really slow) will help make sure that attackers have trouble gaining access to accounts using a stolen dictionary.

Just some thought on this interesting subject, I hope you find them useful.