Testing [LWN.net]

Testing

Posted May 21, 2008 12:58 UTC (Wed) by bangert (subscriber, #28342)
In reply to: Testing by tialaramex
Parent article: Open Source Security Report

writing a test that ensures a PRNG is indeed a PRNG is dificult.

the debian openssl bug however, could have been found by a test that 
ensures that the PRNG generates more than 16bits of random data. i suppose 
checking for 28 or 29 bits should still be pretty fast. 16 bits is abysmal 
and should be caught immediately.

also the slowness factor is really not a problem for a binary 
distribution. i wouldnt mind if openssl had an extended testsuite which 
ran for a couple of days...

(Log in to post comments)

Testing

Posted May 21, 2008 13:13 UTC (Wed) by bvdm (guest, #42755) [Link]

The NIST document describes the range of available statistical tests for PRNG's well enough,
but that's not what I am suggesting.

The OpenSSL bug was made possible because OpenSSL has its own layer of entropy processing on
top of sources such as /dev/random on Linux. This is because OpenSSL needs to support
platforms where /dev/random is not available. So even in the presence of a the high quality
entropy source /dev/random on Debian, a bug in OpenSSL negated that entropy. So I am arguing
that OpenSSL needs to have a test suite on top of their entropy stack to detect future bugs.

That's not what these tests do

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

Here are two data sets, one has 8-bits of true random data input, the other has 16-bits of
true random data input, but like the Debian OpenSSL implementation in each case the actual
data is PRNG output, just one has a smaller range of possible seed values. Simply reply
showing how you algorithmically determined which was which with the generous list of values I
provide...

(Or since that's practically impossible for the reasons I already explained, go away and learn
about PRNGs and seeding and make sure you don't touch any crypto software)

set 1: 9, 89, 64, 12, 49, 19, 72, 28, 34, 6, 9, 31, 65, 73, 17, 28

set 2: 9, 50, 30, 22, 36, 89, 29, 7, 82, 65, 77, 30, 42, 54, 83, 77

I am getting bored of having to roll dice to prove my point here. Please, further
contributions only from people who've both looked at the code in question and already know a
little about the subject.

The tests don't need to do that

Posted May 21, 2008 21:34 UTC (Wed) by man_ls (subscriber, #15091) [Link]

There is a possible mechanism to check not the input, but the output of ssh-keygen. The test could only generate a certain number of keys and check that none of them are repeated. With the Debian hole you would have to generate at most 2^16 keys to find a collision. Given that it took a few hours to generate all the compromised keys, we might expect that the whole process shouldn't last much more than that. Of course the generation might be optimized. In fact on my machine ssh-keygen for RSA with the default key length takes less than 2 seconds; so creating 65536 keys might be done in about 36 hours.

But the process might even be quite shorter. Given that a birthday attack is possible, only about the square root of the number of possible keys is needed. Even less if the keys are not evenly distributed, which was the case. So in this case less than 8 minutes of random generation of keys might have found the security hole, on my hardware. It should be trivial to check this approach in practice, wouldn't it?

A long test ahead

Posted May 21, 2008 23:58 UTC (Wed) by man_ls (subscriber, #15091) [Link]

Uh... I should have read to the end of the comments first, sorry for that. I see that below you mention the birthday attack, and then discard it because the only entropy comes from the process ID which will not repeat itself until it rolls around. So the PRNG is fed with sequential data, and is not random enough even to create a birthday collision.

The time to generate the compromised keys is just a couple of hours -- on a 31-processor cluster. It makes sense that on my lowly AMD64@2.0 GHz it takes about 36 hours. I just checked that generating a few thousand keys does not provide a collision. I will let it run for a while until PID wraps, and then check if there are indeed collisions. But you are right that it is hardly a unit test that which might take longer than a day.

A long test ahead

Posted May 22, 2008 6:08 UTC (Thu) by man_ls (subscriber, #15091) [Link]

After running overnight, my little script is already generating duplicate keys as expected. (PID wrapped around some hours ago.) This with libssl0.9.8 version 0.9.8g-1.

One wonders if such a verification would really be useful for a distro, or if it is indeed "fighting yesterday's battle".