We discuss a lot of topics and use measures of entropy to determine how difficult it is for an attacker to be successful. What does entropy mean in the context of cryptography? How is entropy calculated in the general case?
$\begingroup$
$\endgroup$
3
-
5$\begingroup$ I think of entropy like this: Say the attacker wants to know your password and you are willing to tell her the password by answering her questions... What is the minimum number of questions with yes/no answer the attacker needs to ask in order to find the password? $\endgroup$– Panos KalatzantonakisJun 29, 2016 at 16:01
-
$\begingroup$ @PanosKal.That looks like a poor definition to me. For 128 bit key it would take me 128 questions to find the key (whereas the real entropy should be $2^{128}$). All I have to ask is "is the first bit a one?", "is the second bit a one?" and so on till the 128th bit $\endgroup$– user80567Apr 20, 2021 at 12:50
-
1$\begingroup$ Actually, if we have a 128 bit key (and all $2^{128}$ possibilities have the same probability), that does have 128 bits of entropy $\endgroup$– ponchoMar 8 at 13:33
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
In information theory, entropy is the measure of uncertainty associated with a random variable. In terms of Cryptography, entropy must be supplied by the cipher for injection into the plaintext of a message so as to neutralise the amount of structure that is present in the unsecure plaintext message. How it is measured depends on the cipher.
Have a look at the following article. It provides a survey of entropy measures and their applications in cryptography: "Entropy Measures and Unconditional Security in Cryptography (1997)" (by Christian Cachin).
$\begingroup$
$\endgroup$
3
To give you a short answer to your question: The common notion of entropy is the notion of Shannon entropy. The information content $H_x$ of a value $x$ that occurs with probability $\Pr[x]$ is $$H_x = -\log_2(\Pr[x]) \text.$$ The entropy of a random source is the expected information content of the symbol it outputs, that is $$H(X) = E[H_X] = \sum_x \Pr[x]H_x = \sum_x -\Pr[x]\log_2(\Pr[x]) \text.$$
You can interpret this as the expected uncertainty about a symbol $x$ knowing only the distribution according to which $x$ is chosen. For the case of bit strings the important message is, the entropy not always equals the bit length of $x$. I.e. if you want to seed a pseudo-random generator, it is important to choose a seed with high entropy. If you use the actual time as seed the entropy of the seed is very low, as everybody can easily guess parts of the seed (year, day, perhaps even hour and minute). Ask Netscape, they should have learned this…
There are several other notions of entropy all discussed in the other answer, but I think this is the most important one, if you don't want to study complexity or information theory.
-
-
$\begingroup$ it is an element from the support of a distribution. $\endgroup$– mephistoApr 13, 2022 at 20:37
-
$\begingroup$ What I meant is that it's impossible to enumerate $x$ in the general case (non-IID samples). And then how would it be combined, as algebraic summation won't work? It's pretty much an open question. Hence your loggie formula is inappropriate in the general case as asked in the question. And of course, you don't know the expected information content either, so the entropy has to be the entropy of a fixed sample. Tricky and so it makes the answer incorrect. $\endgroup$ Apr 13, 2022 at 21:58