one algorithm … “to rule them all”

Posted: August 26, 2013 in technical
Tags: , , , , , , , , ,

Cristina gets bored very quickly.

Cristina is bored now.

What Cristina does when she gets bored… hrm… let’s see. I wanna build the best PRNG (pseudo-random number generator) function ever!

The first question is: what does it take a PRNG to make it “the best ever”. I had no idea. A bit of googling and bugging some specialised friends about it, I narrowed it down to 3 main things:

1. Statistical randomness

When it comes to randomness or technical requirements for any algorithms, one of the first places I go looking for requirements is the FIPS standards, more exactly FIPS 140 series on cryptographic strength of algorithms, more exactly FIPS 140-2 in my case. Another nice place I happily visit when in need for ideas on security design, principles and requirements is the NIST website, more exactly SP800-90 series in my case.

2. Cryptographic strength

This means that Mister “Bad guy” should not be able to predict bits in my PRNG output if he has access to a lot of the PRNG output already.

3. Security strength at n-bits

If the intended security of my algorithm is “n”, then Mister “Bad guy” should have to do 2^n (2 at the power of n) operations to break my PRNG.

Bear in mind that an algorithm which scores well in #1 is not necessarily secure in terms of #3!

Now I need to make my algorithm score as well as possible on the 3 classes above. I need a super-strong algorithm, to use a large pool of randomness, to generate a high amount of random output without “repeating itself”. Oh, yes: and I need it implemented in software 🙂

One my ask: why bother creating it in software if you can just acquire a hardware generator, also called TRNG? I agree that a TRNG is better in terms of security, it is non-deterministic and aperiodic. But I need something implementable in software, even if that means it’s gonna be deterministic and have a certain period.

to /dev/random or to /dev/urandom

Btw: my software is going to make use of this PRNG in a multi-threaded fashion and it will probably run on a small Linux box. I am already aware that the usual random functions I may find in different programming languages are not sufficient for my needs 😛 so I want something better, of my own. Of course, the randomness has to come from _somewhere_. My first guess: time to look into /dev/random and /dev/urandom. For those familiar to the Linux file types (for those who are not, have a look here). A first comparison between /dev/random and /dev/urandom shows that both provide randomness – no surprise there, I know.

They both provide random data from the kernel. But _how_ they do it is different. /dev/random takes data from an entropy pool; if the pool is empty, /dev/random will block until the pool is refilled. /dev/urandom makes use of a hashing algorithm if the entropy pool becomes empty, therefore never blocking the operation. Unfortunately, a small Linux box cannot possibly generate a large enough entropy pool for my paranoid needs. A TRNG would consider the level of quantum noise in my laptop’s electronic circuits or some other fancy quantum-random properties or non-quantum-random properties. But I only have software in here. /dev/urandom is clearly too permissive, so I would for sure go with /dev/random for now.

Btw: if you wanna know more about randomness in Linux, have a look at the articles of mister Jake Edge on

On entropy and randomness

Holes in the Linux PRNG?

Another nice article on the Linux PRNG is published by some nice guys from Israel, in iacr.

Sooo…my algorithm needs to have a large pool of randomness. It also needs to use it properly, and NOT abuse it 🙂 I don’t like my functions repeating themselves. It should also be controllable enough to generate as many characters as I like (somewhere between 4 and 128), and give me any combination of numbers, low- and upper-case letters, special characters and so on.

This immediately shows that even /dev/random + a hash algorithm is not sufficient (though passing it through a hash function should ensure it’s forward-secure), as it does not output special characters. Talking about forward-(and backward) security. Forward security (also called Prediction resistance) means that if Mister “Bad guy” gets a hold of my PRNG’s state X, he should not be able to deduce state X-1. Similarly, backward security (also called Backtracking resistance) means that if state X is compromised, the attacker cannot make any inference about state X+i, where i can be any number. And no, I am not too paranoid about these 2 aspects, because it is not super-difficult to break into a PRNG. One can use physical access or buffer overflows – you name it. But I should not assume that the state of my PRNG is hidden safely somewhere in the Linux box.

A nice analysis from the hacker’s perspective is done by Mr. Gutterman in BlackHat 2006.

Hrm, what can I do to obtain special characters? One option is to simply obtain whatever binary output the PRNG gives and use base64 to encode the result. This ought to bring some special characters. Still: it does not give me any more control over how many of them I want to have, for instance. I will worry about this part a bit later.

Now I look around for an algorithm with a good random generator to provide me forward and backward security, with a large enough entropy pool and with a good-enough seeding design to ensure security when reseeding with the same pool. Because Papa Schneier is one of my all-time favourite security geeks, but only just because of that, I had a look at Fortuna. Btw: this one was designed by Schneier and Niels Fergusson. Fortuna seems to be the best so far, in terms of recommendations I had from my friends and from my own research. It also has some nice open-source implementations.

Another option I’ve been given is timer_entropyd, by vanheusden. I am unsure yet about its capabilities: it basically says it feed random data into /dev/random. Is it better than the 32 entropy pools used by Fortuna?

Can I use any of these algorithms to control the amount and looks of my output?

What other options do I have?

Why can’t I produce entropy out of thin air?


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s