[Cryptography] Entropy Needed for SSH Keys?

[Theodore Ts'o]

On Tue, May 24, 2016 at 10:05:16AM -0400, Kent Borg wrote:
> > For example if you read the claims made by the CPU Jitter "True Random
> > Number Generator", it essentially (albeit perhaps slightly unfairly)
> > boils down to "The algorithms L1/L2 cache of an Intel CPU are horribly
> > complex, and no one can figure them out, so we can treat the timing
> > results as true randomness."
> 
> Assume there is no jitter. Just consider that the TSC is running at over
> 2GHz.
> 
> For an observer to know what value the CPU will read, that observer will
> have to know not only how the CPU might jitter (and let's assume zero), but
> also the observer needs to know the state of the clock. Not just how many
> ticks have gone by (hard already), but exactly *where* the edge of those
> ticks are or an LSB value will slip by. The observer needs precise phase
> information.

Right but what are you measuring that CPU clock against?  In the
absence of interrupts if you are running something in a tight loop,
and then periodically sampling the TSC, then if there is no jitter,
the only thing which is unknown is the starting offset of the TSC.  So
maybe that's ten bits of entropy.  But that's *all* which is
unknowable.  Running the jitter "true random number generator"
continuously isn't going to change how bits of initial uncertainty ---
just how many bits you've extracted out.

Keep in mind that on many hardware implementations, there is only a
single crystal-controlled oscillator, and all of the clocks are
generated by using various divide by N circuits.  So you own't even
get any uncertainty caused by two different osclliators beating
against one another.

Now, if you have interrupts, then you may have additional bits of
uncertainty.  But that's not the claim of the jitter true random
number generator.  The claim is that you can run in a tight loop, and
continuously generate lots of high-quality, "true" random numbers.

	     	      	      		    	   	  - Ted