1
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ Entropy is property of process not a data set. $\endgroup$ – kelalaka Apr 3 '20 at 17:14
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ But can't you determine what is plaintext and what's 'junk' from attempting decryption with the incorrect key through entropy though, in that english will have a low entropy compared to essentially random characters? $\endgroup$ – muke Apr 3 '20 at 17:58
  • $\begingroup$ @muke If you use a proper encryption scheme - probably. If you use one susceptible to frequency analysis it will probably work out less well, see above. $\endgroup$ – SEJPM Apr 3 '20 at 18:38
1
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

I think that you've answered your own question:-

But can't you determine what is plaintext and what's 'junk' from attempting decryption with the incorrect key through entropy though, in that english will have a low entropy compared to essentially random characters?

and thus inadvertently accepted the wrong answer.

What you're indeed missing is that your two techniques are virtually equivalent. You need to calculate a probability mass function of the candidate plain text to describe it's letter frequency distribution vis-à-vis single letters and multigraphs. You also need to perform exactly the same step to compute the candidate plain text's entropy. It's just a further combinatorial step using some logarithms.

So if your candidate key is wrong, H(plain text) ~ 8 bits/byte. And if it's correct, the H(plain text) < 3ish bits/byte. Much lower anyway. And yes, not confined to English.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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