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