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
subtitles created by c3subtitles.de
in the year 2017. Join, and help us!