QRN. Practical random numbers generation
May 17, 2004
Random numbers play a significant role in modern cryptography. They are used to produce session keys, generate strong prime numbers, perform some numerical analysis, and many others. It is why creating good random numbers is an important and a hard problem.
There are some pseudorandom number generators (PRNG) available that generate cryptographically secure random numbers by collecting samples from various entropy sources (such as user keystrokes, mouse events, etc.) to a distilling pool. One of the best examples for such PRNG would be Yarrow, designed by J. Kelsey, B. Schneier and N. Ferguson [1]. These PRNGs are excellent apart from a small thing: a generator should collect the proper amount of samples before starting to produce numbers.
Meantime let introduce another generator named QRN. It is extremely simple without slow pools and mandatory initial seeding. QRN is suitable for applications that do not require cryptographically strong PRNG and where full featured generators like Yarrow would be overkill.
All modern Intel processors (and most of the compatible ones like AMD) have a time stamp counter, a feature introduced since first Pentium [2]. This counter is a 64-bit value that increments every clock cycle while CPU is up. Taking low 8 bits of current counter value give a nice unpredictability, especially in a non–realtime multitasking environment like Windows or Linux. Please do not be fooled: this cannot be used as a decent PRNG because the result would fail most of statistical and numerical analysis and tests on randomness. The generator must have a feature to strengthen the output, and this QRN is all about.
Linear feedback shift registers (LFSRs) are something known for ages. There is a nice coverage on these in [3], so we will skip the details here. An LFSR is very simple and is good enough from a mathematical point of view, yet it is cryptographically insecure while used alone. QRN uses an LFSR to strengthen the output of a time stamp counter by confusing them together.
The algorithm is easier to demonstrate than describe. Here is the C implementation, the code is quite 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 */
The output of QRN is a 32-bit random value. QRN passes all in the Diehard battery of tests of randomness [4]. It has a small footprint, high performance, and the generated output sequence is actually hard to reproduce.
The disadvantage of QRN is its platform dependency or, better say, reliance on a presence of a real-time stamp counter. Well, there is always Java and SecureRandom() for whom need a real cross-platform solution.
Why and what is "QRN" means? It is the abbreviation for Quite Random Numbers. It also means an atmospheric noise in Q-code, used in amateur radio communication.
References
- 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
- Intel Architecture Software Developer's Manual. Volume 2: Instruction Set Reference, http://developer.intel.com/design/pentium/manuals/
- B. Schneier, Applied Cryptography. 2nd Edition, 1996, John Wiley & Sons, ISBN 0-471-11709-9
- 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/