[lkml]   [2003]   [Oct]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [RFC] frandom - fast random generator module
    On Oct 16, 2003  12:31 -0400, Jeff Garzik wrote:
    > Andreas Dilger wrote:
    > > Actually, there are several applications of low-cost RNG inside the kernel.
    > >
    > > For Lustre we need a low-cost RNG for generating opaque 64-bit handles in
    > > the kernel. The use of get_random_bytes() showed up near the top of
    > > our profiles and we had to invent our own low-cost crappy PRNG instead (it's
    > > good enough for the time being, but when we start working on real security
    > > it won't be enough).
    > >
    > > The tcp sequence numbers probably do not need to be crypto-secure (I could
    > > of course be wrong on that ;-) and with GigE or 10GigE I imagine the number
    > > of packets being sent would put a strain on the current random pool.
    > We don't need "low cost RNG" and "high cost RNG" in the same kernel.
    > That just begs a "reduce RNG cost" solution... I think security experts
    > can easily come up with arguments as to why creating your own "low-cost
    > crappy PRNG" isn't needed -- you either need crypto-secure, or you
    > don't. If you don't, then you could just as easily create an ascending
    > 64-bit number for your opaque filehandle, or use a hash value, or some
    > other solution that doesn't require an additional PRNG in the kernel.

    Hmm, so every part of the kernel that doesn't need crypto-secure RNG data
    (i.e. fast and relatively unique) should implement its own hash/PRNG then?
    It isn't a matter of unbreakable crypto, but the fact that we want relatively
    unique values that will not be the same on a reboot. Currently we do just
    as you propose for our "crappy PRNG", which is "grab 8 bytes via
    get_random_bytes and increment", but that is a little _too_ easy to guess
    (although good enough for the time being).

    > For VIA CPUs, life is easy. Use xstore insn and "You've got bytes!" :)

    As you say, we could throw away even our crappy PRNG and get better data
    with a single opcode. So you advocate we add CPU/arch-specific code into
    our filesystem? How about we add a wrapper around all the different
    CPU-specific RNG codes and call it the "low cost RNG" which will be faster
    _and_ give better data than any explicitly-coded PRNG. ;-) For our needs
    at least, the asm-generic code would be on the order of maybe 15 lines of C:

    #define RESEED_INTERVAL 65536

    int get_fast_random_bytes(char *buf, int nbytes)
    static int data_arr[NR_CPUS], count_arr[NR_CPUS]; /* use percpu... */
    int *data = &data_arr[smp_processor_id()];
    int *count = &count_arr[smp_processor_id()];

    *count -= nbytes;
    if (*count < 0) {
    *count = RESEED_INTERVAL;
    get_random_bytes(data, sizeof(*data));

    while (nbytes >= sizeof(*data)) {
    *(long *)buf = *data;
    buf += sizeof(*data);
    *data = *data * 1812433253L + 12345L; /* or whatever... */
    memcpy(buf, data, nbytes);

    Cheers, Andreas
    Andreas Dilger

    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:58    [W:0.032 / U:56.108 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site