Slashdot Mirror

← Back to Stories (view on slashdot.org)

Ultra-low-cost True Randomness

Posted by CmdrTaco on from the and-a-damn-fine-hack dept.

Cryptocrat writes "Today I blogged about a new method for secure random sequence generation that is based on physical properties of hardware, but requires only hardware found on most computer systems: from standard PCs to RFID tags." Basically he's powercycling memory and looking at the default state of the bits, which surprisingly (to me anyway) is able to both to fingerprint systems, as well as generate a true random number. There also is a PDF Paper on the subject if you're interested in the concept.

21 of 201 comments (clear)

  1. A Slightly More Expensive Method by eldavojohn · · Score: 4, Interesting

    A slightly more expensive but somehow even more random method is to seed the generator against the words and phrases that come out of the mouth of South Carolina's Miss Teen USA.

    But in all seriousness, I wonder how this compares to the Mersenne Twister (Java implementation & PDF)that I use at home? I am almost sure this new proposed method is more efficient and faster, when will there be (I know, I'm lazy) a universal implementation of it? :)

    Also, this may be a stupid question, but I wonder how one measures the 'randomness' of a generator? Is there a unit that represents randomness? I mean, it would be seemingly impossible to do it using observation of the output so I guess all you can do is discuss how dependent it is on particular prior events and what they are, theoretically. Can you really say that this is 'more random' than another one because you have to know so much more before hand about the particular machine & its fingerprint in order to predict its generated number?

    --
    My work here is dung.
    1. Re:A Slightly More Expensive Method by NetCow · · Score: 3, Informative

      Mersenne Twister is not a random number generator, it's a pseudo-random number generator.

      Randomness is measured as entropy. See here for details: http://mathworld.wolfram.com/Entropy.html

    2. Re:A Slightly More Expensive Method by solafide · · Score: 3, Insightful
      Randomness is measured statistically using multiple tests: see Knuth, Art of Computer Programming Volume 2, Chapter 3 for a thorough discussion of common statistical randomness tests, or here for a practical testing tool.

      I don't expect this to be statistically random: they claim it's based on thermal noise. But the startup temperature of a computer does not have that much entropy, so the thermal noise isn't reliable. Just because something's garbage doesn't mean it's statistically random.

  2. Re:933245789124398 by BadAnalogyGuy · · Score: 5, Funny

    23423483837223429723432891023478343589435892

    You would expect that, you fucking pervert.

  3. Random karma whore by BadAnalogyGuy · · Score: 4, Funny

    Randomness is definable.

    Why, take a look at this Wikipedia link. You can never tell whether it represents the truth or some crackpot's claim to it or just some troll's malicious vandalism.

    Voila! Randomness!

    1. Re:Random karma whore by Mc1brew · · Score: 3, Insightful

      That link brought me to the conclusion that randomness doesn't exist as much as I thought. It uses the example of rolling dice, random right? Not really... Just too many variables to consider over the given amount of time. *Density of dice *Placement of dice in hand *Distance of hand from table *Number of dice *Potential values of dice *Density of table *etc..... By the time you write down all the variables a value has been generated. Just because you didn't have enough time to evaluate the scenario, doesn't make it random. The problem with random number programs is that the algorithm is predictable, thus it depends of the variables fed to it for randomness. The algorithm hopes that by smashing all the variables together it will somehow not be predictable. In essence this seems true because unrepeatable values such as time are taking into consideration, but assuming you know all the variables entering the algorithm, you should be able to predict the output and thus not random. Well that was all probably off topic.....

  4. Oblig. XKCD by IcedTeaisgood · · Score: 5, Funny

    http://xkcd.com/221/

  5. How it compares to the Mersenne Twister by benhocking · · Score: 3, Informative

    The Mersenne Twister is a pseudo-random number generator. For many uses, this is preferable to a true random number generator as it is easily repeatable. (One can also repeat the results of a true random number generator by storing the output, but depending on how many random numbers you're generating, this might be space intensive.)

    That said, although this might be "true" randomness, what kind of randomness it is? Uniform over a range? Gaussian? Weibull? Most likely, none of the above if it can be used for fingerprinting systems. (No, I did not RTFA.)

    --
    Ben Hocking
    Need a professional organizer?
  6. A VERY interesting idea... by nweaver · · Score: 5, Interesting

    the true RNG properties rely on the fact that:

    a: Many of the bits are sorta random, but physically random. So very biased coins, but true randomness.

    b: With the right reduction function, you can turn a LOT (eg, 512 Kb) of cruddy random data to a small amount (128b-512b) of very high quality, well distributed random.

    And the fingerprinting relies on the fact that:

    a: Many other of the bits are physically random, but VERY VERY biased. So map where those are and record them and it is a very good fingerprint. And since it is all silicon process randomness going into that, it is pretty much a physically unclonable function.

    Kevin Fu has some SMART grad students.

    --
    Test your net with Netalyzr
  7. This is hardly random by gillbates · · Score: 3, Informative

    As an embedded engineer, I've encountered numerous cases where power cycling RAM did not alter the contents.

    In fact, I've seen systems boot and run even after the power was cut for several seconds. Some types of SRAM and SDRAM have the ability to retain an (imperfect) memory image even at very low voltage levels. Sure, it's not guaranteed to be accurate by the manufacturer, but RAM "images" are a pretty well known phenomenon. In some cases, the contents of memory can be reconstructed even after the computer has been powered off and removed to a forensic laboratory.

    This is not random at all. In fact, it's more likely to produce an easily exploitable RNG than anything else; I would not be at all surprised if the standard UNIX random number generator provided better security.

    --
    The society for a thought-free internet welcomes you.
    1. Re:This is hardly random by tlhIngan · · Score: 5, Interesting

      As an embedded engineer, I've encountered numerous cases where power cycling RAM did not alter the contents.

      In fact, I've seen systems boot and run even after the power was cut for several seconds. Some types of SRAM and SDRAM have the ability to retain an (imperfect) memory image even at very low voltage levels. Sure, it's not guaranteed to be accurate by the manufacturer, but RAM "images" are a pretty well known phenomenon. In some cases, the contents of memory can be reconstructed even after the computer has been powered off and removed to a forensic laboratory.

      This is not random at all. In fact, it's more likely to produce an easily exploitable RNG than anything else; I would not be at all surprised if the standard UNIX random number generator provided better security.


      I've had this bite me, and exploited it.

      It bit me when booting into Windows CE - you'd power cycle the thing, and the OS would boot with the old RAM disk you had - we'd gotten to the point where we'd have the bootloader wipe the kernel memory so the data structures were all corrupted by the time the OS was trying to decide between mounting the RAM disk (object store) and starting fresh. It turns out that the longer an image is unchanged in RAM, the more likely the cells woudl be biased such that if you cycle the power on them, they're more likely to lean towards the way they were before power was cut.

      The time I exploited it, I didn't have any way of logging. Logging to serial port caused issues (timing-sensitive code), so I logged to memory (and no, I had no filesystem running, so I couldn't log to file). My trick was to simply log to a circular RAM buffer. When it crashed, I would just power cycle and dump the RAM buffer. Even though the data was fresh, it was enough to make out what my debug message was trying to say (almost always perfect). This was readable after a brief power cycle, and was still readable after turning power off for nearly a minute. The characters got corrupted, but since it was regular ASCII, you could still make out the words.
    2. Re:This is hardly random by nickovs · · Score: 3, Insightful

      There are a couple of things to note here. Firstly, SDRAM and SRAM behave very differently. Synchronous dynamic RAM can retain charge in the capacitors for quite some time after being powered down and there is very little one can do about it, but the paper discusses static RAM. With static RAM there is a difference between being "powered off" and having the Vcc rail clamped to ground. Active clamping of the power line is much more effective at clearing the RAM than even just disconnecting it from the power supply, for reasons which become obvious when you look at a classic six transistor CMOS RAM circuit. Without clamping, bias will remain for exactly the same reason that SRAM doesn't consume much power; current only flows when the data changes.

      As for it being a good RNG; the state of RAM on power-up is probably a lousy "random number generator", but the statistics in the paper suggest it is a fairly good "source of randomness". There's a big difference between bias and unpredictability (think about dice with '1' on five of the sides and '0' on the remaining side). You wouldn't want to use the state without putting it through a compression function first, but it's a much better seed than using clock()!

      --
      If intelligent life is too complex to evolve on its own, who designed God?
  8. The problem with random numbers by operagost · · Score: 4, Funny

    You can never be sure.

    --

    Gamingmuseum.com: Give your 3D accelerator a rest.
  9. A suggestion for this blogger by Quila · · Score: 3, Informative

    Learn How To Use Capital Letters At The Beginning Of Sentences!

  10. Our research group will answer questions soon... by fubob · · Score: 5, Informative

    We were surprised to suddenly get attention to this paper, but apparently Slashdot readers are watching the security seminar at UMass Amhest.

    Anyhow, we will be answering questions in this thread. So if you have any questions, post them here and Dan Holcomb will get back to you as soon as he can.

    Cheers,
    -Kevin Fu

  11. Re:Four by ukatoton · · Score: 5, Informative
    RTFA
    There are 3 states the bits can fall into:

    1. initially (almost) always 0
    2. initially 0 or 1 with somewhat even probability
    3. initially (almost) always 1

    Using the bits that fall into category 2 to generate the number will result in a random number, as these are known to change randomly

    since it is now known which bits will change with each power cycle, those bits can be used as a source of true randomness


    Bits falling into the other two states are ignored for the random function and are used for the identification function.
  12. Don't follow the hype. Does not apply to PC's. by rpp3po · · Score: 5, Interesting

    The original paper is much better than CmdrTaco's quick conclusions.
    The described method is ONLY for SRAM (statical RAM), no DRAM, no SDRAM. You can find this on RFID chips and in a CPU'S cache, not in RAM. As there is no way to access a CPU's cache uninitialized, I can't see why this should be useful.
    If you have to modify a CPU first, to allow access to it's unitialized caches (think about all the unwanted implications), it's much cheaper to just give it a thermal diode and register to poll (as most modern CPU's already have).
    After all the described method is just another way of collecting thermal noise. As RFID's are custom designs most of the time, also there it would be cheaper to just use a thermal diode.
    The only application for this would be if you had to develop strong crypto for legacy RFID chips.
    Slashdot stories get worse by the day.

  13. Re:Fingerprinting by benhocking · · Score: 3, Funny

    Wow, that actually makes sense. I'll bet you cheated and RTFA, didn't you?

    --
    Ben Hocking
    Need a professional organizer?
  14. HotBits by The+-e**(i*pi) · · Score: 3, Informative

    The only way I know of generating truly random numbers (not psudorandom) is hot bits which works on the principle of single radioactive atoms decaying after a perfectly random, in every sense of the word, time. http://www.fourmilab.ch/hotbits/

  15. Re:Four by ajs · · Score: 3, Informative

    I'm not entirely clear on why this is more interesting than just using timing like most of the rest of the world does. Perl has, for example, long used a setjmp/longjmp-based timing test for its Math::TrulyRandom package by Matt Blaze and Don Mitchell of AT&T and of course most modern Unix-like systems implement /dev/random and /dev/urandom again based on timing. RFC1750 has given useful directions on how to generate random numbers on generic hardware for well over a decade. I recall first reading this RFC, not long after it came out. It really changed my understanding of random numbers on computer hardware.

    This just doesn't seem all that newsworthy, though it's cool enough as yet another random number generation technique, I suppose.

  16. Old news - I have already been granted patents by ironring · · Score: 5, Informative

    This is a bit of old news. I have already authored and been granted several patents in this area.
    6,906,962 Method for defining the initial state of static random access memory
    6,828,561 Apparatus and method for detecting alpha particles
    6,738,294 Electronic fingerprinting of semiconductor integrated circuits
    I have several other ideas for application of this technology and would be happy to discuss if someone is interested.
    Paul