That's not what these tests do [LWN.net]

That's not what these tests do

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

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.

(Log in to post comments)

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".