Are humans a strong or weak RNG?

Question

Thomas Pornin has stated in the past on multiple occasions (I'm not going to source them, he can argue with me if he wants) that humans are bad RNGs.

While I agree that human RNG for password generation in the mind is abysmal usually, I wanted to ask if human-aided RNG by a computer is equally as bad. KeePass has a feature where you seed the RNG by moving the mouse for a while, and while I know that if KeePass is using /dev/urandom it's more or less secure enough, I've used the mouse-seeded RNG in the past.

I've always thought that RNG aided by human input would be better than just standard PRNG as provided by an operating system. How could someone predict exactly how I'd move my mouse, at what rate, how often I'm pausing, etc.?

Answer 1

Human brains are poor RNG. People are bad at generating random values in the privacy of their heads. They just cannot think randomly; though they can convince themselves that they do.

Physical process, on the other hand, are rather good sources of entropy. Take your mouse movements. A few dozen times per second, the mouse measures how far it has moved since the last tick, and sends that information to the server. When your hand shakes, it tends to do so somewhat regularly, but biology is such that each elementary move will be subject to some jitter, which happens to be substantially bigger than the precision of the mouse; even with a lot of training, it is very hard for a human hand to do the exact same move repeatedly (otherwise there would be a lot more people like Yehudi Menuhin). So the bottom line is that mouse movement measures contain some entropy. (Remember that "entropy" is here defined as "that which the attacker does not know"; the mouse certainly knows how much it has moved, since it is that mouse that actually sends the values on which the RNG are built.)

The other half of the answer is aggregation. A mouse-based RNG will use hundreds or even thousands of measures, accumulate them all and condensate them into an appropriate seed that will concentrate all that entropy. This is simple enough: simply feed all the values to a cryptographic hash function, e.g. SHA-256, and you will get a 256-bit seed that has all the source entropy, wherever it was hiding in the measured mouse movements. Hash functions are good for that; they reduce the size but keep the entropy (up to the hash function output size, but 256 bits is more than enough for all purposes).

An attacker may guess that the user will do circles, but will have a hard time getting all the individual movements right, especially since psychology won't help him: the human user himself has no idea how his hand movements are turned into numbers. Since we are talking about hundreds of numbers, the number of possible combinations (i.e. "entropy") raises exponentially. Contrast that with a human user thinking about a new password: the user will choose letters following some inner "witty" train of thought, that the attacker can guess more or less brutally (e.g. if the letters are all the first letters of some words in a sentence from a book, the attacker can automatically try all sentences from all books he can find in electronic format); and, more importantly, the human user won't be bothered to produce more than a dozen or so of "seemingly random" characters.

In passwords, length does not make strength -- but lack of length can be quite effective at preventing strength.

Answer 2

Humans are very poor generators of randomness, especially upon request.

Most users are going to do one of a few things as human behavior is fairly predictable. Using the mouse as an example users are likely to move it side to side or up and down until enough "randomness" is generated according to the program. Perhaps they'll move it in a circle. What they're unlikely to do is move the mouse in a truly random way. If someone cared they could analyze a set of users, extrapolate likely behaviors and extract useful information from those studies to discover patterns which could be used to attack such a system.

It's really hard to get truly random data.

From Secure Programming Cookbook for C and C++: Unfortunately, most mouse movements follow simple trajectories with very little entropy. The most entropy occurs when the pointer reaches the general vicinity of its destination, and starts to slow down to lock in on a target. There is also often a fair bit of entropy on startup. The in-between motion is usually fairly predictable. Nonetheless, if local attacks are not in your threat model, and the attacker can only guess approximately what parts of your screen the mouse went to in a particular time frame based on observing program behavior, there is potentially a fair bit of entropy in each mouse event, because the attacker will not be able to guess to the pixel where the cursor is at any given moment.

Answer 3

With the following small python script, try to produce a sequence of 42 zeroes or ones by moving the mouse in a 'repeatable' pattern.

import Tkinter

root = Tkinter.Tk()

lx,ly = (0, 0)
while True:
        x,y = root.winfo_pointerxy()
        if ((x-lx)**2+(y-ly)**2) > 42:
                print (x ^ y ^ lx ^ ly) & 1
                lx,ly = (x,y)

If you have Python 3.x, you may also use the following instead:

import tkinter
tkinter.NoDefaultRoot()
root = tkinter.Tk()
x = y = 0
while True:
    x2, y2 = root.winfo_pointerxy()
    if (x - x2) ** 2 + (y - y2) ** 2 > 42:
        print((x ^ y ^ x2 ^ y2) & 1)
        x, y = x2, y2

Answer 4

The quality of a RNG is a question of correlations to the inputs or some other set of non-secret parameters. Obviously if the output of a RNG correlates to something you know, that reduces the entropy drastically by allowing you to cut away large swathes of the possible output space - perhaps a given RNG can now realistically be expected to output only one out of 1,000 numbers as opposed to the advertised 1,000,000, which makes brute-force much more practical.

The RNG constructed by asking a human to think of random words or phrases is in fact poor. The reason is many strong correlates:

• Correlation to culture, allowing you to use an English dictionary for North American targets or focus on 1900-2000 for PINs (also why passwords in other languages are a decent security-through-obscurity strategy)
• Correlation to others, allowing you to build dictionaries of top X most common passwords
• Correlation to historical behavior of self, allowing you to exploit past known passwords, or mine social media for clues like birthdate or hometown

Note that that many "secure" PRNGs are also based on a very predictable input, namely system time.

The key is to recognize that the human is not necessarily the only element of the RNG. It only acts as a seed. There is no reason why you would be allowed to only output the seed as is, so you can apply various functions to it to dilute the correlation (a basic but weak example is to add a very large number, multiply by a very large number and then take the modulo).

The mouse movements are only used as a seed for Keepass's RNG. If the function they use is reasonably capable of returning uncorrelated input, there's no reason to suspect that it's not secure. (granted, I couldn't tell you why exactly they don't just skip the mouse and use system time as their seed, or what function exactly they use and how secure that is)

Answer 5

I think humans are okay, but it depends on how you ask them to generate the number. Also are they required to be able to replicate it? For smaller numbers humans are easily influenced and highly predictable. There's also the problem that humans will often start off with similar patters before they actually start generating something that resembles randomness.. take the following example

952167493... at the start, I began with a familiar number, maybe a phone number that's in the persons mind or street number, then humans might try to be random, and the likelihood of two numbers following a regular counting order will be low, after this they might hop around trying to fill out the number spectrum.

given enough samples, I think many humans would follow similar patterns, and you would get large numbers which aren't very random at all. You may even find whole swathes of numbers that don't show up, merely because they don't feel random to a human as they're creating them, like 123123123123123 or 44455523534333666

I wouldn't trust a human to create a random number unless they had some instructions that would decrease the likelihood of human number/pattern biases, even then it's a bad idea

Answer 6

There are some very good answers here already so I just want to provide some anecdotal evidence. It seems clear already that in motion based RNGs humans can provide a strong source of entropy due to inexact reproduction of movements.

In the case of asking humans to select a random number however, strong trends begin to be shown. I remember a math class back in year 8 where we generated 100 "random" numbers by asking people that we encountered and the results showed just how predictable humans can be. I can't remember the exact results, but the number 7 for example came up three times more often than the next most popular answer, no person gave an answer that was more than two digits and all answers were integers. I'm sure if this was performed on a larger scale a similar trend would be produced.

Answer 7

It is my opinion, that humans are very poor at generating randomness on request. There are ways to "extract" randomness from human interactions. The mouse movement is a good example. The randomness doesn't come from the intentions of the user (most people will draw lines or circles) but from the error in the movement. Humans just can't draw exactly repeatable figures using a mouse.

While looking for answers, I found two 'interesting' papers:

• Humans can consciously generate random number sequences: a possible test for artificial intelligence.[1]
• Humans cannot consciously generate random numbers sequences: Polemic study[2]

Sadly, both are only available commercially, and if you are not a student or researcher at some University you'd have to pay. (don't do it for this papers!) I think the titles are funny enough.

I also found more serious and interesting papers, you could read:

• Games for extracting randomness[3]
• Assessing randomness and complexity in human motion trajectories through analysis of symbolic sequences[4] (not fully on topic, but very interesting)
• This Answer on the Cognitive Sciences Stack Exchange lists some

All of this suggests (except the first paper, but I don't take that very serious) that humans are bad when asked to consciously generate randomness, but if you do it right you can extract good randomness from human movements!