tech-kern archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Towards design criteria for cprng_fast()
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
Home |
Main Index |
Thread Index |
Old Index