It's not help... [LWN.net]

It's not help...

Posted May 21, 2008 8:27 UTC (Wed) by mv (subscriber, #17258) [Link]

The module was designed to be good PRNG too. So statistical analysis will fail. You need to restart it many times and then calculate correlation over million FIRST results. Doable, but SLOOOW - and can be circumvented if someone left time as seed of PRNG...

The output is deterministic though, given the right input.

You could run an automated test with e.g. an LD_PRELOAD wrapper that provides replacements for getpid(), time(), gettimeofday() which return static values. Then feed the PRNG known data using RAND_seed/RAND_add and finally check the output.

That could have caught the missing use of the data provided to RAND_add in the Debian OpenSSL case.

Fighting the last war

Posted May 21, 2008 9:09 UTC (Wed) by tialaramex (subscriber, #21167) [Link]

But now you're very much getting into fighting the last war.

Writing a new unit test for each bug is the sort of thing enthusiastic new students suggest.
But unit tests must be useful enough to justify their continued maintenance. Most unit tests
that "check" a random number source e.g. by statistical analysis would meet that burden, but
wouldn't detect the Debian bug due to it retaining the strong PRNG.

Suppose code of the sort you're suggesting had existed. The Debian developers would have
commented out those lines, rebuilt, run the unit tests, and the entropy test fails.
"Unexpected PRNG output" it says. They find that it compares one known output with the output
from OpenSSL, they conclude that the "uninitialised data" was contaminating this output, and
they "improve" their patch to update the unit test. Now it passes unit tests, the little boy
is still shouting "Wolf" but no-one is coming to save him.

Fighting the last war

Posted May 21, 2008 16:42 UTC (Wed) by stephen_pollei (guest, #23348) [Link]

There is nothing that said that you couldn't do both at the same time. make the time etc
static and test the statistical properties of the output. In fact if you did both you might
find marginal cases which a test of one without the other would have missed.

Not even fighting the last war

Posted May 22, 2008 11:39 UTC (Thu) by tialaramex (subscriber, #21167) [Link]

So your proposal is to create an unchanging environment in which OpenSSL can run, and then run
it several times, using statistical tests to ensure that the random output is statistically
independent between runs despite holding all of the environment (except /dev/random
presumably) constant. That sounds like quite a serious piece of work, how much development
time do you think it would take to build a robust and portable version of that test ?

You can come up with all sorts of sufficiently arbitrary tests that would so happen to be
tripped by this error but they all incur a maintenance cost and don't seem to really justify
it with a rationale as to what proportion of real world bugs they'll catch other than this one
which we already fixed.

Running MD5 over the released OpenSSL source and having a unit test fail with "Stop messing
with things you don't understand" if you've changed it would also have been an effective way
to detect this bug, but I don't think we're really considering that.