# Concatenating "words," is it possible to create a key that is indistinguishable from one made in a truly random manner?

By concatenating "words" and adding them Modulo 26, can a key be created that is indistinguishable from one generated in a truly random manner? Let's say the key is more than about ten letters.

For example, three "words" (EATED, PIG, ELEPHANTINE), whose lengths are coprime, are concatenated with themselves and added like the key of a Vigenère cipher (Modulo 26):

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

ELEPHANTINEELEPHANTINEELEPHANT...
_______________________________
XTDISKCUSFQKTQYAIMMTXTFVWBNIZC...
I              M X


Bob and Alice have already agreed to the specific values, say the 4th, 19th, and 21st letters of the final string, as key material (in this case: I, M, X), so they will discard the rest. Then they will use a different set of words and perhaps different values-- e.g., the 6th, 11th, and 18th letters of the second string-- until they have reached their desired key length. Let's say that they do not choose the numbers in a truly random manner, but ad hoc, with non-uniform distribution, such as out of their heads (for speed), but are aware of the effective key length before they come up with and words.

The point is to get rid of the one-time pad and only have a list of words and numbers in one's possession.

The process is repeated, with different sets of three or more words whose lengths are coprime and corresponding values to be used, until the key is made, e.g., one that is thirty characters long.

They will use a combined dictionary of Mandarin Chinese, Russian, and English entries with 180,000 possible words (Mandarin and Russian are phoneticized). Then, they choose each word in an ad hoc manner.

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

Yes, I would say, if the words were long enough, coprime to each other, and were chosen ad hoc. Is such a key indistinguishable from one generated in a truly random manner? Yes or no?

• 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’. Oct 4, 2019 at 16:53
• 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. Oct 4, 2019 at 17:02

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).

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.