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 lwn.net:

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?

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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