2
$\begingroup$

I'm implementing an entropy gathering program.

For that I collect 2 bits from two gpio-pins connected to a random source. I whiten this stream of bits using the von Neumann decorrelation algorithm. Now 2 out of 4 cases I can't use the bits because of that whitening algorithm (e.g. when both bits are 0 or both are 1). The timestamp when I have to discard bits is random.

My question now is: I use the value of the two bits, can I now also use that bit-discard-timestamp as an entropy source? Or are these (the values and the timestamps) correlated? I think they are not neccessarily correlated but I'm not entirely sure.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ If in doubt => don't use it. What is your system design? What do you do with those bits, specifically? If you use them to reseed a PRNG periodically, it should not be an issue to have your hardware RNG being slow, it is much more important for it to be secure. $\endgroup$
    – Dmitry Janushkevich
    Jul 16, 2014 at 7:56
  • $\begingroup$ The system is a simple random number generator that should be fairly secure. The current version does 1k bit per second and passes the "dieharder" rng test. I'm looking for ways to speed it up by finding other sources of random bits in the system. $\endgroup$
    – Folkert van Heusden
    Jul 16, 2014 at 8:12
  • 1
    $\begingroup$ Hmm. You might want to read this as it explains the design of Linux RNG pretty well. It is exactly about how to speed things up with less "true randomness". $\endgroup$
    – Dmitry Janushkevich
    Jul 16, 2014 at 8:27
  • $\begingroup$ Yes, I'm familiar with what is written there. $\endgroup$
    – Folkert van Heusden
    Jul 16, 2014 at 8:37
  • 1
    $\begingroup$ @Folkert Simply because if your code is to be used in production, it would make much more sense to use techniques tested and proven in other applications. It makes life easier for someone who will support this after you, and chances to get it wrong are less. If it is for your leisure activities, then naturally, feel free to use anything. :-) $\endgroup$
    – Dmitry Janushkevich
    Jul 16, 2014 at 9:54

2 Answers 2

Reset to default
3
$\begingroup$

The values of these timestamps appear to be determined by two components:

  1. when your code decides to sample the GPIO inputs; and
  2. whether a bit is to be discarded or not.

The first component is not proven to be random (and if you assume it is, you would not need to add complexity to this RNG; just create a second RNG based on CPU execution jitter).

The second component is the same information that you have already used in the whitener. In other words, if an attacker can make some (partial) predictions about the raw GPIO inputs, then the timestamps are predictable, too.

Please note that the Wikipedia page you linked is not a complete description of the von Neumann algorithm; if you click through to Von Neumann extractor, you see that this algorithm requires that the source is a Bernoulli sequence. Almost all physical noise sources fail this because their output values are correlated.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, the attacker problem is something I choose to ignore: if someone gets physical access to the setup all is lost anyway. You made a very interesting note regarding that additional notes on the V.M. algorithm, did not know about it! Regarding point 1: I would think there is jitter in the cpu-clock as there is in all (well most) clocks as well. I'll do an experiment with an oxco to see how much it is. Thanks! $\endgroup$
    – Folkert van Heusden
    Jul 16, 2014 at 12:38
  • 1
    $\begingroup$ A prediction can be something like "a bit has a 70% chance of being equal to the last bit", which does not need physical access. $\endgroup$
    – CL.
    Jul 16, 2014 at 12:50
0
$\begingroup$

Assuming the random source is a Bernoulli process such that the von Neumann corrector can make it perfectly random, the bits are, by definition, uncorrelated with anything else, including your timestamps.

In the real world that assumption may not hold, but in that case your existing von Neumann corrected random stream is also faulty.

That said, the timestamps may still not be a good entropy source, even if they are uncorrelated with your random source. There is a widely held belief in the Linux kernel circles, for example, that clock jitter is just a black box PRNG that someone might analyze and break.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm not sure if it is the clock jitter in general that is suspect. If you know your hardware and know which clocks have seperate clock-sources (like the watchdog and the main clock in the arduino), then that is definately a good source. I think that the page you point to complains about measuring jitter in execution of a couple of instructions which is different. I think haveged is doing this. $\endgroup$
    – Folkert van Heusden
    Jul 17, 2014 at 13:29
  • $\begingroup$ @FolkertvanHeusden, maybe so, but the problem of estimating how much entropy there is in the signal remains. $\endgroup$
    – otus
    Jul 17, 2014 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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