PUFs are just so cuddly!

10 12 2009

As I wrote a few entries ago, I have been using FPGAs this semester in my research group. Since it’s the end of the semester and the paper has been submitted, I thought I would talk to you about my research some. The group that I do research with is mainly concerned with identity management and information security and this project was no exception. Specifically, the project I was working on was using Physically Unclonable Functions, or PUFs, to identify users. PUF device

A PUF is a device that when given a “challenge,” will always generate the same “response.” In this way, an authority can give a user a challenge and, based on whether or not he produces the correct response, can determine his identity. Generating responses to challenges is also very fast; much faster than systems using exponents and modulus to prove identities through advanced cryptography. These responses are actually hardwired into the PUF device due to the internal circuitry. Since generating a response takes very little computer power and energy, PUFs are a very viable way for low-power and mobile devices to securely identify themselves.

The idea of a PUF might sound interesting, but wouldn’t it be easy to simply make a copy of a PUF, record several responses, and then impersonate the PUF? A good idea, but PUFs can deal with this easily. You see, Physically Unclonable Functions cannot actually be copied accurately. That is because there is some element of randomness introduced into the PUF so that every PUF gives a different response to the same challenge. The most common way to introduce this randomness is to use manufacturing inconsistencies. For example, you may design the PUF to have 100 nm long wires connecting the internals of the PUF, but if the manufacturing equipment has a tolerance of even 5%, the wire could be 95 nm, 105 nm, or anywhere between those two numbers. Since the tolerance is uncontrollable, two PUFs produced on the same manufacturing line using the same design files will provide very different responses to the same challenges. PUFs are designed to leverage these inconsistencies and amplify them so that even small inconsistencies will cause large differences in the output from all other PUFs.

PUFs are a very cool technology, but as for my first foray into Verilog and FPGA design, they were quite difficult. There are several different designs of PUFs, so first I had to decide which would be the best design to implement. All of them were about the same difficulty, so my group and I decided to implement a ring-oscillator based PUF, as presented by Suh and Devadas of Cornell. At first, it seemed easy enough to implement, but the more I coded and the closer my deadline got, the more difficulty I encountered. Namely, I had big problems with the design software thinking it knew what I wanted and removing large pieces of my code. Normally, it would have been doing me a favor, but in this case I did not want some specific optimizations and it took me forever to notice this was happening. I had some trouble learning and understanding some aspects of Verilog, but this was to be expected, since I hadn’t ever used it prior to this project.

As of now, the PUF device has been successfully implemented and my team has started to integrate it into the rest of our project. I won’t go into the rest of the project here, but when the paper is published (or not), I’ll upload a copy of the final paper, which you can then read for yourself. Or maybe I’ll give a summary in another post.  We’ll see I suppose!

About these ads

Actions

Information

3 responses

15 12 2009
Dado

PUFs are nice, but problems are:

– Reliability. Will it reliably work in 1, 2, 5 or 10 years in the product?
– Security. PUFs are used as secure key storage. There are succesfull attacks to crack PUFs and extract the key. You can within reasonable computational time guess the PUF values. The attacker can sucessfully attack the rest of PUF logic and extract the key. It is difficult but not impossible!

15 12 2009
samkerr

Hi Dado, thanks for reading.

As for reliability, you raise a good point, but I don’t really know the answer to your question. The lifespan of a PUF will really depend on the way it is implemented, be that on an FPGA, ASIC, or something else completely.

As for your security comment, I think I might have explained the PUF incorrectly. The PUF doesn’t actually store any keys at all. A PUF generates responses by running a large amount of ring oscillators through several multiplexers and seeing which oscillators are fastest, which determines the bits of the response. The actual response is never actually written down in the PUF; it is dynamically produced each time. As such, it would be nearly impossible for an attacker to duplicate the PUF, since the circuitry used in the design is usually in the nanometer range. Any type of measurement at this scale will most likely be either inaccurate or simply destroy the PUF.

You also mentioned that given enough time, one could guess the “challenge-response” pairs, but I disagree. For the PUFs that I worked on, these were 128 bit inputs and outputs, which is a very large number indeed.

15 12 2009
Dado

The PUFs are used to produce the trace that is used for key re-/generation. PUFs do not store the key itself but the trace is stored publicly! There are attempts and (it seems) sucessful attacks on PUFs by learning the PUF behavior. Try Google under “machine laerning attacks on PUFs”. We should also not forget the economics of chip design in terms how much space does PUF require on the chip. If it is too big, than it will be hard to accept them, because there are some cheep effective alternatives for key storage.

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.

%d bloggers like this: