Is there a classical method that will allow us to create a key that cannot be distinguished from one that was generated in a truly random manner?

For example, let's say we use three "words" to create a key (EATED, PIG, ELEPHANTINE), whose lengths are coprime, using Modulo 26 addition:



And we have already agreed that we will only use the 4th, 19th, and 21st letters of the final string as the key. (I, M, X) The rest will be discarded.

Repeat, repeat, repeat with different sets of three words whose lengths are coprime/three numbers until we have a key of our needed length. Let's say that we do not choose the numbers in a truly random manner, but in an ad hoc manner, which has non-uniform distribution, such as out of our heads (for speed), but we are aware of the effective key length before we come up with numbers. Let's say we use a combined dictionary of Mandarin Chinese, Russian, and English words that has 150,000 possible values (Mandarin and Russian are phoneticized according to an system agreed upon earlier).

I take it that only using three values from each string will keep the amount of ciphertext below the unicity distance. Would such a key be indistinguishable from one generated in a truly random manner?

  • 1
    $\begingroup$ By the way, a using a pseudorandom generator with a seed chosen at random is a truly random process even though part of it involves a pseudorandom procedure, and a random process is random whether the distribution on its outcome is uniform or nonuniform. That is, nonuniform is a contrast to uniform, not a contrast to ‘truly random’. $\endgroup$ – Squeamish Ossifrage Oct 4 '19 at 16:53
  • 2
    $\begingroup$ The answer depends entirely on the distribution of word choices. No cryptographer would want to go to the trouble of quantifying that—which doesn't mean it will be secure; just that nobody will want to bother studying it well enough to get confidence in its security. $\endgroup$ – Squeamish Ossifrage Oct 4 '19 at 17:02

Is there a classical method that will allow us to create a key...

A key. One. Easy - Just make it up in your head. Take for instance:-

54ec60d3f91cdded70a5b059a4c60fb0ccc17214cd86c97ab3d90c2719a9805f and 38bba30f66691ace36b27cd8fee81839d6b9251e2b0baef8bf8306bc2dea372a.

Both are 256 bits long. One is taken directly from a TRNG, whilst the other I just made up by randomly typing on the keyboard. The point is whether anyone can distinguish one from the other.

You can't. 32 bytes taken from a range of 0-255 is simply not enough of a sample size, and randomness is a function of sample size. Therefore there are no mathematics that can distinguish them if one is disciplined enough not to type the equivalent of all zeros.

FIPS 140-2 tests require at least 2500 bytes, I would use 65,536 bytes ($\text{bins}^2$) for a $\chi^2$ test and ent recommends 500,000 bytes. Fortunately in this case normal random fluctuations will mask any deviation from a uniform distribution. The strings give $ \chi^2 $ of 224 and 240, with entropies of 5.00 and 4.94 bits/byte respectively, both which are meaningless and indistinguishable. Especially given that one of the strings is from a good TRNG. It's the reason why type writer generated one time pads from the war still haven't been broken.

So for one key, just write down what comes into your head. Expansion via a CSPRNG can allow subsequent encryption of oodles of data. And I believe that even if you were to rotate such a key monthly, no one would be able to compute a usable statistical advantage against you. The sample size is just insufficient.

| improve this answer | |

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.