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.

If part of the password is a whole regular English word, does the entropy of that part depend on the number of English words in existence, the number of English words known by the choosing algorithm, the number of English words assumed by the attacker?

Does the language matter, is the average entropy per word in German, French, Italian, or Spanish significantly different from the average entropy in English?

Does a numeric digit always have an entropy of log base 2 of 10 = 3.321928?

share|improve this question
1  
Obligatory XKCD: xkcd.com/936 –  Tangurena Aug 11 '11 at 22:43
    
You forgot to give a unit for entropy; information theoretically, you'll most likely want "bits" and adding it will correct your question "Does a numeric digit have an entropy of log_2(10) bits?" It does if, and only if, your numeric digit is drawn from a pool of 10 possible digits in a uniformly random manner, which is unusual---i.e. if the number refers to a countable quantity, the leading digit tends to follow a logarithmic, not a uniform distribution. –  pyramids Jul 14 at 8:32

3 Answers 3

up vote 28 down vote accepted

Entropy is a measure of what the password could have been so it does not really relate to the password itself, but to the selection process.

We define the entropy as the value S such the best guessing attack will require, on average, S/2 guesses. "Average" here is an important word. We assume that the "best attacker" knows all about what passwords are more probable to be chosen than others, and will do his guessing attack by beginning with the most probable passwords. The model is the following: we suppose that the password is generated with a program on a computer; the program is purely deterministic and uses a cryptographically strong PRNG as source of alea (e.g. /dev/urandom on a Linux system, or CryptGenRandom() on Windows). The attacker has a copy of the source code of the program; what the attacker does not have is a copy of the random bits that the PRNG actually produced.

Entropy is easy to compute if the random parts of the selection process are uniform (e.g. with dice or a computer with a good PRNG -- as opposed to a human being making a "random" chance in his head). For instance, if you have a list of 2000 words and choose one among them (uniformly), then the entropy is S = 2000. Entropy is often expressed in bits: an entropy of n bits is what you get out of a sequence of n bits which have been selected uniformly and independently of each other (e.g. by flipping a coin for each bit); it is a simple logarithmic scale: "n bits of entropy" means "entropy is S = 2n" (and the attack cost is then 2n-1 on average).

If you think of a password as two halves chosen independently of each other, then the total entropy is the product of the entropies of each half; when expressed with bits, this becomes a sum, because that's what logarithms do: they transform multiplications into sums. So if you take two words, randomly and independently (i.e. never ruling out any combination, even if the two words turn out to be the same), out of a list of 2000, then the total entropy is 2000*2000 = 4000000. Expressed in bits, each word implies an entropy of about 11 bits (because 211 is close to 2000), and the total entropy is close to 22 bits (and, indeed, 222 is close to 4000000).

This answers your question about digits: a decimal digit has entropy 10, as long as it is chosen randomly and uniformly and independently from all other random parts of the password. Since 10 = 23.321928... then each digit adds about 3.32 extra bits to the entropy.

If a human being is involved in the selection process then calculating the entropy becomes much more difficult. For instance, if a human chooses two digits and the first digit is '4', then the probability that the second digit is '2' is quite higher than 1/10. It could be argued that it is also difficult for the attacker: he will also have more work to do to sort the potential passwords so that he begins with the most probable. But this becomes a psychological problem, where the attacker tries to model the thinking process of the user, and we try to model the thinking process of the attacker: it will be hard to quantify things with any decent precision.

share|improve this answer
    
So you're saying position of a symbol has no effect on the amount of entropy the symbol contains? –  this.josh Aug 11 '11 at 21:26
3  
A symbol contains no entropy by itself: entropy is a property of the way the symbol was generated -- and that generation process produces an ordered sequence of symbols. Position is part of what is generated. –  Thomas Pornin Aug 11 '11 at 21:29
9  
Perhaps you could put it like this: entropy exists from the perspective of some party. To the user who knows their password, the password has zero entropy. But usually the party we're discussing the entropy is some hypothetical attacker. If you were to show him the password one symbol at a time, how much new information (in units of bits) would he learn as he sees each one arrive in turn? So the entropy is about the generation of the password insofar as we expect the attacker to know the method, but not the values, of that generation process. –  Marsh Ray Aug 11 '11 at 22:02

Information entropy is closely related to the "predictability" of the same information.

When we talk about password entropy we are usually concerned with how easy it is for a password cracking software to predict a password. The more passwords the software has to try before guessing the password the larger the entropy is.

You can check software like John the Ripper (http://www.openwall.com/john/). It's free and you can download for free a list of words from 20 different languages (to answer your question about different languages).

Using this entropy concept, its easy to see that a digit in the middle of a word probably has more entropy than a digit in the end of a word. John will try words + 1~2 digits combinations pretty early in the attempts, so something like crypto5 has less entropy than cryp5to and uses the same characters.

share|improve this answer
    
So position of a symbol impacts the entropy of the symbol based on the likelyness of an attacker to attempt that class of symbols in that position? –  this.josh Aug 11 '11 at 20:52
    
@this.josh If you expect the attacker to expect you to use some positions more than others, yes. Whether or not that's a good expectation is an interesting discussion. There is said to be a government agency using a password restriction of "if there is only one letter or special character, it should not be either the first or last character". I wrote a blog post a while back on this extendedsubset.com/?p=18 –  Marsh Ray Aug 11 '11 at 22:11

Basically, any password is a string of letters and entropy can be easily calculated. For example you can use Shannon entropy calculator or by hand using a scientific calculator.

Entropy is calculated based on frequencies of letters in the password, it does not care about used language. So diverse passwords with many different letters are preferred as entropy will be larger. Words are treated equally if they have the same proportions of used letters, e.g. English 'and' and Indonesian 'dan' has the same entropy). This means, contrary to what Paulo said earlier, that 'cryp5to' and 'crypto5' has the same entropy, entropy does not care about letter order. If you do not believe this, try it yourself by entering similar examples into http://www.shannonentropy.netmark.pl

Of course, if an attacker will assume that your password is a word, not a random string (most people do that) he will use a dictionary to break your password and he will break it earlier, but his knowledge that you use a word, not a random string is actually information which decreases entropy, so he used external information to lower the entropy needed to break it.

"Does the entropy of that part depend on the number of English words in existence, ..." NO, it depends on all the combinations which can be done based on password length and diversity.

"... the number of English words known by the choosing algorithm..." it may affect the algorithm, but not from an entropy point of view, e.g. if this algorithm will be: just try all words from dictionary in which there is no crypto5, but crypto is present, it fails, but if the algorithm is more clever, for instance take all words from dictionary and mutate them by random letter or number it will finally find crypto5.

" ... the number of English words assumed by the attacker?" it may affect the algorithm, but not from an entropy point of view, see above, and remember you do not know who and how will hack your password, so you cannot assume anything like I will use different language, because it has more words, but on the other hand you can use different language if it has more letters (and you will use them in the password).

"Does the language matter, is the average entropy per word in German, French, Italian, or Spanish significantly different from the average entropy in English?" You can calculate entropy for different languages (actually this is what Shannon did), but again it does not influence the entropy of the password.

"Does a numeric digit always have an entropy of log base 2 of 10 = 3.321928?" No, base 2 is the most common, and it has nothing to numeric digits, it can be used also to letters or any other signs, see Wikipedia [information theory entropy]

share|improve this answer
    
The context for the question is passwords in the face of attacks, as covered very well by Thomas' answer. As noted in Entropy (information theory), entropy is defined in the context of a probabilistic model. Clearly we should expect that an attacker is going to use a smart probabilistic model, so it is indeed the case that English words have less useful entropy in a password context than the same letters in a different order. We need to use more than the original "Shannon entropy", which has a different set of assumptions. –  nealmcb Dec 16 at 18:11

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.