Want a FIPS 140-2 RNG? Look at the universe. 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 couple of scientists have run the slide-rule over measurements of the CMB power spectrum and reckon it offers a random number space big enough to beat any current computer.
Not in terms of protecting messages against any current decryption possibility: the CMB's power spectrum offers a key space "too large for the encryption/decryption capacities of present computer systems". A straightforward terrestrial radio telescope, this Arxiv paper states, should be good enough to make "astrophysical entropy sources accessible on comparatively modest budgets".
http://www.theregister.co.uk/2015/11/12/big_bang_left_us_with_a_perfect_random_number_generator/
(Score: 3, Funny) by jdavidb on Friday November 13 2015, @01:30PM
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
Your comment violated the "postercomment" compression filter. Try less whitespace and/or less repetition.
ⓋⒶ☮✝🕊 Secession is the right of all sentient beings
(Score: 3, Funny) by bart9h on Friday November 13 2015, @03:24PM
number nine, number nine, number nine, number nine......
(Score: 0) by Anonymous Coward on Friday November 13 2015, @03:36PM
100110011001…
(Score: 3, Funny) by davester666 on Friday November 13 2015, @07:17PM
ROT26 should be enough for everyone.
(Score: 2) by JoeMerchant on Friday November 13 2015, @01:30PM
In 1997, Makoto Matsumoto san gave us a PRNG that is both sufficiently long in its period, and considerably cheaper than any radio telescope.
https://en.wikipedia.org/wiki/Mersenne_Twister [wikipedia.org]
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by jdavidb on Friday November 13 2015, @02:17PM
Yes, but a certain class of nerd is obsessed with obtaining "true" random numbers. I'm one of them. I visit random.org multiple times per day.
Please help me.
ⓋⒶ☮✝🕊 Secession is the right of all sentient beings
(Score: 2) by JoeMerchant on Friday November 13 2015, @02:24PM
Cosmic background radiation is not truly random, it's part of the intelligent design - if you hold the same attitude toward God as most of the Manhattan project members.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 0) by Anonymous Coward on Friday November 13 2015, @02:26PM
amen
(Score: 2) by dmc on Saturday November 14 2015, @03:13AM
And you never know when it's just H.R. Hadden messin' with ya
(Score: 3, Interesting) by FatPhil on Friday November 13 2015, @03:54PM
Disclaimer: in a former life (when I pretended to be a mathematician) I assisted George Marsaglia with some of his long period PRNGs' proofs. Marsaglia was a known critic of MT (the elastoplasts were applied in response to his complaints).
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 3, Interesting) by melikamp on Friday November 13 2015, @05:59PM
Very few practical PRNGs come with documentation suitable for mathematicians, let alone a thorough mathematical analysis, and the twister is no exception. This kind of goes with the territory, since on one hand we are trying to create something cryptographically secure, so it can't be too simple mathematically (actually, it kind of has to be convoluted just to resist the attempts to crack it), but on the other hand we are trying to make it reasonably fast and easy to code correctly.
I've been dabbling in PRNG research myself, and lately I am pretty unimpressed with all periodic PRNGs. Why settle for a period when we have a huge class of real numbers with essentially perfect properties: the normal numbers. One of the most interesting things I found out lately is that we get normal numbers when we concatenate the outputs of non-constant polynomials:
0.[f(1)][f(2)][f(3)]...
I conjecture that taking something like a 5th degree polynomial with 1000-digit coefficients will make a first grade monte-carlo PRNG: a provably normal sequence implemented in 2 lines of LISP or 20 lines of C, with reasonable speed & memory footprint. This is not a perfect solution from the crypto point of view, since we can roll it backwards, for one, but it's not too ugly either. I am really not that good with crypto, but it seems like if Charly starts reading the output from an unknown place, he's toast. He wouldn't even know where 5000 or so digits of f(n) end and those of f(n+1) begin, or indeed how many digits are in either, so guessing the state is far from a piece of cake.
Oh, and physics-based RNGs? One word: voodoo. What's good for a card game is not necessarily good for encryption or serious monte-carlo work. We (mathemnaticians) can't prove anything at all about numbers obtained from physical systems. I am sure a few physicists will claim that the quantum processes produce the true randomness a la Kolmogorov, but I am just not buying it. This seems like an extraordinary claim requiring a lot of evidence, and it's not even clear what kind of evidence could distinguish between a normal number and a "typical" rational with period 10^(10^10), which would make a difference between totally random and totally deterministic.
(Score: 0) by Anonymous Coward on Friday November 13 2015, @07:21PM
Not always, many applications of RNGs are not security related -- this is true for all applications of MT19937 because this is not a crypographically secure RNG (it is possible to determine the entire state of the generator by observing a handful of outputs).
All deterministic generators with bounded internal state will be periodic, because there are only finitely many possible states. If you generate enough outputs (more than the number of states), the generator must have repeated a state (by pigeon hole principle).
(Score: 2) by melikamp on Friday November 13 2015, @08:01PM
True, but of course there are very simple (non-halting) PRNGs with unbounded state. While technically bounded by the amount of available memory, they would not be bounded for any practical purpose. Like this one, for example, will print the most famous normal number, and won't run out of memory during our lifetimes:
; Using Common LISP for brevity, since having the long arithmetic really helps
(loop for x from 0 do (write x))
(Score: 2) by JoeMerchant on Friday November 13 2015, @09:57PM
5 1000 digit coefficients in 2 lines of code? Your monitor must be wider than mine.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by melikamp on Friday November 13 2015, @10:47PM
Well OK I meant the engine would fit into 2 lines. Here's a normal number printed by a 5th degree polynomial starting with p(x 0) and with coefficients ai :
(loop for x from x0 do (write (+ (* a5 (expt x 5)) (* a4 x x x x) (* a3 x x x) (* a2 x x) (* a1 x) a0)))
A generic state consisting of x and the coefficients would of course be many KiB, but of course it's not impossible to construct very large (non-generic) numbers quickly:
(expt 17 5000)
175633312108452721427154910593816375676045609188236147762172520926313101794626782377302959371185668182012124474768266306604248917384680807806747292682205706327215503961769087974347874640165762944001728597738340683565131284670575788748143866231551159686498529164599400846239981278615270503937793488580806658721202804281807054635951112907504929605445109539143506059421558862556445538020731806999633093042305375390661535397548186188359722677542179808885816588731936127218643639140365801564147090483867454453618553624775828498532004025435165448741825964917193729764165922701192888216794065640950423512843256411763281777945320998754729721884555541718397176355225703010383238024435800626063987134614462065403732660231342072837291206443476116603670199653489987679848862478846935043417196037431164309799400079790508606478813251682980006352221096750286975348109121230933525994636962933541395081273993469864500734110297241770420948833614171417329230122598315090109761690659280031012044865243874407114822664147257592623432654116599449304646288137778757203338682128403105312166782907518388167285439755453847363751166502631379670596798430845937039535447623509590468030323137066946856796935379197912644217029594115860854074935771345585184704373301849748566613193689138763679149561452923238919319638772662331219692427199125395731096771707168497391604287236115742516223987357937103839634451407001236040447203547136995985694892460991723457069383702445228969093822145109486906789026639918320490245755599683998095585127297241031190061204022875270887686252839020210211712169154657990736026710226339850420698394512386894379865146150863019264166856893763517860350169554503045225417960785146637386064190279519443935894697410337891638573966522504356407547460475444066388414884352420176752828409630299050590206071771426127643322001960002581803176902420999844839831174587339521358198795803924385754631860100520039828066064303471139304584911046045989339008351033521540532530569270839044739005330526718914657790718027280821592296613430481758002732284430460153868797091728276352908260317078133915312009449425835997822432454616608006853453350401960966064646756447320019117360389411391439965541982426068747741540989813986059814555213849989910607803919280164257909041865602294906920921681146589932261748790765236523314861238992658796426269836107535390268247536918766845976816061117199507574784898078209016708953021725491811963242729592560279999957972312183247487668073980051960842377251039253913335036326948294897532575295076409324552424290670885388876854518242746830052104741660458649796802994288178969550785944426942212761759761629583670742765723947321373617535406111245507333030398779754769441574514877729185675007932015210242382746728806982064749470453529454127372569007550564121383161649984487234982706965289643941242652698276888692091414163884067172633479640096267909812567164072306810473540472157017153388156168318249100092144563902987954263312189007040081249981863165047606815301894095801741242164263977977983854272252994000644471293686085939256540849642900999751121307978398745462437590183483874902215393338496926410324430086030708634674200722204979458059195450804167704388783966307047784146951568006533524749957739674673018801649837593125305519586523038286497824816823574252996315988586257489513329253365432866115320707115172290805547312473555181480796823554844931696882172285671191614680778662169300682478171059390782312961134037331146881605067229127438402954304991619585321855794388180388335037966158940297937636681454914894526018295822269239654261630129016241025639207851144843898941888142565093503336177896656603979127239011340388257777715792593515538442691165736674579252631904155815690510364895868523266977226037937076883264554570106327168988788362808023006778367678198260026687543048031439343329049912386407448774403354364481950230687659737861349416409383488355401457495516126078814054940444199039252923389473038724328061107690292994480219446676672720420515079572777012566338940400215780571339668241649781374396809924620882671477337968217432630896278471933541863784193488057966871793914262635142169767995136008387916675004251678144707365851843502125668268480493721475917212484122236621262451522315618953776969762410725679143974851786155299466206254182733980642613469283555849882375390208458159577529054311985282741027119213215400435797962035997928364507218358554234732569061653222940210448729100534501722823263110223320912133395116726595124349219370927716932359126979144248649671728123970706982510670289356817106369771576889715077717286309727625684088286043875925829576569501990707212512505716773955175244188333693166367426060106082268338286492759544576654882740073747589531157847387266800907118948558880021144340958991846110339075522166167379965123984458398090325282405745067439441508856555826504832585520305888976612772853535359059043269127979104154267286843636513913392310277099004392981566761533862959776796297712666807083359889063614166090530218032487690584535449814660374125284245843784055435388495021356698635724924278675525177262450838871550013502761842865823757189954680209176165142140267600467234107643161212849008680357734728786997246480183058318316366333813577230717087359194725919643928956278468035239826534426157148843377901224331418317991340920656177084922248280027560541334667582466664600425098435030170271758581828583498119210067195478204683184832876663453793279404719157892079220140821968978119281081913169674997713653884456598683826554698476432259869047623173196072427625121126216364020702961651669891448492145939734317039381874744536176661513901739078371264686483672560789801498973094388837135427649563835584022317066407952912476300380185569413414804306918237676145328082995274206308349230528913173655386784698362714288585780849346559927870551331556711878622808690431661198427464435899340401313300181379288349660725866965530214537256890330650174087174937067812646224052980930879643780528401385376015068289468949400760582595181958044455611426989333135918240692647062804185759340389331050492516816005585605294532148932699976324464041594917008337814060900347005883464822192868224304916159350147182396177631440826837303017736850976393921957658280400001
(Score: 2) by JoeMerchant on Saturday November 14 2015, @05:12AM
So, I like plotting series of recursive polynomial numbers (floating point) vs themselves, Poincaire style - you might like the results:
http://mangocats.com [mangocats.com]
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by FatPhil on Sunday November 15 2015, @03:45PM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by JoeMerchant on Friday November 13 2015, @09:55PM
I guess that these folks are "no real mathematicians" then:
The Mersenne Twister is the default PRNG for the following software systems: R,[3] Python,[4][5] Ruby,[6] PHP,[7] CMU Common Lisp,[8] Embeddable Common Lisp,[9] Steel Bank Common Lisp,[10] Free Pascal,[11] GLib,[12] SageMath,[13] Maple,[14] MATLAB,[15] GAUSS,[16] IDL,[17] Julia,[18] Scilab,[19] Stata,[20] GNU Octave,[21] the GNU Scientific Library,[22] the GNU Multiple Precision Arithmetic Library,[23] and Microsoft Visual C++.[24] It is also available in standard C++ (since C++11)[25][26] and Apache.[27] Add-on implementations are provided in many program libraries, including the Boost C++ Libraries[28] and the NAG Numerical Library.[29]
The Mersenne Twister is one of two PRNGs in SPSS: the other generator is kept only for compatibility with older programs, and the Mersenne Twister is stated to be "more reliable".[30] The Mersenne Twister is similarly one of the PRNGs in SAS: the other generators are older and deprecated.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by FatPhil on Sunday November 15 2015, @03:54PM
Fortunately, real mathematicians, and other people who care, will know how to get good random numbers out of MT. GLib certainly *didn't* last time I looked. (The random "pipes" in GIMP were showing clearly distinguishable from random behaviour, which was pissing me off as it was fucking up the images I was doodling, so I delved into the source to see why.)
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by JoeMerchant on Sunday November 15 2015, @06:12PM
What could they do to get MT wrong? Initialize it with zeroes? I mean, that's just a basic screwup by the implementer.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by FatPhil on Sunday November 15 2015, @06:42PM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 1) by khallow on Friday November 13 2015, @04:51PM
(Score: 2) by twistedcubic on Saturday November 14 2015, @04:27AM
The Mersenne Twister does not pass the harder statistical tests. RANLUX is better, and passes the Spectral Test in high dimensions.
(Score: 2) by JoeMerchant on Saturday November 14 2015, @05:18AM
There comes a time to say "good enough," and 600 dimensions is good enough for me.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by DNied on Friday November 13 2015, @02:13PM
I want it in /dev/cmb, please (with the next kernel release, if possible).
(Score: 1) by throwaway28 on Friday November 13 2015, @02:27PM
Please connect a 1 billion dollar telescope to the USB port to activate /dev/cmb. The upcoming Giant Magellan Telescope will serve nicely.
(Score: 3, Informative) by Zinho on Friday November 13 2015, @09:44PM
Radio telescope not needed; you can observe cosmic rays well enough using a USB webcam in a light-proof box. [archive.org]
Original site is now offline, but the project lives on at sourceforge. [sourceforge.net]
"Space Exploration is not endless circles in low earth orbit." -Buzz Aldrin
(Score: 0) by Anonymous Coward on Friday November 13 2015, @02:15PM
So, I am not a cryptographer nor a physicist, but it occurs to me that given that the radiation is pretty much an
energy wave akin to a wireless network's. Based on that, using all the bytes obtained from the radiation and
use it as a key makes it possible to capture it as it is "generated". I am curious, from a statistical point of view,
what is the probability of collisions.
Even considering an out-of-order capture due to positioning, the bytes of the key would still be known.
Also a RNG is not a one-time pad, it would be used as a key for a cipher, which can be attacked. In other words,
you can't _decrypt_ a RNG.
As always, the evil lies in the details and this comment may be completely off track.
(Score: 2) by jdavidb on Friday November 13 2015, @02:19PM
I think the answer to that is that the field varies across three dimensions (probably more), so two different observers capturing random numbers from it in two different locations would get different numbers.
But I am way, way out of my field of expertise here, so I could be totally wrong.
ⓋⒶ☮✝🕊 Secession is the right of all sentient beings
(Score: 2) by JoeMerchant on Friday November 13 2015, @02:32PM
Using a picosecond clock timing when you log in in the mornings gives a hard-to-guess random number: assume a normal distribution with 100 seconds standard deviation, your clock reading will be more or less random in a range of values on the order of 10^14, even if you are ridiculously punctual with 1 second SD, that's still 10^12.
The key with using background radiation as your key is to collect it with sufficient resolution over a sufficient period such that any attacker (with a similar telescope pointed at a similar region of sky) would not get the same pattern to some level of confidence. Variations in location of antenna, variations in pointing angles, aperture, atmospheric interference, etc. will play into it. It's sort of like anti-science, an experiment that is provably hard to reproduce.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 1, Interesting) by Anonymous Coward on Friday November 13 2015, @02:38PM
You want the non-reproducibility to be reproducible.
(Score: 1) by zoefff on Friday November 13 2015, @03:14PM
Just to imagine another attack vector: What if you shine with a laser into the telescope, wouldn't that make things more predictable?
(Score: 0) by Anonymous Coward on Friday November 13 2015, @05:21PM
The CMB is not measured at those wavelengths.
(Score: 1) by SunTzuWarmaster on Friday November 13 2015, @05:52PM
You are correct in thinking that these numbers are essentially random and that a pico-second clock would be a way around it. However, someone on the other side of the world would be able to adjust *their* pico-second clock until their numbers matched up with yours. Then, presumably, they would win at blackjack, take all your casino money, read all your E-mails, launch the nukes, mix the darks and the lights, and spoil the milk.
PS - obviously using these numbers as an encoding base doesn't work for the same reason, adding some "not random" number doesn't work for crypto reasons, etc.
(Score: 2) by JoeMerchant on Friday November 13 2015, @10:06PM
Not sure we're on the same page: to get a seed for your crypto PRNG for the day, feed it the ps clock value at the time you log in, nobody will measure the time of your login better than 1/100 second, even if they have a high resolution video feed that shows when you hit the enter key (and have managed to sync your ps clock to their camera feed) - and then, they've still got 10^10 codes to try to match up to whatever the visible outputs of your crypto PRNG are that day. Prevent people from seeing you hit the Enter key on video and you up your security by an order of magnitude.
Of course, if they've already crawled that deep into your system, they probably have keyloggers running on you that will make the rest of the security irrelevant.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 1, Interesting) by Anonymous Coward on Friday November 13 2015, @02:34PM
Would it be possible for a space agency to place a satellite at a strategic point above the telescope and reduce the randomness by adding its own (non-random) radiation? A local source of randomness has the advantage that, as far as we know, it can only be manipulated locally.
(Score: 0) by Anonymous Coward on Friday November 13 2015, @03:00PM
No.
(Score: 2) by VortexCortex on Friday November 13 2015, @03:00PM
I have a cheap $3.00 webcam aimed out the window.
The low bits of each pixel are themselves indistinguishable from pure white noise according to all the NIST tests available. However, I just take the video frames and run them through a hash matrix. Each hashing function instance contributes to one block of a randomness pool. If I need more randomness faster than the pool, I can distribute the frame pixels among the hash buckets more scarcely or hook another webcam up. A $20 dollar one that's got 1024 times more pixels per second.
On my robotics projects that have machine learning and thus a need for really good random numbers, I just use a reverse bias diode. There you go. Harnessing "The Big Bang" via quantum randomness. For less than a dollar.
(Score: 2) by wonkey_monkey on Friday November 13 2015, @03:19PM
I used to take the low bits of a soundcard's disconnected line-in.
systemd is Roko's Basilisk
(Score: 2) by FatPhil on Friday November 13 2015, @03:57PM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by maxwell demon on Friday November 13 2015, @09:00PM
But I can't find a Bambleweeny 57 Submeson Brain. Do you know where I could get one?
The Tao of math: The numbers you can count are not the real numbers.
(Score: 2) by SubiculumHammer on Friday November 13 2015, @04:19PM
Yeah...I'm not a cryptographer but this problem seems solved, practically.
(Score: 0) by Anonymous Coward on Friday November 13 2015, @05:18PM
Well, first off they're not trying to "sell" anything. Their paper is about how random the CMB is.
Secondly, what do you mean you run your frames through a hash matrix? Are you taking a single frame and hashing that, or are you doing some sort of time-series analysis of individual pixels? In either case, I don't think it is as random as you think it is. I don't doubt that it is good enough for what you want, but I think you're misleading yourself on how truly random it is. You can only exploit the entropy that you're passing to the hash, otherwise you won't need to pass the hash anything, and the point of their paper is that the CMB is sufficiently random for any current use case.
(Score: 2) by Gravis on Friday November 13 2015, @04:08PM
we have already been using the universe for a perfect random number generator, specifically teh quantims! ok, so Quantis Random Number Generator [idquantique.com] uses "the randomness of quantum physics" to generate an endless stream of random number. now if we discover how that works, we all win at Universe and your RNG is cracked but who cares because we won!
(Score: 2) by Ken_g6 on Friday November 13 2015, @05:45PM
"Drone attacks on astrophysical entropy sources". If you hover a drone in front of the telescope, you should be able to de-randomize what the telescope sees.
(Score: 1) by dak664 on Friday November 13 2015, @06:25PM
So you get a certified random sequence, how does that improve your security?
You can xor it with your message, but need to save it to recover the message, and send it along with the message (or in advance by hand) which makes it no better than any other moderately complex one-time pad. Random images from my phone camera work just as well, and their pre-delivery does not generate the same suspicion of my future communications ;)
(Score: 2) by Ken_g6 on Friday November 13 2015, @08:04PM
https://en.wikipedia.org/wiki/Pseudorandom_number_generator#Potential_problems_with_deterministic_generators [wikipedia.org]
(Score: 0) by Anonymous Coward on Friday November 13 2015, @08:08PM
I claim it is impossible to distinguish a deterministic prng with sufficiently long period from a "truly" random number generator.