RE: Concurrent access to /dev/urandom

David Schwartz
2004-11-30T18:54:29Z

> >Even timer interrupts are incredibly unpredictable. Instructions can
> >take
> >variable times to complete, and all instructions plus some indeterminate
> >cache operations and queue flushing must occur before the CPU can
> >even begin to service an interrupt.
>
> Well, don't timer interrupts happen every 1/1000 s (unless, of
> course, cli() is
> in effect)?

Roughly. If you store the TSC on every timer interrupt, there is nobody in the world that can accurately predict what TSC value you will get. Or, to put it in more precise terms, if you log 100 such TSC values and run an MD5 on all of them together, nobody can predict with better than 50% accuracy the value of any bit of that MD5 output.

> >Also of note, there are small
> >critical
> >sections with interrupts disabled scattered all over the kernel and
> >scheduler,
> >in addition to varying memory latencies, etc. (NOTE: I am not an arch
> >expert
>
> In case you mean the RDTSC, it is of course better than the I8042, for
> random-aphy.

To mine the entropy in the unpredictability of instruction scheduling, cache effectiveness, and slew between the various oscillators in a computer, you need a timing source with the accuracy of the TSC.

You can mine entropy from any two independent oscillators. However, the rate at which you can mine them varies largely upon the frequency of the slowest oscillator. This is why network cards are such good sources of entropy on Pentium machines. You have the network card's oscillator, the oscillator on the network card sending the data to you, and the TSC. All are fast and totally independent.

The timer interrupt may be generated by a clock that ultimately comes from the same source as the TSC clock. This varies from motherboard to motherboard. However, they're generally produced by a PLL that has lots of jitter and slew. So there should be some entropy in there, even without considering unpredictable cache and disk delays.

DS