Aw random

From ActiveWiki
Jump to: navigation, search


Minimum requirements
Added in version 2.1
SDKbuild 13


int aw_random (void)

Description

Returns a random number.

Notes

The psuedo-random number generator (PRNG) employed by this method is Mersenne Twister (MT) by Matsumoto and Nishimura. It sets new standards for the period, quality and speed of random number generators. The incredible period is 219937 - 1, a number with about 6000 digits. The 32-bit random numbers exhibit best possible equidistribution properties in dimensions up to 623 and it's very fast.

Predictability

This PRNG is should not be used in cryptography as it has major vulnerabilities:

  • Observing a sufficiently long sequence of outputs from MT is enough to predict all future outputs.
  • It takes many iterations before the initial non-random state produces output that will pass a randomness test.

Two steps can be taken to mitigate the problems:

  • Generate multiple 32-bit outputs (e.g. 8 would be sufficient) and digest them using a cryptographic hash function such as RIPEMD or SHA-1.
  • Throw away the first x number of outputs from MT (e.g. call aw_random a million times when the SDK application is initialized).

Seed search attack

The implementation used in the SDK is also vulnurable to a "seed search attack" due to only using a 32-bit number for the seed (i.e. it can only produce 2^32 different sequences of psedo-random numbers). This means that attackers would need to try at most 2^32 different seeds before finding the one being used.

If a large number of initial outputs of MT have been thrown away then attackers would need to generate a longer sequence of numbers to test each seed. If 1,000,000 numbers were thrown away and 1000 have been passed to users then an attacker would need to generate roughly 1001000 * 2^32 numbers to be sure of finding the correct seed (in addition to seeding 2^32 times).

Arguments

None

Argument attributes

None

Return values

Signed 32-bit number (i.e. a range of -2147483648 to +2147483647).

Returned attributes

None

Usage

Naive

if (aw_random () == 547891)
  puts ("You sure are lucky");

Better

void random_init (void)
{
  int i;
  
  for (i = 0; i < 1000000; i++)
    aw_random ();
}

int random_secure (void)
{
  int n;
  int i;
  
  n = 0;
  
  /*
    combine multiple outputs into a single number using xor
  */
  for (i = 0; i < 8; i++) 
    n ^= aw_random ();
  
  return n;
}

random_init (); 

if (random_secure () == 547891)
  puts ("You sure are lucky");

Secure

void random_init (void)
{
  int i;
  
  for (i = 0; i < 1000000; i++)
    aw_random ();
}

int random_secure (void)
{
  int buf[8];
  int i;
  
  for (i = 0; i < 8; i++) 
    buf[i] = aw_random ();
  
  /*
    function that takes a buffer as input, digests it using RIPEMD-128
    and returns a 32-bit hash value from the output
  */
  
  return ripemd128_32 ((char*)&buf, sizeof (buf));
}

random_init (); 

if (random_secure () == 547891)
  puts ("You sure are lucky");

See also