0
$\begingroup$

Are there any caveats to the claim that a cryptographic key of size $N$ bits and $N$ bits of entropy are equivalent?

$\endgroup$
  • $\begingroup$ It is not the same, to,compare key length formdifferent encryption schemes you have to,compare,the complexity equivalent (and then it is still only a rough estimate).:For Prime based scenarios the keys must be much bigger, not only to.compensate for fast attacks but also because the key space is less dense than a purely random symmetric key or a large ECC subgroup. $\endgroup$ – eckes Apr 10 '18 at 16:24
6
$\begingroup$

Yes, there are caveats.

The key 982896e097fcb948df5c1dbf89e2e346133db001d9cc37aec4b64b6d8edee224 is 256 bits long but has zero bits of entropy to anyone who knows you are using it.

Suppose you designed a cryptosystem where every legitimate user's secret AES-256 key started with a 192-bit prefix known to you, the designer, which which you chose uniformly at random. To an adversary who doesn't have access to the system, the keys have 256 bits of entropy. But to you, each key has at most 64 bits of entropy. The United States government imposed this kind of requirement on Lotus in the international editions of its proprietary Lotus Notes software system in the 1980s, albeit with much smaller key sizes, back in the days when men were men and they all agreed that encryption was a munition used outside the United States only by terrorists and that 56 bits oughta be enough for anyone who's not a terrorist.

The number of bits in an RSA modulus may be 2048 (not counting the exponent bits, the private key, and any ASN.1 formatting or what-have-you to store it in a practical system), but it may reasonably be generated from a 256-bit seed.

Entropy is a property of a process or state of knowledge when the process or unknown may have many possible outcomes. For a cryptosystem to be useful, from the adversary's perspective, in the adversary's state of knowledge, the legitimate user's key has to have a distribution of possible values with a nonnegligible min-entropy, which is formally defined as $-\max_k \log p(k)$ where $k$ ranges over all possible keys and $p(k)$ is the probability of the key $k$. If the min-entropy is too small, then the adversary has a good chance of guessing the key on the first try.

But the length of the key is necessarily related to its entropy only in that the length in bits cannot be smaller than the entropy in bits, because you need to have at least $2^n$ possibilities in order to have an entropy of $n$ bits.

$\endgroup$
  • $\begingroup$ crypto.SE really needs to sort this entropy definition thing out once and for all. It's causing a mass of confusion and leading to dodgy and inconsistent answers. For instance, your paras. 2 and 4 clearly contradict each other. We had the same with the recent $ \pi $ thing. If your 9828... key has zero entropy, you'll be able to store it in 0 bytes and transmit it with 0 effort, energy or time. All the related answers showing up suffer from the same issues. $\endgroup$ – Paul Uszak Apr 10 '18 at 16:48
  • 3
    $\begingroup$ @PaulUszak: a large part of the problem is that "entropy" is somewhat of a humpty-dumpty word; it tends to mean different things depending on what the speaker intends. Squeamish uses one definition (where it depends on the process that generated it; I would use that same definition); others appear to use a definition based on statistical tests (when they're talking about tools that claim to measure entropy), that is, how random it looks. Statements depending on one definition make no sense when applied to meanings of the other definition. $\endgroup$ – poncho Apr 10 '18 at 17:24
  • 3
    $\begingroup$ @PaulUszak There is no contradiction. In the distribution $p$ on 256-bit strings with $p(\text{982896e097fcb948df5c1dbf89e2e346133db001d9cc37aec4b64b6d8edee224})=1$ and $p(x)=0$ for any other $x$, the min-entropy of $p$ is 0, where we take $\log0=-\infty$ to be less than all finite real numbers. If the receiver already knows that the message I'm sending is 982896e097fcb948df5c1dbf89e2e346133db001d9cc37aec4b64b6d8edee224, then I don't need to send the message. If the receiver has to be prepared for other options, then that's not the distribution of the receiver's state of knowledge. $\endgroup$ – Squeamish Ossifrage Apr 10 '18 at 17:32
  • 3
    $\begingroup$ @poncho There's only two precise definitions here, depending on whether you mean Shannon entropy or min-entropy, nothing humpty-dumptish about it unless you deliberately ignore the standard definitions and run off into the weeds of unintelligible nonsense. They are both defined in terms of probability distributions. What the entropy estimation tools spit out is an average or minimum of values of this quantity for each of various particular (families of) probability distributions, with family parameters inferred from a sample, always using the same definition of entropy. $\endgroup$ – Squeamish Ossifrage Apr 10 '18 at 17:36
0
$\begingroup$

Also, specifically, please note about "export-grade" encryption.

128-bits keys were used but only 40-bits were really used because the rest were leaked on a side channel.

See also: what does "export grade" cryptography mean? and how this related to Logjam attack?

$\endgroup$
  • $\begingroup$ This is not really what the Logjam attack is about, but you are getting at an important point about a different story about the only way that Lotus Notes was permitted by the US government to use full DES—by allowing the US government to know a certain number of bits of each key, so that although the key is physically (say) 56 bits long (footnote: which is too short for any use), and to an adversary who is not the US government it may have 56 bits of entropy, to an adversary who is the US government, in their state of knowledge there are only (say) 48 bits of entropy in the 56-bit keys. $\endgroup$ – Squeamish Ossifrage Apr 10 '18 at 17:59
  • $\begingroup$ If you are writing Also as start of the first sentence then you should post it as a comment, not as an answer. Please rewrite it so it can be read on its own otherwise. And when referring to other answers, please link to them. Other answers may be posted, answers may be reordered etc. You can link to them by hitting the share button and copying the link. $\endgroup$ – Maarten Bodewes Apr 10 '18 at 22:44

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.