Algorithm: How to use x and y mouse movement co-ordinates to generate random data?

Background:

I'm making a program for fun as a learning exercise. I want to generate some actual random key material (not pseudorandom) from a JavaScript program. For my program is just for encrypting/decrypting plain text letter by letter so I've chosen to use the ASCII printable character set (what characters you can type on a standard US keyboard) which gives 95 possible characters.

I want to capture a users' random mouse movements on screen to capture a long stream of random numbers. I want to use the x & y coordinates from each mouse position out of a possible screen resolution of 1920x1080 pixels and then map them back to a character within the list of possible ASCII characters. Then I can use that character in my key material. Let's say the program captures the following series of x and y coordinates like so:

[478,702]
[503,701]
[581,687]
[633,670]
[691,646]
[757,620]
[814,599]


Question 1:

At this point should I multiply the x and y coordinates to get a better random number, ie 478 x 702 = 335556 and use this number? Because if I just took the x number separately then you might end up with consecutive numbers e.g. 121, 122, 123, 127 as they're moving the mouse in one direction which doesn't look particularly random. Or should I add the numbers together ie 478 + 702 = 1180? Or perhaps alternate between adding and multiplying for each set of coordinates I get to make the random number?

Question 2:

Now what's the best way to map the random number to a character in my list (array) of possible characters? If I've got an array of all the 95 characters [0 - 94] for a zero based array, and lets say my random number is 1180, how do I map that back to a character in my array? Do I loop over the array multiple times until I'm at the 1180th character and now use that character for my key? Essentially this would be like repeating the 95 possible characters in a row up to 1180 characters, then taking the last one. Or maybe you can work this out mathematically?

Or do I create a big 2D array with all the characters repeated horizontally and vertically (like a big grid to match the screen size), then when an x and y mouse coordinate comes in I map it to the x and y indexes in the big 2D array and use that character?

Question 3:

What is the entropy quality of the random numbers generated from the mouse movements? Does mapping it back to the reduced character set reduce the entropy? How can you make the process of capturing random data from the mouse movements better?

Question 4:

If my screen size is 1920x1080 pixels and I pull out an x and y coordinate from that. What is the search space ie $2^x$? how do you work that out?

Many thanks

-
stuff them all into a crypto hash such as SHA-512. –  CodesInChaos Jun 12 '13 at 0:38
Q1: Multiplying not-very-random numbers together won't result in numbers being any more random. Q2: Check out modulo operation, the modulo operator in many languages is expressed with a '%' symbol. Ie, 1180 % 95 = 40 (where 1180 is the random number, there are 95 characters, and 40 is the resulting character). –  hunter Jun 12 '13 at 1:32
In general: rolling your own RNG for cryptographic purpose is hard (especially determining that you have enough input), and you should not attempt it for real with you current knowledge. Hint on Q1: consider what happens for the two different inputs [200,330] and [300,220], when you use, on one hand: hash of the whole input, and on the other hand; hash of the product of the two numbers in the input. –  fgrieu Jun 12 '13 at 6:47
Yes, hashing the x and y along with the brackets/colons insure that no entropy is lost. I think it is possible to exhibit colliding pairs with your new ad-hoc scheme (at least I'm sure proving the contrary is hard); in crypto, we like schemes with a simple proof! –  fgrieu Jun 12 '13 at 16:46
You'll want to have a look at random.js from the Stanford JS Crypto Library. E.g., this function is registered to handle mouse movements. Appears to be based on Fortuna –  Steve Clay Jun 13 '13 at 3:46

If you just need to generate random key material, I suggest a simpler solution: use the OS support for generating entropy. On Linux, read from /dev/urandom. On Windows, use CryptGenRandom. Search to find support on other platforms.

If you're doing this in Javascript, read the following:

Those questions fully cover the topic for Javascript. In general, your best bet is probably going to be to use window.crypto.getRandomValues() on browsers that support it, and fall back to something else (server-generated random numbers delivered to the client over SSL, or an existing library, such as the Stanford Javascript Crypto Library).

-
The language I am doing this in does not have access to the raw operating system's PSRNG streams. Also I need actual random not psuedo random. –  zuallauz Jun 12 '13 at 1:50
@zuallauz, "language... does not have access" - Are you sure? What language and platform are you using? (Those primitives are generally available to all user-level programs; you don't need root or administrator permissions to access them.) –  D.W. Jun 12 '13 at 20:08
@zuallauz, "I need actual random not psuedo random" - I very much doubt this. The entropy sources I listed are designed to be cryptographic-strength: i.e., adequate for generating cryptographic keys. (Moreover, the kind of approach you were sketching in your question also generates pseudorandom numbers, not true random ones, so if pseudorandom is insufficient for some unlikely reason, the approach you were sketching is insufficient too. But realistically I think you've misinterpreted the requirements for generating cryptographic keys.) –  D.W. Jun 12 '13 at 20:10
For your edited answer you also mention falling back to server-generated random numbers delivered to the client over SSL. That sounds terrible as then you're sending your random numbers for your one-time pad key over a less secure transmission medium. The security of the one-time pad that used those random numbers would then only be as secure as the SSL used. So if the SSL was broken/intercepted/hijacked they could grab the random numbers and later decrypt your one-time pad. The generation of the random numbers must be done in JavaScript and stay client side as if it was a regular C++ program. –  zuallauz Jun 13 '13 at 1:36
@zuallauz, I see many misconceptions here. Again, as I stated before, what you are calling "pseudorandom" is perfectly fine for this purpose. Also, if SSL is broken, you have far bigger problems: other attacks become possible. The OTP is a poor choice for practical security. Finally, if you need very high-assurance security, for heaven's sakes, don't use Javascript and the web to implement it! –  D.W. Jun 13 '13 at 5:18

This paper gives (starting on page 3) a representation (described in the last paragraph of page 1)
of irreducible polynomials over the binary field, and will suffice for generating the seed from
sources that are less than 10000 bits long. $\:$ This paper gives a deterministic and provably efficient
algorithm to find such polynomials, and can be used for sources that might be 10000 bits or longer.
Let $\;\; \mathbf{c} \: = \: c_0\hspace{.02 in}c_1\hspace{.02 in}c_2\hspace{.02 in}...\hspace{.02 in}c_{L-1} \;\;$ be a bitstring such that
$c_0 \cdot x^0 \: + \: c_1 \cdot x^1 \: + \: c_2 \cdot x^2 \: + \: ... \: + \: c_{L-1} \cdot x^{L-1} \: + \: x^L$
is an irreducible polynomial over the binary field, as described above.
Define $\;\; \operatorname{mbx} : \{0,\hspace{-0.02 in}1\}^L \to \{0,\hspace{-0.02 in}1\}^L \;\;$ by $\;\; \operatorname{mbx}\left(b_0\hspace{.02 in}b_1\hspace{.02 in}b_2\hspace{.02 in}...\hspace{.02 in}b_{L-2}\hspace{.02 in}0\right) \: = \: 0\hspace{.03 in}b_0\hspace{.02 in}b_1\hspace{.02 in}b_2\hspace{.02 in}...\hspace{.02 in}b_{L-2}$
and $\;\;\;\;\;\; \operatorname{mbx}\left(b_0\hspace{.02 in}b_1\hspace{.02 in}b_2\hspace{.02 in}...\hspace{.02 in}b_{L-2}\hspace{.02 in}1\right) \;\;\; = \;\;\; 0\hspace{.03 in}b_0\hspace{.02 in}b_1\hspace{.02 in}b_2\hspace{.02 in}...\hspace{.02 in}b_{L-2} \:\: \text{xor} \:\: c_0\hspace{.02 in}c_1\hspace{.02 in}c_2\hspace{.02 in}...\hspace{.02 in}c_{L-1} \;\;\;\;\;\;$.
Define $\;\; \operatorname{mbx}^0 : \{0,\hspace{-0.02 in}1\}^L \to \{0,\hspace{-0.02 in}1\}^L \;\;$ by $\;\; \operatorname{mbx}\left(b_0\hspace{.02 in}b_1\hspace{.02 in}b_2\hspace{.02 in}...\hspace{.02 in}b_{L-1}\right) \: = \: b_0\hspace{.02 in}b_1\hspace{.02 in}b_2\hspace{.02 in}...\hspace{.02 in}b_{L-1} \;\;$.
For all non-negative integers $n$, define $\;\; \operatorname{mbx}^{\hspace{.01 in}n+1} : \{0,\hspace{-0.02 in}1\}^L \to \{0,\hspace{-0.02 in}1\}^L \;\;$ by
$\operatorname{mbx}^{\hspace{.01 in}n+1}\hspace{-0.01 in}\left(b_0\hspace{.02 in}b_1\hspace{.02 in}b_2\hspace{.02 in}...\hspace{.02 in}b_{L-1}\right) \: = \: \operatorname{mbx}^n\hspace{-0.01 in}\left(\operatorname{mbx}\left(b_0\hspace{.02 in}b_1\hspace{.02 in}b_2\hspace{.02 in}...\hspace{.02 in}b_{L-1}\right)\right) \;\;\;$.
For bitstrings $\;\; \mathbf{a} \: = \: a_0\hspace{.02 in}a_1\hspace{.02 in}a_2\hspace{.02 in}...\hspace{.02 in}a_{L-1} \;\;$ and $\;\; \mathbf{b} \: = \: b_0\hspace{.02 in}b_1\hspace{.02 in}b_2\hspace{.02 in}...\hspace{.02 in}b_{L-1} \;\;$,
let $\:\langle \mathbf{a},\hspace{-0.02 in}\mathbf{b}\rangle\:$ denote $\;\;\;\; a_0 \hspace{.02 in}\text{&}\hspace{.03 in} b_0 \;\; \text{xor} \;\; a_1 \hspace{.02 in}\text{&}\hspace{.03 in} b_1 \;\; \text{xor} \;\; a_2 \hspace{.02 in}\text{&}\hspace{.03 in} b_2 \;\; \text{xor} \;\; a_{L-1} \hspace{.02 in}\text{&}\hspace{.03 in} b_{L-1} \;\;\;\;$.
For all members $s$ of $\{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,...,\hspace{-0.03 in}L\}$, $\:$ define $\;\; \operatorname{BLE}_{\mathbf{c}}^s \: : \: \{0,\hspace{-0.02 in}1\}^L \hspace{-0.01 in} \times \{0,\hspace{-0.02 in}1\}^L \: \to \: \{0,\hspace{-0.02 in}1\}^s \;\;$ by
$\operatorname{BLE}_{\mathbf{c}}^s(\mathbf{a},\hspace{-0.03 in}\mathbf{b}) \;\; = \;\; \left\langle \hspace{-0.03 in}\operatorname{mbx}^0\hspace{-0.02 in}(\mathbf{a}),\hspace{-0.02 in}\mathbf{b}\hspace{-0.04 in} \right\rangle \: \left\langle \hspace{-0.03 in}\operatorname{mbx}^1\hspace{-0.02 in}(\mathbf{a}),\hspace{-0.02 in}\mathbf{b}\hspace{-0.04 in} \right\rangle \: \left\langle \hspace{-0.03 in}\operatorname{mbx}^2\hspace{-0.02 in}(\mathbf{a}),\hspace{-0.02 in}\mathbf{b}\hspace{-0.04 in} \right\rangle \: ... \: \left\langle \hspace{-0.03 in}\operatorname{mbx}^{\hspace{.01 in}s-1}\hspace{-0.02 in}(\mathbf{a}),\hspace{-0.02 in}\mathbf{b}\hspace{-0.04 in} \right\rangle \;\;\;$.

When the user first receives the program, the user generates $\:\mathbf{a} \in \{0,\hspace{-0.02 in}1\}^L\:$,$\:$ then evaluates
and stores $\:\left[\hspace{-0.01 in}\operatorname{mbx}^2\hspace{-0.02 in}(\mathbf{a}),\operatorname{mbx}^2\hspace{-0.02 in}(\mathbf{a}),\operatorname{mbx}^2\hspace{-0.02 in}(\mathbf{a}),...,\operatorname{mbx}^2\hspace{-0.02 in}(\mathbf{a})\hspace{-0.01 in}\right]\:$. $\;\;$ The recursion makes that
computation faster than it would otherwise be, and $\mathbf{a}$ does not need to be kept secret.
To generate random data, the user generates $\:\mathbf{b} \in \{0,\hspace{-0.02 in}1\}^L$
and then outputs $\: \operatorname{BLE}_{\mathbf{c}}^s(\mathbf{a},\hspace{-0.03 in}\mathbf{b}) \:$ as the random data.

For random variables $Z$, let $\:||Z||\:$ denote $\;\; \mathop{\operatorname{max}}_z \: \operatorname{Prob}(Z = z) \;\;$.
(So, $\:||Z||\:$ being small corresponds to $Z$ having high min-entropy.)

For all random variables $X$ and $Y$ taking values on $\{0,\hspace{-0.02 in}1\}^L$, if $\: ||X|| \leq \frac1{2^{b_x}} \:$ and $\: ||Y|| \leq \frac1{2^{b_y}}$
and $X$ is independent of $Y$ then for $U$ uniform on $\{0,\hspace{-0.02 in}1\}^L$ and independent of $Y$,
for all functions $\;\; \mathcal{D} \: : \: \{0,\hspace{-0.02 in}1\}^L \hspace{-0.01 in} \times \{0,\hspace{-0.02 in}1\}^s \: \to \: \{0,\hspace{-0.02 in}1\} \;\;$,
$\left|\operatorname{Prob}\left(\mathcal{D}\left(Y,\operatorname{BLE}_{\mathbf{c}}^s(Y,X)\right) = 1\right)-\operatorname{Prob}(\mathcal{D}(Y,U) = 1)\right| \;\; \leq \;\; 2^\left(-\left(b_x+b_y+2-(L+s)\right)\right) \;\;\;$.

-
As far as I know those theoretical constructions have no known practical advantages over simply hashing it all using a cryptographic hash function. –  D.W. Jun 12 '13 at 20:21
Thanks, but not sure I have enough maths knowledge to understand all the notation in the first PDF. Can you summarise it in layman's terms for me what I need to do? –  zuallauz Jun 13 '13 at 8:28

If you have access to microphone these papers describe a method to generate true random number.

Nur Azman Abu and Zulkiflee Muslim, Random Number Generation for Cryptographic Key, Proceedings International Conference on Engineering and ICT, ICEI 2007, 27–28 November 2007, Melaka, Malaysia, Volume 1, pp 255–260.

Nur Azman Abu and Zulkiflee Muslim, Random Room Noise for Cryptographic Key, Proceedings IEEE International Conference on Digital Ecosystem and Technologies DEST2008, 27–29 February 2008, Phitsanulok, Thailand, pp381–387.

and this thesis proposed a method to generate pseudo random numbers from microphone input in computing devices.

-
+1, Good point. –  Pacerier Jun 10 at 1:04

The PuTTYgen program, which is open source, contains the following comment in WINPGEN.C where it collects mouse movement for key generation:

/*
* My brief statistical tests on mouse movements
* suggest that there are about 2.5 bits of
* randomness in the x position, 2.5 in the y
* position, and 1.7 in the message time, making
* 5.7 bits of unpredictability per mouse movement.
* However, other people have told me it's far less
* than that, so I'm going to be stupidly cautious
* and knock that down to a nice round 2. With this
* method, we require two words per mouse movement,
* so with 2 bits per mouse movement we expect 2
* bits every 2 words.
*/


I don't know how accurate this information is. I just remembered seeing it and though it was worth sharing.

-
It may even be lesser than that, considering users usually draw circles or do zig-zag-zig-zag-zig-zag. –  Pacerier Jun 10 at 1:00

Part 1

There are some methods to do it.

Get the last four bits from x, the last four from y, concatenate them, XOR them with the last 8 bits that you get from your system timer (or from the fastest timer you have available)

you can specify mouse movements to be a source of entropy

• what I would do:

Get your mouse position X, Y (last 4 bits of each), time it was collected (last 4 bits of each), concatenate everything.

Have a pool of random bytes. When a new random number is requested, get the last number, XOR it with the concatenation above, hash it with some hash (like SHA-1, SHA-2, MD5), use the last x bits, update the random pool with this number.

Part 2

And just to add up: it's not because you're using the mouse inputs that you'll have real random number. The numbers got from OS, etc, are called pseudo-random because if you give them the same inputs again, it'll generate the same random number.

If you use mouse moviments, the same thing will happen: you'll have a number that could be generated again, if someone moved it in the same way, etc.

Real random numbers are hard to get. Some devices use quantum effects to get it, for example. Wikipedia is your friend here.

-
downvoter, would you mind to comment / improve my answer and help me (and others) have a better understading? –  woliveirajr Jun 13 '13 at 13:36
I didn't downvote! I'm still processing this answer. Lets say I have X and Y coordinates of 478,702 out of a usable screen space of 1920×1080 pixels. Converting these numbers to binary gives me 001101000011011100111000 for 478 and 001101110011000000110010 for 702, which is 24bits long. In the phrack article I'm only seeing numbers with 16bits of binary code. I think he did his testing in a small portion of the screen ie 99x99 pixels? The largest number I might have is 1920 00110001001110010011001000110000 which is 32bits. Are you saying I can't use all of that and only the last 4 bits? –  zuallauz Jun 13 '13 at 22:49
the idea from the article is that when you make small movements with your mouse (let's say move from 400 to 403), the leftmost bits won't change, but the last four ones will... See how 478, 702 and 1920 all begin with 00110... why bother using those bits, that are constant? That's the idea of the article. :-) I didn't say you downvoted it, just someone did and I was curious why... –  woliveirajr Jun 18 '13 at 1:06

For your questions 1 and 3, you want to know how to convert mouse movements into usable random numbers. Others have made good suggestions there. If the PuTTYGen comments are to be believed, one movement could contribute as much as 2 bits of uncertainty. As you have stated that this project is for fun, this seems like a good place to do an experiment of your own. Multiplication, however, is likely not an effective way to combine the bits to make them particularly random. Instead, I would concatenate the mouse bytes and once I gathered enough data that contained 256 bits of uncertainty, (128 mouse readings, if the 2 bits-per-mouse-movement figure is to be trusted) I would run the concatenated data into a SHA-256 hash algorithm, and the resultant digest value would be my string of random bytes.

I don't personally believe that mouse movements should be the only source of randomness, so I would be mixing in other information as well, but that's not what you asked.

For question 2, it looks like you're trying to use the random data as a one-time pad (OTP), also known as a Vernam cypher, to encrypt some ASCII bytes. The pre-computer way of doing this was to use a random number from 0-25 and shift the character by that many places. In the computer world, we normally use a byte-for-byte XOR operation, where one byte of plaintext is XORed with one byte of random data.

-
OK sure I could include some other entropy sources later into the entropy pool, mouse clicks, time between mouse clicks, keyboard and hardware entropy. Let's say my program returns X and Y mouse coordinates 478,702. This is out of a usable screen space of 1920×1080 screen size. So you're saying concatenate them, then that would become 478,702 but if I run that through an ASCII to binary converter I actually get 7 bytes 0110100 0110111 0111000 0101100 0110111 0110000 0110010. –  zuallauz Jun 13 '13 at 21:51
fgrieu above says to keep the comma in to separate the numbers because you might get two different coordinates 20,111 and 201,11 but they would be the same number 20111 when concatenated together. Putting the comma in keeps them separated and will result in a different hash. –  zuallauz Jun 13 '13 at 21:58
My questions then would be, how does the mouse x and y only produce 2 bits of randomness per mouse movement? Also if I was joining the numbers together in a big string to consolidate 128 mouse readings before hashing, does having that many commas in the string reduce the entropy? –  zuallauz Jun 13 '13 at 22:10
The reason a mouse movement has very little entropy is that there is very little randomness going into it. If your hand is moving mostly left, you will generate 50 pairs of numbers that vary predictably in a sequence: 478,702 477,702 476,702 475,703, 474,703 473,703 etc. The entropy (unpredictability) comes primarily from changes in direction, which certainly don't happen with every mouse reading. ASCII or binary has nothing to do with it - it's simply not very random. –  John Deters Jun 14 '13 at 20:08
Furthermore, you have to understand that ASCII and binary are simply different readable ways for humans to understand the value. 7 apples means 7 apples, regardless if I write it in text "seven apples", decimal "7 apples", or binary "0111 apples". Inside the computer, the mouse value of 478 is stored in a two-byte or four-byte integer. Simply take those two or four bytes, and place them in a buffer. Take another mouse reading, and place them next to the first bytes. Repeat until you have placed as many mouse readings as you have determined the amount of entropy in a mouse reading to be - –  John Deters Jun 14 '13 at 20:13

This is a very detailed description about creating random numbers and how to "distill" randomness from various sources into a single number. It is an older article, but it has its truths.

A good way to get a single random number from various sources is concatenation-then-hash. Since you're doing this for fun, you don't really NEED to consider the minimum entropy of mouse movement, but you should not use the entire number itself. Let's say we want to have 6 bit from each coordinate. Then we calculate $$r = x \text{ mod } 2^{6}\\ s = y \text{ mod } 2^{6}$$ This gives you a fairly even distribution of $(r,s)$ even if you move the mouse only in a certain part of the screen. For an exact analysis of YOUR mouse, you need to do some statistical tests (e.g. if your mouse produces only even numbers, this doesn't work properly). You also might want to make sure, that you throw away x and y, if they are the same as the previous position (no movement). Once you collected enough pair $(r_i,s_i)$ you can just concatenate them and use a decent cryptographic hash function (e.g. SHA-256). If you want to use the entire hash output for random symbols, you should put at least 22 pairs $r_i,s_i$ (assuming 12 bit of entropy each) together, to match the resulting 256 bit output.

From the output $h$ of the hash function you can either go various ways:

• Pick 7 bits from the output and interpret as characters. Throw away numbers beyond your character set (otherwise you get an uneven distribution).
• Arithmetic calculation: Use $(h \text{ mod } 95)$ for your first character and then set $(h = h / 95)$. Then use $(h \text{ mod } 95)$ is your next char, etc.
• Seed a cryptographically pseudo random number generator with $h$ and extract numbers from the resulting stream. You can do fancy constructions like seed a PRNG with $h$, take a number of bits for characters and then take a number of bits, XOR them with the next hash value and use this as a new seed for the PRNG.
-