| |||||||||||||
|
| |||||||||||||
TestingTestingPosted May 21, 2008 4:16 UTC (Wed) by eru (subscriber, #2753)In reply to: Open Source Security Report by orospakr Parent article: Open Source Security Report It is pretty difficult to create an automatic regression test for a module which by its very specification must produce as random results as possible! I guess it could be done, but this probably involves running it millions of times and performing a statistical analysis of the results.
(Log in to post comments)
It's not help... Posted May 21, 2008 7:29 UTC (Wed) by khim (subscriber, #9252) [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...
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.
Testing Posted May 21, 2008 8:34 UTC (Wed) by bvdm (guest, #42755) [Link] There are existing statistical test suites that check for randomness and this is a well explored research area. Hardware (true) RNG generators typically include such tests to guard against physical failure. Given the near ubiquitous of OpenSSL I consider it a shame that such tests are not included in the OpenSSL test suite. The failure mode in the Debian case was so bad that I would venture that even a simple statistical test should have picked it up. Cost due to speed of execution of the test cannot compare to the cost of failure for something this important! Anyone interested in the details should consult NIST Special Publication 800-22 "A Statistical Test Suite for Random and Pseudorandom Number Generators".
Testing Posted May 21, 2008 9:23 UTC (Wed) by tialaramex (subscriber, #21167) [Link] The Debian output should (I haven't checked) pass this test, indeed OpenSSL may well include such a statistical test and it wouldn't have changed a thing. Unless NIST specifies a protocol whereby a large number of such RNGs are tested and the results compared to ensure they are different (which can't be used in a unit test since only one sample is available), it doesn't detect the Debian bug because that bug only removes the entropy from a PRNG seed, and the PRNG output is still pseudo-random, thus passing the test. Statistical tests don't, and indeed can't prove that something is random in the sense needed for most cryptography. They can only prove that the data isn't correlated by the known types of relation handled by the analysis. A program which always outputs... 0, 4, 8, 8, 1, 5, 0, 7 is exactly as "random" as the 10-sided die I just used to actually generate that sequence, so far as a statistical analysis is concerned. Yet for cryptography rolling dice is acceptable (if you do it right) while a program which always outputs that sequence is useless.
Testing Posted May 21, 2008 12:56 UTC (Wed) by bvdm (guest, #42755) [Link] Okay, I was not clear enough. The function of a PRNG is of course to take a small number of bytes of high entropy and turn them into a much longer stream of bytes that has much lower entropy per byte. This is necessary because true high entropy is scarce. So a PRNG solves a "supply and demand" problem. And of course Linux has both /dev/random and /dev/urandom which allows a choice of how much entropy you are guaranteed to get. What I meant was that OpenSSL should have tests where it statistically verifies the quality of its *entropy input*, not the output. This is what hardware RNG's do, they run statistical tests on their entropy input to verify that physical failure of the high entropy phenomenon that is being measured (radioactivity etc.) does not destroy the device's security claims. Hardware devices need to do this because the physical entropy source is typically a single point of failure whereas software PRNG's rely on multiple sources (keyboard strokes, network packet arrival times etc.) The Debian OpenSSL bug went undetected because OpenSSL apparently has no test of the entropy input similar to what hardware RNG's have. I sure that the upstream team carefully verified the mechanism, but given the subtleness by which the bug was introduced, it warrants extra precautions for the future.
Input was perfect! Posted May 21, 2008 13:42 UTC (Wed) by khim (subscriber, #9252) [Link] There are nothing subtle there. OpenSSL used very good source of high entropy: /dev/random. Also there was good PRNG to produce a lot of lower quality entropy. The thing that was at fault was tiny procedure responsible to transfer high entropy to the PRNG pool. In the end it just ignored good source of entropy but shook the pool. So verification of input will be useless: input was not at fault. And verification of output will be hard (as discussed above).
Input was perfect! Posted May 22, 2008 3:07 UTC (Thu) by bvdm (guest, #42755) [Link] You are being disingenuous. Tests can be added at any or multiple levels. And the bug was subtle, just reading the actual code (as in a previous LWN article) does not raise any immediate suspicions.
Testing Posted May 21, 2008 12:58 UTC (Wed) by bangert (subscriber, #28342) [Link] 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...
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".
Testing Posted May 21, 2008 13:47 UTC (Wed) by ajb44 (guest, #12133) [Link] You're talking about different things. A random number generator is required to generate a random *sequence*. In this case, we only want to generate one number, and be sure that our procedure is choosing it from a large set. This bug reduced the size of the set to 2^24, IIRC. Because of the birthday paradox we could detect this in about 2^12 tests. This is not sufficient (because we want a much bigger set than 2^24) but it's probably worth doing.
Not really a unit test Posted May 21, 2008 14:18 UTC (Wed) by tialaramex (subscriber, #21167) [Link] The information I've seen suggested there were at about 2^31 possible initial values for the entropy pool because it was seeded from PID which is usually in the range of a few hundred to 32767 or so on Linux systems. In that case you'd have to run an OpenSSL key generator at least of the order of 100 000 times to get duplicate keys and reject the null hypothesis that the generator produces a random key each time. You must restart OpenSSL each time (most likely by doing this work in a separate process) in order to ensure that it isn't able to keep the entropy pool between keys, since if it does that you will just be testing the PRNG which we already know is strong. A unit test which produces 100 000 distinct keys using OpenSSL would be a real pain. On systems with no dedicated entropy generating hardware it'd almost surely empty the entropy pool, so this "Unit test" suddenly requires either dedicated hardware or a human to go shake things up, otherwise it will hang for long periods waiting for more entropy. This is sounding less and less like a unit test and more and more like an exercise which would be useful in a formal review of the system's security, of the sort which OpenSSL but not Debian has passed previously...
Not really a unit test Posted May 21, 2008 14:36 UTC (Wed) by tialaramex (subscriber, #21167) [Link] Huh, ignore the above particulars since (as any school boy should know), 32767 is a long way short of 2^31 However unfortunately the birthday paradox actually doesn't help you in this case because the "random" factor isn't - you will likely run your unit test on a single machine where PID (the main source of "entropy" left after the disastrous Debian patch) is happily incrementing slowly for each key generator process you run, so you won't get a collision until your PID actually wraps.
Not really a unit test Posted May 22, 2008 3:12 UTC (Thu) by bvdm (guest, #42755) [Link] This bug literally had a global impact. The principle at stake is whether enough control mechanisms exist at present to eliminate future problems. It is well worth considering. Individuals compiling OpenSSL and other FOSS cryptographic packages may choose not to run tests that requires days of processing, but distributions that make modifications are obligated to do so in my opinion.
Testing needs instrumentation Posted May 21, 2008 15:21 UTC (Wed) by dd9jn (subscriber, #4459) [Link] Right, it can be done but the outcome of adding such a test may be worse than without a test. All serious RNG implementations use some kind of hash function before returning the random bytes, thus you can't run statistical tests on the output. To run tests you need to instrument the code. That very instrumentation is a source of bugs and thus it should be avoided. In fact, OpenSSL was recently trapped by such a bug due to extra code added for the FIPS validation of OpenSSL.
|
|
||||||||||||