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, 2020 at 17:14

2 Answers 2

4
$\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, 2020 at 17:58
  • 1
    $\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, 2020 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$

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.