0
$\begingroup$

Can I use something like Shannon entropy to determine the suitability of a symmetric key? I found a symmetric key which wasn't generated using a CSPRNG and it had a very low Shannon entropy.

I ran an experiment on 1 million keys from a CSPRNG having a Shannon entropy of at least x where all the weak symmetric keys I found had a Shannon entropy of less than x. I don't think the value of x here particular important here but I was wondering if it would be reasonable to reject symmetric keys that don't meet this requirement. Basically as a countermeasure for bad configuration.

$\endgroup$
  • 4
    $\begingroup$ There's some confusion going on here. A fixed key does not have any entropy. The source has entropy. $\endgroup$ – Maeher Jun 24 at 9:55
  • $\begingroup$ What the question's "requirement" is not clear. What about computing the probability that a key chosen from a source of independent uniformly random bits fail that requirement, and decide if that's reasonable based on that probability and the consequences of an unwarranted rejection (which are context-dependent)? $\endgroup$ – fgrieu Jun 24 at 10:59
  • $\begingroup$ @fgrieu this is kinda what the Shannon entropy does, I can include some code to illustrate but the question is really about what might go wrong if I decide to filter out keys from the CSPRNG that fail the Shannon entropy test. Also, to be clear. I am computing the Shannon entropy of the symmetric key by partitioning the key into nibbles (groups of 4 bits) counting the frequency of 0-15 to approximate the distribution. I then do the Shannon entropy calculation on top of that to find x. In my case x is at least 0.9 for the final key of 64 bytes from a reliable CSPRNG source. $\endgroup$ – John Leidegren Jun 24 at 11:32
  • $\begingroup$ So it is grouped bits as $n=128$ groups of $b=4$ bits, counted the number $n_i$ of groups with each of the $2^b$ bit patterns $i$, and checked$$x\le-\frac1b\sum_{n_i\ne0}\frac{n_i}n\,\log_2\left(\frac{n_i}n\right)$$for $x=0.9$. It's possible to compute the rejection rate for a true random source, but reasonableness of accepting that many spurious rejections depends on the penalty incurred (does the gismo self-desctruct, or move on to the next sample?). And reasonableness of accepting for use as keys the samples that pass this test can not be asserted without knowing what the source is. $\endgroup$ – fgrieu Jun 24 at 12:26
  • 2
    $\begingroup$ That's not a CSPRNG that is known to be weak, to be honest. You aren't looking at 3DES key per chance? Those have parity bits and are therefore definitely not random over all the bits - only the bits that matter. $\endgroup$ – Maarten Bodewes Jun 24 at 14:09
2
$\begingroup$

Per my understanding of these comments, the question's test takes $\ell=64$ bytes from a Windows RNGCryptoServiceProvider, makes it $n=2\ell=128$ groups of $b=4$ bits, counts the number $n_i$ of groups with each of the $2^b=16$ bit patterns $i$, computes $p_i=n_i/n$, and for a limit $x=0.9$ checks $$x\le-\frac1b\sum_{p_i\ne0}p_\,\log_2\left(p_i\right)$$

The question's test should only fail very rarely. The probability that it does even once in one million tests (as reported) seems to be less than $0.2\%$ according to my simulation: I have seen $25$ events for $18\times10^9$ samples tested. Something is at odds, independently of what follows.


The test is inspired by the formula for Shannon entropy per bit of a source of $b$-bit independent values of known probability $p_i$, but here we do not compute a Shannon entropy, because we are operating on a sample, not on the source, and Shannon entropy is not defined for a sample. The $p_i$ are experimental frequency, not a probability for the source. I can't see how this formula can be justified.

Update: I have asked about that test there, and got a detailed answer. It turns out to be known as the G-test or Woolf's log likelihood ratio test, and a sound alternative to Pearson's $\chi^2$ test.

Can I use something like Shannon entropy to determine the suitability of a symmetric key?

If the source was known for certain to be from a construction aiming at being a CSPRNG, no. Tests on such output can only give a fallacious insurance of security, or detect gross errors. The correct method is to scrutinize the specification and if possible the implementation of the CSPRNG.

But that's not what the question is about.


I am worried that employing such a filter to protect against human error may in turn create a security risk.

It does not in practice. The two following nitpicks are theoretical only:

  • Restricting to keys that pass the test obviously reduces the keyspace to some (imperceptible) degree.
  • Performing the test may leak information about the key, if side channel attacks are an issue. However, if they are, that's the problem, not the test.

I do have serious reservations on trusting that test to catch a bad CSPRNG:

  • The most common issue with CSPRNGs is improper seeding, and the test won't catch it.
  • More generally it is demonstrably impossible to prove or even meaningfully confirm the quality of a CSPRNG from its output: we can make CSPRNGs that pass any pre-existing test, yet are extremely weak for who knows their internals.

Independently, as already stated, if only a million tests have reported a fail (and the key is 64 bytes as stated), that's most likely an anomaly. It could be in the test, or in how the generator is used, or in the assumptions on what the generator is designed to output, rather than in the generator itself.

A poorly chosen key was installed into the system by mistake

The test indeed has some chance to catch some forms of that, and if the small false-positive rate (much less than one in 100 million keys if I get it correctly) is tolerable, why not? However, attempts to detect errors from the value of the key itself are bound to be unreliable. For example, the test won't catch a favorite test key for DES, 0123456789ABCDEF, repeated.

A preferable practice is to have procedures that prevent such mistakes. Like, transmitting keys using dedicated devices, or data blobs with integrity protection, or as a last resort well-thought Key Check Values.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I'm using the Shannon entropy as an estimate of randomness to root out keys that have not been generated using a CSPRNG of high enough quality. In my case, the source is the key and the samples are the 4 bit buckets. I don't see why it couldn't be used. It essentially is a filter on what keys will be acceptable. Though, I am worried that employing such a filter to protect against human error may in turn create a security risk. Maybe there's a better way to protect against misconfiguration, but in my case, this is what happened. A poorly chosen key was installed into the system by mistake. $\endgroup$ – John Leidegren Jun 25 at 11:47
  • 1
    $\begingroup$ "More generally it is demonstrably impossible to confirm the quality of a CSPRNG from its output: we can make CSPRNGs that pass any pre-existing test, yet are extremely weak for who knows their internals." Well, I guess we can say something if the CSPRNG spectacularly fails. But that's generally not what happens. $\endgroup$ – Maarten Bodewes Jun 25 at 13:00
  • $\begingroup$ The quality of the CSPRNG is not in question. Poor wording on my part, I just want to minimize the risk of an obviously not random key to be installed by mistake. $\endgroup$ – John Leidegren Jun 26 at 11:21

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.