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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

All of the responses so far have answered your question, but it is interesting to note that this method of collecting random mouse movements has been implemented before by a commercial Certification Authority. I speak from first hand experience of using this, because I worked for the company the created it. Baltimore Technologies (now Verizon Enterprise Services) own the UniCERT Certification Authority Suite. This features the seeding of the Blum-Blum-Shub RNG using the collection of random key presses and mouse movements. This, in turn, was used to generate random numbers for RSA keys generated in software.

Answer 5

Part 1

There are some methods to do it.

• Phrack magazine

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)

• are you using java?

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.

• also take a look at this analysis on how linux pseudo-random number generator works.

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.

Answer 6

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:

• Compatibility of window.crypto.getRandomValues()
• Generate cryptographically strong pseudorandom numbers in Javascript?

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).

Answer 7

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.

Answer 8

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) \;\;\;$.

Answer 9

You can use PBKF2 key generation function. Use some integer generated by the mouse movement as the input. PBKF2 function will give you a random output with more entropy than the input.

Answer 10

Actually mouse movements are used in some software and projects to create behavioral fingerprints of users (eg people move their mouses in unique ways ) , so needless to say they are no a very good source of randomness , considering a single person , they contain informations that allow to characterize a user ( with some FAR/FRR of course ).

Answer 11

You can use xinput --test to record mouse movement data and then "crunch" the recorded data into a random hash using a hash algorithm like MD5.

E.g. xinput --list (shows your mouse device id is 15) and you want to collect 5 seconds of mouse data:

$> mouse_data=$(timeout 5 xinput --test 15)

If you want to play around with a script that incorporates this already: https://code.google.com/p/gen-uniq-id/source/browse/gen_uniq_id.bsh

I just finished writing it, it is a fairly robust Bash script that incorporates /dev/urandom, mouse movements, current time and dynamic text into a random md5sum. You can turn some features on/off and modify the length of data collection time via user options.

 ## To generate a random md5sum based on random data collected
 ## over 0.004353 seconds without any collected mouse movement data, 
 ## set text block to "my favorite quote" 
 $ gen_uniq_id.bsh -r".000004353354e+03" -m0 -s"my favorite quote"

 ## To turn off random collection and set mouse collection to 1.5 
 ## seconds, and seed with the last 5 commands from history w/debug on 
 ## to see the internal variables
 $ gen_uniq_id.bsh -d -m1.5 -r0 -s$(history|tail -5) 2>&1 | more

As far as your questions regarding the exergy of mouse movement data, it really depends on the user, if you are going to be rather predictable and slide the mouse up a little when the mouse movement data is being collected you're going to be much more predictable than if you zig-zag like a madman.

The good news is that it shouldn't really matter that much as long as you get some decent random seed, from there it is the strength of the pseudo-random generator. I use my script all the time yet tend to get a bit lazy about moving my mouse when its generating so I made it possible to seed additionally with the history data of my shell. Its not really random but when you combine that in a string with time down to the nanosecond, a little bit of /dev/urandom and some mouse movements you get a fairly decent seed to crunch into a MD5 sum.