You are viewing tshb

Ultra-low-cost true randomness AND physical fingerprinting

« previous entry | next entry »
Sep. 10th, 2007 | 01:01 pm


i recommend reading my friend dan holcomb's recent article on low cost random sequence generation: "Initial SRAM State as a Fingerprint and Source of True Random Numbers for RFID Tags" (disclaimer, i was involved in discussions leading up to the publication of this paper).

why is this so cool?

the idea of using meta-stability and thermal noise in integrated circuits is hardly new, indeed it is the basis of many popular true random number generation schemes.  what is new here is that halcomb proposes techniques for harvesting true randomness from the existing RAM of a computer: strong physically based randomness without a single additional transistor.  as a side-benefit, device tied entropy can be gathered which can reliably identify the individual device.

these new techniques are suitable for almost any kind of computer, from desktop PC to the cheapest RFID tags, and could potentially be used to bring much better random number generation and device tied functions to low cost and resource constrained devices.  even better, some devices might be able to enjoy new benefits of their hardware with only a software upgrade.

how does it work?


as we all know, when a computer is powered down, it's RAM looses state.  but what is the state of the RAM when the computer is first powered on?  the answer is that the state of an individual bit of RAM, before it has been written to for the first time during a power cycle, depends largely on the way its transistors were printed during manufacturing.  these bits fall into one of three categories:
  1. initially (almost) always 0
  2. initially 0 or 1 with somewhat even probability
  3. initially (almost) always 1
by performing several power cycles and doing some statistics on the power-on state of a bank of RAM a computer can create a profile of the bank, recording which of these three cases applies to each bit.  this profile can then serve as a fingerprint, since it will be unique to that particular bank of RAM.  since it is now known which bits will change with each power cycle, those bits can be used as a source of true randomness (rather than psuedo-randomess, which is less valuable).  i am glossing over the special algorithms used to make sure that this is all done securely, you can find them in the paper.

Future Work

although thermal noise is well recognized as being suitable for hardware random sequence generation, i would like to see this work examined in the light of the (way cool) identification attacks based on temperature as it effects clock skew such as steven murdoch's "Hot or Not: Revealing Hidden Services by their Clock Skew".  i can't help but wonder if an adversary armed with fine-grained information about a chip's temperature (such as through clock skew) could attack the randomness of holcomb's scheme.

web statistic

Link | Leave a comment | Share

Comments {5}

SRAM based PUF

from: anonymous
date: Sep. 10th, 2007 04:03 pm (UTC)
Link

The usage of SRAM startup values is nothing new. The paper entitled "FPGA intrinsic PUFs and their use for IP protection" on CHES 2007 describes how it can be used to realize a Physical Unclonable Function with SRAM. They describe how to generate a unique 128 bit key from about 4600 SRAM memory bits.

The paper you refer to needs 256 SRAM bytes "to identify circuits among a population of 160 virtual tags". That is 2048 SRAM bits to generate a 7.32 bit key. So better postprocessing (with appropiate error correcting code) helps a lot.

Reply | Thread

Some of this has already been patented

from: anonymous
date: Sep. 10th, 2007 08:41 pm (UTC)
Link

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

Paul

Reply | Thread

Jacob Appelbaum

(no subject)

from: ioerror
date: Sep. 10th, 2007 09:54 pm (UTC)
Link

Interesting work. I think that there are some funny problems that are inherent in this scheme when it comes to consumer hardware...

Reply | Thread

Idetrorce

from: anonymous
date: Dec. 16th, 2007 02:09 am (UTC)
Link

very interesting, but I don't agree with you
Idetrorce

Reply | Thread

loses not looses

from: anonymous
date: Apr. 20th, 2008 11:33 am (UTC)
Link

don't mind me, just spell checking the internet...

Reply | Thread