Motto: It's just the int interpretation of a float's binary representation.

~ This is part of the EuCrypt series. Start with Introducing EuCrypt. ~

This unexpected chapter equips EuCrypt with more convenient ways of using the excellent Fuckgoats (FG) for generating random numbers in various formats. The backstory is a heartwarming (if short) tale of idiocy stabbing itself in its own useless foot, so let's indulge for a moment.

As you might be aware, cryptography algorithms such as RSA and games such as Eulora rely to a significant extent on randomly generated numbers. As you might not fully appreciate though, the usual "random number generator" available on your computer is at best pseudo-random but the pseudo - here starts the idiocy - is not mentioned much, preferably not at all. So one gets /dev/random, /dev/urandom but never, ever, ever /dev/pseudorandom. One might say "what's in a name"¹ and attempt to sort-of still work with it - let's just feed /dev/random with truly random bits from the FG and keep it around the house, as it might still be useful, why not? But of course the whole thing is made so that there isn't in fact a clear and straightforward way to even feed it better inputs - in other words, through its own working, /dev/random managed to push itself into being discarded even sooner rather than later. Isn't that... nice?

Once the silly idea of still using /dev/random in some way was thus abandoned as it should be, the only remaining thing was to provide some reliable ways of directly converting the raw random bits that FGs produce into some actual numbers of the sort that a user (a human, a game or anything else) needs in practice. Obviously, there can never be a full list of what sort of formats and ranges of numbers one might want, so this is by no means a comprehensive set or the only set of formats, ranges and even ways of converting FG bits into random numbers. It's simply a starter set of methods that are useful to S.MG at this time and may be perhaps useful to you at some time. As always, before using them, first read and understand their working and their limitations so that you can actually decide whether they meet your needs or not. And if they don't, either change them into what you need them to be or - even better yet - add to them your own methods that do exactly what you need them to do.

A random number generator based on FG would logically be a library on its own so that it can be easily used by any code - even without importing the whole EuCrypt if it doesn't need the rest. However, at the moment, the new code is simply an addition to truerandom.c that is part of smg_rsa, as it effectively builds on the other methods in there (those for accessing FGs specifically). I refrained from extracting the RNG into a separate module at this time because of a lack of tools: current vdiff does not know about simply moving code without changing it. As soon as the new vtools are ready and fully functional, it should be an easy task to simply move the relevant code to a different module with a short and easy to read vpatch (as opposed to the large delete & add vpatch that would result now from such a simple move). Until then at least, smg_rng will effectively be part of smg_rsa.

There are 4 new methods for obtaining random numbers using bits from a source of entropy², providing the following types and ranges of numbers:

• an unsigned integer between 0 and 2^32 - 1 (i.e. on precisely 32 bits): this method reads 32 bits from the specified entropy source and then copies them directly to the memory address of an uint32_t (unsigned integer on 32 bits) variable that is the result. Although working at bit-level, the method doesn't really care about endianness, since the bits are random anyway: sure, same bits will be interpreted as a different value by your Big Endian iron compared to your Little Endian iron but that doesn't make the series obtained with successive calls to this method from *the same machine* any less random.
• an unsigned integer between 0 and 2^64 - 1 (i.e. on precisely 64 bits): this method is just like the above, but for larger numbers (64 bits instead of 32); specifically, this method reads 64 bits from the specified entropy source and then copies them directly to the memory address of an uint64_t (unsigned integer on 64 bits) variable that is the result. Although working at bit-level, the method doesn't really care about endianness, since the bits are random anyway: sure, same bits will be interpreted as a different value by your Big Endian iron compared to your Little Endian iron but that doesn't make the series obtained with successive calls to this method from *the same machine* any less random.
• a "dirty" float between 0 and 1: this method obtains first a 32-bit random integer value with the relevant method above and then divides this (as a float) by the maximum possible value on 32 bits (2^32 - 1). The resulting float is deemed "dirty" from a randomness perspective because of the way in which floating points are stored: basically there will be some unpredictable rounding of the least significant bits so use this *only* if this degradation is insignificant to you.
• a float between 1 and 2, assuming the IEEE 754/1985 internal representation: unlike the "dirty" float method, this one directly writes the random bits obtained from FG to the mantissa part of a float number in memory (it also sets the sign bit to 0 and the exponent to 127 effectively ensuring that the result is read as a positive float with value 1.mantissa). For clarity reasons, the code of this method actually writes first 32 random bits at the address of the desired float and then simply goes in and sets the sign to 0 and the exponent to 127, leaving the rest (i.e. the mantissa) with the random bits. Because of this direct bit-diddling, this method has to take into account the endianness: on Big Endian, the sign and exponent are the first two octets at the address of the float, while on Little Endian the exponent and sign are the last 2 octets. To handle this, the method first calls a little bit of new code that tests the endianness and then it sets accordingly the relevant offsets for the 2 octets that need diddling.

The signatures of the above methods as well as the new snippet of code for testing endianness at run-time are added to the relevant header file, eucrypt/smg_rsa/include/smg_rsa.h, together with the usual comments to help the reader understand the code.

The run-time test of endianness:

/* A way to determine endianness at runtime.
 * Required for diddling a float's mantissa for instance.
 */
static const int onect = 1;
#define is_bigendian() ( (*(char*)&onect) == 0 )

The signatures of rng methods:

/* Returns (in parameter *n) a *potentially biased* random float between 0 and 1
 * Uses bits from ENTROPY_SOURCE but it rounds when converting to float
 * NB: This function rounds impredictably.
       Use it ONLY if LSB normalization is insignificant to you!
 * This function uses rng_uint64 below.
 *
 * @param n - a float value (LSB rounded) between 0 and 1, obtained using
 *            a 64-bit random integer (64 bits from ENTROPY_SOURCE)
 * @return  - a positive value on success and a negative value in case of error
 *            main possible cause for error: failure to open ENTROPY_SOURCE.
 *            NB: a non-responsive/malconfigured source can result in blocking
 */
int rng_dirty_float(float *n);

/* Returns (in parameter *n)  a randomly generated float between 1 and 2 using:
 *    - the IEEE 754/1985 format for single float representation
 *    - ENTROPY_SOURCE to obtain bits that are *directly* used as mantissa
 * NB: this value is between 1 and 2 due to the normalised format that includes
 *     an implicit 1 ( i.e. value is (-1)^sign * 2^(e-127) * (1.mantissa) )
 *
 * From IEEE 754/1985, a description of the single float format:
 *   msb means most significant bit
 *   lsb means least significant bit
 *  1    8               23            ... widths
 * +-+-------+-----------------------+
 * |s|   e   |            f          |
 * +-+-------+-----------------------+
 *    msb lsb msb                 lsb  ... order

 * A 32-bit single format number X is divided as shown in the figure above. The
 * value v of X is inferred from its constituent fields thus:
 * 1. If e = 255 and f != 0 , then v is NaN regardless of s
 * 2. If e = 255 and f = 0 , then v = (-1)^s INFINITY
 * 3. If 0 < e < 255 , then v = (-1)^s * 2^(e-127) * ( 1.f )
 * 4. If e = 0 and f != 0 , then v = (-1)^s * 2^(-126) * ( 0.f ) (denormalized
 *    numbers)
 * 5. If e = 0 and f = 0 , then v = ( -1 )^s * 0 (zero)
 *
 * @param n - the address of an IEEE 754/1985 float: its mantissa will be set to
 *              random bits obtained from ENTROPY_SOURCE; its sign will be set
 *              to 0; its exponent will be set to 127 (the bias value so
 *              that the actual exponent is 0).
 * @return  - a positive value on success and a negative value in case of error
 *              main possible cause for error: failure to open ENTROPY_SOURCE.
 *              NB: a non-responsive/malconfigured source can result in blocking
 */
int rng_float_754_1985(float *n);

/* Returns (in parameter *n) a random unsigned integer value on 32 bits.
 * Uses random bits from ENTROPY_SOURCE that are directly interpreted as int
 *
 * @param n - it will contain the random integer obtained by interpreting 32
 *            bits from ENTROPY_SOURCE as an unsigned int value on 32 bits.
 * @return  - a positive value on success and a negative value in case of error
 */
int rng_uint32( uint32_t *n );

/* Returns (in parameter *n) a random unsigned integer value on 64 bits.
 * Uses random bits from ENTROPY_SOURCE that are directly interpreted as int
 *
 * @param n - it will contain the random integer obtained by interpreting 64
 *            bits from ENTROPY_SOURCE as an unsigned int value on 64 bits.
 * @return  - a positive value on success and a negative value in case of error
 */
int rng_uint64( uint64_t *n );

The actual implementation of the above methods is in eucrypt/smg_rsa/truerandom.c:

int rng_dirty_float(float *n) {
  int status;   /* for aborting in case of error */
  uint32_t r;   /* a random value on 32 bits */
  uint32_t maxval = 0xffffffff; /* maximum value on 32 bits */

  /* obtain a random number on 32 bits using ENTROPY_SOURCE */
  status = rng_uint32( &r );
  if ( status < 0 )
    return status;

  /* calculate and assign the floating-point random value as (r*1.0)/max val */
  /* multiplication by 1.0 IS NEEDED to do float division rather than int div*/
  *n = ( r * 1.0 ) / maxval;

  return 1;
}

int rng_float_754_1985(float *n) {
  /* Single float ieee 754/1985 has 23 bits that can be set for the mantissa
   * (and one implicit bit=1).
   * Full single float ieee 754/1985 representation takes 4 octets in total.
   */
  int noctets = 4; /* number of octets to read from ENTROPY_SOURCE */
  int nread;       /* number of octets *read* from ENTROPY_SOURCE  */
  unsigned char bits[ noctets ]; /* the random bits from ENTROPY_SOURCE */
  int oSignExp, oExpM;/* offsets for sign+exponent octet, exponent+mantissa*/

  /* obtain random bits */
  nread = get_random_octets( noctets, bits );

  if (nread != noctets )
    return -1;  /* something wrong at reading from ENTROPY_SOURCE, abort */

  /* set offsets for bit diddling depending on endianness of iron */
  if (is_bigendian()) {
    oSignExp = 0;
    oExpM = 1;
  }
  else {
    oSignExp = 3;
    oExpM = 2;
  }

  /* set sign=0; exponent=127; explicit mantissa = random bits (23 bits) */
  *(bits+oExpM) = *(bits+2) | 0x80;  /* one bit of exponent set */
  *(bits+oSignExp) = 0x3f;           /* sign=0; exponent bits for 127 */

  /* now copy the bits to the result var (i.e. as a float's representation */
  memcpy( n, bits, noctets );
  return 1;
}

int rng_uint32( uint32_t *n ) {
  int noctets = 4;  /*  32 bits aka 4 octets to read from ENTROPY_SOURCE     */
  int nread;        /*  the number of octets read from ENTROPY_SOURCE        */
  unsigned char bits[ noctets ]; /* for storing the bits from ENTROPY_SOURCE */

  /* read random 32 bits from ENTROPY_SOURCE */
  nread = get_random_octets( noctets, bits );
  if ( nread != noctets )
    return -1;

  /* copy the random bits to n, to be interpreted as uint32 */
  /* endianness is irrelevant here - the bits are random anyway */
  memcpy( n, bits, noctets );

  return 1;
}

int rng_uint64( uint64_t *n ) {
  int noctets = 8;  /*  64 bits aka 8 octets to read from ENTROPY_SOURCE     */
  int nread;        /*  the number of octets read from ENTROPY_SOURCE        */
  unsigned char bits[ noctets ]; /* for storing the bits from ENTROPY_SOURCE */

  /* read random 64 bits from ENTROPY_SOURCE */
  nread = get_random_octets( noctets, bits );
  if ( nread != noctets )
    return -1;

  /* copy the random bits to n, to be interpreted as uint64 */
  /* endianness is irrelevant here - the bits are random anyway */
  memcpy( n, bits, noctets );

  return 1;
}

As usual, for every new piece of code, there are also new tests. In this case, the tests are very basic, simply calling each method and reporting both the resulting number and the status code (i.e. whether the method reported any errors). Note that assessing the outputs of a random number generator is way beyond the scope of those basic tests - you should devise and use your own tools for evaluating (to a degree that is satisfying for yourself) the resulting sequence of numbers obtained through repeated calls to any or all of these methods. The new tests in eucrypt/smg_rsa/tests/tests.c:

void test_dirty_float_rng( int nruns ) {
  int i, status;
  float dirty;

  printf("Running test for smg rng dirty float with %d runsn", nruns);
  for (i=0; i0 ? "OK" : "FAIL");
  }
}

void test_ieee_float_rng( int nruns ) {
  int i, status;
  float ieee;

  printf("Running test for smg rng ieee 745/1985 float with %d runsn", nruns);
  for (i=0; i0 ? "OK" : "FAIL");
  }
}

void test_uint32_rng( int nruns ) {
  int i, status;
  uint32_t n;

  printf("Running test for smg rng unsigned int32 with %d runsn", nruns);
  for (i=0; i0 ? "OK" : "FAIL");
  }
}

void test_uint64_rng( int nruns ) {
  int i, status;
  uint64_t n;

  printf("Running test for smg rng unsigned int64 with %d runsn", nruns);
  for (i=0; i0 ? "OK" : "FAIL");
  }
}

The .vpatch for the above smg rng implementation can be found on my Reference Code Shelf as well as below:

• eucrypt_ch13_smg_rng.vpatch
  • eucrypt_ch13_smg_rng.vpatch.diana_coman.sig

1. A full backstory, at the very least! But let's not digress even more from the code... ↩

2. The source of entropy is assumed to be a FG but - unlike /dev/urandom - you can change this quite easily. ↩

Category: EuCrypt

Comments feed: RSS 2.0