Cryptographically secure random number generation

[NickJohnson]

I've started using some random numbers for internal purposes on my OS, and I know for certain that I will need these to be cryptographically secure (i.e. actually unpredictable) if I want the system to be secure. Essentially, the security of my system depends on it being impossible to guess a 64-bit random number. What are some suitable methods for generating these sorts of numbers? What are good entropy sources to use? Is 64 bits enough? (The worst that could happen if the number were guessed is that a process would gain write access to one file, but not be able to spoof it's identity or change users, etc.)

This is obviously not very urgent, because I can just use a PRNG with suitable seeding for testing purposes, but I definitely will need to know in the future.

[turdus]

Creating a real random number is impossible. All well known pseudo random generator code has one weakness, the seed. If you can generate it unpredictable enough, you'll be fine. For this 64 bit is more than enough imho. The key part is, change it in a non-periodic way, like xor-ing with some (also changing) magic for every IRQ. This way your seed number will be changed whenever a network packet arrives or the user presses a key. Since every user has a different typing and mouse dragging habbit, this make things quite unpredictable. Also note the relying on network packets alone is not enough, a well crafted attacker can take advantage of it. Other sources (the more the better) needed.

[bluemoon]

Possible source are temperature readings, mic (if exists), key stokes, the (x,y) pixel of Astronomy Picture of the Day image, podcast channel wave pattern, or text feed from random google, etc.
You may also update the seed at random interval based on the source factors.
However, there is no true random as most readings from hardware may tends to some stable values in long run, unless you have some kind of antena to catch the CMBR.

[GAT]

For a random number generator I just use port 40h.

in al,40h

That get a seed, then xor it to some arbitrary value.

[NickJohnson]

It seems that collecting sources of entropy will be more complex than I thought. My system is microkernel-based, so it's difficult to do real I/O (like network requests or file requests) purely from the kernel. I guess I'll have to have some sort of entropy-collecting daemon to manage all of this.

I've been looking at Linux's drivers/char/random.c, and it seems tractable to just port it's core algorithm to my system. I was going to have the RNG partially in kernelspace for convenience, but since I'm now moving it to userspace anyway, the GPL stuff shouldn't be an issue.

[brain]

I would make the random generator a server, and add a get_entropy call to other servers most notably networking and keyboard, scheduler etc, using these to generate entropy. I would avoid deterministic algorithms and xor etc, these are liable to introduce security issues unless you are certain what you are doing. have you looked how other oses such as freebsd do it?

Edit: damn beat me to it takes ages to type replies on this phone...

[Brynet-Inc]

http://www.openbsd.org/cgi-bin/man.cgi? ... SD+Current
http://www.openbsd.org/cgi-bin/man.cgi? ... SD+Current

[qw]

You may use this internet service.

[Solar]

As laudable as that service may be - an internet source for cryptographic randomness? I see the words "man in the middle" jumping up and down in front of my inner eye...

[qw]

Well, the OP could use the numbers from the service to encrypt his communication with the service

EDIT: Okay, I admit, that was just plain stupid.

[invalid]

As laudable as that service may be - an internet source for cryptographic randomness? I see the words "man in the middle" jumping up and down in front of my inner eye...

Even if it was secure - I really hate when software initiates outgoing connections that I didn't directly request (or for self-update...).

[Brendan]

Hi,

Just wanted to add that some pieces of hardware do have true random number generators. The first I know of is VIA's "Padlock" where the random number generator is built into the CPU itself. I have no idea why Intel took so long to copy VIA, but they are planning to introduce hardware random number generator to their CPUs soon. I'm not sure what AMD is doing - I'm hoping they aren't going to do anything until Intel creates an (inevitably "not compatible with VIA") standard that AMD can implement too.

There's also a random number generator built into some Intel chipsets (specifically, "Intel(R) 810 Chipset Family, Intel(R) 815 Chipset Family, Intel(R) 830 Chipset Family , Intel(R) 845G Chipset Family" according to Intel's article).


Cheers,

Brendan

[Yoda]

The task of generating random sequence that can't be distinguished from true random sequence has real solution.
For this you need two key parts. 1 - seed, 2 - algorithm of sequence generation.
For the first the best way is to use combination of hard predictable sources:
1. BIOS timer counter;
2. Junk in memory;
3. CPU clock counter (rdtsc);
4. Mouse and keyboard events;
5. And of course, built into chipset (as Brendan wrote) quantum random number generator.
For systems with implemented security on file access there is one more source (one of the most powerful):
6. Previously stored seed. It may be generated by working RNG.

About size of number. 32 bit size is definitely weak. 64 bit is probably enough for most applications. But in case of distributed attack by an horde of zombied computers and supercomputers it may become insufficiently strong. 128 bit is now treated as strong enough for any possible attack.

RNG algorithm.
1. You take seed. Then encrypt it by strong cryptographic algorithm, for example AES. The result is the random number.
2. For the next number in sequence increment the seed by one and also encrypt it by AES.
Note! Don't take the previously generated number as the feed for next step of algorithm! You may run into the short loop.
At the system shutdown generate one random number and save it to the disk as a seed for the next system startup.

About combining the various sources for first seed. It is not enough for them to be just XORed together. The most powerful combination is feeding them one by one to the RNG algorithm. Take the first source, encrypt, after that XOR the result with the next source and encrypt it again. And so on. The last output will be the starting seed.

[Rudster816]

Times is an excellent source of seeds for PRNGs, but has no business as a seed for cryptography because it's guessed way too easily. The same is true for the RDTSC\Junk in memory methods because those are deterministic. The BIOS startup isn't black magic, it's the same every time so if you read the TSC at the same point in the kernel at each boot, the value is going to close enough to the same value every time to where a trivial brute force would guess. So long as a computer is off for a sufficient amount of time, all DRAM will be zero'd out on power up, so junk in memory can easily be reproduced reliably. Obviously cracking a kernel's RNG using these sources as seeds would be difficult, they are far from cyptographically secure. In fact, even introducing a predictable source of entropy is a risk even if used to complement an otherwise truly random source of data.

Also, I don't think using AES to as an RNG is a very good idea. Since encryption by it nature is reversible, if one were to know the key, you could trivially work out the seed based on a random number given from the given RNG. A better method would be to use a good hash function (e.g. SHA256), but I think a proven PRNG algorithm would be the best choice.


Making anything secure from a sophisticated attack is very difficult even for experts (just look at WEP), so I wouldn't lose too much sleep over not having a sufficiently secure implementation of whatever you're trying to do.

[Solar]

@ Yoda:

And that, dear sir, is why so many homegrown attempts at cryptography fail.

Just one example: You say to encrypt the seed, to yield a random number. How do you encrypt cryptographically secure if you don't have a random number yet?

Remember: "Cryptographically secure" means "secure even if Mallory knows the exact implementation of the algorithm"...