Random number generation is a frequent topic of discussion in projects that involve encryption and security. Intel has just announced a new feature coming to many of their processors that affect random number generation.
The random number generator, which they call Bull Mountain, marks a departure from Intel’s traditional method of generating random number seeds from analog hardware. Bull Mountain relies on all-digital hardware, pitting two inverters against each other and letting thermal noise tip the hand in one direction or the other. The system is monitored at several steps along the way, tuning the hardware to ensure that the random digits are not falling more frequently in one direction or the other. Pairs of 256-bit sequences are then run through a mathematical process to further offset the chance of predictability, before they are then used as a pseudorandom number seed. Why go though all of this? Transitioning to an all-digital process makes it easier and cheaper to reduce the size of microchips.
A new instruction has been added to access this hardware module: RdRand. If it works as promised, this should remove the need for elaborate external hardware as a random number source.
[via Reddit]
It seems. to me, with no training in physics or mathematics, that the more involved a random number generator, the less random the numbers. An all digital process sounds like it makes for a lot of collapsed waefunctions…like every single bit?
good! … make my AES a bit stronger :3
will it replace the old system or be a second system?
IE. will it require another line to use or go in to the standard randomness line?
It seems like a replacement, so they can make their chip fabrication process use digital-only components. This would allow for simpler, perhaps more automated, layout.
may i also add i like the fact that it uses thermal noise … unlike atmospheric noise it cant be spoofed so easy!
I think thermal variation might be easier to spoof… I bet they only test their chips “randomness” for the standard temperature ranges.
well you should not exceed factory recomended tempatures anyway … when u overclock you should get newer fans or cooling system
I don’t think you understand the method being used here (but I don’t really either so someone please correct me if I’m wrong). From what I gather you would not be able to spoof it if you raised the temperature of the whole chip, as you have to create a difference over the two inverters used, which would be extremely difficult because they are inside the chip and very small.
As far I understand…
The thermal energy moves electrons back and forth. The higher the temperature, higher the energy will be.
The logic circuit in an undetermined state, won’t stay too long undetermined due the electron movement in the joints that will create currents in both logic gates. One will be greater than other and that difference will break the balance.
No one can foresee which logic gate will be set high or low. It’s just… noise.
The same way you can’t guess where and when a black dot will be shown in your tv tuned on a blank channel.
It’s called thermal noise, because thermal energy create it. But they’re not biasing their gates with heat, they’re biasing them with noise.
With the rate of ECC ram adoption, they could just use cosmic rays…
The system is monitored at several steps along the way, tuning the hardware to ensure that the random digits are not falling more frequently in one direction or the other.
Not random.
We bow before your obvious grasp of the matter and ask you humbly to lead us in the creation of a truly random number generator.
oaf.
He has a point though. It does seem to ruin the randomness of it.
Was my first thought as well… but you have to assume they didn’t make such an obvious blunder in the design.
Perhaps its not so bad, though. Say you get a seed that is out-of-range, so you “wrap” it back to the low side of the range. Still the same original randomness, but contained within expected bounds. There are many solutions, and they probably won’t be sharing theirs, but I’m sure they have one.
conventional science states that nothing is ever truly random
unless we want to go in to the quantum world of mind-fuckivness i think this is good enough
Actually, that’s more of an assumption of SOME sciences, as opposed to a statement of most.
The sciences that believe in truly random things must be really stupid, because it would invalidate the very definition of science.
True randomness is a logical fallacy, there are only events that you don’t have access to their causes, and thus to you they appear random, but there’s no such thing as actual absolute randomness.
The practice of the scientific method involves gaining access somehow to those causes (even if just theoretically). It’s the whole point.
I rather say “the number generated in the first step it’s not random… enough”.
The number delivered to the software could be on the 99.ldjhjkasd% of randomness. I would say you gotta be pretty lucky to predict those numbers.
(So, I’m not saying it’s impossible, but the results you’d get from one PC won’t be very useful in another… maybe neither in the same PC just a few minutes later)
From TFA:
“Why go though all of this? Transitioning to an all-digital process makes it easier and cheaper to reduce the size of microchips.”
So they do this to save money, not improve security.
They can also generate orders of magnitude more random data with this process.
its both easier to do and it creates far more random numbers that cant be exploited or cracked no matter how large your samples are
There’s a helluva bigger number space in a float_ that any sort of int_. We’re comparing a functionally infinite space to a finite space, are we not?
There’s a difference between random and unpredictable. For most things, including encryption, you only need the latter. Remember, the goal here is to be able to generate a sequence of bits in which it is impossible to predict the next sequence given a historical sequence and vice-versa. Another goal, is that the distribution is homogenous within a specific range (i.e., if you’re generating random numbers between 1 and 100, you want just as many numbers between 1-50 as you have between 51 and 100).
In this case, performing some mathematical transformation on the output of an unpredictable process (the relative temperatures of two inverters) is fine and the purpose of doing so is to probably ensure the above.
The term random says more about the process in which some outcome was obtained whereas the term unpredictable describes the nature of the information produced by that process. Many of you are right to point out that the mathematical transformation they perform are not random, but that does not necessarily make their products predictable either — but it may actually increase unpredictability.
Andrew-
If I had a truly random coin-flipper, then over an infinite number of flips, I would expect half to be heads, and half to be tails. However, if each flip is a truly random event, then I would argue that there is nothing to prevent, say, 10 million “heads” from appearing in a row.
It seems to me that if you superimpose homogenous distribution upon an otherwise random number generator, then must surely decrease the overall randomness.
Why? Look at it this way: Suppose I have a 1-10 random number generator that is forced into homogeneity. Furthermore, suppose in recent cycles, I have observed that it has “hit” all of the numbers 0-9. Because of the imposed homogeneity requirement, the odds that the next hit will be a 10 must, by definition, be greater than chance, and the odds go up the longer the generator fails to produce a 10.
Granted, if you are imposing homogeneous distribution over 10 million possible numbers instead of 10, the effect is less noticeable, but it seems to me that it would still be there.
I’m wondering if you can explain your comment in more detail.
Intel should just hire me as a random number generator. Any time they need a random number they can just call me up and I’ll tell them one, like “seven” or “four hundred and eight” or “twenty three”.
You’re welcome.
As long as we can pay you less than we pay the average CPU to do the job, fine. (also you have to promise to produce roughly equally balanced numbers over the entire range of desired outputs.)
Oh wait nevermind. The cost of a phone call would exceed the CPU’s. You’d actually have to pay Intel for this job. You also don’t get the required troughput with a single phone call, but that’s something for v2.
Actually, they’d just record the conversation and use the hash. :P
hey, those were MY numbers!
Generating a truly random number is like the holy grail of computing. Its funny really when you consider that computers and digital logic are fundamentally designed to be predictable ;-)
And as someone wise once said: “Anyone who expects a truly random output from an equation is a fool.”
Can’t remember who said it though..
Randomness hack I did I while back.
Get a cheap optical mouse if you sit it on its cable just right it half focuses it’s self and because of the background noise in the low res. camera it makes the mouse pointer jitter around the screen. (good for making the semi computer literate look confused) on most mice it tends to try to slowly edge the cursor to the top left of the screen. I’m not sure if this is hardware of software as Iv never delven into it far enough. I used it with an old DOS mouse program the returned the x-y coordinates of the pointer to variables. I added a function to compensate for the drift and it seemed to work fairly well. I’m tempted to try this analog optical randomness on a microcontroler of some description. Or maybe use an old webcam with some card stuck over the lens to remove the picture noise.
Your last line sounds like the hardware used by the LavaRnd project:
http://www.lavarnd.org/what/can-details.html
The article contains the excerpt, “pitting two inverters against each other and letting thermal noise tip the hand in one direction or the other.” Hate to break it to you, but that is not a digital process. That’s quite emphatically analog.
More precisely, Intel is reducing the analog parts count traditionally needed, but they cannot reduce that count to zero.
Dude they only claim ‘pseudo’ anyway. This won’t eliminate the need for elaborate external hardware to generate RANDOM numbers.
You want to generate random numbers?
Step 1: Obtain image sensor from cheap 4 year old P&S camera
Step 2: Mount it against a black field
Step 3: Turn ISO on sensor to 12,800
Step 4: Infinite random noise!
Yes, that was kind of a joke. But it does seem to me that a digital image sensor with its ISO pumped up waaay too high would be pretty good at generating random values. Sure looks that way on my old P&S.
They know this isn’t random.
This is a trick to help undermine keys on demand in the future.
The algorithm used to work out the time left in software installers and file downloads seems good at generating random numbers. They should use that.
@Piku
Awesome
The things intel goes through to aid the bastards with their DRM eh…
Lot’s of crypto concerns, but I’m more interested in seeing how this will effect simulations. Their current algorythm produces a set that seems too smooth, not enough irregular clumping to give a truly random ‘impression’ – this method of sampling data to get random seems superior – but the proof is in the pudding.
Philosophically I don’t believe in random, or chaos, or any of those other terms created to put a cover over ignorance.
a long time ago, some friends and I wanted to play some D’n’D type game that used odd shaped dice that we didn’t have.
So I broke out my old 486 laptop and wrote a dice roller in QBASIC. The problem of course, was that whenever you started the program and gave it the same number of dice to roll the same number of times, you would get the same results.
this was fixed by having the program constantly generate random numbers while waiting for the next job to roll dice again.
it was great, you could roll 100,000 dice in a matter of minutes. and it kept stats on the results telling you your success rate vs. target number and other such things.
I don’t know much about how the numbers are actually generated, but I’ve always wondered if “time” or “timing” could be used as a factor in generating a random seed. maybe it’s already done, I don’t know.
Sounds like they’re just using a PSRO. (performance screen ring oscillator) Which is an odd number of inverters configured in a ring. Which really isn’t that different from an analog circuit. The speed of the ring is dependent on the process the die ended up in (how fast are your n and p transistors) and the temperature of the circuit.
Pitting inverters against each other made me think of meta-stability: http://en.wikipedia.org/wiki/Metastability_in_electronics
Agreed on the image sensor technique. Combine that with a radioisotope and a reflective bit of silver mirror and you’ve got a great source of noise.
Anything to do with nuclear radiation seems like a great source of randomness. Forgiving all the regulatory constraints that is..
What about random background noise? You know, the stuff that COBE was detecting way back when.. Remember?