Claude Shannon's randomness-guessing machine

https://www.loper-os.org/bad-at-entropy/manmach.html

by Kotlopou • 6 months ago

36 12 6 months ago

grayhatter• 6 months ago

It is not hard to win this game. If you spent a whole day playing it, shame on you. But what if you did not know that you are playing a game? I dug up this toy when I saw people talking about generating 'random' numbers for cryptography by mashing keys or shouting into microphones. It is meant to educate you regarding the folly of such methods.

I wouldn't trust a human to generate enough entropy for any kind of key material. But I'd happily feed their output, and more importantly, the metadata around said output (like the ns delay between key presses) into the seed of a CSPRNG, (much more importantly, along with plenty of other sources of entropy).

The primary characteristic of a CSPRNG, is the inability to predict the next output, from the previous output. Once you get sufficient entropy to seed a CSPRNG, nothing you (correctly) mix into the state, can decrease it's security.

There is no folly in using human interactions to help seed a random number generator. Assuming you dont use the characters they type as the only seed input.

kurisufag• 6 months ago

mildly related: when i want a single bit of entropy in my day-to-day without fooling myself, i think of a random long-ish word and decide based on the evenness of the number of letters. probably this isn't an unbiased oracle, but it's good enough when i don't have a coin handy and care about avoiding self-delusion more than fair odds.

robertk• 6 months ago

It’s slightly biased. ( P(even) = 0.5702; Bias = +0.0702 (about 7 percentage points toward heads) ). You can use this Claude Code prompt to determine how much:

Use your web search tool call. Fetch a list of English words and find their incident frequency in common text (as a proxy for likelihood of someone knowing or thinking of the word on the fly). Take all words 10 characters or longer. Consider their parity (even number of letters or odd). What is the likelihood a coin comes up heads if and only if a word is even when sampled by incidence rate? You can compute this by grouping even and odd words, and summing up their respective incident rates in numerator and denominator. Report back how biased away this is from 0.5. Then do the same for words at least 9 characters to avoid “even start bias” given slight Zipf distribution statistics by word length. Average the two for a “fair sample” of the bias. Then run a bootstrap estimator with random choice of “at least N chars” (8 <= N <= 15) and random subsets of the dictionary (say 50% of words or whatever makes statistical sense). Report back the estimate of the bias with confidence interval (multiple bootstrap methods). How biased is this method from exactly random bits (0.5 prob heads/tails) at various confidence intervals?

rosseitsa• 6 months ago

good one, though it has to be a fairly long word. Personally I check the current minutes of the hour :P

RandomBK• 6 months ago

Additionally, so long as we can be sure the human's output is not actively adversarial, we can xor it into the entropy pool. Entropy can only increase this way.

arn3n• 6 months ago

There’s a basic approach to this using markov chains which works surprisingly well. Scott Aaronson once challenged some students to beat his algorithm — only one student could, who claimed he just “used his free will”. Human randomness isn’t so random. There’s a neat little writeup about it here: https://planetbanatt.net/articles/freewill.html

kelseyfrog• 6 months ago

I like to think that this is a measurement of free will in the literal, naïve sense. It makes just as much sense as other definitions (the ability to take action independent of external cause) and it has the bonus of being quantifiable.

The only downside? A LOT of people get very mad at the implications.

Tzt• 6 months ago

"free will" also known as digits of pi mod 2

continuational• 6 months ago

Got 50% in first try, the computer only made two guesses, one right and one wrong, and passed the rest.

3ple_alpha• 6 months ago

Did you stop after 14 iterations? Because the game is, in fact, infinite.

tucnak• 6 months ago

I did a couple runs without thinking much about it, and the computer never got more than 25%. I guess 0000 and 1111 don't feel random, but work pretty well. Probably by random chance is only 1/8 or 12.5%. In other words it will happen all the time.

ChocMontePy• 6 months ago

I got 58% after 100 attempts.

My method uses the fact that the letters a-k + u make up around 49.9% of letters in a normal text. So I just go through a text letter by letter in my mind, giving 0 if the letter is a-k or u, and a 1 if it's l-t or v-z.

For example, the Gettysburg Address:

f - 0

o - 1

u - 0

r - 1

s - 1

c - 0

o - 1

r - 1

e - 0

Claude Shannon's randomness-guessing machine

Related Stories