How to generate cryptographically strong pseudorandom data very rapidly?

Question

What's the best way to go about generating a fast stream of cryptographically strong pseudorandom data without installing uncommon packages? Drawing from /dev/urandom is far too slow.

I had an idea from reading the 'wipe' manpage:

will use the fresh RC6 algorythm as a PRNG; RC6 is keyed with the 128-bit seed, and then a null block is repeatedly encrypted to get the pseudo-random stream.

Encrypting a null block with only a single key is probably not the best idea, especially when large amounts of pseudorandom data are required, so I quickly made this in bash:

while dd if=/dev/zero bs=$(shuf -n 1 -i 1024-67108864) count=1 2>/dev/null | openssl aes-256-cbc -nosalt -k "$(head -c 32 < /dev/random)"; do :; done > [whateverneedsrandomness]

This encrypts a stream of zeros with a random 32 byte seed. The stream is reseeded on average every 32 MB (the range is between 1 KB and 64 MB with a resolution of one byte). The reseed interval is random to prevent anyone from guessing where a new key is used. I purposefully chose CBC as the block mode instead of CTR even though it's faster because I've read that CTR is only good for constant streams, and my very limited cryptographic knowledge tells me that a repeating counter that restarts all the time isn't a good idea when the "stream" will only be a few MB long, although I really don't know for sure.

One worry I have is whether or not the stream leaving openssl is fully encrypted. If the input is not evenly divisible by the block size, would openssl leave the extra data blank (leaving "gaps" of 0s scattered throughout the resulting stream)? Does padding have anything to do with that?

So my question is, is this a good way to create fast random data? And is there anything I missed/overlooked, etc, such as using the wrong blockmode?

Answer 1

Edit: The obviousness was blinding so I missed it. OpenSSL already offers an interface to its own internal PRNG, which is seeded with the machine's /dev/urandom, but then extends it with its own crypto. Just do this:

openssl rand 10000000

to produce 10 millions of pseudo-random bytes. On my laptop, this appears to be about 3 times faster than /dev/urandom, i.e. 11 MByte/s or so. If this is not fast enough for you, read on.

---

Original response:

It really depends on the involved hardware and context. Since you are talking about a bash script, /dev/urandom and OpenSSL, I suppose that:

• You use Linux.
• You want to produce a big file full of pseudorandom bytes.
• You want a solution which is a scripted assembly of existing, "normal" packages, not a programmatic solution.

Indeed, if you could write your own C code, your best options would be either AES encryption in CTR mode with the AES-NI instructions (on recent PC which offer these instruction), or a dedicated stream cipher (e.g. one of these). On a 2.4 GHz Core2 CPU, I could get 700 MByte/s of pseudorandom bytes out of Sosemanuk. I hereafter suppose that you are limited to scripts.

Using OpenSSL encryption is not a bad idea, but there are details:

• Randomizing the length of each chunk is a useless complication.
• There is no need to go to AES-256; AES-128 is already fine. AES-256 is 40% slower than AES-128, and adds no practical improvement in security.
• When encrypting a long sequence of zeros with CBC, you are actually running the block cipher in OFB mode (encrypt a block, encrypt it again, and again, and again). This is reasonable as long as you remain below the 2^n/2 limit, meaning that with AES (128-bit blocks) you don't use a chunk longer than 2⁶⁴ 16-byte blocks, i.e. 250 millions of terabytes. Chances are that you won't reach it anyway. In that sense, the "reseeding" is not really needed.
• When you "reseed" (if you decide to maintain this feature, which is not necessary), use /dev/urandom, not /dev/random. /dev/urandom is fine for cryptography (the OS boot scripts ensure that the internal PRNG is properly seeded), despite the misguided paranoid qualms of the /dev/random implementation. On the other hand, /dev/random may block, and thus be really slow (nothing is slower than a blocked process).
• Beware of strings. bash uses character strings; /dev/random and /dev/urandom return bytes, including bytes of value 0. This may result in an artificially truncated key, and lowered security. This is bad. Instead, you should encode the bytes in hexadecimal and the the -K and -iv command-line arguments with openssl.
• OpenSSL may add a header which begins with 8 fixed bytes (thus totally non-random). It does not do so if you use -K and -iv.
• OpenSSL will also use some padding so you will get an extra 16-byte block at the end (this is not a problem; the padding is on the cleartext, and encryption "randomizes" it).

This leads to the following script:

#!/bin/sh
key=$(dd if=/dev/urandom bs=16 count=1 2>/dev/null | md5sum | cut -d' ' -f1)
iv=$(dd if=/dev/urandom bs=16 count=1 2>/dev/null | md5sum | cut -d' ' -f1)
dd if=/dev/zero bs=65536 count=8192 2>/dev/null | openssl aes-128-cbc -K $key -iv $iv

When invoked, this script outputs a sequence of exactly 536870928 pseudorandom bytes, which are fit for cryptographic purposes. Feel free to modify the bs and count parameters, but remember that dd will allocate a RAM buffer of size bs, so you usually want to keep bs small, but not too small to avoid too many roundtrips into the kernel (8192 to 65536 are usually good values).

I use MD5 here only for the convenience of the bytes-to-hexadecimal conversion (the known shortcomings of MD5 have no influence whatsoever on the security in this case).

This script should work on any decent Linux installation. It uses only packages which should be there by default. On my not-very-powerful laptop, this script produces pseudorandom bytes at the rate of 73 MBytes per second, which is not bad and probably enough for your purposes (if that is not enough, then you will probably have other issues with I/O bottlenecks).

Answer 2

If you find yourself often depleting the random data source, I would advise you investing in a hardware random number generator such as http://www.entropykey.co.uk/.

You are typically limited to the amount of random data that can be generated by the random number generator hardware on your CPU. External devices such as these can generate good random data at a much faster rate.