4
$\begingroup$

This is a pretty open question, so I'm mostly looking for gut reactions from experts more educated than I.

Given these assumptions which are easy to verify with a quick Google search:

  • One Time Pads need to be truly random to be unbreakable
  • Human beings cannot generate truly random numbers mentally

My question is: how insecure are human-generated numbers really? Obviously without perfect randomness the One Time Pad cannot guarantee perfect secrecy. But might it be good enough? Consider a use case where two people use a pen-and-paper implementation of the One Time Pad, but use human-generated keys (e.g. writing down "random" digits on paper) instead of a truly random source. Let's suppose these people exchange 10,000 characters worth of messages encrypted in this manner. How might the strength of this pend-and-paper-and-mind cipher compare to say, AES-256, in terms of difficulty to break?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I would suspect that random numbers generated by a cryptographer to be better than from a layperson. And it might differ from person to person as well what is considered "good enough". That makes this question very subjective if you ask me. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 24, 2023 at 21:51
  • $\begingroup$ I like the idea of @MaartenBodewes. Assuming humans are bad at generating randomness, we wouldn't be able to conceptualise (cryptographically) secure random generators. Given enough time, humans can simulate those algorithms. Therefore I would state it as follows: Most humans are inexperienced in generating randomness and therefore bad at it. $\endgroup$
    – Titanlord
    Commented Jan 25, 2023 at 9:16
  • $\begingroup$ Yes good point following a mental algorithm. I should have clarified that I was talking about mentally generating numbers very rapidly, simply writing down digits quickly as they pop into one's mind. Mentally generating "random" numbers is much faster than rolling dice, etc., for pen-and-paper encryption. But using dice would be faster than following a mental PRNG algorithm. $\endgroup$
    – Ben Hershey
    Commented Jan 25, 2023 at 14:57
  • 1
    $\begingroup$ Try the Aaronson Oracle here, see if you can consistently get a result to stay at 50%. Remember that cryptographic attacks can be fantastically sensitive, so if it starts guessing more than 51% correct you've utterly failed to generate random numbers. $\endgroup$
    – SAI Peregrinus
    Commented Jan 26, 2023 at 2:20
  • $\begingroup$ Asking for "gut reactions" is the same as asking for opinions. While opinions cannot be completely excluded, this question should be clearly answerable using hard mathematics, or existing studies and research that have investigated the quality of human randomness. Otherwise, it's better in Cryptography Chat $\endgroup$
    – Criggie
    Commented Jan 27, 2023 at 3:37

3 Answers 3

Reset to default
8
$\begingroup$

Humans are very bad at this. Here's a Reddit post which shows a distribution of asking 8500 students to pick a random number from 1 to 10. Now, knowing that humans are bad at this, someone has proposed a whitening algorithm for producing a better distribution based on this sample data.

However, that probably doesn't account for culture. In the U.S., 7 is considered lucky, probably accounting for its overrepresentation. However, in China, 3, 6, and 8 are considered lucky, whereas 4 is unlucky, so you're more likely to get a different distribution there.

If you pick a random string of 10 digits, each combination is equally likely. It is just as likely to get 3044298114 (digits from the hex representation of the SHA-256 of the empty string) as it is 0000000000. However, humans are substantially more likely to pick the former than the latter, the latter seeming "unrandom".

I should point out that in general, very small advantages can be enormously advantageous when it comes to cryptanalysis. The biases in RC4 are not that large, but when you consider many messages, they lead to breaking of the cipher. I won't hazard to guess an exact number, but considering that $ 2^{256} $ is simply astronomical in size, I'll take AES-256 or ChaCha20 in a secure construction any day over a human-generated one-time pad.

Improve this answer
$\endgroup$
3
$\begingroup$

How might the strength of this pen-and-paper-and-mind cipher compare to say, AES-256, in terms of difficulty to break?

It depends a lot on the setup and what we consider a "break". Here is one case where the human-generated OTP is blatantly insecure.

The watchtower of a military installation is sending a report to command every hours. It's critical that eavesdroppers can't tell if the watchtower has observed something out of the ordinary. Unusually long messages would be a telltale sign of that, and for this reason, the messages all are made the same length (say 1000 characters), by padding with space characters. When there's nothing to tell, which is by far the most common, the messages are space characters except perhaps for the first few ones.

All that traffic is OTP-encrypted: each week, command manually prepares a week worth of One Time Pads (like 170), each 1000-character and made in two identical copies. One copy is kept at command, the other securely conveyed to the watchtower. The pads are indexed so that their order is well-defined. Each side securely store the pads until they are used. Agreeing on a single AES key of like 24 characters every week would be much more convenient (which is the reason ciphers have been invented in the first place).

An eavesdropper can take the 1000-character messages intercepted, and submit each message to some statistical test: a bidirectional Chi-squared test of the frequency of individual characters would do. If the OTPs have been humanly generated without some form of mechanical help, the test will detect some bias (see this other answer for references), to a certain high degree of confidence measured as a p-value. That degree of confidence will be typically much higher for messages essentially consisting of spaces, than it is for genuine messages conveying observations. In our setup, this is a break.

I'm not telling that in this setup, the messages conveying actual information could be fully decoded (though perhaps, it could be told with some degree of confidence if they contained a certain keyword). That's unless some cardinal rule of One Time Pad is breached and pads are deterministically generated, or reused. Both have reportedly happened and allowed reading thru some meaningful messages.

Also, not all methods of generating the pads are equally insecure. A modest degree of mechanization allows to make good pads. For example, prepare Scrabble-like tiles with the characters, one tile each, in an opaque box. Shake the box before each draw, and immediately replace the character in the box. After drawing some number of pads, check that the box still has one each of every character (discard the pads if not). At two draws per second (including writing down the two pads with a carbon copy), the 170.000 weekly draws require about three 8-hours shifts per week.

The main issue with the OTP is not that it's insecure if used correctly. It's that is utterly inconvenient, thus is tends to be not used, or be used incorrectly.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 1) But OTPs have been successfully used for the last hundred years. 2) They are used more and more today inside quantum key distribution networks. 3) Bias is not a break as all random sequences are biased. Have you seen inside my white box? It's pretty biased. And the shorter (10,000), the more biased. 4) All agencies know that convenience is not security. 5) AES might already be broken: Absence of academic evidence is not evidence of states' absence. $\endgroup$
    – Paul Uszak
    Commented Jan 25, 2023 at 13:00
  • 2
    $\begingroup$ @Paul Uszak: 1) OPT has mixed operational sucess. See ref. 2) The proportion of encrypted data that is OPT-encrypted on a given day is minuscule (including in most commercial QKD systems, which tend to use AES for the bulk of the data). I see no evidence that it grows. 3) No contest for the measured bias of most sequences (including all odd-sized ones). I'm talking about the bias of the generator. The later kind, above some threshold (including with human generation) leads to a break in some scenarios (including the one in the answer). $\endgroup$
    – fgrieu ♦
    Commented Jan 25, 2023 at 13:18
  • $\begingroup$ @fgrieu Thank for this illustration. I guess that goes to show it really depends on the application of the one time pad, and what is considered a break. $\endgroup$
    – Ben Hershey
    Commented Jan 25, 2023 at 15:03
-2
$\begingroup$

I suggest about evens.

"Obviously without perfect randomness the One Time Pad cannot guarantee perfect secrecy" requires caveat in that randomness is a function of sample length. The effect of the chi squared distribution upon randomness is at it's greatest when the sample size is small. What might appear non random can be truly random with $\chi^2$ variance. That's why randomness test suites require large sample sizes. An example:-

walk

Imagine randomness testing the above 2d random walk. You might expect the points within the white box to fail if tested independently, whilst passing the points within the purple box. Yet the entire sample is from a true random number generator with both boxes featuring exactly the same degree of randomness. That's just randomness being pesky.

10,000 characters is approximately 2,000 words or only 1,000 words per person. If 10,000 characters were generated by keyboard smashing, and the messages spanned various topics with differing semantics, I can't see how a correlation could be inferred between the plain and cipher texts. All plain texts might not be possibly likely (as per information theoretic security) but many could.

And the proof of the pudding is in the type writer generated OTPs used years ago. Those messages have never been broken in cases where all OTP rules were adhered to.

P.S. I'm willing to provide such a test case if someone is willing to try to decrypt it...

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Are you trying to claim that non-random keystream is secure? This answer is incorrect. $\endgroup$
    – forest
    Commented Jan 25, 2023 at 5:16
  • $\begingroup$ No; you're confusing a truly random source with a (must be) biased very small sample at the whims of the Chi distribution. Probably worth while staring at pi for a while. Or my white box above. $\endgroup$
    – Paul Uszak
    Commented Jan 27, 2023 at 1:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.