Randomness and Pseudorandom Generators

CS 463/480 Lecture, Dr. Lawlor

If you need random numbers for crypto, you need *real* random numbers, and there's only one safe place to get them: the OS, which watches the hardware interrupts and has access to nanosecond-resolution timers to give you unpredictable values.
 Windows UNIX #pragma comment(lib, "advapi32.lib") BYTE buf; // however much you need H CRYPTPROV h; if (!CryptAcquireContext(&h,0,0,          PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))     die("CryptAquire failed"); if (!CryptGenRandom(h,sizeof(buf),buf))     die("CryptGen failed"); Read bytes from the file     /dev/urandom (Don't bother with /dev/random)

Pseudorandom Numbers

For scientific programming, where repeatability is critical, we often want a series of "pseudorandom" numbers.  These normally don't need to be as unpredictable as cryptographic random numbers, in fact for debugging or controlled experiments we want to be able to spit out the same numbers again, and we often need a lot of them to be generated quickly.

 Name Usage Timing Comments Mersenne Twister std::mt19937 generator;           next=generator(); 12ns Initialization is slow, and the algorithm is complicated (but fast). C++11 default_random_engine std::default_random_engine generator;           next=generator(); 12ns This is just the 1988 version of Park-Miller, minstd_rand0.  It cycles after two billion steps. Park-Miller next = (last * 48271) % 2147483647UL; or std::minstd_rand. 5ns Gets stuck if given an input of zero. Surprisingly fast because the compiler transforms the mod to a multiply. drand48 48-bit arithmetic:   next = last*0x5DEECE66DuL + 13; 10ns Low hex digits cycle through this sequence: 0d6bc92785e341af randu 31-bit arithmetic:    next = last * 65539; 5ns Only useful with odd numbers. Gets stuck if given an input of zero. Low hex digits cycle through 1,3,9,B. All values fall into 15 planes in 3D (fails spectral test).

There's an exhaustive table of random number generator performance at the Boost site.

State Recovery

One serious problem with most scientific random number generators is they have a small internal state, as small as 32 bits.  This means an attacker can use any output derived from their random number stream to brute-force the generator's state, and predict all future outputs of the generator.

Blum Blum Shub (BBS) is designed to be provably robust to this sort of attack.  Generation is simply as follows:
next = (last * last) % (P*Q);
Your random number stream consists of the low few bits of "next".

P and Q are two large prime numbers, with thousands of bits each, meaning this requires multi-precision arithmetic, and generating random numbers is very slow.  But there is a proof reducing the problem of reconstructing this random number stream from its low order bits to factoring the product P*Q, which appears to be intractable on current machines (although not on quantum computers!).

PRN to Encryption

If you can reliably generate a stream of pseudorandom numbers, you can use them to encrypt data in a variety of ways (most of them bad!).  For example, since srand/rand gives a deterministic stream (if you stay on the same OS), you can just XOR each character like this:
srand(3); // the key
std::string plaintext=bar, ciphertext="";
for (unsigned int i=0;i<plaintext.size();i++) {
int keyi=rand()&0xff; // 8 bits of pseudorandom data
keyi&=0x1f; // drop to 5 bits to stay in printable ASCII
char c=plaintext[i]; // extract char from input
c=c^keyi; // encryption! (or decryption, same thing)
ciphertext+=c; // add char to output
}
return ciphertext;

(Try this in NetRun now!)

Note we only XOR the low 5 bits of the character data, solely to avoid the hassle of reading and writing binary data.  For a real cipher, you would use all 8 bits, resulting in binary garbage as ciphertext, which can't be safely printed to the screen.

But the plaintext "To_be_or_not_to_be" still becomes the ciphertext " N~GjtCgb^~ep^uVjj", which actually isn't too bad at first glance.  However, note that decryption is the same operation as encryption, which is our first bug:
• If the attacker can feed ciphertext back in as plaintext to be encrypted, we will decrypt it for them.  (XOR is a symmetric operation)
Also, note that changing one bit in the plaintext changes exactly one bit in the ciphertext, which allows differential cryptanalysis--given the same key, the bit differences between two messages are exactly the bit differences between the two ciphertexts, leaking information about the plaintext.  Also, changing one bit in the ciphertext changes the same bit in the plaintext.  This is really disaster, because this means the attacker can modify our messages in a very controlled way--for example, by flipping bits on ATM-to-bank messages to increase the apparent amount of an ATM deposit, or flipping the proceed/deny bit on a bank-to-ATM message to allow a huge withdrawal.
• Plaintext and ciphertext bits match up 1-1, which is disaster.
Finally, the key size is limited by the random number generator's state, which is only 32 bits here.  This allows explicit enumeration of all possible keys in only a few seconds.
• The key size is too small.

Lawlor Cryptosystem 0 (LC0)

Back in 1996, as a skinny undergraduate in Nerland hall, I wrote an encryption scheme based on pseudorandom number generation.  The key setup phase went like this:
unsigned long randS ,mulBy ,addBy ;  // In the 1990's, these were 4 bytes each

randS=(long)newDialog;randS2=(long)*myH; // OS memory handles as entropy source
randS2^=TickCount(); // 60ths of a second as entropy source
short len=strlen(i);
for (short i=len;i<41;i++) // repeat passphrase to fill up buffer
pass[i]=pass[i%len]-i;
for (short i=0;i<8;i++)
{//pervert these numbers by the password in a deterministic way.
//Recall that the low four bits of the password are the most random ones.
//hence, we will xor by the low two bits each iteration (masking the passwd)
mulBy^=(long(pass[i<<2])<<(i<<1))+pass[i+3];