2
$\begingroup$

In the questions, Are mouse movement coordinates useful as a seed for a RNG? and Is this a good entropy collector and whitening technique? the posters each talk about collecting mouse and keyboard input as a source of entropy. The replies make the good point about this being dangerous and requiring a large sample to ensure sufficient entropy for cryptographic purposes.

I am wondering if the quality of these inputs as entropy sources would be improved given the following scheme and, if so, by how much?

Imagine a system where X is some input from the user (e.g. mouse coordinate pair or key code combined with current timestamp) and H is some latest-generation hashing function and e is our current entropy pool state after each iteration. After the first input is collected we have:

e = H(X1)

This has low entropy. We collect another sample from the user and this time combine with the previous entropy and and hash it:

e = H( X2 + e )

or:

e = H( X2 + H(X1) )

Then we keep doing the same thing for each new value collected, combining it with the previous entropy and hashing them together:

e = H( Xn + e )

or:

e = H( Xn + H(Xn-1 + H(Xn-2 + H(Xn-3 + ...))) )

Does hashing iteratively like this in any way change the rate of improvement of the quality of the entropy produced, or is it about the same as collecting all of the samples and hashing them once like this:

e = H( X1 + X2 + X3 ... Xn )

Update

This answer to What happens to entropy after hashing? also has a good analysis that I think applies here:

If we have a Hash function SHA which doesn't have any collisions, then it has no effect on entropy; that is, H(X) = H(SHA(X));

$\endgroup$
  • 1
    $\begingroup$ This is pretty much what happens anyway — either automatically when you interact with the system, or manually when you send anything to /dev/random. For example, Yarrow is based in part on the SHA-1 hashing algorithm. Just use /dev/random. It's perfectly adequate. $\endgroup$ – squeamish ossifrage Sep 8 '16 at 10:32
  • $\begingroup$ Yes, "use /dev/urandom" is 100% correct, but for the sake of this question I am interested in the mathematics of why hashing iteratively might or might not produce better randomness. Do you think I should I add to the question "assume the user does not have access to actual good sources of entropy like /dev/urandom"? $\endgroup$ – Chris McCormick Sep 8 '16 at 10:47
  • 1
    $\begingroup$ In theory, iterated hashing may have problems that simple feeding hashing does not (e.g. collisions and same paths and stuff like that), but in practice there's no relevant difference. $\endgroup$ – SEJPM Sep 8 '16 at 12:10
  • $\begingroup$ Note that usually a PRNG already does things like that when handling new entropy. So usually you would not get any benefit from it for the simple reason that it is already performed. Entropy needs to be extracted / compacted anyway before it can be mixed with the state ($e$). $\endgroup$ – Maarten Bodewes Sep 12 '16 at 14:55
2
$\begingroup$

The biggest problem with capturing mouse & keyboard input is that the number of likely things a user does within a small timeframe is limited.

Imagine that you hash 3 alphanumeric characters of userinput H(X1 + X2 + X3) (assuming + means concatenation and H is a cryptographic hashing function). The number of possibilities from 000 to ZZZ would be about 62^3. Now if instead you would use H(X3 + H(X2 + H(X1))) the number of possibilities would still be 62^3. You could even use something like pbkdf2 with a ridiculous number of iterations without changing the number of possible outputs.

$\endgroup$
  • 1
    $\begingroup$ Keyboard and mouse input can be captured with nanosecond resolution. This is how the Linux kernel gets randomness and can genuinely provide quite a lot of entropy. $\endgroup$ – forest Dec 15 '17 at 6:09
0
$\begingroup$

One should always apply a slow, one-way function to user input. While it has no effect on the number of possible outputs, applying such a function (like an iterated hash) does help defend against attacks.

Imagine you ask the user to click on random locations. Upon each click, you record the location of the cursor. After the third click, you have three points in the space of 1920x1080 (on a full HD screen, as an example). This is your upper bound on the randomness of it, as Daan Bakker already described.

Now some novel research is released which describes how users select such locations. It might turn out that few people click the same place twice after each other. This allows an attacker to predict the next two points with a higher probability, and such an attacker can start cracking any keys which were based on this entropy source.

If a slow one-way function such as Scrypt or Argon2 (or, in a more basic form, any iterative hash) had been applied to the user input, an attacker can only do guesses as fast as this function allows. For example, I was looking through some source code which generates private keys, and it bases the keys solely on input from mouse movements. The RSA key generation process is still slow so that is lucky for the user, but the derived keys might as well have been something like symmetric keys for disk encryption. Those are extremely fast to generate, and could be guessed at very high speeds if no slow function is applied to the randomness.

$\endgroup$
  • 1
    $\begingroup$ The slow one way function is a good idea for the computation fo a final output used for crypto purposes. But for continuously mixing entropy gathered from a mouse, the objective should be to gather as much entropy as possible given the affordable CPU power, and that typically implies a fast hash. $\endgroup$ – fgrieu Feb 20 at 13:22

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.