prng change feedback

This is merely a historical archive of years 2008-2021, before the migration to mailman3.

A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/OpenBSC@lists.osmocom.org/.

ringsignature at riseup.net ringsignature at riseup.net
Thu Oct 5 22:51:47 UTC 2017


Hello,

> Would be interesting to run a few tests on how quickly we can end up in entropy
> exhaustion. Using getrandom() always would be the easiest and safest. Saying
> that we prefer to be quick rather than secure sounds wrong indeed. But if we
> practically block because of too little entropy, then we annoy lab / testing
> setups that don't care about security, and we provide a DoS attack vector.
>

I conducted some simple experiments with small C program running on a
quad core Intel(R) Core(TM) i5-2520M CPU. The program is in the body of
this email. It utilized only a single core at full capacity. The test
runs syscall(SYS_getrandom, &buf, bufsize, flags) in a while(1) loop.
The bufsize is 512 (bytes) for each call to SYS_getrandom. The program
measures the system entropy as SYS_getrandom is repeatedly called. As
the program uses syscall() without #defines for getrandom(), I #defined
the flags manually. The name GRND_BLOCKONCE seemed appropriate though
non-standard it meaningfully describes the defined behavior. The two
flags I tested were:

  #define GRND_BLOCKONCE 0
  #define GRND_RANDOM 0x0002

The first method of calling ensured that the syscall may block until the
system entropy pool is initialized. It did not block on my machine as
the entropy pool was initialized around two weeks ago at the last system
boot. During a ~fifteen minute run with 412100000 iterations fetching
512 bytes per iteration, the entropy pool increased from ~3700 to ~3867.
In another run over ~eleven minutes with 277200000 iterations, I found
that the pool went from ~3920 to ~3727. During the second run, I suspect
other software on my machine used the /dev/random device directly. In
both cases, the output matches my expectation of a very large ratio for
the estimated entropy bits to PRNG output bits. The core of the
iteration was effectively this single line:

  actual_bytes_fetched = syscall(SYS_getrandom, &buf, bufsize,
GRND_BLOCKONCE)

The value of actual_bytes_fetched was always equal to the size of
bufsize. It never underflowed. With GRND_BLOCKONCE, any concerns about
intermittent blocking or a denial of service vectors through getrandom()
should be be mitigated. GRND_BLOCKONCE seems ideal for TMSI generation
even if an adversary were requesting (tens of) thousands of TMSIs a
second.

The second method of calling getrandom() was configured to use the
actual bits of the random device pool as clarified in the documentation
for getrandom():

       GRND_RANDOM
              If  this  bit  is set, then random bytes are drawn from
the random source (i.e., the same source as the
              /dev/random device) instead of the urandom source.  The
random source is limited based on  the  entropy
              that  can  be obtained from environmental noise.  If the
number of available bytes in the random source
              is less than requested in buflen, the call returns just
the available random bytes.  If no random bytes
              are available, the behavior depends on the presence of
GRND_NONBLOCK in the flags argument.

The core of the iteration was the same with only a different flag set:

  actual_bytes_fetched = syscall(SYS_getrandom, &buf, bufsize,
GRND_RANDOM)

The value of actual_bytes_fetched varied at every iteration and did
often underflow. The ratio of entropy pool bits to output bits appears
to be closer to one to one. It does not seem ideal to use GRND_RANDOM
for TMSI generation, especially if a possible adversary is the
requesting party - they would seem to be able to drain the device
entropy pool very quickly. If this mode was used and it is configured to
be non-blocking, it seems that it could fail very badly.

After running the above tests and reading the related documentation, my
conclusion is that it would be reasonable to use syscall(SYS_getrandom,
&buf, bufsize, 0) as a suitable replacement for rand() in all cases
without any concrete security or performance concerns. The overhead is
also significantly less than importing or otherwise depending on
OpenSSL, GnuTLS,  NaCL, or probably even glibc. It may make sense to use
the platform's libc interface if it is available. It may also be
worthwhile to try to ensure that buffer is indeed changed. The small
program below could also easily be modified to test that the buffer is
indeed completely filled with some new data and to additionally hash the
buffer before use in any cryptographic application.

Happy Hacking,
RS

/*
 *
 * This program is Free Software under the GPLv3.
 * Copyleft ringsignature 2017.
 *
 * Compile with:
 * gcc -Wall -std=c11 -o getrandom-exhaust getrandom-exhaust.c
 *
 * */

#define _GNU_SOURCE 1
#include <sys/types.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>

#define GRND_BLOCKONCE 0x0000
#define GRND_NONBLOCK 0x0001
#define GRND_RANDOM 0x0002

void pp(unsigned char *buf, uint s){
    uint z = 0;
    for (z=0; z<s; z++){
      printf("%x", buf[z]);
    }
    printf("\n");
}

void ms(unsigned char *buf, uint s, unsigned char f){
    memset(buf, f, s);
}

uint ea(void){
   FILE *f;
   uint i = 0;
   int val = 0;
   f = fopen("/proc/sys/kernel/random/entropy_avail", "r");
   if (f == NULL) { return -1; }
   i = fscanf(f, "%u", &val);  
   if (i == EOF) { return -1; }
   fclose(f);
   return val;
}

void ppea(void) {
   uint e = -1;
   e = ea();
   if (e != -1) {
       printf("Current entropy available: %u\n", e);
   } else {
       fprintf(stderr, "Error fetching currently available entropy!\n");
   }
}

void pps(uint b, uint c) {
    printf("\e[1;1H\e[2J");
    printf("getrandom status - byte size requested: %i iteration: %i\n",
b, c);
    ppea();
}

int main(void) {
    uint bufsize = 512;
    unsigned char buf[bufsize];
    int actual_bytes = 0;
    int count = 0;
    int es = ea();
    ms(buf, bufsize, 0x0);
    pps(actual_bytes, count);
    while (count != -1) {
        ms(buf, bufsize, 0x42);
        actual_bytes = syscall(SYS_getrandom, &buf, bufsize,
GRND_BLOCKONCE);
        if (actual_bytes != bufsize) {
            pps(actual_bytes, count);
            printf("getrandom underflow!\n");
            pp(buf, bufsize);
        }
        count++;
        if ( (count % 100000) == 0) { 
            pps(actual_bytes, count);
            ms(buf, bufsize, 0x47);
        }
    }
    pps(actual_bytes, count);
    printf("Original entropy estimate: %i\n", es);
    return 0;
}



More information about the OpenBSC mailing list