Entropy test vs frequency analysis

Question

I'm currently doing the cryptopals challenges and for it's first set of problems it tells you to use frequency analysis of occurring letters to determine the likelihood of a key guess being correct and yielding legible english.

I was wondering, would calculating the entropy of the resulting plaintext not serve the same purpose, if not to a better degree seeing as it's not confined to the english language? Are there any benefits or drawbacks that one approach has over the other I'm missing?

Answer 1

I was wondering, would calculating the entropy of the resulting plaintext not serve the same purpose, if not to a better degree seeing as it's not confined to the english language?

First note that a cipher is susceptible to frequency analysis if it doesn't change the frequency at which characters occur. That is the "probability" of each substituted letter occuring is the same as the probability of the cleartext language. Now remember how the entropy is usually computed:

$$H(X)=-\sum_{x_i\in X} \Pr[X=x_i]\cdot \log_2(\Pr[X=x_i])$$

while replacing the probability terms for the measured approximation. Now as you can see entropy doesn't care where each probability value sits, if the same set of probabilities occurs you'll get the same entropy. And the set of probabilities is the same for each key for a given ciphertext susceptible to frequency analysis.

So "no", entropy will not help you here.

Answer 2

I think that letter frequency and entropy can give us some tips if the password source is biased. What advantage can these measures give us if the passwords are chosen with a good percentage of randomness? Therefore, people don't toss coins to choose passwords.

So, suppose a bad way of choosing passwords, like this: always starting with (03) three numbers... for example. This way, entropy will give us some tips: because it is a measure of uncertainty, in this case the entropy will be lower in comparison to the entropy of truly random chosen passwords. Therefore, I don't think entropy is helpful, but, in this particular case, does the frequency of the letters give us some help? I'm not sure, maybe.

You know, some sites demand things like that: passwords must have at least a number,... , at least a capital letter, etc.

Information Theory extends Shannon Entropy and gives us other tools. For example, Typical Sequences: under entropy, we can define what are the most probable set of sequences $x^n$, where $x$ is distributed according to $x\sim X$; $H(x)$ is the entropy of $X$; So the sequences $X^n$ wich satisfy:

$$2^{-n(H(X)+\epsilon)} \leq p(x_1, x_2,..., x_n) \leq 2^{-n(H(X)-\epsilon)}$$

are the typical sequence with respect to entropy $H$.

From AEP property, we have for big $n$'s:

• Typical sequences happen with probability almost 1;
• The typical set is small in comparison to the whole set (unless the source is random).

AEP is a cornerstone of compression algorithms. We can concentrate fire on the typical sequences. Can we use this for passwords guest?

Counter-intuitively, let's suppose the words under the alphabet $\{0,1\}$, with $p(1)=0.9$. The most probable word must be $[1,1,1,...,1]$, which is not a typical sequence.

Finally, what is the interpretation we can give to these things? I) If the passwords are chosen with a good piece of randomness, both Letter Counting and Information Theory don't provide us any help. II) If the passwords are chosen in a biased way, letter counting and IT can be useful, but it isn't true that they can give us a crystal ball.