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_2(10) = 3.321928$?

  • 12
    Obligatory XKCD: xkcd.com/936 – Tangurena Aug 11 '11 at 22:43
  • 1
    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 '14 at 8:32
  • i think of "entropy" as "total number of bruteforce combinations". and clearly this depends on the assumptions of the attacker. the entropy of your password changes according to the assumptions makes about your chosen format. – mulllhausen Mar 21 '15 at 13:11
up vote 81 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 = 2^n$" (and the attack cost is then $2^{n-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\cdot2000 = 4000000$. Expressed in bits, each word implies an entropy of about 11 bits (because $2^{11}$ is close to 2000), and the total entropy is close to 22 bits (and, indeed, $2^{22}$ 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 = 2^{3.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 $\frac1{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.

  • 1
    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
  • 8
    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
  • 20
    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
  • Entropy is defined for random variable. It would be great to re-state the above write-up in terms of random variable. – user1700890 Sep 20 '15 at 20:22
  • @ThomasPornin As a follow up, if an attacker KNEW that the password was an all lowercase English word, then could you say that the entropy is actually much less? Could we even calculate entropy in that case, where we are roughly looking at 1 in 1 Million words rather than individual characters? – Chiramisu Sep 11 '17 at 16:56

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.

  • 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_2(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]

  • 6
    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 '14 at 18:11

If the English word is a mnemonic and represents some underlying index value or other code value such as ASCII or UTF-8, then I don't think there is a difference so long as it was chosen randomly, as its entropy will depend entirely on the range of words or letters that it was chosen from. There is a difference though between choosing a word, versus randomly chosen letters that "happen" to equal a word when read from left to right etc..

Here is a simple explanation regarding password entropy, and depending on what needs to be measured. Let's first assume two following two points:

  1. The password has a specific "length" (consisting of its number of characters, some of - or all of which - may be duplicate/identical and/or repeat consecutively).
  2. Any character in the password has been chosen from a single common library or "range" of unique characters and chosen randomly using a cryptographically secure process.

Formula:

  • Log2(Possible combinations)= overall password entropy

  • Range^Length=Possible combinations (can also be rounded as 2^overall password entropy)

  • Log2(Range) = Entropy per character
  • Entropy per character * Length = overall password entropy

Example Test:

  • Range = 2048 unique character values (or 2048 unique words)
  • Length =12 characters (or 12 words, some or all of which may repeat)
  • Possibilities = 5444517870735015415413993718908291383296 or 2048^12
  • Overall Entropy = 132 or log2(possibilities)
  • Entropy per character (or per word if words are used) = 11 or log2(2048)

Blockquote

Another way to double check roughly (depending on precision available if dealing with decimals and not whole number results): 2^(log2(Range)*Length) == (2^Entropy)

Blockquote

in Python3: 2**(int(math.log2(2048))*12) == int(2**132)


P.S. I think frequency analysis is useful here in two situations, one) the password was chosen deterministically without a crypto-secure process, and/or two) the characters in the library are either not distinctly unique (i.e. one or more duplicates exist, or many characters share strong similarities) or other unknown leakages of information in the library set.

  • Nice math but misses the point for passwords which as not random sequences. Consider frequent passwords lists. ordered by usage frequency. If the password is toward the front of the list is is not secure al all. Passwords are cracked using such lists in most instances. – zaph Sep 24 at 16:12
  • I was addressing the question and more important point, which is - now more than ever it's critical to start using random passwords, and knowing the entropy for a given password will entirely depend on its length and the range of characters available in the library used. Even if you choose a password yourself, there are ways to make it more secure by first being aware of how entropy is calculated. – Steven Hatzakis Sep 24 at 16:17
  • See NIST Digital Identity Guidelines. Also passwords created by humans are rarely random. – zaph Sep 24 at 16:19
  • I was just looking at the link a few days ago! I agree humans cannot choose randomly to the degree a cryptographically-secure process can (even hitting the keyboard randomly is not entirely random when repeated). But there are still steps one can take, such as in the NIST guidelines, along with two-factor authentication and mixing salts and sourcing entropy from various methods so that if one is corrupt the password is still secured by the other entropy inputs (among many other proven and new methods). – Steven Hatzakis Sep 24 at 16:29

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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