0
$\begingroup$

How do I calculate the entropy of a password selected as described?

Choose 4 distinct words randomly from a list of 2000 words. Words can contain special-character substitutions. For example, the following substitutions may be used:

 Sub = {a; 0; i; e; /a; 8}
 Letter a -> @; Letter o -> 0; Letter i -> {1; !} Letter e -> 9;
 Letter a -> 6; Letter 8 -> &

Assume, uniform selection of alternatives:

ex: i is mapped to {i; 1; !} with the same probability.

Assume 90% of words have 1 of the letters in Sub, and 50% of them have 2 letters in Sub.

I know that since we're selecting 4 words from a list of 2000, then entropy in general must be 2000x2000x2000x2000, which expressed in bits would be around 44bits, since each word contributes about 11 bits (2^11 = 2000). Now I don't know how to attribute the fact that these words may contain special symbols. Please help. Thanks

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ There was a question about this kind of password on Information Security: Short complex password, or long dictionary passphrase? $\endgroup$
    – Ailton Andrade de Oliveira
    Oct 13, 2016 at 8:09
  • 1
    $\begingroup$ You can't tell without knowing the distribution of the number of possible replacements. If the number of substitutes for each letter in sub was fixed, one could easily compute the entropy using conditional entropy and the law of total expectation, but the information given is currently incomplete: For example, with words = {a, b} and sub = {a -> {1, 2, 3}} the entropy is $1+\log_23\approx 2.6$ bits, but with words = {a, b} and sub = {a -> {1, 2}} it is only $3/2=1.5$ bits. $\endgroup$
    – yyyyyyy
    Oct 13, 2016 at 12:37
  • $\begingroup$ Is the process that you that you first pick 4 words at random from the list of 2000 words and then do the substitutions (picking the substitutions uniformly at random as well)? If so this is equivalent to just computing the list of all possible words including those derived from substitutions and then picking 4 random words from that list. I.e., you just need to compute the size of that list in order to get your answer. $\endgroup$
    – Guut Boy
    Oct 13, 2016 at 20:44
  • 1
    $\begingroup$ @GuutBoy It's not equivalent: Not all choices from that list including substitutions are equally likely. Take my second example: The final list of words is {1, 2, b}, but b is twice as probable as 1 or 2. Thus, the distribution of the outcome is not uniformly random, and therefore computing the entropy is more complicated than just taking $\log_2$ of the cardinality. $\endgroup$
    – yyyyyyy
    Oct 14, 2016 at 0:09
  • $\begingroup$ @yyyyyyy my mistake, you are completely right. However, the method of simply picking words randomly from a list expanded with all possible substitutions should give a higher entropy then. So might be worth considering. $\endgroup$
    – Guut Boy
    Oct 14, 2016 at 2:16

1 Answer 1

Reset to default
1
$\begingroup$

If you have a rule such as "substitute 5 random letters with a fixed symbol" a direct calculation might be possible if you know average word length.

If you can't enumerate all the symbol substitutions into each word via a rule, it will be difficult to calculate directly.

A reasonable way estimate entropy when you can't calculate it is to use data compression. Write a script to output 1 million passwords generated using your method to a text file. Then compress with a high compression, slow algorithm such as LZMA on maximum settings. Perhaps use the 7-zip utility and try all of its available algorithms, picking the smallest result. The size of the resulting file in bits divided by the number of passwords in it should be pretty close to the entropy per password in bits.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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