Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

If you've got a website aimed at people that are not neccessarily 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 strenght 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.

share|improve this question
    
A number of years ago I wrote a password generator that basically works on the concept of generating nonsensical but somewhat meaningful phrases mixed with other randomness and word alterations to prevent the limits imposed by a fixed wordlist: xato.net/windows-security/pafwert-smarter-passwords. It sounds similar in concept to what you are talking about. –  Mark Burnett Jun 9 '12 at 22:59
    
@AardvarkSoup - So you want want to replace non-dictionary passwords with dictionary passphrases. It would be a simple matter of trying every single 5 dictionary combination would not exactly take that long. –  Ramhound Jun 15 '12 at 10:58
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
+1 Good analysis. Its worth noting that ~46 bits of entropy with a simple hash (e.g., sha256) is still in the range brute forceable by a GPU in a day with an electricity cost of ~$0.50. So you still should use a per-user salt, and a little bit of key strengthening depending on the maximum value of the cracked resource (e.g., 100 rounds makes it cost $50 in electricity; a million rounds would cost $500 000) –  dr jimbob Jun 14 '12 at 21:31
    
@drjimbob: Yes, per-user salt and key stretching is the right thing to do, for exactly the reasons you mention. –  David Cary Jun 17 '12 at 6:22
add comment

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.

share|improve this answer
    
You have a good point regarding the refreshing list and reordering; it does reduce entropy. I didn't think of it that way but giving the users more choices is actually a bad thing because they will have common preferences regarding word choice. But, looking at the sheer size of the Oxford dictionary I doubt that dictionary size or common words will be the problem. :) –  sharpcloud Jun 8 '12 at 22:07
    
It's not a given that letting users pick words from a refreshable list reduces entropy. If the words are chosen by a predictable process, refreshing and reordering might be the only entropy in the system. System generated passwords have routinely been cracked by cracking the generator. –  Major Major Jun 9 '12 at 0:03
1  
@MajorMajor, well, we assume a working random number generator. This is not about a poorly designed algorithm for password generation, but about a specified one: Pick four words in order from a list of 2000-3000 common words. For this algorithm, those actions obviously reduce entropy. –  Hendrik Brummermann Jun 9 '12 at 7:39
    
@Hendrik, how does letting the user change the order of the words and expand the presented list of words form 20 to 40 or 60 reduce entropy? –  Major Major Jun 9 '12 at 15:39
    
@Hendrik, BTW assuming a working random number generator has been the downfall of many security schemes, especially password and key generaton schemes. See developer.com/tech/article.php/616221/… and suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers and en.wikipedia.org/wiki/… –  Major Major Jun 9 '12 at 16:27
show 4 more comments

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.

share|improve this answer
    
Thanks, those are some good points. However, I don't think the dictionary is such a problem: the Oxford dictionary contains about 170000 words, which would translate to a word list of about 1MB (you can reduce its size by e.g. using a smaller dictionary of more common words and not including short words). That's not very difficult to do lookups in at the server-side. If someone where to use only five words (without anything added to make it into a valid sentence) you'd still have a massive amount of possible combinations. –  AardvarkSoup Jun 8 '12 at 21:55
1  
Additionally, the possibility of two people choosing the same sentence shouldn't be any problem if you salt the hashes with a unique random string for each user, so that each user has a unique hash. This is already good practice for regular passwords, so I didn't mention it. –  AardvarkSoup Jun 8 '12 at 21:58
    
That is true I guess. English is not my primary language, I forgot how vast the set of English words actually is. I would opt to use words no shorter than four characters (three bare minimum). The total character count is important. Make sure it exceeds 12 at the most minimum case possible. Preferably higher. –  sharpcloud Jun 8 '12 at 22:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.