CPRNGs and assurance...

[Jerry Leichter]

On Dec 17, 2008, at 3:18 PM, Perry E. Metzger wrote:
>
> I'd like to expand on a point I made a little while ago about the
> "just throw everything at it, and hope the good sources drown out the
> bad ones" entropy collection strategy.
>
> The biggest problem in security systems isn't whether you're using 128
> bit or 256 bit AES keys or similar trivia. The biggest problem is the
> limited ability of the human mind to understand a design. This leads
> to design bugs and implementation bugs. Design and implementation
> flaws are the biggest failure mode for security systems, not whether
> it will take all the energy in our galaxy vs. the entire visible
> universe to brute force a key.
>
> So, if you're designing any security system, the biggest thing on your
> mind has to be how to validate that the system is secure. That
> requires ways to know your design was correct, and ways to know you
> actually implemented your design correctly....
Excellent points.

For the particular case of random generators based on mixing multiple  
sources, I would suggest that there are some obvious - if, apparently,  
little-used - testing strategies that will eliminate the most common  
failure modes:

1.  Test the combiner.  The combiner is a deterministic function.  If  
you give it known inputs, the results will always be the same.  The  
result is supposed to depend sensitively on all the inputs, so if you  
change any input, you should get very outputs.  This kind of testing  
would have avoid the Debian fiasco.

Note that knowing you have to write such a test will also discourage  
throwing in all sorts of complexity you don't understand because "it  
can't hurt".  It can, and has.

2.  There are many tests you can apply that will detect *non*- 
randomness.  Test the *inputs* to your combiner.  If an input  
consistently fails, think about whether it's adding adding enough  
value to be worth the complexity.  If your inputs normally succeed and  
start failing ... something is wrong.

Since it's cheap to do, you might as well apply the same test to the  
output of the combiner - but don't expect to learn anything:  With any  
decent combiner, even fixed inputs should produce random-looking  
output.  So any problem detected this way is very serious.
                                                         -- Jerry

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com