Run-time tests for random number quality

[mjb]

In light of recent events do you think it would be useful to include run-time tests for random number quality, such as Dieharder, into MultiBit?

Java has many different implementations and a popular Java/OS combination with weak random number generation could be very detrimental to MultiBit's (and Bitcoin's) public image - even if it is not MultiBit's fault at all.

The question is whether one can implement a sensible and fast test that can be run each time MultiBit starts up (in the background) or at least when MultiBit detects a change of the JRE used.

Bundling the JRE could be another option - although even in this case a random number test could be performed just to be on the safe side. Finally, foregoing Java libraries altogether for random number generation could be another way of avoiding what is happening with Android wallets right now.

[jim618]

Hi mjb,

That is an interesting suite of tests.
I think it is the sort of thing that would make a very interesting comp sci/ stats dissertation or PHD rather than something you want running on every MultiBit start up.

The main reason for this is that most people don't have a good grasp of probability. For instance something significant at the 95% level in stats isn't *especially* unusual - it normally means there might be something to look into further. However a "1 in 20" chance people consider to be a real coincidence - or in gambling that they have a canny system and are beating chance BIG TIME.


From the number of MultiBit downloads (2,000 to 2,500 a day) I estimate there are probably 50,000 downloads of MultiBit that are currently active.

Say each of these is used just a couple of times a week and runs a random number quality test when it starts up. So you are running 100,000 tests a week. Assume for a moment that the random number generator is fine.

However, due to the number of tests being done:

5,000 of these will differ from random at a 95% confidence level.
1,000 of these will differ from random at the 99% confidence level.
100 of these will differ from random at the 99.9% confidence level.

So that is a thread on reddit or bitcointalk *every week* with 100 comments saying:
"OMG my random number generator is 99.9% broken".
"So's mine"
"And mine"
etc

However that would just be false positives due to the nature of stats tests.

That isn't to say testing the random number generator is a bad idea but continuous mass testing is guaranteed to create false positives, which then would get preferentially reported using social media.

[mjb]

I see where you are coming from.

From the Dieharder web site:

dieharder is a tool designed to permit one to push a weak generator to unambiguous failure (at the e.g. 0.0001% level), not leave one in the "limbo" of 1% or 5% maybe-failure.

So that would be a one in a million false positive rate. This is probably still too high for testing at every start-up (and probably too resource-demanding).

What about making it a MultiBit/bitcoinj command line option so only experienced (and sufficiently paranoid) users can easily test their PRNG.
In case of test failure MultiBit could come up with a message such as:

The PRNG test failed with 99.9999% certainty. This could still be a false positive. Do you want to submit anonymous information about your OS / JRE to the authors of MultiBit/bitcoinj?

Only if you get more than one independent failure report (--> 1E-12 false positive rate) about a setup there may be reason to act.

A quick Google search brings up two Java random testing suites:
http://sourceforge.net/projects/jrandtest/
http://www.r-project.org/conferences/DSC-2001/Proceedings/Narasimhan.pdf

[jim618]

That would be a pretty interesting tool.
You only need a command line interface for it - no need for a gui.

I hope someone writes one and tests it out !
(Ah the beauty of open source)

:-)

[phr33]

I've been working with validating true RNG's awhile back and just want to point out that it's anything but straightforward.

Sure you can run output numbers through test suits like dieharder etc, but they only catch specific types of errors like the distribution of patterns in a binary stream. The simplest example is that it checks that there are roughly equal amount of 1's and 0's.
A random number generator usually consist of some source of entropy. This could be a radiation monitor, moving your mouse around, a webcam on a lava lamp or whatever. It could also be pure user input. This is passed through a "whitener", which makes sure we gt data with characteristics of white noise. It's deterministic and could for instance be a standard hash function like sha2.
My point is that as soon as you include the whitener you are most likely going to hide all non trivial defects of everything before the whitener. All your fancy tests suits are going to statistically accept what is coming out.
It's trivial to make something that is trivial to crack, but still passes statistical tests.

One option is to instead monitor the entropy source. But such sources are most likely not to pass test like dieharder. After all, that's why they are coupled with whiteners.

I don't know the details on the recent android bug, but it sounded like it was something with reusing seeds. So rather than looking at consecutive random numbers during a session one should compare different sessions with eachother.

I'm not sure what you can take from my post other than "it's not easy". Please have a think about what you really want to test before spending too much time setting up dieharder tests and alike in potentially the wrong places.

Thanks for a great app and good luck!

[jim618]

Hi phr33,

Thanks for your input.
I think you are right that it is a difficult task (which is probably why that Android bug slipped through testing etc).

I can imagine your boss tapping you on the shoulder and saying:
"phr33 - just check these random numbers are random, you'll be done in 10 minutes won't you?"

Weeks later you are still at it.
:-)



My personal feeling is to crack on with the existing MultiBit work before starting anything else significant I must admit.

[mjb]

Thanks for the valuable feedback - it looks like testing for randomness is much harder than taking additional precautions in case of a failing system-level PRNG.

Interesting discussion in another thread (emphasis mine):

Your better off concatenating and then hashing the concatenation to the needed size. XORing is not a good idea. To see why, consider which of these is safer (where | is concatenation).

1) XOR(SHA256(X), SHA256(X))

2) SHA256(X | X)

The former is zero no matter what X is. The latter is safe so long as X is safe.

Now, consider this. X and Y are fairly random but, due to a broken PRNG, only differ in a few bits. Which is safer:

1) XOR(X, Y)

2) SHA256(X | Y)

The former can be insecure even if both X and Y are secure alone because all the common bits drop out. 2 is at least as strong as the stronger of X alone or Y alone.

So asking the user for additional random input (the "Y", for instance by "randomly" banging the keyboard for 100 characters) seems to do no harm, at least, and could prevent catastrophic failures that hit many users at the same time and allow for time to react (key rotation etc).