Re: [PROPOSAL/PATCH] Fortuna PRNG in /dev/random

["Theodore Ts'o" <tytso@mit.edu>]

On Mon, Sep 27, 2004 at 12:50:33AM -0000, linux@horizon.com wrote:
> > And the ring-buffer system which delays the expensive mixing stages untill a
> > a sort interrupt does a great job (current and my fortuna-patch).  Difference
> > being, fortuna-patch appears to be 2x faster.
> 
> Ooh, cool!  Must play with to steal the speed benefits.  Thank you!

The speed benefits come from the fact that /dev/random is currently
using a large pool to store entropy, and so we end up taking cache
line misses as we access the memory.  Worse yet, the cache lines are
scattered across the memory (due to the how the LFSR works), and we're
using/updating information from the pool 32 bits at a time.  In
contrast, in JLC's patch, each pool only has enough space for 256 bits
of entropy (assuming the use of SHA-256), and said 256 bits are stored
packed next to each other, so it can fetch the entire pool in one or
two cache lines.

This is somewhat fundamental to the philosophical question of whether
you store a large amount of entropy, taking advantage of the fact that
the kernel has easy access to hardware-generated entropy, or use tiny
pools and put a greater faith in crypto primitives.

So the bottom line is that while Fortuna's input mixing uses more CPU
(ALU) resources, /dev/random is slower because of memory latency
issue.  On processors with Hyperthreading / SMT enabled (which seems
to be the trend across all architectures --- PowerPC, AMD64, Intel,
etc.), the memory latency usage may be less important, since other
tasks will be able to use the other (virtual) half of the CPU while
the entropy mixing is waiting on the memory access to complete.  On
the other hand, it does mean that we're chewing up a slightly greater
amount of memory bandwidth during the entropy mixing process.  Whether
or not any of this is actually measurable during real-life mixing is
an interesting and non-obvious question.

						- Ted