Intel’s new way of creating randomness from digital orderliness

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]

Comments

  1. insapio says:

    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?

  2. BiOzZ says:

    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?

  3. BiOzZ says:

    may i also add i like the fact that it uses thermal noise … unlike atmospheric noise it cant be spoofed so easy!

    • cptfalcon says:

      I think thermal variation might be easier to spoof… I bet they only test their chips “randomness” for the standard temperature ranges.

      • BiOzZ says:

        well you should not exceed factory recomended tempatures anyway … when u overclock you should get newer fans or cooling system

      • Boop says:

        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.

      • Sdlion says:

        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.

  4. Tyler says:

    With the rate of ECC ram adoption, they could just use cosmic rays…

  5. fr4nk says:

    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.

    • bolke says:

      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.

    • cpmike says:

      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.

    • BiOzZ says:

      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

      • andrew says:

        Actually, that’s more of an assumption of SOME sciences, as opposed to a statement of most.

      • NoShit says:

        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.

    • Sdlion says:

      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)

  6. Miroslav says:

    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.

  7. andrew says:

    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.

    • pi says:

      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.

  8. Mike says:

    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.

  9. Mime says:

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

  10. CRJEEA says:

    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.

  11. Munch says:

    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.

  12. Dan Fruzzetti says:

    Dude they only claim ‘pseudo’ anyway. This won’t eliminate the need for elaborate external hardware to generate RANDOM numbers.

  13. hawkeye18 says:

    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.

  14. MrX_TLO says:

    They know this isn’t random.

    This is a trick to help undermine keys on demand in the future.

  15. Piku says:

    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.

  16. default says:

    @Piku
    Awesome

  17. Whatnot says:

    The things intel goes through to aid the bastards with their DRM eh…

  18. amodedoma says:

    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.

  19. The Timmy says:

    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.

  20. Larry says:

    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.

  21. Leigh says:

    Pitting inverters against each other made me think of meta-stability: http://en.wikipedia.org/wiki/Metastability_in_electronics

  22. Keith Golon says:

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

  23. Keith Golon says:

    What about random background noise? You know, the stuff that COBE was detecting way back when.. Remember?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 96,357 other followers