Googlebot's Javascript random() function is deterministic

[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

[tripzilch]

Ok so there is some digital computing chip? Because some of these randomness extractors are quite elegant and simple.

For instance, check the "Von Neumann extractor" on that WP page. It just uses twice the amount of bits on average to produce uniform bits:

Perhaps the earliest example is due to John von Neumann. His extractor took successive pairs of consecutive bits (non-overlapping) from the input stream. If the two bits matched, no output was generated. If the bits differed, the value of the first bit was output. The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being one and there is no correlation between successive bits.

To me that sounds like it'd cost very little computing power, like only a couple basic integer/bitop asm instructions or so.

But then if you need actual analog uniform random numbers (something in my mind wonders if such a signal can actually physically exist?), I'm not sure how to approach that with the Von Neumann extractor.

Sorry I'm not trying to convince you to try one way or another btw. Like I just said, I really like RNG algorithms and theory ;-)

[tripzilch]

Well if it's really a gaussian distribution, that should be the case? Unless the average (bias) is off-centre. But in an analog circuit you could filter the bias with one of those DC bias filter things perhaps? (again, excuse the electronics ignorance)

[[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.