1
$\begingroup$

By concatenating "words" and adding them Modulo 26, can we 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:

  EATEDEATEDEATEDEATEDEATEDEATED...       
  PIGPIGPIGPIGPIGPIGPIGPIGPIGPIG...
  _______________________________ 
  TIZTLKPBKSMGIMJTIZTLKPBKSMGIMJ...  

  ELEPHANTINEELEPHANTINEELEPHANT...
  _______________________________
  XTDISKCUSFQKTQYAIMMTXTFVWBNIZC...

And sender and receiver have already agreed that they will only use certain values, say the 4th, 19th, and 21st letters of the final string, as the key. (I, M, X) The rest will be discarded. Then we use a different set of words and a different choice of values to keep, say the 6th, 11th, and 21st, determined ad hoc beforehand. The sender and receiver must have shared this information beforehand in a secure manner, of course.

The point is to get rid of the one-time pad and only have a list of words and numbers on you.

Repeat with different sets of three or more words whose lengths are coprime until we have our key, let's say thirty characters long.

Let's say we use a combined dictionary of Mandarin Chinese, Russian, and English words that has a total of 180,000 possible words (Mandarin and Russian are phoneticized). Let's say we choose each word in a random manner.

Only using a small number of letters from each result is going to create a short key and require effort, but the question is this: would such a key be indistinguishable from one generated in a truly random manner?

I think so--if the words are long enough and coprime to each other and the words were chosen in a manner that was random i.e., it did involve a TRNG.

Indistinguishable or not?

Improve this question
$\endgroup$
2
  • 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
1
$\begingroup$

No. From 3 “words” as in the question, there can't be any fast public transformation (like the one considered in the question) creating a key of more than about 10 letters in A…Z that is indistinguishable from a key made in a truly random manner, in the sense that has in crypto.

Taking the question's numbers, we pick 3 words in a set of 180,000. That's $(180,000)^3$ choices (ignoring the requirement of length being coprime, which reduces the number of choices significantly; and assuming the position of the letters kept is known, or found by trial and error). Whatever deterministic transformation we make of this input, it can't have more outcomes. If the transformation has for outcome 12 letters in A…Z, not all such strings can be obtained, since $(180,000)^3\ll26^{12}$. Given a string of 12 letters in A…Z, it can in principle be tested if it could have been generated by the transformation applied to the input words, or not (at least by enumerating the $(180,000)^3$ choices and applying the transformation). For 12 letters in A…Z chosen "in a truly random manner", the probability is at most $(180,000)^3/26^{12}<6.2\%$, when that's $100\%$ when using the transformation. That's "distinguishable from a key made in a truly random manner", in the sense that has in crypto, if the test "could have been generated by the transformation applied to the input words" is feasible.

For the question's transformation, that test is feasible, and much faster than testing the $(180,000)^3$ possible input words. One way is to consider only the $(180,000)^2$ combinations of two words, deduce what the selected letters must be considering the key tested, and see if that exists in the dictionary. I estimate that such test lasts a fraction of an hour on a single computer.

Even if we used a cryptographic transformation like SHA-256, the test remains feasible, since $(180,000)^3\approx2^{52.4}$ SHA-256 hashes is within reach.

The first paragraph says "more than about 10 letters" rather than "more than 11", because even with 11 letters, we can still distinguish outputs of the transformation from random, with a few example outputs. Problem is that no transformation can make all the $26^{11}$ outcomes of 11 letters equally likely, because $26^{11}$ does not evenly divide $(180,000)^3$. At best, some (41%) 11-letter outputs will have probability $1/((180,000)^3)$, and the others (59%) twice that. Which is distinguishable from true random with a few examples. With 10-letter outputs, we could still pull that trick with some more examples. That's for the best possible fast cryptographic transformation, and is much easier for the question's simple transformation, where we could recognize the output from random based on a large sample of the first few characters of the output keys.

The best crypto has to offer here is a password-based key derivation function such as Argon2, which is a purposely slow hash, and can be used to a generate a key (of any length) that is indistinguishable from random for practical adversaries, given an input with enough combinations (and here, we have $(180,000)^3\approx2^{52.4}$, which is quite respectable if we are willing to wait 1 second for the Argon2 transformation to run on a computer).

Improve this answer
$\endgroup$
0
$\begingroup$

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
$\endgroup$

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.