| |||||||||||||
|
| |||||||||||||
The tests don't need to do thatThe tests don't need to do thatPosted May 21, 2008 21:34 UTC (Wed) by man_ls (subscriber, #15091)In reply to: That's not what these tests do by tialaramex Parent article: Open Source Security Report 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?
(Log in to post comments)
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".
|
|
||||||||||||