QRN. Practical Random Number Generation

Random numbers plays a significant role in the modern cryptography. They are using to produce session keys, generate strong prime numbers, perform some numerical analysis, and many others. This is why creating a good random numbers is an important but a hard problem.

There are some pseudorandom number generators (PRNG) available, that generates cryptographically secure random numbers by collecting samples from entropy sources (such as user keystrokes, mouse events, etc.) in the pool to distill. One of the best examples of such PRNG is Yarrow, designed by J. Kelsey, B. Schneier and N. Ferguson [1]. They are excellent apart from small thing - a proper amount of samples should be collected before start producing numbers.

Meantime there is another generator I’d like to introduce here -QRN. It is very simple with no slow pools and no mandatory initial seeding.

All modern Intel processors (and most of the compatible ones such AMD) has a time stamp counter - a feature introduced since first Pentium [2]. This counter is a 64-bit value, increments every clock cycle while processor is up. Taking low 8 bits of the counter’s current value gives a nice unpredictability especially in such multitasking environment as Windows and Linux. Please do not be fooled - unfortunately it cannot be used as a proper PRNG because it fails some statistical and numerical analysis and tests on randomness. Thus it must be strengthened and this QRN is all about.

Linear Feedback Shift Registers (LFSR) are something known for years. There is a nice coverage of them in [3] so I’m not going for details here. LFSR is very simple and good enough from the mathematical point of view yet cryptographically insecure while alone. QRN uses a LFSR to strengthen output of the time stamp counter by confusing them together. The algorithm itself is much easy to demonstrate than describe. Here is the C version, the code is straightforward:

#define LFSR(n)    {if (n&1) n=((n^0x80000055)>>1)|0x80000000; else n>>=1;}
#define ROT(x, y)  (x=(x<<y)|(x>>(32-y)))

unsigned long qrn(void)
{
  static unsigned long rnd=0x41594c49, x=0x94c49514;
  unsigned char y;

  __asm
  {
     rdtsc;
     mov [y], al;
  }
  LFSR(x); rnd^=y^x; ROT(rnd,7);
  return (rnd);
} // qrn

Output of QRN is a 32-bit random value. QRN pass all in the Diehard battery of tests of randomness [4]. It has small footprint, high performance, and generated sequence is actually hard to reproduce.

The disadvantage of QRN is dependency on the platform or, better say, dependency on presence of a real-time stamp counter. Well, there is always Java and SecureRandom() for whom needs a real cross-platform solution.

Why “QRN”? It is abbreviation for “Quite Random Numbers”. QRN is also means “atmospheric noise” in Q-code, using in amateur radio communication.

References:

1. J. Kelsey, B. Schneier and N. Ferguson. “Yarrow-160: Notes
   on the Design and Analysis of the Yarrow Cryptographic
   Pseudorandom Number Generator”,
   http://www.schneier.com/paper-yarrow.html
2. “Intel Architecture Software Developer’s Manual. Volume 2:
   Instruction Set Reference”,
   http://developer.intel.com/design/pentium/manuals/
3. B. Schneier, “Applied Cryptography” 2nd Edition, 1996, John
   Wiley & Sons, ISBN 0-471-11709-9
4. The Marsaglia Random Number CDROM with The Diehard Battery
   of Tests of Randomness, http://stat.fsu.edu/~geo/,
   http://www.csis.hku.hk/~diehard/cdrom/