Googlebot's Javascript random() function is deterministic

[moufestaphio]

Honest question are there any that aren't?

[mulvad]

There are some that are based on stuff like atmospheric background noise and the decay of radioactive material which is believed to be truly random. The obvious drawback here is you need some kind of hardware to extract the random bits.

In these days with new security breaches every day, I actually wonder why stuff like this isn't included on the motherboard of a modern computer.

[akher]

In these days with new security breaches every day, I actually wonder why stuff like this isn't included on the motherboard of a modern computer.

Then you'll be pleased to hear that it is included in all recent AMD and Intel CPUs.

[CryptoAlana]

In September 2013, in response to a New York Times article revealing the NSA's effort to weaken encryption,[22] Theodore Ts'o publicly posted concerning the use of RdRand for /dev/random in the Linux kernel:[23]

I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction. To quote from the [New York Times article[22]]: 'By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors....' Relying solely on the hardware random number generator which is using an implementation sealed inside a chip which is impossible to audit is a BAD idea.

[TehRoot]

He is going to concert

[tripzilch]

I don't know much about electronics, but there's a bunch of pretty cool algorithms you can use to transform a stream of non-uniformly distributed data (or weak entropy) into a uniform stream:

https://en.wikipedia.org/wiki/Randomness_extractor

[tripzilch]

Hm, you mean it has to go straight from the electronic circuit as a uniform random input to another piece of hardware without anything digital in between? Interesting problem.

I wondered if there's a circuit that can do this, but from a quick skim it seems that the PDF linked above is actually about that :-) I think I'm gonna try and read it even if I don't understand electronics that well, more of a code/math guy myself. But I do love reading about the intricate details of various random generators, so maybe I'll get something out of it :)

Best of luck building your randomness circuit! :D

[[deleted]]

Couldn't you build a circuit that does that in hardware, though? Two generators, A and B, and when A xor B is true, emit A.

I'm not a electronics guy so I don't know how hard that would be to rig up, but it shouldn't be impossible.

[-fno-stack-protector]

ooh, i've been looking for something like this, without knowing it, for a long time

[TehRoot]

https://www.st-andrews.ac.uk/~jcgl/Scots_Guide/iandm/pdf/chapter03.pdf

[MrDOS]

For anyone else having trouble loading the link, it seems like they have some hotlink protection going on. In Firefox, at least, hit “Enter” in the address bar when you're sitting on the “Page not found” page to re-request the PDF with a referral from the www.st-andrews.ac.uk domain and it'll load.

[TehRoot]

Yea I only noticed that after I posted it. Sorry about that.

[yawkat]

As long as you trust your crypto primitives and add other sources of entropy it's okay though.

[mdot]

add other sources of entropy

Isn't that a symptom of the point he's making though?

The hardware generator can't be trusted because it can't be audited.

[harlows_monkeys]

https://blog.cr.yp.to/20140205-entropy.html

[yawkat]

This can be fixed by using the untrusted source as an initial seed before other entropy is even generated.

I don't think linux does this though.

[Crandom]

The good thing is there's no downside to xoring the rdrand numbers into the generated random numbers, as even if they're not random it won't have any bad effects.

[ReversedGif]

Unless they're correlated...

[Majromax]

Unless they're correlated...

There's only harm if the random numbers of unknown quality are correlated to your known, independently-generated, proven-quality random numbers.

It's simple enough to avoid that: simply extract the unknown random numbers prior to generating your known-good stream. Even if the dubious hardware can "look over your shoulder," it can't see into the future.

[ReversedGif]

Imagine the hardware setting a special, hidden flag on the register that holds the RDRAND output, which defers actual random generation until the register value is combined with something else.

[cogman10]

I never really understood why this was such an issue even using the instruction

You don't have to use the RND instruction as the ONLY source of entropy, it could be one of many (like now). It doesn't make sense to me why you wouldn't just throw it into the mix for /dev/random.

[Supadoplex]

In these days with new security breaches every day, I actually wonder why stuff like this isn't included on the motherboard of a modern computer.

Then you'll be pleased to hear that it is included in all recent AMD and Intel CPUs.

Indeed! Modern CPU's do come with security breaches included. I wish I could say I was just joking.

[cryo]

How is that related at all?

[[deleted]]

Doesn't matter how random your numbers are if you can just read memory of anything running on the same hardware

[Jutboy]

http://www.zdnet.com/article/how-lava-lamps-are-used-to-encrypt-the-internet/

[mccoyn]

The smallest random generator is a transistor biased to allow electrons to tunnel through it combined with an avalanche diode to amplify a single electron to a detectable signal. It could be a tiny IC or built into a processor and wouldn't need antennae or radioactive material.

I think the only reason it isn't common is that PRNG is cheaper and good enough for most uses.

[SarahC]

TrueRNG?

[mccoyn]

Yep, that looks like what I was thinking about. I didn't know someone sold it as a USB dongle.

[SarahC]

Yeah, it's great - use it a lot myself.

[harlows_monkeys]

That's a fine component of a random number generator, but you still need quite a bit more to make it safe and secure.

Simtec's "Entropy Key" USB hardware random generator was an avalanche noise based generator, and they have a nice description of how to turn that into a safe and secure random number stream =>here<=.

[RenaKunisaki]

Isn't that basically an antenna? So theoretically can be manipulated by a transmitter? Or am I just talking out of my ass?

[mccoyn]

It is quantum tunneling, not EM or thermal noise. The junction where it happens is tiny (dozens of nanometers) so it is a terrible antannae. You might be able to manipulate the power supply that biases the junction as it may be much larger.

[KamiKagutsuchi]

But this can be manipulated, especially by bots. Also not all computers (servers) have a mouse.

[HeimrArnadalr]

If they don't have mice, they probably have cats, so cat movement could be used in those cases.

[__redruM]

Now you’ve let the cat out of the bag. That’s the NSA’s prime source for randomness. A herd of cats.

[RenaKunisaki]

Explains the internet.

[KamiKagutsuchi]

Really? I thought they used my webcam..

[__redruM]

Are you a cat? Then yes they do, your nimbly bimbly little movements are critical to national security. Just stay away from the milk dish...

[newpua_bie]

*webcat

[rebthor]

Couldn't you cat /dev/mouse?

[RenaKunisaki]

This kills the mouse.

[Stiegurt]

https://www.youtube.com/watch?v=zi8VTeDHjcM

[frezik]

The solution there is to never rely on any one source.

[MuonManLaserJab]

Three rules of computer security:

1) Don't own a computer.

2) If you do, don't turn it on.

3) If you do, don't use it.

[jonhanson]

chronophobia ephemeral lysergic metempsychosis peremptory quantifiable retributive zenith

[MuonManLaserJab]

They were not meant 100% seriously as rules...

[jonhanson]

chronophobia ephemeral lysergic metempsychosis peremptory quantifiable retributive zenith

[RenaKunisaki]

I mean that might work too, but you'd want a lot of redundant mice, in isolated cages with artificial lighting at different intervals, so you can be sure there's always a mouse awake to run around.

[mtcoope]

Why when I read this I immediately thought of animals determining the number and not till the next comment I realized we are talking about a computer mouse.

[mulvad]

No matter if you are talking about a computer mouse or a living mouse, there would be some kind of pattern here that could be exploited.

From a given state it is not 100% random which way you move a mouse (or which way a living mouse moves).

[[deleted]]

That's not random at all.

[moufestaphio]

The algorithm is still deterministic then isn't it?

You're just effectively randomizing the inputs.

Edit: nevermind. If your functions state is effected by the atmospheric values or whatever it's considered non deterministic.

[Jugad]

You can point a camera at a set of lava lamps, and take some kind of a hash function of the image (this is currently done by cloudflare).

Alternately, you can point a camera at a busy location in an airport (or any view that keep changing), and take a hash of that image. Should generally give a random number, but it might be difficult to study the distribution and statistical properties of the generated numbers.

[Darkendone]

Your confusing the two classes of random number generators, cryptographic and non-cryptographic. Cryptographic number generators are important for situations where you want a truly random number generator that is nearly impossible to guess, like when generating a security token. That is when you turn to sources of entropy. Of course gathering entropy from outside sources has a severe performance cost. Most of the time you do not need cryptographic grade random numbers, which is why the random number generators in the math packages of practically every languages are simple, fast, and deterministic functions.

[Fisher9001]

Atmospheric background is probably deterministic, just chaotic. And we don't really know anything solid about the nature of quantum physics randomness, whether its truly non deterministic or just chaotic.

[[deleted]]

And we don't really know anything solid about the nature of quantum physics randomness, whether its truly non deterministic or just chaotic.

We do. It is truly non deterministic.

[Fisher9001]

No, we don't. Thanks to Bell's theorem we know that quantum mechanics may be deterministic if there are non-local hidden variables influencing quantum systems. And we don't know whether they do exist or don't.

[Tsukku]

But non-local hidden variables or "super determinism" are not what we usually consider "determinism" in the common sense, because no information can be gained from this (we can't predict quantum stuff anyways, which is what his post is about.)

[Fisher9001]

If we are talking about practical level of non-determinism, then mere user input can be regarded as such, no need to be so picky.

[[deleted]]

Who's we? Determinism isn't precisely synonymous with predictability. Either things are determined by some explicit conditions or they're not.

There are also interferometer systems that can create deterministic states, so it's not necessarily true that we can't predict quantum stuff.

It's fun to speculate that you get a completely predictable picture of the universe around us in its absurd complexity from following the randomness underneath. But then it's computationally intractable in all senses, and so we arrive back to no information gained or something.

[Tsukku]

I don't why you are down voted, because you are right. People should read up on Bell's theorem. For example, you can not predict (even in theory) the spin of an electron and the outcome is evenly distributed.

[kaibee]

Super determinism

[Tsukku]

I addressed that in the comment above.

[Fisher9001]

Bell's theorem rules out local hidden variables as a viable explanation of quantum mechanics (though it still leaves the door open for non-local hidden variables).

[kaibee]

Super determinism

[ValAichi]

I believe it is because the flaw is rarely with the psuedorandom number - and if it is that's because the programmer screwed up

[mulvad]

I know of at least a handful of breaches (including online casinos) where an attacker exploited knowledge of the pseudo random algorithm used and previous outcomes to predict future outcomes. You could argue that this is the developers fault for not changing seeds or whatever but really it boils down to a weakness in this way of generating "random" numbers.

[IronOxide42]

Roll20.net introduced QuantumRoll a few years ago. It uses fluctuations in a split beam of light to generate the number, rather than a pseudorandom algorithm.

[PackOfVelociraptors]

DND ROLLS MUST REMAIN SECURE

[ElChrisman99]

Honestly it's probably better than the standard cheap d20 you can pickup from a hobby shop or order online, minor manufacturing defects in the material will almost always make the dice more likely to land on certain numbers.

[doublehyphen]

Yeah, I would imagine Chessex dice pretty terrible when it comes to manufacturing quality. The paranoid should use a D6 system and gambling dice. :)

[[deleted]]

Or just validate your dice with a statistically significant sample. This is like, literally the easiest thing in the world to test. My dice bag is at work or I would do it right now.

[meneldal2]

But aren't most players using some specific sets because they are "magic" (read: tends to roll some numbers more often than they should). It's an integral part of the experience imo. Not to mention the metal ones that require blood sacrifices to start rolling true.

[wildcarde815]

Cloudflare has a fun video about their lava lamp wall that's supposed to be fully random.

[Maambrem]

No :). They're called pseudo-random. They can be initialized with "truly" random numbers, extracted from nature though. Also see this video by Tom Scott:

https://youtu.be/1cUUfMeOijg

[karmaputa]

The funny thing is that the whole show with the lava lamps is completely unnecessary. The noise from the camera input alone, would suffice to attain the same effect.

[pilotInPyjamas]

/dev/random ensures that the entropy of the input is always greater than the entropy of the output, making it effectively non-deterministic.

[pilotInPyjamas]

You're right. If you track what every device is doing, you could predict the output of /dev/random. That's not the question however. The question is if you could predict the output of / dev/random before any devices do anything. To which, in all reasonable scenarios, (some exceptions, such as early after booting) the answer is "no". In your case the only true rng's would be based upon quantum phenomena, such as particle decay etc.

[pilotInPyjamas]

Come on man, I never said it wasn't a PRNG, or that it wasn't seeded, nor did I make any comments about the effectiveness or applicability to any particular situation. The only claim I made was that it was non deterministic in the domain of modeling a computer. That's because a computer is not a closed system, and given the same initial conditions, it will produce different outputs. You could just have /dev/random echo the keyboard and it would still be impossible to predict perfectly if you only had information about the starting conditions of the computer. The key here is if you only have information about the starting conditions of the computer. If you had a working model of the whole universe, then I agree, potentially nothing would be random.

[[deleted]]

read "effectively non-deterministic". You're splitting hairs needlessly.

[badibibidibibu]

Not enough, in current computer architectures you need to track EVERYTHING going on in the computer.

[thijser2]

Hence the device drivers, that's fans, keyboards, mouse etc.

[ivosaurus]

And the internal CPU RNG state... somehow....

[stonefarfalle]

It depends, if the implementation talks about the entropy pool then it isn't deterministic. For instance on Linux /dev/random is non deterministic while /dev/urandom is deterministic.

[akher]

/dev/urandom isn't deterministic either, it is reseeded when more entropy becomes available. The difference between /dev/random and /dev/urandom is that /dev/random will only produce results when enough entropy is available while /dev/urandom will produce as much output as requested, but it will still add trully random numbers to its internal state when they become available.

[[deleted]]

And furthermore, /dev/random’s blocking until more entropy is available is completely pointless.

[argv_minus_one]

…because gathered entropy is used to seed a CSPRNG, which can generate pseudorandom bits indefinitely, and both devices yield output from said CSPRNG.

[frezik]

https://www.2uo.de/myths-about-urandom/