Towards design criteria for cprng_fast()

[Thor Lancelot Simon <tls%panix.com@localhost>]

I would like to offer some observations about the use of cprng_fast()
(once known as arc4random()) in our kernel and, from these, express
what I believe are reasonable design criteria for that function.

O1) cprng_fast() is used in some performance-critical parts of the kernel:

        A) It's used to permute memory mappings

        B) It's used, indirectly, at every program startup, because its
           output is sucked down by userspace via sysctl() for use by SSP.

        C) It's used to generate initialization vectors for other ciphers,
           including for use by line-rate crypto accellerators.

        D) It appears that it can be called per-packet by a few parts of
           the networking stack in some cases -- ALTQ, possibly ip_id.

O2) cprng_fast() is *never* used to encrypt data.

        A) This would seem to imply that IV generation for other ciphers
           is its most sensitive use.

        B) We can swap out the algorithm underlying cprng_fast() at any
           time with no compatibility concerns.

O3) cprng_fast() is usually used via cprg_fast32() to generate just 32 bits
    of data at once.

        A) This suggests that whatever algorithm we use, we'll need a way
           to use it to service short requests efficiently.

O4) We have non-cryptographic RNGs in the kernel (random(), mertwist)) which
    seem to exist for two reasons: reproducible testing, and performance.

With those observations in mind, I offer these design criteria for
cprng_fast():

        Strength criterion: At the time of the selection of an algorithm
                              for cprng_fast(), there should be no known,
                              practical cryptographic attack which either:

                A) Recovers the key for the underlying algorithm
                B) Distinguishes the output of the underlying algorithm
                   from a truly random stream

                Within 2^10 times the number of bytes we will generate on a
                single key in the worst case for our generator.

                Rationale:

                A) The algorithm can be changed at will in our
                   sources should any new attack be discovered in the future

                B) The worst consequence of compromise of a key for the
                   algorithm is limited to prediction of future IVs for
                   another, stronger cipher.  Post-hoc analysis of old
                   keystreams is of no value since the subsequent IVs must
                   be assumed to be already known.

                C) 2^10 is a very conservative safety factor for this
                   application, intended solely to buy time to replace
                   existing binary implementations in the field.  We can
                   manipulate the maximum bytes-on-key at will to meet it.

        Speed criterion 1: cprng_fast() should be as fast as possible subject
                           to the Strength criterion and the general mandates
                           of portability and code cleanliness which apply
                           throughout our tree.

                Rationale:
                        A) cprng_fast() is already used in performance
                           critical parts of our tree.

                        B) Where performance motivates the use of any other
                           generator, we would like cprng_fast() to perform
                           as well or better.  The ideal goal is to never use
                           any predictable generator for any reason (for
                           reproducible testing, perhaps a mode should be
                           provided that fixes the keys of cprng_fast()).

        Speed criterion 2: cprng_fast()'s performance should be evaluated
                           primarily with regard to short requests.

                        Rationale: Most of the calls to cprng_fast() in our
                        tree are by way of cprng_fast32().

Final note: We should *always* *immediately* replace the cprng_fast()
algorithm if it ever fails to meet the security criterion given above.  

This is the best *I* can write down what I have been aiming for while
revising cprng_fast() recently.  In the process I have arrived in agreement
with rmind's suspicion that adding that mutex to arc4random() for correctness
during my RNG overhaul two years ago likely had much worse performance
consequences in the real system than I anticipated.

Thor