[PLUG] Security Flaw in RSA/SSL Found

[Keith Lofstrom]

On Tue, Feb 14, 2012 at 11:56:49AM -0800, Rich Shepard wrote:
>   For those working to keep financial and personal data secure, and for
> those who want something else about which to fret, is this NY Times article:
> 
>                         <http://tinyurl.com/6qedb5h>
> 
>   Most of us probably don't need to worry excessively. I'd like to read what
> Bruce Scheier has to write about this.

What they identified was flaws in two databases of products of
allegedly random numbers.  With luck, those were put there to
troll for researchers.   Probably not, sigh.   Random is hard.

I sell hardware random numbers (I hope).  ALL random numbers
are hardware random numbers.   Some come from hardware running
software that is seeded from limited entropy that may have
unexpectedly high correlation.  Your computer did not get a
correlation/entropy test before it was shipped. 

If your entropy generator is dependent on the user flailing
at "random" on the keyboard and looking at timing, the keys
won't be all that random.  Hands and fingers trajectories
are predictable by physics and psychology.  Timing resolution
is dependent on the keyboard scan rate (80 to 400Hz), not
the exact microsecond your finger landed on the key.  If
the scan rate was faster, your keyboard would emit a lot
more detectable EM radiation, making you vulnerable to
a TEMPEST attack. 

With the right model, I bet the entropy of keyboard banging
will turn out to be a LOT less than programmers imagine.

A lot of things are like that.  Hardware designers try to
design entropy OUT of their systems, so they behave more
predictably and are less likely to fail.

Those "random" numbers are used as a seed for a polynomial
generator.  That generates a lot of numbers, most of which
are not primes.  Primality can't be proved, but it can be
strongly conjectured by repeatedly running so-called
"orthogonal" tests, each one doubling the confidence that
the number is prime.  You might run a thousand tests, and
expect the chance that a surviving candidate is not a prime
is one in 2^1000.  But if there is any correlation at all
in the tests, not between a pair, but in large combinations
of them when applied to the subset of seeds your entropy
generator produces, you are hosed.  And how do you examine
all the combinations?  The math becomes much too hard.
You just hope a lot, and ignore the fact that many eyes
tend to make all secrets public.

Even if the numbers really are prime, this kind of test
is a sieve - it throws out non-primes with high confidence,
but it also throws out plenty of primes.  There may be
detectable patterns in that, "the ghost of the sieve",
resulting in a subset of possible primes that are far more
predictable than you would like.

The first question about random /must/ be:  how can you tell?
The second question is, what are the consequences of a failure?

There are two applicable xkcd cartoons:

http://xkcd.com/221/   and   http://xkcd.com/538/

Keith

-- 
Keith Lofstrom          keithl at keithl.com         Voice (503)-520-1993
KLIC --- Keith Lofstrom Integrated Circuits --- "Your Ideas in Silicon"
Design Contracting in Bipolar and CMOS - Analog, Digital, and Scan ICs