Chaoskey_A_Hardware_Random_Number_Generator_for_Everyone.webm

Bdale Garbee and Keith Packard present their open hardware design 'Chaoskey', a random number generator for everyone.

Good morning everyone

Hopefully you're here for the
same reason I am,

to drink coffee - I mean,
to talk about random numbers.

This is not the first time that a talk
about this particular project

has happened at DebConf, in fact

two years ago in Portland
Tom Marble gave a talk

about the need for having good
sources of entropy

and why it was that Keith and I had
begun a project to build a good

high-quality hardware random
number generator.

It so often happens in life we get a
little distracted between then and now

but if we jump to the very end we're at
the point where we have finally

got to a design that we really like

We're in the middle of an initial,
significantly-sized production run

of the devices. Unfortunately best-laid
plans and all that - we had hoped

to be here with the production units,
and I guess at this point we're still two

or three weeks away from actually
being through that first production run.

So we have a handful of devices we
can show people today - we might even

try to demo before we're done - but we
don't have huge quantities of them

to sell yet, which I'm sorry about.

It's a little unfortunate that that's how
things have worked out.

So I guess the first thing I would say
is if you want more

of a theoretical backround on the
point of random numbers

and why they're important in
our computing lives

I would recommend that you go back
and find the video

of the talk that Tom Marble
gave at DebConf in 2014.

We don't have the time or the inclination
to try and repeat all of that today.

This is going to be much more about
the actual thing that we've designed and built.

But I think a little bit of background
is probably worthwhile.

The fundamental thing is that
cryptographic security

really depends on a robust source of entropy.

This is because cryptographic security
depends on our ability to

have keys that people can't trivially
guess, and various other things.

Entropy is the notion of a source of
randomness that can be

applied and taken advantage of
in the rest of the system.

In Linux systems, our source of entropy
is usually this pool

that's inside the kernel, and where it gets
its entropy from varies.

But if you don't have some other
explicit source of random numbers

on the system, it's coming from things
like the timing of keystrokes

or disk operations and things like that
which are reasonably random.

But it's unfortunately the case that most
of the computers we have and use

don't have a robust hardware
source of randomness.

Lots of other people have worked
on this before -

some of the devices that I'm sure
some of you in this room

have stumbled over are things
like the Entropy Key.

That was a lovely device - I had one

- past tense, unfortunately, because
like so many things

I don't have it any more - but I used to.

Unfortunately those are no longer available
and the design wasn't open

so there's no straightforward way
for us to duplicate that.

There are other products which
are interesting and have

various characteristics which we
think are really cool

but for one reason and another
they're just not quite exactly what

we were looking for.
So the goals we had were:

First and most importantly we wanted
a source of truly random bits

and I'll talk a little about what that
means and show you

some of our measurements to try and
prove that we think we've done

the right thing there.

Keith and I also really wanted this
to be automatically useable

in Linux systems.
One of the things that the Entropy Key

developers did a great job of was
ensuring that those of us in Debian

had easy access to packaged software
that was in the distro and you can

just install the right package and you have
the pieces you need to make it all work

and that was really cool.

But when we started thinking about
the things that we wanted to guarantee

and didn't feel the need to guarantee,
and where the trade-off was in our design,

actually making it so that the Linux kernel -
the upstream kernel - could just

do the right thing when it discovered one
of these devices is present

seemed like such a simpler deal, and
something that would make it

much more likely that more people would
be able to actually take advantage of this.

Because we are who we are, it must
be a completely open

hardware and software design, and in fact

when we get to the end of the talk and
you see where we define things,

the schematics, printed circuit board
artwork, bill of materials,

complete source code tree, all that
is available on our web site right now

and in fact it has been for a while.

We want the device to be secure
against software hacks.

What does this mean?
Well, what we've built is a physical

device which plugs into a USB port
and it has a micro-controller

that has code running on it.

When we initially produce the device
we flash that with code.

If you want to re-flash it later,
you can do this any time you want

over USB, using a utility which is
already packaged in Debian

but: you have to take the plastic
cover off the box

and you have to short two holes
in the board together

in order to enable reflashing.

So nobody can randomly spoof
your device by from some distance

reflashing - you know, if they
break into your system -

they can't just re-flash your random
number generator with some other code.

I guess they could re-flash something else
with your random number generator code

but that's all getting a little whacky.

Our device, at least, can't just be broken
through an attack - a remote attack -

on the software.

And we want it to be as
inexpensive as possible

because again this is all part of
believing that the world needs more entropy

and we'd like lots of people to be
able to afford to use these.

So this is one of those devices where,
on some level, if you get it right you

could charge an arbitrary amount of money

because people who want this want it,
but from our perspective

it's really important to have these
be as widely available as possible.

The one really big decision we made
- and it goes into our thoughts

on open hardware - is that we
are not trying to protect

and make this secure against
hardware attacks.

Fundamentally, if someone has
physical access to your device

we're not guaranteeing what
happens after that.

In particular, as I've already mentioned,

if they have physical access they
could re-flash it at a minimum

but they could also do other
things to it as well.

That also means we've not done things
to try and dramatically

environmentally harden the device:

we don't POT it, we don't do all that
kind of stuff that people sometimes do

when they're trying to make things secure.

In terms of the actual hardware device,
two or two-and-a-half years ago

I designed a prototype and I tried
to do something really clever

in the design of the actual noise source

and as so often happens when you try
to be a little bit clever

it didn't really work right the first time.

For a lot of reasons having to do with
where we were and trying to build a house

and all of this, I got distracted and just
didn't get back to it for a very long time.

Keith picked it up and all of
the hardware work on this since then

has been pretty much led by Keith,
with me and other folks chiming in

from time to time.

So I'm going to let Keith talk about the hardware.

So this is the device that we've built.
It's a tiny little board

about the size of a USB plug
- well, connector.

The design of the board was predicated
on the box that I found.

When you start actually trying to build
hardware it turns out

the hardest thing to do is try to find
a box. A lot of people try and think,

"OK, I'm going to build a device, and then
I'm going to find somebody

to manufacture an enclosure for me".

Well, if you're build a million of them,
that's pretty plausible - I mean

look at Buddy Huang's articles
on his adventures in getting injection

moulding for his laptop prototypes, right?

It was like, "OK, so in the ninety-ninth
iteration of a machined metal enclosure

or mould, we eventually got the things to
work", right, so that cost about

a bazillion dollars.

So we found this tiny little enclosure.

And I thought "OK, how can I get something
to fit in this tiny little enclosure?"

Well, the first design that we did
with the new noise source

fitted this size enclosure.

The reason for that is the processor
is huge - look at the size of that processor.

It's almost a centimetre on a side.

And the funny thing is that very same
processor is advertised

in a much more reasonable,
plausibly-sized package.

So this package is about
four millimetres on a side

and you can see it - oops,
Bdale will go back

You can see the processor
in the upper-right hand corner there,

it's about four millimetres square.
And so I was actually able to lay out

the board to fit in this tiny little box.
Which was pretty cool.

Because the problem with this box
is that it's too wide

so if you have two USB connectors
in your laptop next to each other

you can't use both of them

and that was, like, "well that's going to suck".

So I manage to get it to fit
in this tiny little box.

The other interesting part
of course is that Bdale's design

had a really fun noise source -
a little zener diode, a reverse-biased

zener diode - and then of course

Bdale being an actual electrical
engineer - unlike me - designed

an amplifier with a transistor in it,
and I looked at that and said

"Ah, a transistor, scary!"
(audience laughter)

I really did. Because getting
a transistor to operate in a linear mode -

I understand that it's theoretically possible
(audience laughter)

but my training in college
on electrical circuits was

a single physics lab that involved op-amps.

So I know how to do op-amp stuff.

So I replaced his awesome transistor
amplifier with an op-amp, because

that's what I'm capable of understanding,
because I'm a wimp.

You know, software engineer trying
to play hardware.

So there's an op-amp here, kind of
in between the two holes.

And in the upper centre is
the actual noise source,

a six-pin package with two transistors in it.

And in the lower right corner is a
twenty-volt power supply,

so caution - if you open the device up,
you could possibly shock yourself

with about a milli-amp at twenty volts.

Or fry your machine, if you feed
twenty volts back into USB.

So it isn't as harmless
a device as it looks.

I mean, I wish I could have put,
like, a kilovolt on it

to really give you a warning.

There you go, physical security -
it could attack you if you try to open it.

(laughter)

So the box now fits in
this tiny little package.

The noise generator we actually lifted
from the OneRNG - the New Zealand

team that's doing a noise source.

Is that where the noise source is from?

I think so, yeh.

So the left-hand side of the circuit
is all just a twenty-volt power supply.

All those pieces.

And on the right of R3 - that's
the noise generator.

It's really just two transistors in
the bizzarest circuit you'll ever see.

Isn't that awesome?

It's actually the left-hand transistor
that's the noise source -

the right-hand transistor is
just giving a little bit of buffering.

So it's really just that connection
between the emitter and the base

of that transistor.
It's a reverse-biased P-N junction

generating noise, and then
and emitter-follower

buffering and amplifying it
just slightly.

And then we run that through a capacitor.

So out of that we get about
ten millivolts of noise

and then we run that through an op-amp,
amplify it and then through an ADC.

The awesome part is that when
you just look at the output of that

from the ADC - here's a histogram of
values from that, it's like

"Oh, that's a lovely little kind of
perfect normal distribution of noise".

So you can actually see that we're generating
a fairly nice distribution of values.

Of course this is not what you want
if you want a random number, right?

Random numbers are
not normally distributed.

If you want an evenly-distributed
random number

you don't want normal distribution.

This is what a plot of about two thousand
points looks like

and you can see that it's kind of
biased towards the centre.

However, the good news is that
if you just take this data

and run it through an FFT

you'll notice that the frequency
response is nice and flat -

or chaotic, as the case may be -

run chaos through an FFT and
you get chaos out.

But it's nice and flat, so
we know that we don't have

a frequency response problem, which we
did in the earlier circuit.

The big problem with my original
design is that the biasing of the

reverse-biased zener was a little off

and as a result it was very susceptible
to low-frequency noise

and there was a source of low-frequency
noise about a millimetre away.

I would have fixed it eventually, maybe.

I did the cheap thing and applied an op-amp!

And now we have a working product
- it's all good!

This is how we work together by the way -

we sort of, you know, give each other crap
until somebody breaks down

and spends the time to fix something.

Well the awesome part is that
Bdale has been very patient

at letting me design hardware - I think
this is the fifth version of the board.

I'm a software guy, right?
How do you do software design? You iterate.

And you know, release early and often.

But then every iteration takes - instead of
ten minutes like a software iteration -

it takes like two weeks, because you have
to send it off to the PCB fabrication place

and then the boards come back
and you put parts on

and then you think, "Man, that was stupid!
Why did I hook up that connection backwards?"

In software you just go change the software.

Hardware: two weeks later
and you get to try again.

So I'm slowly learning how to do hardware
but I'm still terrible at it.

So we built this noise source.
We need to make sure it's actually random

because if you have something that looks
random, and dump it in your computer

and it's not actually random, and
actually turns out to be predictable,

then you've kind of lost already.

So there's a bunch of stuff that
we've done on this thing.

There are the FIPS standards - which are
hilarious, you should read

the FIPS standards on random numbers.

The FIPS 140-2 Standard for Random Numbers
literally says,

"OK, just make sure that the chunk of data
that you're sending never repeats".

That's the entire standard - all that
it requires of random numbers

is that you never reproduce
the same value twice.

Don't say "4444" - that's wrong -
but "43214321": that's perfectly OK.

But the standard is... yeh, ridiculous.
It's a federal standard.

So nobody actually falls to that
lower standard that we're aware of.

But the point is that in the standard
there's some discussion about

what it means to be random,
that's not very useful,

and there's a bunch of discussion
about sort of how do you know

that you have a device that's OK
to actually use.

And some of those bits are useful.

In particular, when I first
flash the device during production

I do a bunch of tests on it to make sure
that the values are coming out random.

I do the FFT tests, I do a bunch
of other tests to make sure

the circuit was constructed as we expect.

Because one of the big problems
with physical hardware

is that you don't have perfect replication.

Actually the first - I made a bunch of
these boards and got a bunch of parts

and built them all, only to discover that
the parts supplier sent me the wrong parts

for the noise source.
I don't know what they sent me

but it wasn't a transistor.

It was even the wrong package.
And I still need to send the wrong thing

back to them so they can
close up the final bill.

It was funny - I built the device
and I plugged it in

and my production test said
"No, that's broken".

I'm, like, "how can that be broken?"
and I looked at the noise source

and it looked like, "oh, that's not
actually generating random numbers

at all."

So we do a bunch of production tests
which are extensive and make sure

the device operates with
the right behaviour.

When the device powers on -
the first time you plug it in -

we do some testing as a
kind of real sanity check

(The production test is all
in the source tree, right?)

We haven't quite finished it...
I have some ideas about how it might work.

What we do with all of our products though
is there are turn-on test scripts for them

including the rocket avionics stuff
all in the source tree

so eventually when it's all folded
in the right place, if you want -

I still have two weeks, right?

You still have two weeks.
- Awesome.

Just-in-time software.

As with everything else we do,
not just the hardware design

but how we go about turning them on,
what our production test process is

all of that is also open, so
if you want to look at it

and provide feedback or comments
or suggest something different

you're always welcome to have input.

I've actually been working with a friend
of mine who is a Professor

at Portland State where we had DebConf
a couple of years ago -

he's got some students off generating
some useful tests.

There is an interesting random number
generator test - I don't remember the name

It's a huge long suite of tests that I've
run on this thing and it passes that fine.

It says that there are 7.99992 bits
of entropy per byte.

I don't know why it doesn't think
there are eight, but I guess

getting all the way to eight is hard
or something.

Random round-off there?

Yeh, random round-off, probably.

And then as the device is running it's
constantly testing the data generated

to make sure that it looks pretty random.

What we're doing with that is currently
I actually just make sure the normal

distribution looks like a bell-curve, looks
reasonable and isn't spiky or something.

I want to do kind of a point FFT to make
sure the frequency doesn't look

like you just have a sine wave , which
is a common failure mode in the hardware

because if the transistor goes
"catty-walkers" sometimes you just get -

you're just picking up noise from
the environment and you get a sine wave out

which is not very random.
So we do online tests, we do power on tests

and then we do production tests.
That's how we're making sure it's random.

And you also mentioned that you're using
the CRC generator to whiten? Or not?

Yes. Yeh, so as we said the noise right
here is normally distributed - the values

that I'm getting out of the noise source
source are randomly distributed.

What we discovered was that the middle
eight bits are completely random

and as you can see these are about twelve
or thirteen bits of data coming out

so that we get values from zero to 4096,
centred around 2048.

So, how many bits is that? Thirteen bits?
Twelve bits, OK.

So we have twelve bit values
distributed around, but if you throw away

the top bit then the bottom eight bits
are really quite flat.

We could have just used the bottom eight
bits for our noise source

and that would probably would
have worked fine.

What I did instead was the chip - as
with many SoCs - has random extra

functional units, so one of the things
it has is a CRC32 generator in hardware

so you dump data in and you pull data out,
you know, one instruction in and one out

so I took all sixteen bits out of the
the noise value that I read from the ADC

and I dump that in the CRC generator
and pull eight bits out

and because I know that the noise source
has at least eight bits of entropy.

I know that it's a valid thing to do,
because whichever eight bits I pull out

they're going to be random.

So we're using that CRC to kind of
whiten or flatten that data, so that

we get truly flat data.
This is actually of course a plot from

the raw source, but if you look
at the plot from the whitened source,

it's completely flat - all of the values
are evenly distributed.

It's normally distributed randomness,
which you can get into arguments

with people about whether it's
really random, but what you seem

to really want in the cryptographic world
is a uniform distribution of values

which are not predictable.

So to wrap things up, I already mentioned
we have an initial production run of

a thousand of these currently underway.

I've been asked by a couple of people
where we're having them built.

To explain just briefly, the micro-controller
chip we chose is one from ST Micros that

we've used for some other things.
It's a tiny little - this one's a Cortex 0?

Yeh.

And it has 32K of flash, and it has a
tiny little in-built USB bootloader thing.

So we're actually having these
manufactured in Shenzhen in the first run

and a lot of folks are "Oh my God, China,
you're letting the Chinese touch your

crypto-related stuff."
Well the answer is we're not having them

flash anything. The boards come to us
and we're doing the flash and the

production tests. So I guess on some level
of theoreticalness somebody could be

putting different chips in them than
the ones we actually asked for and

spoofing us at a very deep hardware level.
But I kind of doubt it.

Frankly at some point you have to decide
where in this chain of importance versus

ridiculousness you want to fall.
I certainly don't want to start with sand

and a heat source to make chips, so
we think this is a pretty reasonable place

because we're not relying on anybody else
to put the code in that's on the device

when we ship them.
By the way, the reason that we think

we meet FIPS level 2 is that it has to be
"tamper-evident", and you have to cut

the label to get the box apart, and it's
almost impossible to cut these labels

without just sort of destroying them,
so... eh, we think it's tamper evident.

It's certainly not tamper-proof.

We do expect to have this production run
delivered to us in the next couple of weeks

- as I said we really just missed
having them in time to be here.

We really had hoped to be here
with a big bag of them

for anybody who's interested.

Oh, we decided to set the quantity one
price at US $40

and then to discount for quantity.
If people are interested in

real quantities of them, let me know
and we can talk about that.

I have somewhere in my bag in my notebook
a set of proposed quantity discounts.

Our goal here is really to make sure that
people have access to high-quality

sources of entropy and we really hope
this ends up being something

that lots of people are having.

We do have a few more of these which
are sort of, you know, we had a small run

done by our manufacturer to validate
their prodution processes.

We have a few more of those if
somebody really desperately needs

to have one today. But because we
only have a few, if you're really interested

the right thing to do would be to watch
chaoskey.org, and we will change

the status at the top of that page
to indicate when we have them for sale

and I'm happy to stick them in envelopes
or boxes or whatever and send them out.

So with that, I guess we're pretty much
done with the content part of this

and we'd be happy to take any questions.

(audience)
I'll take fifty! (laughter)

We don't have that many with us today.

The one thing that I'm trying to do right
now is to get the drivers in the Stretch kernel

but it's not in the stable kernel, so I
need to backport the driver to the stable

kernel so the DSA folks will be happy.
It's a completely separate driver, so

I can either construct just a package
which has the driver that you could load,

or I could merge the patch into the current
stable kernel and just deliver it as part

of the kernel package - does anybody
have any preference?

Could you just use RNGD?

We don't need to use RNGD, it's
built directly into the kernel.

We don't need any external applications.

Microphone please, aba.

OK, I am the first to take a microphone
but the cameras can see me.

So does it work with the backports kernel
because that might be enough?

The driver should just compile - it's
just a USB driver, so there's nothing

magic in it.

But it is not in the stable
kernel yet -

What version is the backports kernel?
We don't know.

It's just basically the same as testing.

Oh, then it's already in
the backports kernel.

I think that DSA wanted to have it in
the stable kernel, yes?

Yes.

And Keith also mentioned that people
have asked us, "well gee, you'll have your

own kernel driver?" Well, yeh, I guess,
except he's already accepted a USB

VID/PID pair from somebody else who
wanted to just use that driver with

their source of entropy. So if that
ends up being a standard approach

people take for building more
and diverse things.

And you recently took a change or are
working on a change or something

so that the kernel will accept and blend
data from multiple sources of hardware

randomness - in the past it's been,
you know, pick the most random-looking

thing and use it -

No, the most recently-attached thing.

The most recently-attached thing. So
we generally believe that another way

to sort of help you deal with the possible
- so if somebody walked up and stuck

something random into your machine -
ha ha, you see what I did there -

is that if you had a known good source
of randomness on the machine already

and you were interleaving the bits
that you get from all of them

it would just make it exponentially
hard for anybody to really spoof

your random number generator.

And of course the kernel's been doing
its own thing - I don't know

on any given day exactly what happens
between the entropy pool and the bits

that are delivered by /dev/random and
/dev/urandom.

That's been written about elsewhere -
Greg Kroah-Hartman had an article

which was referenced by Tom Marble
in his Portland talk.

Andy?

So, hardware RNGs are notorious for
temperature stability problems.

First of all, are you monitoring
temperature to determine whether

you are drifting?

And second, have you tested across
temperature ranges?

It's been tested across some amount
of temperature range

because Keith and I have entirely
different environmental desires personally

(laughter)

He's in a couple of layers of jacket
and I am not.

But no, we have not done that.
We probably should.

Yes, it would be easy.

There is at least one temperature
sensing point on this device already.

Isn't there?

I don't think so.
I don't know if this one does or not.

It's a good question, Andy.
I don't know the answer.

Certainly testing it across a broader range
is not a terribly hard thing to do.

Again, it's completely open hardware
design. We would love for all of you

to go take a look and tell us what a
bunch of idiots we are.

Of course it would be nice if we'd sold
at least a few of the thousand

before we found that out.
(laughter)

OK, any other questions?

If you compare the Entropy Key, which has
the EGD daemon, that would distribute

randomness and make it easier to transport
randomness to a virtual machine

or something like that. Have you -

So if you have a kernel that has an
essentially infinitely deep well of entropy

I would assume that you could figure
out some way to happily pump

the bits to other machines. Using the same
daemon and just saying "trust the

local kernel to have a lot of randomness",
then...

And we can keep a full-speed USB
pipe full, which is not quite

a megabyte per second in actual
throughput. It's like a megabyte

per second-ish of randomness.

Our time is up, so thank you very much.

We appreciate your time and attention.
(audience applause)