PUFs, protection, privacy, PRNGs (33c3)

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!