Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I don't yet perfectly understand the difference between brute-force and dictionary attack since this differentiates one attacking the key and another attacking password: apparently attacking passwords can take longer, right?

But it's not necessarily true depending how unaware users can be, and that's where dictionaries shine.

So as the recent XKCD demonstrated, pass phrases are much more secure not because of their bit entropy, but because of their bit length, and even if a pass phrase is done with common words which also are in a dictionary, a dictionary attack of a pass phrase is still "infeasible" if it is at least 3 or 4 words, which makes it still very easy to memorize.

So would it be a good design choice to force users to choose at least 3 words in the dictionary to have a long enough password, for example with some auto-complete feature? What do you think?

PS: I'm asking this not in the context of expensive information requiring design efforts, I'm more thinking into good privacy for public use, considering the attacker has access to the cipher-text (which is not necessarily true on the web).

share|improve this question
    
Is your question about the difference between brute-force and dictionary attacks, or between passwords and passphrases? Or mainly about your password choice idea? –  Paŭlo Ebermann Aug 22 '11 at 1:18
    
Except that XKCD is showing a four word pass phrase at 44 bits of entropy by choosing 4 words from a 2^11 entry dictionary. He's not saying it's more secure because of the plain string length. –  Marsh Ray Aug 22 '11 at 21:35
    
what 2^11 dictionary ? the english dictionary ? what are you talking about ? –  jokoon Aug 22 '11 at 21:49
    
From 44 bits of entropy for 4 words assumed chosen at random in a dictionary, which is in the XKCD reference, we can infer the dictionary has 2^11 words. –  fgrieu Aug 22 '11 at 22:01
1  
The Second Edition of the 20-volume Oxford English Dictionary reportedly contains full entries for 171,476 words in current use, and 47,156 obsolete words. This is two decimal order of magnitudes above 2^11. In the XKCD cartoon, each little grey squares represents one bit of entropy. –  fgrieu Aug 23 '11 at 8:37
show 1 more comment

3 Answers

up vote 2 down vote accepted

"Brute force" is a loosely-defined traditional expression to designate a kind of attack of low mathematical cleverness, namely trying all possible values for some unknown. For instance, in the context of symmetric encryption with AES, using a 128-bit key, "bruteforcing" would be trying all possible sequences of 128 bits as possible keys, until one matches (and there are so many such sequences that the average attack cost will be astronomical, hence totally impractical).

A dictionary is a set of "possible passwords", and a dictionary attack is about trying all possible passwords from a dictionary. Thus, a dictionary attack can be called "brute force". However, the expression "brute force" somehow suggests unsubtlety, and there can be quite some psychological finesse in the definition of a dictionary. As I said, "brute force" does not have a well-established mathematically meaning.

In "to force users to choose at least 3 words in the dictionary", the worst word is "force". Enforcing password rules on users tend to be counterproductive. Users should cooperate, and if you antagonize them, then they will actively seek countermeasures with great creativity. You really do not want the users to resent the password as a burden. Remember that almost none of your users will have a mathematically correct notion of password entropy; most will not care, and most of those who care will think about passwords in the same way as passwords are used in movies: witty allusions to some events or objects, supposed to defeat attackers through some "cleverness".

The second worst word in your proposal is "choose". To defeat a dictionary attack, the dictionary (as "the set of potential passwords") should be huge. The set of potential passwords is what users will effectively choose, not the length of the list you gave them. If you give them a list of 1000 words and tell them to "choose" one of them at random, many will pick a word in the first 10. Human beings are simply not good at doing things with uniform randomness. The password selection process should involve a physical device (e.g. dice, or a coin) and -- that's the important point -- the user MUST stick with the randomly selected words. If users are free to choose as they see fit, most will see fit to select words with a meaning (e.g. a sequence of words which "says something") because that's what they will remember best.

share|improve this answer
    
If we shuffle the huge list before presenting it to the user, choosing one of the first 10 is still quite random :-) –  Paŭlo Ebermann Aug 23 '11 at 16:38
    
Like I said in other comments, I'm not thinking about a 1000-words list, but I'm rather suggesting the user to choose common words, because I'll ask him to use a password with at least 24 characters (minimum 16 characters if words used are short). You can't explain encryption to users, but the encryption is defeated if one can easily find the password of 80% of users. It is commonly known that most passwords in the world have 6+ characters. What XKCD shows is that we should tell users to use pass phrases, not pass words, and tell them we can't secure their data if they don't listen. –  jokoon Aug 23 '11 at 18:14
    
But of course this doesn't apply to website's passwords, since you can prevent dictionary attacks. I just ask this question because I think one day OSes will be clustered across users machines, and we will need to encrypt data, and thus password choice could matter. –  jokoon Aug 23 '11 at 18:17
    
"dictionary attack" also has a quite different alternate meaning, in the context of ciphers: an attack that builds a translation dictionary between known plaintext and ciphertext, then exploit repetition in ciphertext. This is the case in SSL documentation –  fgrieu Aug 23 '11 at 18:18
add comment

A dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its passphrase by searching likely possibilities. It uses a targeted technique of successively trying all the words in an exhaustive list called a dictionary (from a pre-arranged list of values).

In contrast with a brute force attack, where a large proportion key space is searched systematically, a dictionary attack tries only those possibilities which are most likely to succeed, and are typically derived from a list of words for example a dictionary (hence the phrase dictionary attack) or a bible etc.

Generally, dictionary attacks succeed because many people have a tendency to choose passwords which are short (7 characters or fewer), single words found in dictionaries or simple, easily-predicted variations on words, such as appending a digit.

A brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system (if any exist) that would make the task easier. It involves systematically checking all possible keys until the correct key is found. In the worst case, this would involve traversing the entire search space.

As for answering your question about whether or not it is a good decision to force the user to select three words from a dictionary, I believe the answer to be no, only because there are many password checkers / managers that prevent the user from entering more than 8 characters, say. I know it sucks but that is a reality. What would be better would be to get the user to select a combination of letters, numbers and punctuation marks (if possible), not in consecutive order though. Again, there are some password checkers / managers that prevent punctuation marks from being entered. If possible, you could also force them to use a combination of upper and lower case characters in the password.

share|improve this answer
    
Can't enter more than 8 characters, what ? And i want to implement this password rule into my system, it's not for other websites. –  jokoon Aug 22 '11 at 23:30
    
Not saying that you can't allow the user to enter more than 8 characters. I'm just saying that there are some password checkers / managers that don't allow the user to enter more than a certain number of characters. I just used 8 as an example. –  user476 Aug 23 '11 at 0:44
    
P.S. Note that my reason for mentioning the limits that some password checkers / managers place on the user is more for consistency than anything else. Furthermore, trying to remember one word is bad enough. Trying to remember three is prone to errors in the sense that the user will more than likely need to enter the password two to three times before he/she gets it right. I know because I have been there, done that.... –  user476 Aug 23 '11 at 2:13
add comment

In the context of block ciphers like DES, or historical ciphers, the usual terminology is that a brute force attack enumerates all the keys to find one matching all intercepted data; in this context, dictionary attack is sometime used to describe an attack where a number of correspondences between known plaintext and ciphertext are accumulated, forming a growing translation dictionary, which can be reused later without attempting to guess the key, should the same ciphertext reappear.

In the context of human-memorable password, the terminology is less well established. An attack attempting to enumerate all acceptable passwords in lexicographic order would be a brute force attack, but other attacks could qualify, such as one trying all passwords in a dictionary of common passwords, which is also the simplest example of dictionary attack in this context, where the term is used for about any attack that use a list of common words or passwords. With some poor schemes, a pre-computation can be performed on the dictionary of common passwords, the result is called a rainbow table.

In that context of human-memorable password, mechanically "forcing users to take at least 3 words in a dictionary of words" would be very bad, if the dictionary is static: it prevents users to make variations, which increase entropy dramatically; many if not most users would use short words, reducing entropy; and would stick to common words after having one rejected because it is not in the dictionary, further reducing entropy. Also, XKCD#936 misses at least the points that short passwords are faster to type, and contain less typos!

On the other hand, suggesting to the user the use of like 4 words as a basis to form a memorable pass phrase, and using that term rather than password, looks like a reasonable idea.

share|improve this answer
    
Actually, the "building pairs of plain/ciphertext" is known as "rainbow table", not dictionary attack. (It is based on a dictionary, too.) –  Paŭlo Ebermann Aug 22 '11 at 9:15
    
When I say 3 words, I mean 3 english words, not 3 words from a small list I give. That would be stupid. –  jokoon Aug 22 '11 at 11:05
    
@gokoon English is, effectively, a small list of words. –  Marsh Ray Aug 22 '11 at 15:18
    
@gokoon: Actually I would prefer German (or Esperanto) words, since I can easier memorize them. Restricting the users to certain words just keeps down the entropy. –  Paŭlo Ebermann Aug 22 '11 at 22:45
    
@Paŭlo Ebermann: I added text on "rainbow table". I maintain "dictionary attack" has the meaning I give in the context of ciphers. There's an example of that use of the term in SSL documentation –  fgrieu Aug 23 '11 at 18:22
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.