7
$\begingroup$

I know the topic of human brains generating random numbers has been discussed here and in Cognitive Sciences before, but I am interested in a particular part of it:

In an introductory book to cryptography I read recently ("Cuando la criptografia falla", by Arturo Quirantes), it is mentioned that in some historical occasions, mecanographers were used to generate random numbers for cryptographic purposes. However, as we know now, it was not truly random (or at least uniformly distributed) and some numbers would appear more than others. I had read about this before, but I have failed to find examples of historical events when this technique was used. I am also curious about whether any important information has ever been leaked because of the low entropy of human-brain generated numbers.

Could you please point me to some documentation about this?

$\endgroup$

migrated from security.stackexchange.com Apr 24 '15 at 15:59

This question came from our site for information security professionals.

  • $\begingroup$ I'd be shocked if a human spewing out numbers was non-random enough to be exploitable, and if the information being protected was important enough to warrant trying. I say this because if it was, they could have simply used a 10 sided die and prevented the problem in the first place. $\endgroup$ – TTT Apr 23 '15 at 18:43
  • 2
    $\begingroup$ @TTT, a human spewing out numbers tends not to generate the same number twice in a row, and almost never generates runs longer than 2. A good cryptographer could easily exploit this. $\endgroup$ – Mark Apr 24 '15 at 8:16
  • $\begingroup$ @Mark but isn't that just ~10% decrease in entropy. Can you reference some significantly better exploitation of this? $\endgroup$ – domen Apr 24 '15 at 9:03
  • $\begingroup$ @Mark - suppose we had an algorithm where you roll a 10 sided die, but if a number appears 3 times in a row, you skip it until a different number comes up. You could tell the good cryptographer that you are using this algorithm and he would not be much better off than if you didn't add this condition. As domen said, when a number is duplicated, you now go from a 10% chance of guessing the next number to 11%. That's hardly enough to predict the human spewer's next series. $\endgroup$ – TTT May 15 '15 at 20:30
10
$\begingroup$

In World War II, this practice of generating "random" code books by hand is known to have been used by the Special Operations Executive, or SOE:

Various techniques have been used to do the random generation. Marks describes how SOE agents’ silken keys were manufactured in Oxford by little old ladies shuffling counters.

(Security Engineering: A Guide to building Dependable Distributed Systems)

The Marks mentioned there is Leo Marks, who was the cryptographer for SOE. His book Between Silk and Cyanide describes a meeting with Commander Denniston of Bletchley Park:

[Commander Denniston] questioned me closely about WOK-production, and wanted to know why we preferred keys made by hand to the machine-made keys supplied by Bletchley.

I explained that Bletchley hadn't produced them in sufficient quantities, and that the ones which they'd sent us didn't seem to me as random as the keys the girls produced by shuffling counters.

He looked at me doubtfully, so I gave him six sheets of keys produced by the girls, and six by Bletchley. He correctly identified Bletchley's, agreed there was a pattern to them, ...

(WOK stands for Worked Out Keys, and is a hand-enciphered code using shared random keys to seed it)

While I'm unable to cite a specific instance of hand-generated random data being insufficient, I'm sure it happened. The coding systems used in World War II, both manual and machine-based, generally relied upon unpredictable keys rather than strong cryptographic algorithms. Attacks upon keying material were the primary focus (again, both by hand and by machine). Any weakness in randomness could be exploited.

When you consider the fact that the systematic and massive compromise of Enigma was kept largely secret for around 30 years, the likelihood of a particular hand-shuffled one-time pad being compromised and documented as such is pretty low. So the fact that examples don't abound isn't really noteworthy.

Neal Stephenson's fiction novel Cryptonomicon does include such a story (although, again, it's fiction) - Detachment 2702's one-time pad traffic is decoded for a few reasons, including re-use of pads but also insufficient randomness:

"Enoch, why are you . . . here?"

"Oh. I am here, in a larger sense, because Mrs. Tenney, the vicar’s wife, has become sloppy, and forgotten to close her eyes when she takes the balls out of the bingo machine."

$\endgroup$
4
$\begingroup$

Probably yes, the shortage of human-generated entropy seems to have caused real problems: in this declassified memo (starting last paragraph of page 1), written for the 50 years of the VENONA project, is a documented case where OTP duplication is what enabled cryptanalysis; at least allegedly (from where we stand it is hard to tell if this whole story is genuine, or made up as a cover to protect the real source of a plain old-fashioned information leak).

In summary, the story goes that a soviet-union manufacturer of OTP books, under pressure to produce them fast, made 35000 page with duplicate material; that was found, and enabled deciphering encrypted messages.

$\endgroup$
  • 1
    $\begingroup$ If I understood the story properly, the problem here was the reuse of OTPs, but that would have been a problem even if each OTP had been generated with a perfectly random algorithm, right? $\endgroup$ – user2891462 Apr 27 '15 at 17:02
  • $\begingroup$ @user2891462: Indeed, there is no claim that the OTP would have been vulnerable without reuse, and I have no proof that the initial generation involved a human (e.g. rolling and reading dices). Still, what in the end was believed to be fresh entropy was not and that turned out to be a problem; and what generated the problematic entropy as used involved humans, that are responsible of the goof. So we are pretty close to "human-generated entropy (being) a real problem" $\endgroup$ – fgrieu Apr 27 '15 at 18:04

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.