More Than Five Years In The Making: Creating A New Linux Random Number Generator

[CochainComplex]

https://xkcd.com/221/

That's why ps3 got back Linux again. The hackers found exactly this random function and where able to crack it because of that very reason.

[Ironmask]

How did you test your generators, just probability distribution or there other tests that you used?

Not sure if you're into probabilistic theory, but wondering what you think about nuclear decay for RNG? (AFIAK many casinos have to use it by law)

I always wondered why all consumer computers don't have some sort of environmental RNG using something like background radiation or something. Is it too expensive? Would the electronics be too big? Or is it simply not something the industry cares about?
I guess for consumer electronics the user's input is perfectly random enough anyway.

[KesZerda]

I always wondered why all consumer computers don't have some sort of environmental RNG using something like background radiation or something. Is it too expensive? Would the electronics be too big? Or is it simply not something the industry cares about?
I guess for consumer electronics the user's input is perfectly random enough anyway.

Most modern CPUs do have a hardware random number generator that works off physical effects like thermal noise, diode noise, and other sources. x86 CPUs have the RDRAND/RDSEED instructions, Arm's TrustZone has an API, OpenPower has an rng function, etc. However, to make sure things are as random as possible, and that potential weaknesses in any given RNG are mitigated ahead of time, OSes don't use these functions raw. They'll instead mix together randomness from various sources, and do some massaging in software, to ensure things are random and detached from any easily observable vulnerabilities. Additionally, hardware random number generation is often fairly slow -- RDRAND for example takes hundreds of clock cycles for up to 64 bits of data -- so software algorithms, which tend to be much faster, are useful for if you need a lot of random data.

[phred14]

How did you test your generators, just probability distribution or there other tests that you used?

Not sure if you're into probabilistic theory, but wondering what you think about nuclear decay for RNG? (AFIAK many casinos have to use it by law)

NIST 800-90b Entropy Evaluation Suite. I know enough to know that I can't do better, though we did know that the results of one test had to be taken as pessimistic. That part was improved on a later version of the suite.

As for your own TRNG, the devil is in the details. Even if the radioactive source could do a "perfect" job, don't forget that you're using a human-designed detector. Power and temperature fluctuations may not affect the radioactive source, but they may affect the detector. Then you also have to worry about side-channel leaks, say if your detector has a blip of higher current consumption when it sees a particle. There are special circuit libraries designed to have constant power regardless of the logic states applied, as one example of a mitigation. The list goes on... and on... and on...

[Turbine]

It can be as easy as this. You can even initialize it with an init value so it is not always the same sequence:

unsigned int add_rand(unsigned int init)
{
static unsigned int i = 55 - 55, j = 55 - 24, rnd[55] = {
2119143891, 539910039, 1575653545, 2895236586, 720721766,
3796759033, 2168811136, 4164009002, 1900432158, 2159501702,
1130496637, 3333382236, 3052557060, 2695495719, 1318991387,
2738962699, 2185866067, 48629606, 2329654333, 679289708,
1718021111, 1271830277, 1724388399, 302011795, 2652267456,
1998782778, 917190237, 2249349853, 994983638, 1523084771,
3092548715, 1348680929, 1387745169, 684553147, 3000244631,
399773554, 4254444685, 3409797126, 2372139430, 1961762825,
1714777267, 3827680163, 1666351833, 2668833907, 2954262917,
999306914, 1816480068, 3799268783, 4133402570, 4233338020,
3633793169, 4077180655, 1431655054, 773436891, 3213814927 };

unsigned int new_rnd = rnd[i] + rnd[j];
new_rnd ^= init;
rnd[i] = new_rnd;

if (++i == 55) i = 0;
if (++j == 55) j = 0;

return new_rnd;
}

But hell I wouldn't use it for anything else than fun and gaming...

That's not random at all.

[George99]

That's not random at all.

That's why it is called a pseudo random number generator.

[hotaru]

But hell I wouldn't use it for anything else than fun and gaming...

if you want a PRNG for that, this is much better:

typedef uint64_t uint64x2 __attribute__((__vector_size__(16)));

uint64x2 rnd(uint64x2 *state)
{
  const uint64x2 s0 = state[0],
                 s1 = state[1] ^ s0,
                 v  = state[1] + s0;
  state[0] = ((s0 << 24) | (s1 >> 40)) ^ s1 ^ (s1 << 16);
  state[1] = (s1 << 37) | (s1 >> 27);
  return v;
}

but still not good enough for the Linux kernel.

[rabcor]

If you're not joking, then you're completely missing the point. In fact, "just random numbers" are incredibly difficult. One of those difficult aspects is designing a random number that can't be made slightly less random by "external attacks" like changing voltage, temperature, etc. Yes, my day job does involve random numbers, and though at the moment I'm not designing a random number generator, I have done one.

I was joking, I know how hard it can be, but I also know how hard it can not be, it depends on your goals but at the same time I am aware of the likely goals that this rng would have that would make it so hard to develop (which happens to be exactly what you mentioned). So I was indeed mostly joking... mostly joking but still... 5 years...

MS-DOS: 6 weeks
Google Chrome: 2 years
Windows 1.0: 4 years
A random number generator: 5 years and counting, not ready yet.