back to article Big Bang left us with a perfect random number generator

UK Home Secretary Theresa May will have to revamp the Investigatory Powers Bill to ban astrophysics: the cosmic background radiation bathes Earth in enough random numbers to encrypt everything forever. Using the cosmic background radiation – the “echo of the Big Bang*” – as a random number generation isn't a new idea, but a …

Re: How random is random?

"..dipped into a strong Brownian motion source."

Oh thanks for offering, I'll take milk and two sugar please.

6
0

Re: How random is random?

Olius, yo should look at the work DJB does.

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

There are potential attacks against multiple random sources at the CPU level, of course they would only be practical if say the NSA has replaced the microcode of the CPU you are using.

1
0

Re: How random is random?

Thanks v much for the answers chaps, I'll have a read.

Re: reseeding a pseudo-random number generator - that's not quite the same effect because you would end up with small predictable sequences within your pool. If you instead create a pool and stir it, you would (in my mind) break all the relationships between all the numbers in the pool. Does that increase "randomness"? No idea - quite possible only in my fragile, poorly read mind ;-)

1
0
Silver badge

Re: How random is random?

If you instead create a pool and stir it, you would (in my mind) break all the relationships between all the numbers in the pool. Does that increase "randomness"?

Depends on which definition of "randomness" you mean.

First, though, note that you don't "break all the relationships". Even a "perfect" cryptographic hash function, if such a thing even has a sensible definition, can't introduce new information entropy. So while the "stirring" process does hide those relationships, by discarding some entropy (compression) and rearranging what remains (mixing), it can't eliminate all of them. That would cause it to produce information out of nothing; you'd have the information-theoretic equivalent of a perpetual motion machine.

Now, as to the question of "increased randomness": This approach does not increase randomness in information-theoretic terms. Under Shannon's definition of information entropy, randomness is the same as information content, and you can't produce more information by encoding the message differently.

Similar results apply to Kolmogorov's three definitions of information content, or Chaitin's. Under the algorithmic definitions offered by Kolmogorov and Chaitin,1 this sort of "stir entropy into a PRNG" construction (which as others pointed out is widely used) has only a small constant increase in information (or randomness) over the entropy source - and that is the size of the smallest program that can implement the stirring algorithm.

However, we can also talk about other definitions of randomness. Statistical randomness, for example, is a matter of how random - pattern-free - the output appears to be under various statistical measures. The stirring process, if it's good, should increase statistical randomness.

We can also talk about practical randomness or unpredictability. Outside straightforward statistical analysis, a pseudorandom sequence might still be predictable with a significantly better probability than guessing, for example by training a Markov model to recognize patterns in it. Here, too, a good stirring mechanism should defeat feasible implementations of predictive algorithms. Ideally you want output that's incompressible in Chaitin's sense - the smallest program for producing it is as large as the output itself. That's impossible with a PRNG that produces unbounded output, but the bigger you can make that hypothetical "smallest program", the better.

There is a ton of material on this subject - both the theoretical stuff (all the folks I named above, and others) and the practical material from cryptographers and cryptanalysts who've looked into CPRNGs. But the short answer2 to your question is "it depends on what you mean by 'randomness'".

1Invented independently but at pretty much the same time. They were both inspired by Shannon and the metamathematical intellectual tradition (considering mathematical formalisms as objects of mathematics in themselves): Turing, Godel, Church - who in turn had been inspired in no small part by Hilbert's Entscheidungsproblem, which Chaitin has rightly identified as probably the most useful unsolvable problem in mathematics. It more or less led to the entire IT industry, which is a pretty good result for a failed project.

2Too late!

4
0

Re: How random is random?

An amazingly in-depth answer - thank you very much. I'll have to read this through a few times and google some of the terms you use I think to fully understand it :-)

1
0
Coat

NIST compliance

'Except for one thing: back when FIPS was created, the standard didn't consider astrophysical sources for randomness, so it stipulates that “the RGB or portion of the RGB cryptographic module that generates the key must 'reside' within the FIPS 140 key-generating module.”'

So if the key-generating module is the universe, the CMB is within the module, no?

2
0
Silver badge

Re: NIST compliance

So if the key-generating module is the universe, the CMB is within the module, no?

Yup! Now someone just has to get the entire universe FIPS 140-2 validated by the CMVP.

I kid, of course. You'd only have to submit our Hubble volume. Everything else is out of scope.

0
0
Silver badge

Aren't RNGs based on de-tuned radio noise already using the Big Bang as source...? What exactly is new here?

0
0

WIth de-tuned FM radio all you need is someone transmitting on the same frequency and suddenly your radio is not de-tuned any longer. I suspect that transmitting in the required microwave bands to poison the CMB readings from radio telescopes would get noticed.

1
0
Unhappy

Paging Tom Clancy...

Wasn't the Mercury (not space) program in Tom Clancy's The Sum of all Fears based on this method? That was published 15 years ago. Apparently kids don't read anymore...

3
0
Silver badge

If you decode it and read it backwards

It says: Paul is dead.

2
0

And now for something completely different...

Randomness in images of lava-lamps

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

3
0
Silver badge

DoS attack

Anything relying on this for randomness could presumably be jammed / spoofed using the magnetron from a microwave oven? A signal orders of magnitude higher than the CMB would presumably saturate the sensor which would read either an error (jammed) or a known value (spoofed).

0
0

Re: DoS attack

In theory your sensor logic would report errors when the input source was too hot or cold. For example if the NSA is blasting your receiver with a high energy beam you may want to return (ERROR: Big Crunch Final Countdown) or if no input is picked up at the receiver (ERROR: Heat Death Has Occurred).

0
0

CMB on a budget

IIRC according to Brian Cox & Co. the snow on old fashioned analogue TVs was in part caused by the CMB. Surely a simple way to sample that datastream would give a practical random sequence..

0
0
Boffin

So 20th Century

>>"These days it's common to use the thermal noise generated by a zener diode"

une chapeau ancienne

These days we exploit the meta-stability of ring oscillators, especially inside all digital devices

0
0
FAIL

Re: So 20th Century & une chapeau ancienne

une chapeau ancienne

would have to be un chapeau ancien

1
0

Never Let an Astrophysicist do Cryptography

This article has many misconceptions. It's good that we have cryptographers to do the cryptography and don't leave it to the astrophysicists. My corner of the crypto universe is making RNGs.

The CMB may be entropic, but it is not in any way indistinguishable from uniform. You might expect gaussian noise with Raleigh or Recian fading, along with some secondary effects. A secure RNG could use an antenna as a noise source, but the resulting partially entropic data would need to be passed through an entropy extractor first.

FIPS 140-2 is a boundary spec. It says what must go on inside the boundary and provides rules for data crossing the boundary. Entropy input is absolutely allowed. The RNG in a FIPS 140-2 compliant module must be SP800-90A compliant and show it has a good noise source. However, while the gathering of noise must be in the module, the noise itself always comes from the environment in part from outside of the module boundary.

An antenna is an effective entropy source. Cell phones sometimes use them. However, compared to silicon entropy sources (http://www.deadhat.com/papers/uRNG.pdf) they are large, power hungry and have a horrible attack surface. Pointing an antenna at the sky makes no difference. Any antenna picks up noise, part of which is from the CMB. In this respect, the cell phone antenna is much better - It's smaller, mobile and has cryptographic verification on the data send over it, so you can know when the amplifier chain is linear and so know when the noise from the modem is not lost through limiting.

I strongly suspect the authors are not fully aware of the requirements for entropy extractors in SP800-90B (currently in draft, but if you're building an RNG now for a FIPS 140-2 context, that's what you're going to be complying with).

4
0

Re: Never Let an Astrophysicist do Cryptography

It is even worse because a known antenna as a source of entropy has a very obvious vulnerability. Thermal noise in a diode is difficult to gain phsyical access to but a huge antenna is anything but difficult to transmit to.

1
0
Silver badge
Pint

Zener diodes, transistors, ring oscillators and such ...as sources of noise

It seems obvious that such noise should be packaged up into 1kB blocks, and then written to pairs of multi-TB SSDs for physical distribution. The hardware would look like a HDD duplicating machine.

"Several TB of One-Time Pad should be enough for anyone."

2
0

Passing of Random Data

I'm still inspired by the scientist who would regularly send himself large blocks of random data over the internet. If enough of us shared email addresses and swapped random blocks it would play havoc with the spooks trying to look for interesting stuff. Not quite sure how you'd handle being asked for the decryption keys, although if you had an electronic copy of War and Peace, you could generate a key on the fly by xoring it with the random data.

2
0
Anonymous Coward

Re: Passing of Random Data

8207708300072188250415117521267707663773

31892251559270547281247861237688421462016

3141592653589793238462643383279502884197

16939937510582097494459230781640628620899

Hmmm... I think it goes badly wrong, about in the middle.

0
0
Silver badge

Re: Passing of Random Data

One way of looking at a perfect file compressor is that, without knowing the decompression algorithm, its output should appear to be a stream of random data. So you can always claim that random data is not an encrypted message, it's merely a message.

The fact that it doesn't decompress in ZIP, etc. is neither here nor there.

Of course, and alas, ZIP and its equivalents cannot actually get that close to the Shannon limit.

2
0
Anonymous Coward

Re: Passing of Random Data

8207708300072188250415117521267707663773...

ATTACKINPARISONFRIDAY13TH...

0
0
Silver badge

Re: Passing of Random Data

There are already multiple websites that claim to distribute true-random data, such as HotBits and EntropyPool. Of course, if you're not getting them over a secure channel, an attacker might substitute chosen data. And you have to trust the source in the first place.

(HotBits offers conventional TLS for a secure channel, so that's great, unless there are any problems with TLS or the X.509 PKI. Hmm. EntropyPool doesn't even use TLS.)

If such a scheme were popular, who's to say the NSA wouldn't set up a whole bunch of sock puppets sending data generated with DUAL_EC_DRBG? No one's shown how to distinguish its output from truly random data, but it's widely believed to be backdoored.

And if you already have a trustworthy channel, why do you need those "large blocks of random data"?

1
0

Until the NSA put some satellites up there that mimic this "Randomness" and make it decidedly "Nonrandom" /tinfoil

2
0

God doesn't play dice with the universe

If Albert Einstein was wrong on this quote, maybe the universe is a truly random number generator. If he was right, maybe the universe can be used as a pseudo random generator e.g. in the manner the article describes. I read an article in New Scientist a few years ago which claimed it to be inherently unprovable as to whether randomness is an emergent property of fundamentally deterministic physical processes (as in a very good pseudo-random generator whose algorithm is sufficiently obscure and whose cycles are sufficiently long as to be undetectable as such) or an inherent property of various physical processes. Current scientific opinion seems to regard Heisenberg's principle as suggesting the universe to be genuinely random, but I very much doubt there's any proof either way.

1
0

Page:

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Forums

Biting the hand that feeds IT © 1998–2018