[vlc-devel] [PATCH] rand: implement a per-thread PCG random number generator for POSIX

[Yegor Timoshenko]

All fixed!

By the way, if VLC doesn't use vlc_rand_bytes() often (and I don't
think it does): I could prepare a patch to drop RNG code entirely and
just source bytes directly from /dev/urandom (or, better yet, from
getrandom(2) on Linux, arc4random(3) on BSDs and Darwin, and
/dev/urandom on other POSIX platforms).

/dev/urandom on most POSIX platforms (FreeBSD, Linux, OpenBSD) uses
ChaCha20, which is a very good streaming cipher that can be used as a
RNG, and unlike any other RNG is considered cryptographically secure.
getrandom() in glibc, unfortunately, is rather new and only applies to
releases after 2.25, which means that for older glibc versions VLC
would have to use /dev/urandom.

That being said, PCG is very compact. What do you think?

On Fri, Oct 20, 2017 at 10:44 PM, Tristan Matthews <tmatth at videolan.org> wrote:
> Hi,
>
> On Fri, Oct 20, 2017 at 6:30 PM, Yegor Timoshenko
> <yegortimoshenko at gmail.com> wrote:
>> And done! Tristan, thanks for pointing this out.
>>
>> On Fri, Oct 20, 2017 at 10:19 PM, Yegor Timoshenko
>> <yegortimoshenko at gmail.com> wrote:
>>> PCG RNG has a lot of useful qualities that make it the best fit as of
>>> yet for VLC. It generates numbers of very high statistical quality,
>>> very fast, with very little code, and is not easily predictable. See:
>>>
>>> http://www.pcg-random.org
>>> http://www.pcg-random.org/other-rngs.html
>>>
>>> Now there's one RNG for each thread, instead of locking.
>>>
>>> The next logical step would be to decouple platform-specific entropy
>>> sources (used for seeding) and RNG implementations, currently these
>>> two are intermingled in vlc_rand_bytes() function. Then it would be
>>> possible to use this RNG algorithm on other platforms.
>>> ---
>>>  src/posix/rand.c | 148 +++++++++++++++++++++++++++----------------------------
>>>  1 file changed, 72 insertions(+), 76 deletions(-)
>>>
>>> diff --git a/src/posix/rand.c b/src/posix/rand.c
>>> index 338f4675da..48b179b120 100644
>>> --- a/src/posix/rand.c
>>> +++ b/src/posix/rand.c
>>> @@ -1,8 +1,8 @@
>>>  /*****************************************************************************
>>> - * rand.c : non-predictible random bytes generator
>>> + * rand.c : per-thread PCG RNG (see http://www.pcg-random.org)
>>>   *****************************************************************************
>>> - * Copyright © 2007 Rémi Denis-Courmont
>>> - * $Id$
>>> + * Copyright (C) 2007 Rémi Denis-Courmont
>>> + * Copyright (C) 2017 Yegor Timoshenko <yegortimoshenko at gmail.com>
>>>   *
>>>   * This program is free software; you can redistribute it and/or modify it
>>>   * under the terms of the GNU Lesser General Public License as published by
>>> @@ -20,98 +20,94 @@
>>>   *****************************************************************************/
>>>
>>>  #ifdef HAVE_CONFIG_H
>>> -# include "config.h"
>>> +#include "config.h"
>>>  #endif
>>>
>>>  #include <vlc_common.h>
>>> +#include <vlc_fs.h>
>>>  #include <vlc_rand.h>
>>>
>>> +#include <fcntl.h>
>>> +#include <pthread.h>
>>>  #include <stdint.h>
>>>  #include <string.h>
>>>  #include <stdlib.h>
>>> -
>>> -#include <sys/types.h>
>>> -#include <fcntl.h>
>>>  #include <unistd.h>
>>> -#include <pthread.h>
>>> -#include <vlc_fs.h>
>>>
>>> -#include <vlc_md5.h>
>>> +typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;
>>>
>>> -/*
>>> - * Pseudo-random number generator using a HMAC-MD5 in counter mode.
>>> - * Probably not very secure (expert patches welcome) but definitely
>>> - * better than rand() which is defined to be reproducible...
>>> - */
>>> -#define BLOCK_SIZE 64
>>> +static uint32_t pcg32_random_r(pcg32_random_t *rng)
>>> +{
>>> +  uint64_t xsh, rot;
>>> +
>>> +  xsh = ((rng->state >> 18u) ^ rng->state) >> 27u;
>>> +  rot = rng->state >> 59u;
>>>
>>> -static uint8_t okey[BLOCK_SIZE], ikey[BLOCK_SIZE];
>>> +  rng->state *= 6364136223846793005ULL;
>>> +  rng->state += rng->inc | 1;
>>> +
>>> +  return (xsh >> rot) | (xsh << ((-rot) & 31));
>>> +}
>>>
>>> -static void vlc_rand_init (void)
>>> +static void pcg32_random_b(pcg32_random_t *rng, uint8_t *buf, size_t len)
>>>  {
>>> -    uint8_t key[BLOCK_SIZE];
>>> -
>>> -    /* Get non-predictible value as key for HMAC */
>>> -    int fd = vlc_open ("/dev/urandom", O_RDONLY);
>>> -    if (fd == -1)
>>> -        return; /* Uho! */
>>> -
>>> -    for (size_t i = 0; i < sizeof (key);)
>>> -    {
>>> -         ssize_t val = read (fd, key + i, sizeof (key) - i);
>>> -         if (val > 0)
>>> -             i += val;
>>> -    }
>>> +  size_t i, j;
>>> +  uint32_t n;
>>>
>>> -    /* Precompute outer and inner keys for HMAC */
>>> -    for (size_t i = 0; i < sizeof (key); i++)
>>> -    {
>>> -        okey[i] = key[i] ^ 0x5c;
>>> -        ikey[i] = key[i] ^ 0x36;
>>> -    }
>>> +  for (i = 0; i < len; i += sizeof(n)) {
>>> +    j = len - i;
>>> +    n = pcg32_random_r(rng);
>>>
>>> -    vlc_close (fd);
>>> +    memcpy(buf + i, &n, j < sizeof(n) ? j : sizeof(n));
>>> +  }
>>>  }
>>>
>>> +static void pcg32_srandom_r(pcg32_random_t* rng, uint64_t state, uint64_t inc)
>>> +{
>>> +  rng->state = 0U;
>>> +  rng->inc = (inc << 1u) | 1u;
>>> +  pcg32_random_r(rng);
>>>
>>> -void vlc_rand_bytes (void *buf, size_t len)
>>> +  rng->state += state;
>>> +  pcg32_random_r(rng);
>>> +}
>>> +
>>> +static pthread_key_t pcg32_rng;
>>> +static pthread_once_t pcg32_rng_once = PTHREAD_ONCE_INIT;
>>> +
>>> +static void pcg32_rng_key_create()
>>>  {
>>> -    static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
>>> -    static uint64_t counter = 0;
>>> -
>>> -    uint64_t stamp = NTPtime64 ();
>>> -
>>> -    while (len > 0)
>>> -    {
>>> -        uint64_t val;
>>> -        struct md5_s mdi, mdo;
>>> -
>>> -        InitMD5 (&mdi);
>>> -        InitMD5 (&mdo);
>>> -
>>> -        pthread_mutex_lock (&lock);
>>> -        if (counter == 0)
>>> -            vlc_rand_init ();
>>> -        val = counter++;
>>> -
>>> -        AddMD5 (&mdi, ikey, sizeof (ikey));
>>> -        AddMD5 (&mdo, okey, sizeof (okey));
>>> -        pthread_mutex_unlock (&lock);
>>> -
>>> -        AddMD5 (&mdi, &stamp, sizeof (stamp));
>>> -        AddMD5 (&mdi, &val, sizeof (val));
>>> -        EndMD5 (&mdi);
>>> -        AddMD5 (&mdo, mdi.buf, 16);
>>> -        EndMD5 (&mdo);
>>> -
>>> -        if (len < 16)
>>> -        {
>>> -            memcpy (buf, mdo.buf, len);
>>> -            break;
>>> -        }
>>> -
>>> -        memcpy (buf, mdo.buf, 16);
>>> -        len -= 16;
>>> -        buf = ((uint8_t *)buf) + 16;
>>> +  pthread_key_create(&pcg32_rng, NULL);
>>> +}
>>> +
>>> +void vlc_rand_bytes(void *buf, size_t len)
>>> +{
>>> +  pcg32_random_t *rng;
>>> +  uint64_t state, inc;
>>> +  int fd;
>>> +
>>> +  pthread_once(&pcg32_rng_once, pcg32_rng_key_create);
>>> +
>>> +  if ((rng = pthread_getspecific(pcg32_rng)) == NULL) {
>>> +    rng = malloc(sizeof(pcg32_random_t));
>
> You need to check if malloc returned NULL here.
>
>>> +    fd = vlc_open("/dev/urandom", O_RDONLY);
>>> +
>>> +    if (fd == -1) {
>>> +      free(rng);
>>> +      return;
>>> +    }
>>> +
>>> +    if (read(fd, &state, sizeof(state)) == -1 ||
>>> +       read(fd, &inc, sizeof(inc)) == -1) {
>>> +      vlc_close(fd);
>>> +      free(rng);
>>> +      return;
>>>      }
>>> +
>>> +    vlc_close(fd);
>>> +    pcg32_srandom_r(rng, state, inc);
>>> +    pthread_setspecific(pcg32_rng, rng);
>
> You should check the return value of pthread_setspecific, and clean up
> if it failed.
>
> Best,
> Tristan
>
>>> +  }
>>> +
>>> +  pcg32_random_b(rng, buf, len);
>>>  }
>>> --
>>> 2.14.2
>>>
>> _______________________________________________
>> vlc-devel mailing list
>> To unsubscribe or modify your subscription options:
>> https://mailman.videolan.org/listinfo/vlc-devel
> _______________________________________________
> vlc-devel mailing list
> To unsubscribe or modify your subscription options:
> https://mailman.videolan.org/listinfo/vlc-devel