3

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?

    • 2
      If you rely on this for the source of your entropy what happens if the phone is not moving? Or if it has faulty accelerometers? And just because the accelerometer values will be different at two different times doesn't mean that there isn't a correlation between values. – Neil Smithline Oct 2 '15 at 18:29
    • 3
      Do you have reason to believe that the host platform's secure random function is broken? I think that both iOS and Android are now considered to have secure random functions. If you want to add a new source of entropy to them, that seems fine. But if you replace /dev/random bits with accelerometer, you run the risk of drastically hurting your RNG's security – Neil Smithline Oct 2 '15 at 18:32
    • Thanks for the answers :D But can someone show me an example? In which case the values I obtain are not in correlation? It's not clear to me :/ If I replace the urandom bits with mine the entire RNG will be insecure, so CSPRNG still remains the best choice, because it gets random entropy bits from OS. But I've another question: if I seed a CSPRNG with a truly random seed, what I obtain remains a CSPRNG or a TRNG? Because I found LavaRand, that is considered a TRNG because gets random entropy bits from a picture and use it as seed for a PRNG. So it is not a TRNG but a CSPRNG, right? – Riccardo Leschiutta Oct 6 '15 at 11:47
    • @NeilSmithline, in my experience, there's considerable noise in a smartphone's accelerometer output. – Mark Dec 19 '15 at 9:15
    • @Mark, considerable noise is not the same as cryptographically random. To my eye, insecure PRNG look random but I know they're not secure. – Neil Smithline Dec 19 '15 at 16:35
    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.

    Your Answer

    By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

    Not the answer you're looking for? Browse other questions tagged or ask your own question.