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
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, withwords = {a, b}
andsub = {a -> {1, 2, 3}}
the entropy is $1+\log_23\approx 2.6$ bits, but withwords = {a, b}
andsub = {a -> {1, 2}}
it is only $3/2=1.5$ bits. $\endgroup${1, 2, b}
, butb
is twice as probable as1
or2
. 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$