Practice Cryptography!

Another endless source of amusement for me is the lack of understanding that people have about what they need to do with random numbers... as in, how to generate them, how to use them, and how to prevent them from being found after they're used.

In order to be secure, a cryptographic system requires a truly random source of information -- the measure of which is called 'entropy'. The problem is that there are relatively few places where such information can be obtained from a normal, everyday, consumer-level computer.

A correspondent of mine, Philipp Gühring (of the CACert.org project), sent me a paper describing some possible sources of entropy that are available in most computer systems (the effect of the brownian motion of air in changing the precise timing of a hard disk's read head obtaining the proper data being one of them), and possible ways to make use of them to obtain truly random data (causing artificial thrashing of the swap file and measuring the read and write times, for example). There is only a little bit of trouble with this approach: it really doesn't create that much random data per operation. This causes extension to be required, which is normally the realm of hashing algorithms. However, even these hashes have to be expired, once the chaos that led to their creation is exhausted.

(As an aside, there's a government standard -- FIPS 140-2 -- that mandates the parameters of any encryption used by the US government. This standard actually doesn't certify 'nondeterministic random number generators' -- the technical name for 'truly random number generators' -- it only certifies 'deterministic random number generators' (pseudo-random number generators) of a specific algorithm. This could cause... issues.)

Linux, FreeBSD, Windows 2000/XP/2003/Vista, NetBSD, OpenBSD, Solaris 9 and 10... these all have built-in means of getting the entropy that the system generates on a fairly consistent basis into a random number generator device that is managed by the system. Alas, there's also usually a secondary pseudo-random number generator, which will happily continue giving pseudorandom bytes even if the chaos is exhausted. This isn't appropriate for cryptographic operations.

/dev/random is your cryptographic friend.
/dev/urandom is not.

(this oversimplifies, based as it is on the concept and requirement that the names refer to the proper device Major/Minor numbers.)

On MS Windows, there's an API called the CryptoAPI. (I'm going to get into the problems with this in another post -- there's absolutely NO excuse for their negligence in documentation.) This API will, upon request, produce pseudorandom and (according to MS, at least) cryptographically-practical numbers by applying the RC4 stream-cipher algorithm to a value with a perhaps-specified key.

Either way, though, if the numbers aren't random, then the encryption is open to attack, since the "keyspace" (the number of possible keys, usually 2 to the power of however many bits the cipher uses) is greatly reduced. (A brute force attack against 2¹²⁷ possibilities takes half as long to search as 2¹²⁸, 2¹²⁶ takes half as long as that, and so on. If an attacker can guess at the pool you're getting your random numbers from, that reduces the power-of-two dramatically, sometimes halving or quartering it... and 2⁴⁰ and 2⁵⁶ have been shown to be easily brute-forceable by modern hardware.)

So, how to make sure your source is random? I honestly don't know. For RSA, Philipp suggested chopping off the top bit and the bottom 8 bits, and testing the remaining bits for various statistical anomalies. I have not yet looked at his code [he's rather hoping that someone else will take over development of it], but it's available at RNGQA-light.tar.bz2 on his website.

As well, there's another issue: Proper usage of random numbers. This is a topic I'll go into in another post.