*33C3 preroll music*
Herald: Ok, please welcome Pol van Aubel, PhD student at Radboud University in
Nijmegen, and he's going to give a talk of physically uncloneable functions.
A warm round of applause, please.
*applause* Thank you.
Pol: Thank you, thank you for having me, thank you for having me on prime time,
when everybody is finally awake, but not yet drunk.
*mild laughter*
And, thank you for letting me compete with the space track. So, well, my Herald just
explained who I am, but the work in this talk is actually mostly not from me. It's
by many many authors, and there will be citations on almost every slide. Don't pay
attention to those. It was simply too hard for me to make two different sets of
slides. Download the slides afterwards, if something interests you. The entire intent
of this talk is to get you interested in this material, get you reading the papers,
and get you implementing this stuff yourself. So, without further ado, and
without any further egocentric blathering, let's look at the problem we're trying to
solve. In computer security, since the 1980's, we've noticed that we might want
unique identification and authentication of devices. And then, specifically, integrated
circuits. So, we want to distinguish chips, uniquely, from the same
manufacturing masks, even, and with high accuracy, unforgeably. Eh, simple task,
right? So, in order to explain how we get to physically uncloneable functions, I'm
first going to explain some history in anti-counterfeiting. And
anti-counterfeiting, you can think of money, you can think of magstripe cards,
you can think of identity documents, and nuke counters, or as they are commonly
called in literature, "Treaty Limited Item" identifiers. So let's start with
money. Historically, money has been protected with highly intricate imagery.
This is an example from right after the US Revolution, and I personally really like
the, let's see, the "To Counterfeit is Death". Because, you know, while it was a
crime against the state, you were drawn and quartered when you did it. Then we
fast forward a few centuries, and I would like to know from the audience, who has
ever seen this? ... Quite a lot. Can anybody tell me what it is?
*audience comment* (inaudible)
The EURion constellation. It's intended to prevent photocopiers from
copying your money. So basically, when the photocopier detects this thing, it'll just
not... it'll just say, "I don't want to copy." You can actually use this on your
own stuff if you want. But, we see a common theme in those entire few
centuries, namely, you mark all valid bills the same, and then you make sure
that you can check the marks in order to identify that it is legitimate. An
alternative to this would be to have different marks for each bill, and sign
that marking. But, you get into a whole bunch of questions, like, how do I then
prevent somebody from copying that bill-specific valid mark a hundred
thousand times, and just, you know, copying the signature as well. It's not as
though anybody is checking paper money online. So, back in 1983, Bader proposed
an anti-counterfeiting measure, which basically meant you sprinkle random-length
cuts of optical fibers into your paper, before it becomes paper, the... mull. (?)
And then, you make the money, and you use basically a light bar scanner, so whatever
a photocopier does as well. And then there will be a dot pattern that appears around
the light bar. And you extract that dot pattern, you make that into a series of
bits, and you sign that dot pattern. And then you print the signature onto the bill. Now
there's several problems with this, which are all explained in those papers, I don't
have time to go into that, but in principle, this works. Then, next, cards.
You know magnetic stripes and PIN, the way we used to use them in Europe, I think you
still use them in the US, I'm not sure... But because nobody knows how to copy
magstripes, right? So, you add stuff to the card, so that it becomes detectable
when somebody has copied the card onto a forgery. So, you use holograms. So far as
I know, holograms are also copyable, now, I don't have a literature reference there,
but... stuff can be done. Now somebody in 1980 already proposed this: You randomly
disperse magnetic fibers in a coating, you scan those fibers with a, well,
electromagnetic sensing device, and turn them into pulses and AND the pulses with clock
etc., turn them into bits again, sign that pattern etc. Then there's also
this nice proposal where you randomly disperse conductive particles in an
insulating material, scan it with microwave, it's basically the same principle from
also the 1980s. Next, identity documents, somebody proposed using the translucency
of a paper strip in an identity document, scan that strip, turn the translucency
pattern into a bitmask, sign the bitmask, etc. Now, Simmons already said that
this was too easily cloneable, because, you know, you can just take a photograph
of this and reproduce it through photographic techniques. So translucency
isn't really nice. Now you could also potentially use the exact
three-dimensional cotton fiber pattern of the paper. But that proposal was also in
1991, and Simmons also said, this is infeasible to do. However, in 1999,
somebody came up with something similar, they take the texture hash of a postal
envelope, so you just print a square on the envelope, take a high resolution
picture of that, and then hash that with a certain hashing code that ensures that all
these things collapse into the same bit pattern every time. This works. Then
finally, those Treaty Limited Items, the reflective particle tags, you basically
affix such a tag to the surface of a treaty-limited item, then you cure them
with ultraviolet light, so that you turn it into a glass-like substance, which
makes a tamper evident, if I try to take it off, the glass breaks, and it also
preserves the particle orientation, and then you put a laser onto it, you look at the
reflective pattern, and you have your identifier. So, if you ever have a bunch
of nukes to count, that might be interesting. The common theme here is that
we are using an intrinsic aspect of an item that's infeasible to copy, but easily
readable. It's unpredictable, and it should ideally be unchanging. Which brings
us to a proposal in 2001 of physical one-way-functions. Basically the idea was,
you have an epoxy with miniscule glass spheres, you cure the epoxy, you make it
into a ten by ten by two and a half millimeters, don't know the exact
dimensions anymore, ... I say "sphere", I mean, what's it called, cube... cuboids,
something like that... And then you illuminate it by a laser, and then you get a speckle
pattern out of that, because the laser will disperse in a really unpredictable
pattern, and you capture that at 320 by 240 pixels, you turn that into a 2400 bit
key with a so called Gabor transform. I have no idea how the math behind that works because
that's not my field of expertise. And you get interesting properties like drilling a
hole here causes half the bits to flip, so it’s tamper resistant, and it mirrors the
way one-way functions work, like SHA-1 and SHA-256: ideally, if you flip one bit in
your input, half your output bits are flipped. So this paper is really the first
paper that proposed this as a connection with cryptography. So here, reading the
structure is feasible, because, you know, you have this glass pattern, you can just
– I say just, but you can use microscopic techniques to read it out
exactly, but good luck with having this sub-micron accuracy for all those glass
spheres in the epoxy. So, you can, in theory, if you know the structure, emulate
or simulate how a laser passes through this. But it requires a lot of
computational power, and in order to... you also can't build a database of responses
to challenges, because imagine that the challenge to the structure is a laser at
different orientations, like, I can say a laser under an angle of 5 degrees, or 10
degrees or 20 degrees, and at different locations, and all those responses will be
different. So this challenge-response space is infeasibly huge. So the protocol here
would be, first, you read this thing on a trusted terminal, and you create a random
collection of challenge-response pairs. Your challenges have to be kept secret
because, next, you get an authentication request from an untrusted terminal, and
you challenge that terminal. And the idea would be that it is infeasible to send the
correct response key if you don't have the device containing this PUF, er, this
physical one-way function. So you then receive the response key, and you reject
this if the key differs by too many bits. Because it won't be a perfect match. There
might be scratches, there might be slight micron differences in the orientations, it
might be a bad camera, you get some differences, and the way you then do this
is you calculate the least probable acceptance rate of a counterfeit device
that you want, and then you get to this amount of bits. And then you can get a
better match rate if you repeat steps (4) - (6) a few times, and if you run
out of challenge pairs you can just go back to (1). That's the general idea. So
this is the first paper that made this connection with cryptography, it has a
defined protocol, but there are several not-so-nice things, like, you have special
equipment required, and we would really like to have the same possibility in
silicon and silicon only. Now in this paper already, the proposal was that you
might be able to have a similar approach, if you scatter electrons... uhhh... I
don't understand what this says, but I know that it is not what we're going to
see next. As an aside, if you do this kind of thing, then you get to read very old
papers. So, wasn't it nice, back when you could say this: "In the fuel rod placement
monitor … high radiation levels in the "hot" cell provided the general tamper resistance."
Or: "The seismic sensors … would detect any attempt to gain physical access to the
package long before the information security is in jeopardy." Now I wouldn't
actually take that one as a bet because I know you guys, but, uhhm, the first one
is pretty good. And you get to see things like this. This is how RSA was done in
1984. This is a – I think – that's an ISA, maybe pre-ISA bus, I dont know... So
this is how that was done. And the text is really beautiful: they scanned an old,
basically typed on a typing machine paper. This is available online, by the
way, if you have university access... sorry... Then, there are other solutions
to this problem, of course. You have hardware security modules, you have
smartcards, you have trusted platform modules... actually, I found out we only
have those since 2006, I felt [like] they were older?... But you still have the
problem of key management, right? Because the key isn't tied to the platform. If I
can extract the key, and put it into another trusted platform module, or
another hardware security module, then we're still dead in the water. So the aspects of
these things is the key never leaves the device – ideally – but then how does
the key enter the device? You can enter new keys, you can enter key-encrypting
keys to decrypt keys that you never see, that another hardware security module exports,
it's all interesting crypto, but you also get the problem of what can the key do,
are you limited to 1024 bits RSA, and is it possible to emulate all this once you
have the key, right? We really want to have other aspects to our function. Now,
this is the first name for PUFs, "silicon physical random functions", but they
already knew that "PRF" might have some three letter acronym that clashes with
"pseudo-random function", so they decided to go for "physical uncloneable
functions". There's an interesting discussion going on whether it should be
"physical" or "physically"... not going into that. The idea is, tamper resistance
in general is expensive, is difficult, it's just... let's look at a different
approach. There is enough process variation across identical integrated
circuits, where... yeah, so, they're not identical because of those process
variations. And already in 2000 somebody made a... Lofstrom, Daasch and Taylor had
a small paper on specific special device identification circuits. But, if you want
to use those for secure device identification and authentication, then
just a single such circuit is not enough. You need more. So, what do you do? You
build this. And I don't think it's really feasible, ... basically, this is
the entire circuit, you have a delay circuit here, ...this is a ring oscillator
PUF. So you have a delay circuit here, this is a self-oscillating loop,
basically, this feeds back into this. And the challenge here is a bit for each of
these blocks. And what the bit says: if it's one then you pass through, if it's
zero you pass over. So if you have a different challenge, you have a different
path through this PUF. So ideally, for each challenge, it should be unpredictable
whether this final arbiter block here... uhh, somewhere over there... gives a one
or a zero, and then you count the pulses, and you identify your circuits. Now
attacks on this were also quite well studied in this paper... possible attacks.
So, you have the duplication attack, which is basically cloning, which should be
impossible. Right, that's the general idea: Cloning should be impossible. There
is emulation from measuring, so, you build a model from this by measuring the exact
distances between logical units inside the PUF, or the length of the wires inside the
PUF, also deemed infeasible because how are you going to measure this without
destroying the PUF. This is back in 2001. Then there was emulation from modeling, so basically, if
you get these challenge-response pairs, if you get enough of them, you can apply some
nice maching-learning algorithms to that, and then you get prediction of responses.
And, finally, you have the control algorithm attack, which is
attacking the PUF's control algorithm without ever getting into the PUF. If you
can do that, then your PUF is useless. So, they also proposed controlled physically
uncloneable functions, which is the same but with bells on. So you have an access
function for the PUF, which is part of the PUF. This is to prevent against that final
attack. So basically you overlay the logic of the access function with the PUF, so
that to access the logic of the access function, you have to break the PUF. And
if you break the PUF, everything breaks, no longer works. So this gives additional
properties. An uncontrolled PUF can only be used for device authentication. This
can be used to have nice things like proof of execution on a specific device.
Potentially [for] things that I don't have an opinion on: on code that only runs on specific
devices, but basically whatever you need a secure cryptographic key for, you should
really be using a controlled PUF. Is the idea. But you can still do device
identification. So, how does a controlled PUF look? You have a random hash here, you
have a potential ID here, you have the PUF here, Challenge, ID, Personality into the
random hash, you run that through the PUF, do some error correction, because PUFs are
not ideal, and then the random hash again, and then the response. This is to prevent
all these attacks. If you're interested in this, read the paper. Then, in 2011, a
formal model was proposed, what do we really need from PUFs? First, we need
robustness. Across evaluations, we need the same response. We need physical
uncloneability, it really shouldn't be possible to clone these things, and we
need unpredictability. Now, these two are potentially a lot, so we'll get into that
on the final slide, I think... And since then, since 2001 there have been a lot of proposals
and attacks on PUFs. So, first, there are the Arbiter PUFs, which are all delay
based. So, the general idea here is that if you run a signal through a chip, it is
delayed by a certain amount. But the amount is unique per chip. But it turns
out that you can pretty easily model this. And even the Bistable Ring PUF, which is
fairly recent, I think, you can do some fancy machine learning... I highly
recommend this paper, "Pac learning of arbiter PUFs". Basically, the idea is, you
have 30000 challenge-response pairs, and that is enough to give you 100% accuracy
on a 256-bit challenge PUF. That's not good. This doesn't really work, if you can
model it that way. And you can also use optical measuring of signals through
devices at six pico-second accuracy. So these things might not be around for much
longer. Then there are memory-based PUFs. They are based on bistable memory, which
basically looks like this, and it's also delay-based, but here it's unique to this
cell. You have a block of these cells, they are all independent, so you get a
pattern out of this. These cells go to one or zero, and they are pretty fairly stable
in doing it. I'll show you a picture later of what happens if you have a nice PUF of
this type and if you don't have a nice PUF of this type. However, if you have a SRAM
PUF, for instance, you have fairly limited SRAM. So you can just, in principle, read
all this out and store all the bits in a database. And then you can, er, clone the
PUF. Because you can use focused ion beams to trim the SRAM of another chip into the
correct orientation. And, well, emulation, if you have this database, you can just
respond from your database. So, this is, in some literature, termed a "weak PUF",
but it's probably still the most useful one we have right now. This is usually
also what's in your devices if it's claimed to have a physical uncloneable
function. But they are of the control variety most of the time. Then finally,
recently somebody proposed, I think that was, yeah, Schaller, Xiong, and
Anagnosto... can not pronounce it. But the decay-based PUFs, the idea is, you have
DRAM, take the power off, put the power back on, look how it decayed. No attacks
on that that I have seen yet. So, the final few minutes of this talk will be
about your very own memory PUFs. Which is trivial. Right? ...No. It's not, actually.
And all this time before, you might think, why would we even bother with this? It
seems to be hopeless for PUFs, there is not enough randomness in the silicon, but
I disagree. Because for one, some protection is better than none, which is
what most system-on-chip devices have. And two, I do not believe in silver bullets.
This should be part of a greater security mechanism. So if nothing else, if all you
want from this talk is some interesting paper to read, just one, read this one.
That's on slide 39, it's called "Lightweight anti-counterfeiting solution
for low and commodity hardware using inherent PUFs." And, preferably, you also
read this related one, "PUF based software protection for low end embedded devices."
Don't be fooled by the terms "IP protection" and "license model". This is a
Secure Boot environment. You want it, in your Raspberry Pi, for instance. I don't
know whether Raspberry Pis have it, that's for you to find out. So what you'll need
is a device with a masked ROM to hold the boot loader, like the first stage of code
needs to be under your control. You need to have that modifiable startup code, you
need to be able to modify it, obviously. And you need on-board SRAM, to build the
PUF from. And then you need some non-volatile memory for encrypted firmware
and helper data. So, in the puffin project, which that earlier pic was a result
of... So, there are several results here. This is an STM32F100B microcontroller,
this is PandaBoard, which is pretty much like a mobile phone actually, so what you want to
see is this. White noise. This part is a PUF-like memory range, this part is
probably spoiled by the bootloader or something like that or the wrong code, but
this you can use. This looks good. So, once you have such a white-noise area, you
start measuring a lot of times, and then you compute the Hamming distance between
lots of measurements from lots of different devices. And you want it to look
like this, you want it be around half. Because that means that every device will
look different. By about 50%. You also measure the inner class Hamming distance, which is same
measurements from the same PUF, and you want that to be below 0.1. You don't want
that to be too inaccurate, because then your error correction becomes too complex
and starts leaking information, and you will need error correction, using for
example Golay codes. So this first paper I mentioned, the... this one... the
lightweight anti-counterfeiting one, this is also from that paper. Read it, it also
explains how this fuzzy extraction works. If you're interested in this, there's lots
of scientific literature out there. And then finally, you build this fuzzy
extractor, and then you enrol your chip. And you generate some helper data for
this error correction, and then once you challenge the chip you send this
error-correcting data with the challenge. And in the end the idea would be that you
get a secret S' from every chip. Now how can you use this? You have the bootloader
in the masked ROM, this is the first-stage bootloader, it challenges the PUF, and
decrypts the second-stage bootloader, which comes from external memory. And then
you boot the embedded operating system. So, this should look familiar to a lot of
you, because this is basically also how device attestation on x86 works if you're
using trusted platform modules. So, in a bit more detail, same procedure, query the
PUF, decrypt and call, here the key also ends up, and you decrypt and call the
kernel, and then finally, this is how it really looks in real detail. And even if
you don't want to build this, you'll still have this: So, remember when I showed you
the inner class Hamming distance, the 10% of differences between meausurements? That's
caused by the red dots. Those are the unstable SRAM cells. You can use those as
seeds for a random function. And hopefully, you won't have this. This looks
wrong, this is not a PUF, this is too predictable. Unfortunately, all this won't
be possible on x86, because we looked for the PUFs in the CPUs, but Intel and AMD
both explicitly zero everything. Finally, a word on privacy. I don't have too much
time for this, but I really liked the fact they mentioned they feel that users... users
feel that they can be tracked if you have a unique identifier. As though, its not a
valid concern. Damn the users, being paranoid. Now, back to the controlled PUF. You can
add personality IDs as a user. If they challenge it, you add a personality, so
one application reading the PUF gets a different ID from another application,
which changes the entire output of the hash function, no paranoia required
anymore. Hopefully. Finally, the references. Google Scholar is your friend. The rest of
the slides are... all kinds of references... Read it! You've already seen
all of those, read it, thank you for your attention.
*applause*
Herald: Thank you, Pol. We have time for maybe two questions.
Please come up to the mics... Mic 3!
Mic 3: What do you think about MEMS-based physically uncloneable functions, where
they basically use the accelerometer sensors, and the deviations in these
sensors by inducing challenges as controlled vibration?
Pol: Sorry, I missed the first word of your question.
Mik 3: The MEMS-based… basically the technology that is being used to build
accelerometers in silicon. So Bosch has some PUF chips based on that, where they
have arrays of these MEMS-chips, and then a controlled vibrator to induce the
challenge into that.
Pol: I think they're probably more secure than silicon-based PUFs, because they are
built for randomness, whereas we're here trying to extract randomness from an
existing circuit. Yeah, they're interesting. Use them if you can, but most
people don't have the option.
Mik 3: Thank you.
Herald: More questions? Pol: Up there!
Herald: Ok, Mic 7!
Mic 7: Hi, thanks for your talk, I'd never heard of PUFs. I recently went on a
quest to find a usable smartcard that met all the things I wanted to do, like open
source, et cetera. Can you expand a bit on how PUFs could be used with an OpenPGP
smartcard or similar?
Pol: Short answer: no. I have no idea whether OpenPGP will ever support anything
like this. You have the PKCS protocols, I know that in theory this is possible.
I don't know whether anything has implemented it. There are PUFs on
smartcards, but whether.. We haven't looked into this, I don't know of anyone who has.
Mic 7: Thank you.
Pol: But that doesn't mean it doesn't exist.
Herald: That would be all. Please give it up for Pol, one more time.
Pol: Thanks! *applause*
*postroll music*