Perl Encryption Primer: The Importance of Randomness

I’ll be doing a presentation for MadMongers in April on encryption in Perl, and I’m going to try something a little different. This series of blog entries will lay out a written primer on encryption in Perl, which will then form a condensed outline for the presentation. I feel the final presentation should have high-quality information, so hopefully anything I get wrong can be pointed out and corrected before then.

We’ll start with the most fundamental building block of encryption, which is random numbers. Now, a naive new programmer might jump right in and start calling rand():

The int truncates the decimals; it would otherwise return a float. The parameter to rand() tells it the maximum number, which is 1 by default. The code above will return a number between 0 and 10,000.

Here, we already hit two different hidden snags:

  1. Random numbers are surprisingly difficult to do right
  2. Computers are deterministic machines. You can’t get much randomness out of determinism.

The rand() function starts with a seed. You can put in your own seed with srand(), or you can start out with the seed Perl gives you by default. The means Perl uses to get that initial seed is actually quite complicated; look at util.c and search for the function “Perl_seed” for the gory details.

Notably, if we put in our own seed, call rand() a few times, and then do it again, we’ll get the same output:

Same pattern each time! This means that an attacker doesn’t need to know the output of rand(). They just need to know what srand() input you started with. Let’s say you give srand() a 32-bit input. You then use that generate a 128-bit key for a cipher. This means that your cipher doesn’t have 128-bits of security; the attacker only needs to brute force the 32-bits that you put into srand(), which is a far easier task.

This brings us to an important consideration in security, which is building things in chains versus building things in layers. A chain is only as secure as its weakest link. In the above, the 128-bit block cipher only had 32-bits of security, because srand() was part of its chain.

Building in layers is more like a castle. Breaching the outer wall doesn’t mean you’ve breached the inner walls. Breaching the inner walls still leaves you the Keep to deal with. The Keep may also be built of narrow, maze-like hallways with the defenders attacking from above. This is defense-in-depth. We won’t be explicitly covering building in layers in this post, but it’s good to keep this in mind when building security systems.

For this and other reasons, rand() is not the right choice for a cryptographic-strength random number generator.

There are random number generators that can take a longer seed, but this leads to another question: where did you get the seed from? If it’s a timestamp, the attacker may be able to make a rough guess of the time period when you first generated that key. That could easily end up with even less than 232 possibilities (as in the case of 32-bits of randomness). Whatever else you use, can you be confident that an attacker can’t narrow down the input seed?

We end up needing to be really careful about where we get our random numbers. Since computers are such deterministic machines, we need a source that is somehow external to the computer.

Preferably, all computers would come with a special piece of hardware. Intel and AMD both used to put one in their chipsets (i8xx and 76x-based motherboards, respectively), but these fell into disuse. The VIA PadLock Security Engine also has a hardware RNG on their CPUs. Intel has also returned the hardware RNGs with RdRand on IA-64 CPUs.

If you don’t have a specific CPU, then there are also ways to add hardware for generating RNGs. LavaRnd was a project that used a web cam in a dark environment to pick up on cosmic background radiation, which can be used for randomness. Sadly, the project hasn’t been updated in quite some time. There are a number of other hardware RNGs to purchase, ranging from cheap to very expensive. I would urge careful research before buying any of them.

If we can’t buy hardware, then there’s an option to take randomness from the world around the computer. Consider that there is a slight variation between the timing of your keystrokes and mouse movements. By having the OS kernel listen in on this data, a random number generator can use this as input. This and a few other things is what the Linux /dev/random driver does. Similar techniques are used on Windows, Mac, and most everything else.

One problem with this approach is headless servers. Since they rarely have keyboard or mouse in use, the few remaining sources might not be enough. /dev/random will block until it gets more random numbers. /dev/urandom will continue onward using lower-quality sources, which isn’t what we want, either. This is where proper hardware random number generators come into play.

No matter what OS you use, Crypt::Random is the Perl module to use. This will use /dev/random on systems that have it, and the userspace Entropy Gathering Daemon on systems that don’t. It’s easy to use:

The Size parameter is the number of random bits to generate, and Strength set to 1 says that we won’t fallback to less-secure alternative.

Next post will be on One Time Pads, which is an encryption algorithm so good that we can never use it.

Website Pin Facebook Twitter Myspace Friendfeed Technorati del.icio.us Digg Google StumbleUpon Premium Responsive

Tagged , , , , , , . Bookmark the permalink.

10 Responses to Perl Encryption Primer: The Importance of Randomness

  1. Rjamet says:

    You’re missing an important point : even when it is correctly seeded, rand() is not a cryptographically secure random generator, and you should absolutely not use it in this kind of applications.

    http://perldoc.perl.org/functions/rand.html

    • Timm Murray says:

      I was hoping the reader would come to that conclusion on their own based on the narrative, but it’s probably a good idea to state it explicitly. Edited a line in.

  2. Jim Davis says:

    The int puts rand() into integer context; it would otherwise return a float.

    There isn’t an “integer context,” int just truncates the decimal portion of what rand returns.

  3. Dana Jacobsen says:

    Personally, I’d recommend Bytes::Random::Secure over Crypt::Random. If you want bytes from /dev/random, I think Crypt::Random::Seed is a lighter alternative to Crypt::Random (e.g. no need for Math::Pari), and it’s easy enough to use the from_hex methods of Math::BigInt, Math::Pari, Math::GMP, Math::GMPz etc to make a big integer if that is what is needed.

    /dev/random vs. /dev/urandom is definitely something not everyone agrees on. Note that Win32’s Crypto API uses a well seeded CSPRNG, so really is no different than /dev/urandom.

  4. David says:

    My favourite is Crypt::PRNG which is not only cryptographically secure (as other mentioned alternatives) but handles thread/fork-safety

    BTW: CryptX distribution (that includes Crypt::PRNG among others) is probably worth mentioning if you are gonna talk about cryptography in perl

    • Dana Jacobsen says:

      CryptX is very cool. I think it’s a good option. By default it does Fortuna seeded with /dev/urandom, Win32, or a backup userspace voodoo entropy method (not dissimilar to Crypt::Random::Seed’s backup method — timer entropy mixed with sha256).

      All of these except Crypt::Random will do the right thing on Win32. The sources and ordering is different in each (e.g. EGD comes after /dev/[u]random in Crypt::Random, comes before them in Crypt::Random::Seed, and isn’t used in CryptX).

      I think a downside of something like hotbits (e.g. Net::Random) is that for crypto purposes you probably don’t want to get your data over the net (basically what Net::Random says in “Security Concerns” — it’s not that we don’t trust Fourmilab, it’s that there is a big communication path that could be subverted or eavesdropped on). If it were fed into a mixer with other sources (e.g. Fortuna, Yarrow, or added to O/S entropy pool) that could be useful.

      If one can’t get a hardware random device (e.g. Entropy Key), HAVEGED (http://www.issihosts.com/haveged/) is a good alternative, especially for headless servers or cases like CPAN smoking.

  5. Meir Guttman says:

    Another option is HotBits: Genuine random numbers, generated by radioactive decay https://www.fourmilab.ch/hotbits/

  6. Jason says:

    It’s impossible to read the output of your code snippets without copying and paste the page into a text editor. The code snippets are showing black text on a dark blue background for the output of the perl commands. Please consider changing it to something readable. It’s currently serving as a barrier to understanding your article.

    • Timm Murray says:

      I’ve updated all example code to be parsed by the syntax highligher as bash instead of Perl. That should look much better.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">