Pseudorandom Number Generator using the Skein Hash

Aaron Logue, Aug 2013

I needed the equivalent of /dev/urandom on Windows. Here is C source code and a random file generator executable based on the Skein hash. Saves a seed file to avoid risk of repeating sequence in low-entropy environments, or the seed file can be used to repeat sequences. 0 to N-1 function includes modulo bias rejection for uniform distribution.
skrand.zip

--------------------------------------------------------------------

This is a Cryptographically Secure Pseudorandom Number Generater (CSPRNG)
based on the Skein V1.3 hash.  Two precompiled exes and their C source
and MSVC nmake makefile are included in skrand.zip.  The first, skgen.exe,
simply writes the requested number of bytes to output.dat.  The second,
sktest.exe, performs several tests of the skrand_int() function's uniformity.
If you need 0 to N-1 random uniformity for much larger integers, see the
bigint page here.

C:\dev\skrand>skgen 10000000

C:\dev\skrand>dir output.dat
08/23/2013  03:00 AM        10,000,000 output.dat

C:\dev\skrand>sktest
Test 1: Reading 1000000 integers from 0 to 12...
0 was selected 76845 times
1 was selected 76968 times
2 was selected 76682 times
3 was selected 76545 times
4 was selected 77225 times
5 was selected 77016 times
6 was selected 76923 times
7 was selected 76732 times
8 was selected 76861 times
9 was selected 77155 times
10 was selected 77314 times
11 was selected 76755 times
12 was selected 76979 times

Test 2: Reading 1000000 integers from 0 to 3221225468...
Values from 0 to 1073741823: 333134
Values from 1073741824 to 2147483647: 333315
Values from 2147483648 to 3221225468: 333551

Test 3: Reading 1000000 integers, either 0 or 1...
0 was selected 499881 times
1 was selected 500119 times

Here's what the stored seed file looked like after the above run:

C:\dev\skrand>hexdump skrand.bin
   0: 4E C4 5A 31 34 ED 2C 05-76 1E 7A 11 BD 41 26 88 N.Z14.,.v.z..A&.
  10: 49 56 A6 7F 14 FA 5F 69-D9 8E D2 9C 4B 4A 7A E4 IV...._i....KJz.
  20: 76 28 09 A3 B8 4B 06 92-40 95 92 83 D6 31 6B 76 v(...K..@....1kv
  30: 52 2E C2 15 7E A0 6C BB-1D CB A5 15 36 5A 49 92 R...~.l.....6ZI.

--------------------------------------------------------------------

The zip file available above contains skrand.c and skrand.h with the
following functions:

/*************************************************************
 * skrand_init()
 * Open a pseudorandom stream and optionally seed it with the
 * first 64 bytes of the specified file. Returns a pointer to
 * an instance of a CSPRNG.
 ************************************************************/
skrand_t * skrand_init(char * filename);

/*************************************************************
 * skrand_read()
 * This works much like Linux's /dev/urandom
 * Takes an instance of a CSPRNG, a pointer to the caller's
 * buffer to copy PRNG output to, and how many bytes to copy.
 ************************************************************/
void skrand_read(skrand_t *skrand, char *var, int len);

/*************************************************************
 * skrand_stir()
 * Optional function to call with any entropy that you can get
 * (anything from the physical world such as timings between
 * mouse clicks or keystrokes or how long the human looked at a
 * web page) to perturb the hash's state with. Anything that
 * varies and is later hard to figure out what it might've been
 * is good. Takes an instance of a CSPRNG, a pointer to a buffer
 * containing the caller's entropy, and how many bytes to read
 * from the caller's buffer.
 ************************************************************/
void skrand_stir(skrand_t *skrand, char *var, int len);

/*************************************************************
 * skrand_int()
 * Return a value from 0 to N-1 with uniform distribution.
 ************************************************************/
unsigned int skrand_int(skrand_t *skrand, unsigned int n);

/*************************************************************
 * skrand_free()
 * Cycles the generator one last time and writes 64 bytes of
 * output to an optional file for seeding the next skrand_init().
 ************************************************************/
void skrand_free(skrand_t *skrand, char *filename);

--------------------------------------------------------------------

If you'd like to compile this into your own project, you'll also need
http://www.skein-hash.info/sites/default/files/NIST_CD_102610.zip

I used the following seven files from its optimized 32-bit directory:
[gorf@box skrand]$ ls -al *.h *.c
-rw-r--r--    1 gorf     users        6141 Jun 30 14:43 brg_endian.h
-rw-r--r--    1 gorf     users        6921 Jun 30 14:21 brg_types.h
-rw-r--r--    1 gorf     users       26877 Jun 30 14:38 skein_block.c
-rw-r--r--    1 gorf     users       35534 Jun 29 08:03 skein.c
-rw-r--r--    1 gorf     users       16551 Jun 29 08:02 skein.h
-rw-r--r--    1 gorf     users        5856 Jun 30 14:23 skein_iv.h
-rw-r--r--    1 gorf     users        4576 Jun 30 14:43 skein_port.h

--------------------------------------------------------------------

Here's a method of generating a random value from 0.0f to 1.0f:

float random_float(skrand_t * skrand) {
 unsigned int r;
   skrand_read(skrand, (char *)&r, 4);
   r &= 0x7fffffff;
   return r/(float)0x7fffffff;
}

--------------------------------------------------------------------

Returning a random integer from 0 to N-1 with uniform distribution
can be done with modulo division provided that the random number used
is selected from a range that is a multiplicative of the group mod N.
To accomplish this, a multiple of N is chosen to serve as a maximum
cutoff value that will trigger an RNG re-roll if a random value is
greater than it.  This prevents values that would wrap around to the
lower portion without reaching N-1 (which would introduce a bias
toward 0) from being used.  The cutoff value can be made sufficiently
high (for example, twice the bit width of N or larger) to make the
likelihood of having to perform a re-roll small.

For example, if N is ten, which requires 4 bits (1010b) we could
compute a cutoff maximum as a multiple of ten that is closest to
an 8-bit value 255 (11111111b) by computing (255 - (255 mod 10))
which is 250 (11111010b).  Then, we read an 8-bit random value and
test to see if it is less than the cutoff value.  If not, we re-roll
and try again.  By rejecting values that fall outside of the range
of a multiple of N, we achieve uniform distribution.  See the code
in skrand.c for more.  It uses a 64-bit cutoff, which should all but
eliminate re-rolling.

--------------------------------------------------------------------

Here's an example of use from a multiplatform prime number generator.
If compiled for Windows, it reads random bytes from skrand_read().
Otherwise it reads from /dev/urandom: 


#ifdef WIN32
 skrand_t *skrand;
   skrand = skrand_init("skrand.bin");
   /* Stir hash state to be sure that multiple instances diverge */
   sprintf(temp, "%d", GetCurrentProcessId());
   skrand_stir(skrand, temp, strlen(temp));
#else
 FILE *fdrand;
   fdrand = open("/dev/urandom", O_RDONLY);
#endif

...

/****************************************************************************
 * my_bigint_random()
 ***************************************************************************/
#ifdef WIN32
void my_bigint_random(skrand_t * skrand, bigint_t * var, unsigned int bits) {
#else
void my_bigint_random(FILE * fdrand, bigint_t * var, unsigned int bits) {
#endif
 unsigned int i, elements;

   elements = bits >> SHIFTBITS;
   if (bits & (INTBITS-1)) {
      elements++;
   }
   if (elements > var->elements) {
      bigint_extend(var, elements - var->elements);
   }
   for (i=0; i < elements; i++) {
#ifdef WIN32
      skrand_read(skrand, (char *)&var->b[i], sizeof(int_type));
#else
      read(fdrand, &var->b[i], sizeof(int_type));
#endif
   }
   i = bits % INTBITS;
   if (i) {
      var->b[elements - 1] >>= INTBITS - i;
   }
   while (elements < var->elements) {
      var->b[elements] = 0;
      elements++;
   }
   return;
}