Can a smartphone’s accelerometer data be used for implementing a TRNG?

Question

I'm trying to generate a true random number from smartphone's accelerometer, then pass it as a seed to a CSPRNG to generate true random numbers.

I know that a lot of people tried it and the SecureRandom (without custom seed) remains a better choice, but I don't understand why this is not possibile.

I've read about some issues about this approach: the accelerometer can generate low entropy, an attacker could guess patterns of movements...

I've also read the Randomness extractor page on Wikipedia, and 2 methods are proposed:

Von Neumann extractor

Cryptographic hash function

Let's suppose I want to use the Neumann approach, a requirement is that:

there is no correlation between successive bits

But have the X, Y and Z input values I collect from the accelerometer a correlation between successive bits? Why? A X value at time t1 could be different at time t2, so they are not in correlation... or not?

If the requirement is satisfied let's suppose the algorithm is something like this:

Get an amount of consecutive X,Y,Z float values from the acceleromenter for, let's say, 10 seconds.

Convert each value to bits and store them into different arrays => X[] Y[] Z[]

For each arrays position use the Von Neumann extractor and create an output bit array.
(ex. I'll check X[i] with Y[i], and the result with Z[i])

Now each 3 input bits will produce 1 output bit

At the end convert the output bit array to value.

Is the output a random value?
Can this be a reliable method?
If not, how can this be improved?

But if I choose the method 2 (the Cryptographic hash function) can I simply hash the input stream obtained from the accelerometer?

Answer 1

The answer depends on several factors...

1. What is the accuracy, sensitivity, sample rate, and precision of the accelerometer?

2. How often is the cell phone being moved around? How is it being moved around?

3. How many "raw" bits are you extracting for every bit in the seed? Only 3?

The root source of entropy

Let's assume that the accelerometer is extremely accurate, is sensitive to very small changes, has a very high sample rate, and has very high precision. Let's also assume that you are moving the device around manually. In this case, the entropy comes from the following sources:

1. Imprecision and "noise" in the accelerometer. More sensitivity means more noise.

2. Stochastic processes present in the operation of our neurons and muscle cells.

If the sensor is accurate enough, then microscopic variations in the biological processes that create muscle movements will result in a significant amount of entropy available for harvesting. The time it takes an action potential to propagate down your neurons, the time it takes to finally depolarize a neuron to its firing threshold, the time it takes a muscle cell to respond to neurotransmitters, which motor units are recruited first in a muscle... These all depend on factors that cannot be predicted by an attacker. While we are terrible at consciously producing an unpredictable string of random numbers, we are, much unlike deterministic computer algorithms, excellent at producing randomness through our naturally imprecise muscle movements.

Note, however, that you would be wise to add in the timing of each motion event, not just the value of the changed coordinates. When you operate at nanosecond precision, even a professional drummer who is trying to move with the most rhythmic patterns possible will introduce significant entropy to a system when his movements are precisely timed. This timing, if sufficiently fine-grained, is actually a more valuable source of entropy than the value of a given event itself.

Your proposed algorithm

I would say your algorithm is not safe. Creating 1 output bit for every three input bits assumes that each input has 1/3 of a bit worth of entropy, which is very optimistic, to say the least. The Linux kernel for example is extremely conservative with its entropy estimation. Only a single bit of randomness is assumed to be present after 64 consecutive injections into a 128 bit pool. A superior algorithm would be to input the raw events along with the precise time of the event (in the form of the number of CPU cycles since boot, aka the TSC) into a fast cryptographic hash like SHA-256. Keep this up until you are done collecting entropy, and use the final digest as your random seed. If you are certain that you want to implement your own RNG, this would be the way to do it. There would be no need for explicit debiasing or whitening, or entropy estimation.

If you truly insist on doing this, you should at least take the output seed and mix it with an equivalent amount of randomness from the system CSPRNG. This can be done by using a involutory operation such as XOR or addition/subtraction with overflow. that ensures that the entropy of the output is at least as good as the quality of the most entropic input. In mathematical notation, for two mutually independent entropy sources A and B of identical size, H(A ⊕ B) ≥ max(H(A), H(B)).

The accelerometer as a source of entropy by default

The accelerometer may already be used to generate entropy! While I know little about mobile device architecture, hardware generally alerts the main CPU that an event has been detected by issuing an interrupt. An interrupt is an asynchronous signal that causes the CPU to pause whatever it is doing and execute a particular handler for that interrupt. This handler may, for example, query a keyboard buffer. That way, the system does not have to continuously poll the keyboard and can instead wait for the keyboard to send an interrupt, telling the system that it is time to read from it. This may also happen with a mobile device's accelerometer. Every time a motion is detected, it may send a signal to the CPU telling it that there is data to be read. Every time this happens, the interrupt data and the exact time it occurred are used as a source of entropy. Only after 64 events is a single bit of entropy assumed to be collected. This entropy is mixed with the system pool.