WEBVTT
00:00:00.000 --> 00:00:10.064
preroll music
00:00:10.064 --> 00:00:12.189
Herald: Tanja Lange and djb,
00:00:12.189 --> 00:00:15.519
or, Daniel Bernstein,
00:00:15.519 --> 00:00:19.980
came from the elliptic curve
00:00:19.980 --> 00:00:21.710
are gonna talk today also about
00:00:21.710 --> 00:00:24.380
the McEliece crypto where they took us.
00:00:24.380 --> 00:00:25.759
They're both in the steering committee
00:00:25.759 --> 00:00:28.219
for the PQCrypt
00:00:28.219 --> 00:00:30.259
and I've talked to other people
in the community
00:00:30.259 --> 00:00:31.239
and they said,
00:00:31.239 --> 00:00:32.390
especially about Tanja,
00:00:32.390 --> 00:00:37.739
she is the one that brings practice
and reality into all this theoretical mess
00:00:37.739 --> 00:00:44.420
so let's please have a hand for
Tanja Lange and Daniel Bernstein.
00:00:44.420 --> 00:00:55.260
applause
00:00:55.260 --> 00:00:58.769
djb: Okay. Am I on? I apparently am.
00:00:58.769 --> 00:01:01.980
Welcome to a late night show,
with Dan and Tanja.
00:01:01.980 --> 00:01:05.570
laughter
There's a lot of crypto talks out there
00:01:05.570 --> 00:01:09.560
where you'll get the idea that
crypto has problems.
00:01:09.560 --> 00:01:12.340
Crypto has massive usability problems,
00:01:12.340 --> 00:01:13.890
has performance problems,
00:01:13.890 --> 00:01:15.460
has pitfalls for implementors,
00:01:15.460 --> 00:01:17.750
has crazy complexity in implementation,
00:01:17.750 --> 00:01:19.729
stupid standards,
00:01:19.729 --> 00:01:21.920
millions of lines of unauditable code,
00:01:21.920 --> 00:01:23.320
and then all of these problems
00:01:23.320 --> 00:01:27.189
are combined into a
grand unified clusterfuck
00:01:27.189 --> 00:01:30.030
called transport layer security.
00:01:30.030 --> 00:01:38.030
laughter, applause
00:01:38.030 --> 00:01:41.449
But, actually, the situation is worse.
00:01:41.449 --> 00:01:43.510
laughter
00:01:43.510 --> 00:01:45.790
Because of what's coming, namely,
00:01:45.790 --> 00:01:49.260
quantum computers.
00:01:49.260 --> 00:01:51.610
These typical talks will give you the idea
00:01:51.610 --> 00:01:54.829
that the core of crypto,
the basic cryptographic primitives
00:01:54.829 --> 00:01:57.280
like elliptic curve crypto, ECC,
00:01:57.280 --> 00:01:59.240
that those are just fine,
and all the problems
00:01:59.240 --> 00:02:01.229
are integration into applications,
00:02:01.229 --> 00:02:03.100
that's where the security problems happen.
00:02:03.100 --> 00:02:06.609
But quantum computers will break ECC.
00:02:06.609 --> 00:02:09.258
This has been know since the 1990s.
00:02:09.258 --> 00:02:11.500
For people who don't recognise
the picture here,
00:02:11.500 --> 00:02:17.040
this is a mathematician named Peter Shor,
20 years ago.
00:02:17.040 --> 00:02:25.769
laughter, applause
00:02:25.769 --> 00:02:27.640
20 years ago he wrote a paper saying
00:02:27.640 --> 00:02:29.340
that a big quantum computer would be
00:02:29.340 --> 00:02:33.300
able to factor big integers
in polynomial time.
00:02:33.300 --> 00:02:34.770
Now, if you like doing attacks,
00:02:34.770 --> 00:02:36.259
and you hear about something like this,
00:02:36.259 --> 00:02:37.190
then your first thought is
00:02:37.190 --> 00:02:39.080
"Ooh, I wanna quantum computer!"
00:02:39.080 --> 00:02:41.430
"I want a big quantum computer
so I can run this attack!"
00:02:41.430 --> 00:02:43.350
"And, where is it? Does anybody have one?"
00:02:43.350 --> 00:02:44.620
"Can anybody gimme one?"
00:02:44.620 --> 00:02:46.610
"Oh, it isn't there yet?
Well, what's the progress?"
00:02:46.610 --> 00:02:48.670
"Are we there yet?
Can I have one, please?"
00:02:48.670 --> 00:02:50.470
And, well, in the news, you now hear
00:02:50.470 --> 00:02:53.669
about this D-wave quantum computer,
00:02:53.669 --> 00:02:56.879
which, okay, there's some very good
quantum engineering
00:02:56.879 --> 00:02:58.180
that goes into this machine.
00:02:58.180 --> 00:02:59.420
It's pretty clear that it's quantum,
00:02:59.420 --> 00:03:01.800
I mean, it's actually doing the quantum
stuff they say it does.
00:03:01.800 --> 00:03:04.920
And there's some fantastic
marketing in this machine.
00:03:04.920 --> 00:03:06.230
But, unfortunately,
00:03:06.230 --> 00:03:07.650
it's not actually useful.
00:03:07.650 --> 00:03:09.780
So the D-wave quantum computer
00:03:09.780 --> 00:03:11.690
doesn't do the basic things
00:03:11.690 --> 00:03:14.830
that we expect a universal
quantum computer to do.
00:03:14.830 --> 00:03:18.159
It can only do very limited
kinds of quantum computation.
00:03:18.159 --> 00:03:20.480
It cannot maintain qubits,
00:03:20.480 --> 00:03:22.520
do error correction on qubits for a while,
00:03:22.520 --> 00:03:23.750
hold on to them to be able to do
00:03:23.750 --> 00:03:25.659
basic qubit computations.
00:03:25.659 --> 00:03:27.739
It can't even do those computations,
00:03:27.739 --> 00:03:29.769
even if it could hold on to the qubits.
00:03:29.769 --> 00:03:31.299
It can't do Shor's algorithm.
00:03:31.299 --> 00:03:32.939
Can't factor big numbers.
00:03:32.939 --> 00:03:35.390
Can't do other quantum algorithms
that we care about.
00:03:35.390 --> 00:03:38.080
Now, the D-wave company says that's
not the point,
00:03:38.080 --> 00:03:39.519
there's some other computations
00:03:39.519 --> 00:03:41.799
that we designed this machine to do.
00:03:41.799 --> 00:03:43.549
But they cherry-picked the computations
00:03:43.549 --> 00:03:45.280
for this machine, saying basically
00:03:45.280 --> 00:03:48.769
Here is the problem of
simulating this machine
00:03:48.769 --> 00:03:51.129
simulating the quantum
thing that it's doing,
00:03:51.129 --> 00:03:53.400
and of course the machine is very good
at simulating itself,
00:03:53.400 --> 00:03:54.610
by just running,
00:03:54.610 --> 00:03:57.909
whereas a normal laptop, they compared to
00:03:57.909 --> 00:04:00.189
sort of standard programs
on a normal laptop,
00:04:00.189 --> 00:04:02.439
and latest results, 10^8 times faster
00:04:02.439 --> 00:04:06.129
except, well, there's a much
more optimised program
00:04:06.129 --> 00:04:07.780
that somebody put out last year,
00:04:07.780 --> 00:04:10.159
which basically is the same speed
as the D-wave machine
00:04:10.159 --> 00:04:12.049
and like ten thousand times cheaper.
00:04:12.049 --> 00:04:15.630
So, the D-wave machine is not,
for the moment, something useful.
00:04:15.630 --> 00:04:18.360
Lange: Well, if this makes you
kind of comfortable,
00:04:18.360 --> 00:04:22.440
so, no Shor monster coming,
00:04:22.440 --> 00:04:23.720
there is progress.
00:04:23.720 --> 00:04:25.760
There will be a universal
quantum computer,
00:04:25.760 --> 00:04:28.000
so, something that can run
Shor's algorithm,
00:04:28.000 --> 00:04:30.020
and there's a lot of research effort
going into this,
00:04:30.020 --> 00:04:32.120
so if you track, like, spending on crypto
00:04:32.120 --> 00:04:33.320
and you can spend...
00:04:33.320 --> 00:04:36.450
and track spending on quantum computers,
00:04:36.450 --> 00:04:37.670
that is a lot of money.
00:04:37.670 --> 00:04:39.850
And there's a lot of institutions
and companies
00:04:39.850 --> 00:04:41.700
and of course governments
all over the world
00:04:41.700 --> 00:04:43.090
building stuff.
00:04:43.090 --> 00:04:44.250
And we do see progress, so
00:04:44.250 --> 00:04:45.730
we're keeping track on this,
00:04:45.730 --> 00:04:48.300
and, go to the Wikipedia page here
00:04:48.300 --> 00:04:50.270
so we see over the last few years
00:04:50.270 --> 00:04:53.980
a huge progress in stability of qubits,
00:04:53.980 --> 00:04:56.430
so these things usually
forget what they had,
00:04:56.430 --> 00:04:57.930
they decay,
00:04:57.930 --> 00:04:59.890
but they get more stable,
00:04:59.890 --> 00:05:01.730
there's better error correction,
00:05:01.730 --> 00:05:03.040
and there's better communication.
00:05:03.040 --> 00:05:06.900
So the latest was that
even silicon-based qubits can communicate.
00:05:06.900 --> 00:05:08.530
So something is happening.
00:05:08.530 --> 00:05:12.970
Um, IBM has
on the record of Mark Ketchen
00:05:12.970 --> 00:05:15.390
who's their CEO saying
00:05:15.390 --> 00:05:19.640
"We actually do things that make us think
like, hey, this isn't 50 years off"
00:05:19.640 --> 00:05:23.260
"This is maybe just 10 or 15 years off.
It's within reach."
00:05:23.260 --> 00:05:24.590
So IBM is leaning out the window
00:05:24.590 --> 00:05:27.510
and saying, yup, we're gonna be there
pretty damn soon.
00:05:27.510 --> 00:05:31.560
They said that in 2012, so
let's fast-forward by 10 to 15 years
00:05:31.560 --> 00:05:34.930
so it's now 2022 or 2027
00:05:34.930 --> 00:05:37.990
and so there is a universal
quantum computer.
00:05:37.990 --> 00:05:42.220
The effect this has on the Internet crypto
00:05:42.220 --> 00:05:45.320
is that RSA, which is still the majority
00:05:45.320 --> 00:05:46.650
of all the connections today,
00:05:46.650 --> 00:05:49.760
RSA is broken. RSA is dead.
00:05:49.760 --> 00:05:51.820
Discrete logs in finite fields.
00:05:51.820 --> 00:05:53.250
You might have thought a lot about it
00:05:53.250 --> 00:05:55.000
earlier this year about Logjam.
00:05:55.000 --> 00:05:57.740
But Logjam just breaks the very small one.
00:05:57.740 --> 00:06:00.210
This is breaking any big one.
00:06:00.210 --> 00:06:03.250
So, discrete logs in finite fields
is totally dead as well.
00:06:03.250 --> 00:06:05.810
Elliptic curves, that I already mentioned,
ECC is dead.
00:06:05.810 --> 00:06:11.030
So this breaks all public-key crypto
on the Internet.
00:06:11.030 --> 00:06:13.460
There's another algorithm due to Grover,
00:06:13.460 --> 00:06:16.190
which is somewhat better under control,
00:06:16.190 --> 00:06:18.360
somewhat less scary for crypto,
00:06:18.360 --> 00:06:19.820
but it still has quite an effect,
00:06:19.820 --> 00:06:22.250
so if you believe in the security of AES
00:06:22.250 --> 00:06:26.010
and go like, well, AES-128 seems just fine,
00:06:26.010 --> 00:06:27.200
has been not getting any
00:06:27.200 --> 00:06:30.300
big progress in cryptanalysis,
00:06:30.300 --> 00:06:33.850
but it halves the security,
so AES 128-bit keys
00:06:33.850 --> 00:06:36.800
are only 64-bit secure.
00:06:36.800 --> 00:06:40.460
However, you can go to 256 bits.
00:06:40.460 --> 00:06:43.470
djb: Okay, so, the AES situation:
not so bad,
00:06:43.470 --> 00:06:45.530
but all this public key stuff is broken.
00:06:45.530 --> 00:06:46.470
So what do we do?
00:06:46.470 --> 00:06:48.370
Well, you could bury
your head in the sand,
00:06:48.370 --> 00:06:50.870
you could hope that quantum computers
don't come along,
00:06:50.870 --> 00:06:55.800
you could deploy
a physically secure crypto.
00:06:55.800 --> 00:06:59.100
You could take a locked briefcase
and chain it to your wrist,
00:06:59.100 --> 00:07:01.090
or you could do quantum key distribution.
00:07:01.090 --> 00:07:04.000
Now these things, obviously,
are very very expensive.
00:07:04.000 --> 00:07:07.610
This is crypto, information protection
for rich people.
00:07:07.610 --> 00:07:11.980
Or, quantum key distribution is crypto
for even richer people.
00:07:11.980 --> 00:07:15.370
You, obviously, aren't going to be able
to democratically give this
00:07:15.370 --> 00:07:16.840
to everybody who has a laptop.
00:07:16.840 --> 00:07:19.210
But, well, okay, imagine that
you have enough money,
00:07:19.210 --> 00:07:20.490
that you don't mind this.
00:07:20.490 --> 00:07:23.830
There's a bigger problem
with physical cryptography,
00:07:23.830 --> 00:07:25.290
which is the security.
00:07:25.290 --> 00:07:26.950
Now these things are always advertised
00:07:26.950 --> 00:07:30.100
as provably secure, guaranteed secure.
00:07:30.100 --> 00:07:31.760
Nobody can get into this briefcase!
00:07:31.760 --> 00:07:34.300
Nobody can get into this
quantum key distribution system!
00:07:34.300 --> 00:07:36.340
Assuming, of course, blah blah blah.
00:07:36.340 --> 00:07:37.550
And then you look at the assumptions
00:07:37.550 --> 00:07:38.410
and you start saying
00:07:38.410 --> 00:07:40.570
"Wait a minute, is that actually true?"
00:07:40.570 --> 00:07:43.440
And then it turns out that when people try
attacking these systems,
00:07:43.440 --> 00:07:44.770
the assumptions are not true.
00:07:44.770 --> 00:07:47.520
And the systems get broken
again and again and again
00:07:47.520 --> 00:07:50.380
for a very reasonable attack cost.
00:07:50.380 --> 00:07:54.270
Okay. Even if you have a system
where you think it's secure,
00:07:54.270 --> 00:07:55.770
which nobody's managed to build yet,
00:07:55.770 --> 00:07:59.080
even if you had that, the design of
this physical security system
00:07:59.080 --> 00:08:01.590
is incredibly difficult to audit.
00:08:01.590 --> 00:08:03.700
It's something where, if somebody wants
to slip in a backdoor,
00:08:03.700 --> 00:08:05.020
it's really easy.
00:08:05.020 --> 00:08:06.260
But there's an even worse problem
00:08:06.260 --> 00:08:07.860
with physical cryptography,
00:08:07.860 --> 00:08:10.480
which is that it doesn't
do very much crypto.
00:08:10.480 --> 00:08:14.860
Typically these systems do about
the same thing that AES does.
00:08:14.860 --> 00:08:17.000
You start with a shared secret,
00:08:17.000 --> 00:08:18.310
and then from that shared secret
00:08:18.310 --> 00:08:20.560
you can authenticate more secrets
00:08:20.560 --> 00:08:24.590
that you transmit through this
physically secure communication mechanism.
00:08:24.590 --> 00:08:26.050
For instance, quantum key distribution
00:08:26.050 --> 00:08:28.520
starts with some way,
some pre-existing way
00:08:28.520 --> 00:08:30.190
of authenticating.
00:08:30.190 --> 00:08:33.070
But that's just like AES starts with
a, a secret key
00:08:33.070 --> 00:08:34.450
which is then used to generate
00:08:34.450 --> 00:08:36.529
more and more secret data.
00:08:36.529 --> 00:08:38.330
And quantum key distribution says
00:08:38.330 --> 00:08:40.610
well, it's provably secure under
certain assumptions,
00:08:40.610 --> 00:08:42.770
instead of AES which, well,
00:08:42.770 --> 00:08:44.860
we just heard AES may be a little affected
00:08:44.860 --> 00:08:46.260
by quantum computers, but
00:08:46.260 --> 00:08:48.160
AES-256 is not broken.
00:08:48.160 --> 00:08:50.030
Nobody has any idea how to break it.
00:08:50.030 --> 00:08:52.200
So this physical cryptography
00:08:52.200 --> 00:08:54.570
isn't actually serving
the needs that we want.
00:08:54.570 --> 00:08:58.470
Imagine trying to distribute
operating system updates
00:08:58.470 --> 00:09:00.550
through locked briefcases.
00:09:00.550 --> 00:09:01.810
It's just not going to happen.
00:09:01.810 --> 00:09:04.330
Microsoft sending out billions
of locked briefcases
00:09:04.330 --> 00:09:05.800
to all of its customers.
00:09:05.800 --> 00:09:07.020
If you think that's realistic,
00:09:07.020 --> 00:09:11.150
or if you think that,
just, lasers are cool,
00:09:11.150 --> 00:09:13.450
then there's a talk about quantum crypto
00:09:13.450 --> 00:09:15.340
tomorrow, I believe.
00:09:15.340 --> 00:09:20.010
Back in the real world, we obviously
need to do something better with crypto.
00:09:20.010 --> 00:09:22.770
Lange: Alright, so,
let me take, momentarily,
00:09:22.770 --> 00:09:24.770
a slightly more optimistic perspective.
00:09:24.770 --> 00:09:26.370
Is there any hope? Yes.
00:09:26.370 --> 00:09:29.180
So, the title of this talk, PQCHacks,
00:09:29.180 --> 00:09:31.310
comes from post-quantum crypto,
00:09:31.310 --> 00:09:32.860
and that's the term Dan coined
00:09:32.860 --> 00:09:34.510
back in 2003
00:09:34.510 --> 00:09:36.290
for crypto that remains secure
00:09:36.290 --> 00:09:38.840
even if the adversary has
a quantum computer.
00:09:38.840 --> 00:09:42.500
So you, the normal people,
me, him, the normal people,
00:09:42.500 --> 00:09:44.290
the Internet, all the connections,
00:09:44.290 --> 00:09:46.740
we have normal computers.
00:09:46.740 --> 00:09:49.080
The adversary has a quantum computer.
00:09:49.080 --> 00:09:50.700
We, today, encrypt something.
00:09:50.700 --> 00:09:51.970
Adversary has all the time in the world
00:09:51.970 --> 00:09:53.450
to build the quantum computer,
00:09:53.450 --> 00:09:56.390
break us now or break us in the future.
00:09:56.390 --> 00:09:57.370
And so this took off,
00:09:57.370 --> 00:09:58.550
and there's been the first workshop
00:09:58.550 --> 00:10:02.370
on post-quantum crypto,
called PQCrypto2006
00:10:02.370 --> 00:10:03.770
and then there's been
a series of workshops
00:10:03.770 --> 00:10:04.850
you can see here.
00:10:04.850 --> 00:10:07.270
These are the attendees
of the last edition
00:10:07.270 --> 00:10:09.580
which was in Waterloo.
It's more than a hundred people,
00:10:09.580 --> 00:10:11.390
going like, yes,
this is an important topic,
00:10:11.390 --> 00:10:13.490
let's do some research on it.
00:10:13.490 --> 00:10:15.740
So something is happening.
00:10:15.740 --> 00:10:17.500
If you're curious what's happening,
00:10:17.500 --> 00:10:20.620
next there's a workshop in Japan
in February
00:10:20.620 --> 00:10:23.420
and then in the Netherlands
in 2017,
00:10:23.420 --> 00:10:26.630
and we also got a project through
from the EU
00:10:26.630 --> 00:10:28.810
to support research on post-quantum.
00:10:28.810 --> 00:10:30.320
So something is happening.
00:10:30.320 --> 00:10:34.260
Actually, um, did I forget somebody?
Yes.
00:10:34.260 --> 00:10:38.280
Um, the NSA is also saying,
let's do something.
00:10:38.280 --> 00:10:44.400
So, on August 11 the NSA posted
on their Suite B... page
00:10:44.400 --> 00:10:47.540
saying, "The Information Assurance
Director (so, IAD)
00:10:47.540 --> 00:10:51.640
recognizes that there will be a move, in
the not distant future, to a
00:10:51.640 --> 00:10:53.480
quantum resistant algorithm suite."
00:10:53.480 --> 00:10:56.180
Oh my god! Somebody is doing something!
00:10:56.180 --> 00:10:58.210
The public has realised
we have to do something!
00:10:58.210 --> 00:11:00.510
Quick, quick,
let's put out a press release!
00:11:00.510 --> 00:11:02.590
Um.
00:11:02.590 --> 00:11:05.560
Looks like they kind of realised
it was embarrassing.
00:11:05.560 --> 00:11:09.690
So, eight days later they pushed
a new release, saying
00:11:09.690 --> 00:11:15.210
"IAD will initiate a transition to quantum
resistant algorithms in the not distant future."
00:11:15.210 --> 00:11:19.910
So, NSA will lead us to a bright and
glorious future.
00:11:19.910 --> 00:11:22.760
djb: America, fuck yeah.
00:11:22.760 --> 00:11:30.790
laughter, applause
00:11:30.790 --> 00:11:34.510
Lange: But if you thought that,
so far, this was bad,
00:11:34.510 --> 00:11:38.340
it actually takes a lot of time
to build crypto.
00:11:38.340 --> 00:11:41.810
With let's say, NSA
all ask the researchers
00:11:41.810 --> 00:11:44.000
If you have some idea of
what could be secure
00:11:44.000 --> 00:11:45.510
against a quantum computer,
00:11:45.510 --> 00:11:47.120
say AES-256,
00:11:47.120 --> 00:11:48.590
the reason that you have confidence in it
00:11:48.590 --> 00:11:51.250
is we had more than ten years of people
00:11:51.250 --> 00:11:53.000
trying to break it,
00:11:53.000 --> 00:11:54.570
trying all kinds of approaches
00:11:54.570 --> 00:11:55.870
and not getting anywhere.
00:11:55.870 --> 00:12:00.350
It takes a lot of time to explore
the space of cryptosystems.
00:12:00.350 --> 00:12:01.540
Once you have figured out
00:12:01.540 --> 00:12:02.880
what could be actually doable,
00:12:02.880 --> 00:12:05.230
you want to figure
what the best attacks are,
00:12:05.230 --> 00:12:06.940
you want to focus on the security system,
00:12:06.940 --> 00:12:09.430
you want to figure out
how to implement them,
00:12:09.430 --> 00:12:10.380
how to implement them securely,
00:12:10.380 --> 00:12:13.570
that is a whole lot of work
that needs to be done
00:12:13.570 --> 00:12:15.860
before you can say, well,
this is actually practical.
00:12:15.860 --> 00:12:18.060
We can actually use this.
00:12:18.060 --> 00:12:22.680
Or sometimes, this is as practical
as we can get it.
00:12:22.680 --> 00:12:27.210
And then, you have this tiny little
crypto primitive,
00:12:27.210 --> 00:12:28.410
and then you have to build the hooks
00:12:28.410 --> 00:12:31.200
and connections to get it into TLS.
00:12:31.200 --> 00:12:32.670
Then we said at the beginning
00:12:32.670 --> 00:12:33.910
that maybe you believe
00:12:33.910 --> 00:12:36.670
that the cute little crypto cores
are all secure
00:12:36.670 --> 00:12:37.600
and it's just the connections
00:12:37.600 --> 00:12:39.500
with the AES, sorry, with the TLS
00:12:39.500 --> 00:12:42.029
in other world that is the problem.
00:12:42.029 --> 00:12:44.620
That still needs to be done
for post-quantum as well.
00:12:44.620 --> 00:12:46.500
And, the side-channel attacks,
00:12:46.500 --> 00:12:48.260
there's, uh, as an example,
00:12:48.260 --> 00:12:52.370
ECC was introduced back in 85,
00:12:52.370 --> 00:12:54.100
and now 30 years later,
00:12:54.100 --> 00:12:57.460
we're seeing that ECC is actually
getting deployed on the Internet,
00:12:57.460 --> 00:13:02.340
that now the IETF, having called
for having elliptic curve crypto,
00:13:02.340 --> 00:13:05.560
because people start saying, yes,
we would like to use this.
00:13:05.560 --> 00:13:08.440
So we cannot wait until
there's a quantum computer
00:13:08.440 --> 00:13:10.670
in order to start research on it.
00:13:10.670 --> 00:13:14.770
If you remember what 85 looked like
00:13:14.770 --> 00:13:18.770
That's a while ago.
00:13:18.770 --> 00:13:21.970
Now, if that sounded bad,
00:13:21.970 --> 00:13:23.170
it's actually worse.
00:13:23.170 --> 00:13:26.400
It's not just that, in 15 years from now,
00:13:26.400 --> 00:13:29.259
whatever you send then will be broken.
00:13:29.259 --> 00:13:33.420
There's some indication that some entities
00:13:33.420 --> 00:13:40.690
might be recording your traffic.
00:13:40.690 --> 00:13:42.700
We've given a talk like this in 2012
00:13:42.700 --> 00:13:44.220
which was "Crypto for the Paranoid",
00:13:44.220 --> 00:13:45.400
everybody thought it was, like,
00:13:45.400 --> 00:13:46.960
pfft, you're crazy,
00:13:46.960 --> 00:13:48.720
now it goes like
"well, there might be an entity"
00:13:48.720 --> 00:13:52.960
and everybody goes like, yeah, hmm, yeah.
00:13:52.960 --> 00:13:54.560
So, let's assume that this entity
00:13:54.560 --> 00:13:57.020
has the records of all the connections,
00:13:57.020 --> 00:14:01.220
and, that in ten years, you're going
to be an interesting person.
00:14:01.220 --> 00:14:04.540
Maybe you're a politician,
maybe you've become rich,
00:14:04.540 --> 00:14:07.880
maybe you associate with the wrong people,
or so they think,
00:14:07.880 --> 00:14:12.630
and so somehow they go back to
the 27th of December 2015,
00:14:12.630 --> 00:14:16.000
and figure out what you
were emailing during the talks,
00:14:16.000 --> 00:14:18.279
because they have all the connections here
00:14:18.279 --> 00:14:20.410
so they can go back in time
00:14:20.410 --> 00:14:26.050
just by the metadata,
and of course the real data.
00:14:26.050 --> 00:14:28.630
From the metadata, they can decrypt it,
00:14:28.630 --> 00:14:31.670
because this metadata is using RSA or ECC
00:14:31.670 --> 00:14:33.090
which are broken.
00:14:33.090 --> 00:14:34.550
And then they get the same key
00:14:34.550 --> 00:14:38.180
than you're currently using with your
other side to communicate.
00:14:38.180 --> 00:14:42.920
And so they can go and decrypt this.
00:14:42.920 --> 00:14:45.529
So it's not only that we can't wait for
quantum computers to come,
00:14:45.529 --> 00:14:51.320
we might already be too late.
00:14:51.320 --> 00:14:53.359
Well, on the next slide,
00:14:53.359 --> 00:14:56.190
here's a bunch of people who are getting
together in this EU project,
00:14:56.190 --> 00:14:59.720
and we have come up with
what we're currently thinking
00:14:59.720 --> 00:15:02.290
are good recommendations.
00:15:02.290 --> 00:15:04.080
We think it's necessary for people
00:15:04.080 --> 00:15:07.190
who really care about the security
of their connections,
00:15:07.190 --> 00:15:08.480
and when I say people I include myself,
00:15:08.480 --> 00:15:10.740
I care about the security of
my connections,
00:15:10.740 --> 00:15:12.330
we would like to have something
00:15:12.330 --> 00:15:15.050
that we believe is secure
for the next hundred years.
00:15:15.050 --> 00:15:17.310
And so we put out
a list of recommendations.
00:15:17.310 --> 00:15:19.910
So, for symmetric, it's relatively easy.
00:15:19.910 --> 00:15:22.500
You want something which is at least
a 256-bit key
00:15:22.500 --> 00:15:25.110
and is sufficiently well understood
00:15:25.110 --> 00:15:29.129
so there we have Salsa20,
and we have AES-256.
00:15:29.129 --> 00:15:32.990
Then, for authentication in symmetric,
00:15:32.990 --> 00:15:35.430
there, we don't actually have any decrease
00:15:35.430 --> 00:15:36.750
from a quantum computer, because
00:15:36.750 --> 00:15:38.899
these are already
information-theoretically secure.
00:15:38.899 --> 00:15:40.899
So these are the nice part.
00:15:40.899 --> 00:15:44.220
These two talk items is where we go like
00:15:44.220 --> 00:15:47.690
"Pff. We might be okay on those."
00:15:47.690 --> 00:15:49.880
We can do better,
we can have nice research
00:15:49.880 --> 00:15:51.740
and get something which is even
better protected,
00:15:51.740 --> 00:15:54.010
even faster under the new scenario,
00:15:54.010 --> 00:15:55.740
but it's not so dire.
00:15:55.740 --> 00:15:59.240
The bottom two, these are
the public key systems.
00:15:59.240 --> 00:16:03.399
That's public key encryption
and public key signatures.
00:16:03.399 --> 00:16:05.220
That's what we're going to
focus on in this talk.
00:16:05.220 --> 00:16:07.750
So, for public key encryption,
we're recommending
00:16:07.750 --> 00:16:10.620
the McEliece cryptosystem
with Goppa codes
00:16:10.620 --> 00:16:13.250
for a certain parameter size,
00:16:13.250 --> 00:16:15.240
and then for signatures,
00:16:15.240 --> 00:16:17.959
the recommendation is to use hash-based.
00:16:17.959 --> 00:16:19.170
djb: Okay, so...
00:16:19.170 --> 00:16:23.240
Let me dive into
the hash-based part of this.
00:16:23.240 --> 00:16:26.220
This is something which goes back
even further than the 80s.
00:16:26.220 --> 00:16:28.720
It goes back to the 1970s. Lamport.
00:16:28.720 --> 00:16:32.810
So here's a way to use hashes
to do one-time signatures.
00:16:32.810 --> 00:16:34.300
Which are, we'll see in a few minutes,
00:16:34.300 --> 00:16:35.700
signatures that you can use
00:16:35.700 --> 00:16:38.460
to sign one message under a given key.
00:16:38.460 --> 00:16:40.660
And then, well, that's a little bit
inconvenient
00:16:40.660 --> 00:16:41.910
that you can't sign more messages
00:16:41.910 --> 00:16:43.470
so then Merkle came along
00:16:43.470 --> 00:16:45.100
and said, you can sign more messages
00:16:45.100 --> 00:16:46.339
by modifying the system,
00:16:46.339 --> 00:16:47.730
and we'll also take a look at that.
00:16:47.730 --> 00:16:50.890
The only thing you need
for these public-key signature systems
00:16:50.890 --> 00:16:52.130
is a good hash function.
00:16:52.130 --> 00:16:54.690
And, okay, that's something where
historically,
00:16:54.690 --> 00:16:57.740
some hash functions designed in like, 1991
00:16:57.740 --> 00:16:58.580
had trouble.
00:16:58.580 --> 00:17:00.920
But, now, we have some good hash functions
00:17:00.920 --> 00:17:03.660
so, for instance, SHA-3 has
some great hash functions,
00:17:03.660 --> 00:17:05.790
even SHA-2, there's no sign of trouble,
00:17:05.790 --> 00:17:07.400
of those things being broken.
00:17:07.400 --> 00:17:10.119
And then after these original systems
from Lamport and Merkle,
00:17:10.119 --> 00:17:11.859
there's lots and lots of improvements,
00:17:11.859 --> 00:17:14.020
but all of these hash-based systems,
00:17:14.020 --> 00:17:16.670
it's really easy to
understand the security.
00:17:16.670 --> 00:17:18.329
It's something where the basic idea
00:17:18.329 --> 00:17:19.589
is really, really simple,
00:17:19.589 --> 00:17:21.280
and the security analysis also ends up
00:17:21.280 --> 00:17:22.869
being very straightforward.
00:17:22.869 --> 00:17:24.679
You have to be careful about some things,
00:17:24.679 --> 00:17:26.589
but, when you're careful about those,
00:17:26.589 --> 00:17:28.790
and there's nothing subtle
about it, nothing tricky,
00:17:28.790 --> 00:17:32.110
then we understand exactly
what security we get from these.
00:17:32.110 --> 00:17:35.130
So let's dive into a signature scheme
00:17:35.130 --> 00:17:37.820
that can only sign empty messages.
00:17:37.820 --> 00:17:40.690
Now, this sounds kind of, like,
wait a minute,
00:17:40.690 --> 00:17:42.760
what do you mean,
"can only sign empty messages?"
00:17:42.760 --> 00:17:44.600
There's only one empty string,
00:17:44.600 --> 00:17:46.290
and that's the only thing you can sign.
00:17:46.290 --> 00:17:49.550
But imagine that you want
to have a panic button,
00:17:49.550 --> 00:17:51.000
like, your revocation key,
00:17:51.000 --> 00:17:52.000
you want to be able to say,
00:17:52.000 --> 00:17:56.290
"Here's a message that says,
my house, my computer's been compromised,
00:17:56.290 --> 00:17:58.290
don't trust anything from this anymore".
00:17:58.290 --> 00:18:00.750
It's this one message
that you want to sign,
00:18:00.750 --> 00:18:01.500
under a certain key,
00:18:01.500 --> 00:18:03.750
and if anybody has that public key,
00:18:03.750 --> 00:18:06.800
then they should be able to verify
that you sent that message,
00:18:06.800 --> 00:18:08.350
and nobody should be able to forge that,
00:18:08.350 --> 00:18:10.000
because it's really bad
if somebody can forge
00:18:10.000 --> 00:18:10.880
your panic message.
00:18:10.880 --> 00:18:12.960
So, being able to sign just one message
00:18:12.960 --> 00:18:15.550
is not actually such a useless thing,
00:18:15.550 --> 00:18:16.790
and we'll also see that it builds up
00:18:16.790 --> 00:18:19.550
to the rest of hash-based crypto.
00:18:19.550 --> 00:18:23.040
Okay. Let's look at
some Python stuff here,
00:18:23.040 --> 00:18:25.650
simple SHA-3 you can get online
00:18:25.650 --> 00:18:29.580
under Ubuntu or Debian
do install python-pip and python-dev
00:18:29.580 --> 00:18:31.360
because it's a C library actually,
00:18:31.360 --> 00:18:33.840
and then, pip install simplesha3,
00:18:33.840 --> 00:18:36.210
that will give you SHA3-256,
00:18:36.210 --> 00:18:38.000
and then to generate a keypair
00:18:38.000 --> 00:18:41.140
in this empty-message signature system,
00:18:41.140 --> 00:18:43.850
all you do is you make 32 bytes
of random data
00:18:43.850 --> 00:18:45.070
and just hash it again,
00:18:45.070 --> 00:18:49.740
just in in case... urandom is not
too well-reviewed...
00:18:49.740 --> 00:18:51.770
I mean, we should trust urandom,
00:18:51.770 --> 00:18:54.090
but it's really cheap
to put an extra hash on it.
00:18:54.090 --> 00:18:57.140
So that's your secret key,
it's a 32-byte hash.
00:18:57.140 --> 00:18:58.530
And then the public key is,
00:18:58.530 --> 00:18:59.890
hash that secret again.
00:18:59.890 --> 00:19:03.040
So the public key is simply
a hash of the secret key.
00:19:03.040 --> 00:19:05.120
And then return the public key
and the secret key,
00:19:05.120 --> 00:19:06.640
of course the public key
will get published,
00:19:06.640 --> 00:19:08.860
and the secret key you keep for yourself.
00:19:08.860 --> 00:19:11.370
As an example of doing this, well, um,
00:19:11.370 --> 00:19:12.600
you just get random-looking data
00:19:12.600 --> 00:19:15.000
coming out from your public key
at the bottom
00:19:15.000 --> 00:19:17.910
your secret key right at the bottom
and public key above that.
00:19:17.910 --> 00:19:19.870
And you can check that one
of them's a hash of the other
00:19:19.870 --> 00:19:21.290
if you know the secret key,
00:19:21.290 --> 00:19:22.730
you can hash it to get the public.
00:19:22.730 --> 00:19:25.000
Okay, now, how do you sign a message?
00:19:25.000 --> 00:19:27.380
Well, this maybe sort of spelled out
00:19:27.380 --> 00:19:29.230
in more steps than it has to be.
00:19:29.230 --> 00:19:32.260
The API here, this is, I would say,
00:19:32.260 --> 00:19:33.910
getting to be a pretty popular API
00:19:33.910 --> 00:19:36.790
for signatures and for verification,
00:19:36.790 --> 00:19:40.010
where you include the signature
and the message together,
00:19:40.010 --> 00:19:41.230
as a signed message.
00:19:41.230 --> 00:19:44.940
And to emphasise that, here's a returned
signed message from the sign function.
00:19:44.940 --> 00:19:48.730
Now, the signed message
will be later on verified,
00:19:48.730 --> 00:19:50.450
and you get a message out of it,
00:19:50.450 --> 00:19:52.080
where the only possible message
00:19:52.080 --> 00:19:53.670
to be signed is the empty string,
00:19:53.670 --> 00:19:55.610
and you can see that the top there
00:19:55.610 --> 00:19:57.540
of the signature is checking
00:19:57.540 --> 00:19:59.530
if the message is anything
other than the empty string
00:19:59.530 --> 00:20:01.750
then you're not allowed to sign it.
00:20:01.750 --> 00:20:04.740
Um, if you have the empty string coming in
00:20:04.740 --> 00:20:09.600
then the signature is simply
your secret key.
00:20:09.600 --> 00:20:11.780
So you reveal your secret key
00:20:11.780 --> 00:20:13.610
and the whole idea of hash-based crypto
00:20:13.610 --> 00:20:16.160
is that somebody can publicly check
00:20:16.160 --> 00:20:18.650
the hashes of something that you reveal
00:20:18.650 --> 00:20:22.220
to sign, in this case, the empty message.
00:20:22.220 --> 00:20:23.860
And we'll see later how
you can use the same idea
00:20:23.860 --> 00:20:25.390
to sign lots more.
00:20:25.390 --> 00:20:27.030
And then, okay, verification,
00:20:27.030 --> 00:20:29.270
you simply checked that signedmessage,
00:20:29.270 --> 00:20:31.340
which is supposed to be the secret key,
00:20:31.340 --> 00:20:32.480
check its hash
00:20:32.480 --> 00:20:34.480
and see if that matches the public key.
00:20:34.480 --> 00:20:36.120
What would somebody have to do
to attack this?
00:20:36.120 --> 00:20:37.360
He would have to,
00:20:37.360 --> 00:20:39.549
if you haven't actually signed a message,
00:20:39.549 --> 00:20:40.540
the one message,
00:20:40.540 --> 00:20:41.710
then he would have to figure out
00:20:41.710 --> 00:20:45.010
some string that, when you hash it,
00:20:45.010 --> 00:20:46.510
gives this public key.
00:20:46.510 --> 00:20:48.460
And, well, that public key,
00:20:48.460 --> 00:20:50.260
this is a preimage problem,
00:20:50.260 --> 00:20:51.760
inverting the hash function.
00:20:51.760 --> 00:20:53.580
The hash is supposed to be one-way,
00:20:53.580 --> 00:20:55.460
if the input were low-entropy,
00:20:55.460 --> 00:20:56.860
then this would be doable,
00:20:56.860 --> 00:20:59.140
but the input was a 32-byte random string,
00:20:59.140 --> 00:21:00.760
so nobody will be able to guess that,
00:21:00.760 --> 00:21:03.730
or find any other string that passes this.
00:21:03.730 --> 00:21:05.410
And then you return the message
00:21:05.410 --> 00:21:06.660
and you can try this out
00:21:06.660 --> 00:21:08.240
and see that it works.
00:21:08.240 --> 00:21:09.610
Alright, let's move on.
00:21:09.610 --> 00:21:11.470
We've managed to sign empty messages.
00:21:11.470 --> 00:21:13.790
How about signing 0 or 1?
00:21:13.790 --> 00:21:15.929
So now we'll make a signature system
00:21:15.929 --> 00:21:18.270
where your key can sign 0
00:21:18.270 --> 00:21:19.730
and your key can sign 1.
00:21:19.730 --> 00:21:22.400
And, well, this is going
to be kind of stupid,
00:21:22.400 --> 00:21:24.850
what you do is, you make two keys,
00:21:24.850 --> 00:21:26.480
one of them is signing 0,
00:21:26.480 --> 00:21:28.370
and the other one is signing 1.
00:21:28.370 --> 00:21:31.600
You can see how complicated
this hash-based signature stuff is,
00:21:31.600 --> 00:21:34.460
it's, okay, you put two keys together,
00:21:34.460 --> 00:21:36.450
you make one key that will sign 0,
00:21:36.450 --> 00:21:37.470
one key that will sign 1,
00:21:37.470 --> 00:21:38.610
concatenate the public keys,
00:21:38.610 --> 00:21:40.130
concatenate the secret keys,
00:21:40.130 --> 00:21:42.520
the p0+p1, s0+s1,
00:21:42.520 --> 00:21:43.880
and then if you want to sign, then,
00:21:43.880 --> 00:21:45.860
well, if you're signing 0,
00:21:45.860 --> 00:21:48.020
now the messages being signed
are integers now
00:21:48.020 --> 00:21:49.490
instead the empty string,
00:21:49.490 --> 00:21:50.670
if you want to sign 0,
00:21:50.670 --> 00:21:51.940
then the signed message will be
00:21:51.940 --> 00:21:55.830
the string "0", followed by the 32 bytes,
00:21:55.830 --> 00:21:59.059
well, this is again more complicated
than it has to be,
00:21:59.059 --> 00:22:01.400
but think of this as
signing the empty message
00:22:01.400 --> 00:22:03.460
with the empty signature system,
00:22:03.460 --> 00:22:06.540
which is just copying the 32 bytes
of the secret key.
00:22:06.540 --> 00:22:08.410
And then if you want to sign message 1,
00:22:08.410 --> 00:22:12.240
then you do that with the other 32 bytes
of the secret key.
00:22:12.240 --> 00:22:13.770
And then, to verify it,
00:22:13.770 --> 00:22:16.100
well, just whether the
signed message is 0 or 1,
00:22:16.100 --> 00:22:18.150
just do the obvious thing.
00:22:18.150 --> 00:22:19.950
Maybe I should emphasise this code
00:22:19.950 --> 00:22:22.440
was written just for this talk,
00:22:22.440 --> 00:22:24.179
it has not been reviewed,
00:22:24.179 --> 00:22:25.860
and you should audit everything.
00:22:25.860 --> 00:22:26.809
You know, you might feel like
00:22:26.809 --> 00:22:28.990
six lines of code,
you can't possibly screw it up,
00:22:28.990 --> 00:22:32.530
but, don't ever
use code like that in crypto.
00:22:32.530 --> 00:22:34.760
So, this is just meant for
you to understand
00:22:34.760 --> 00:22:35.700
what this is supposed to be doing,
00:22:35.700 --> 00:22:36.860
this has not passed review.
00:22:36.860 --> 00:22:39.640
But, I like to think it would pass review.
00:22:39.640 --> 00:22:41.650
Um, okay, if you try
00:22:41.650 --> 00:22:44.570
signing the 1 message, for example,
00:22:44.570 --> 00:22:47.549
and take the signed 1 message
and open that signed message,
00:22:47.549 --> 00:22:49.360
you do get the integer 1 back.
00:22:49.360 --> 00:22:50.470
And if you try forging it,
00:22:50.470 --> 00:22:51.600
you're again faced with this problem
00:22:51.600 --> 00:22:53.980
of coming up with some 32-byte string
00:22:53.980 --> 00:22:56.580
that hashes to a particular result.
00:22:56.580 --> 00:22:59.790
Alright, let's move on to 4-bit messages!
00:22:59.790 --> 00:23:02.440
So, I promise I won't do
every possible length.
00:23:02.440 --> 00:23:04.610
But, 4 bits, this will make
an important point
00:23:04.610 --> 00:23:06.600
that you don't see from 1 bit.
00:23:06.600 --> 00:23:08.720
Let's try to sign a 4-bit message
00:23:08.720 --> 00:23:11.150
by signing each of the four bits.
00:23:11.150 --> 00:23:13.960
This all scales up to signing 1000 bits
if you want.
00:23:13.960 --> 00:23:17.950
Um, so, okay, let's make
4 sign-bit keypairs
00:23:17.950 --> 00:23:21.179
where each of those was
two 32-byte hashes,
00:23:21.179 --> 00:23:25.590
I mean, each secret key is
two 32-byte random strings
00:23:25.590 --> 00:23:29.380
and each of the public keys is the hash
of those 32-byte random strings.
00:23:29.380 --> 00:23:31.970
Make 4 of those pairs
and concatenate them
00:23:31.970 --> 00:23:34.950
to make some new public keys
and secret keys.
00:23:34.950 --> 00:23:38.489
Alright, and now to sign a message, well,
you look at the message
00:23:38.489 --> 00:23:41.179
and check,
is it an integer between 0 and 15,
00:23:41.179 --> 00:23:42.580
and reject otherwise,
00:23:42.580 --> 00:23:44.960
and then sign each bit of the message.
00:23:44.960 --> 00:23:47.850
You can see m shifted right by 0, 1, 2, 3,
00:23:47.850 --> 00:23:49.750
extract the bottom bit of each of those,
00:23:49.750 --> 00:23:51.690
and then sign each of those bits,
00:23:51.690 --> 00:23:53.730
and then concatenate the signatures
00:23:53.730 --> 00:23:56.970
to get, well, signatures of the four bits
of the message.
00:23:56.970 --> 00:24:00.200
And then verification works the way
you expect
00:24:00.200 --> 00:24:02.750
and I'll just skip that.
00:24:02.750 --> 00:24:04.290
Alright, this has a problem.
00:24:04.290 --> 00:24:06.919
That if you use this signature system
00:24:06.919 --> 00:24:09.960
to sign two different messages,
00:24:09.960 --> 00:24:13.360
then you might actually allow forgeries.
00:24:13.360 --> 00:24:14.620
So let's look, for example,
00:24:14.620 --> 00:24:18.100
suppose you sign 11 and you sign 7.
00:24:18.100 --> 00:24:20.200
Now what is that signature of 11,
00:24:20.200 --> 00:24:22.799
11, uh-oh, I have to do 11 in binary now,
00:24:22.799 --> 00:24:27.260
so 11 sounds like 8+2+1.
00:24:27.260 --> 00:24:30.990
And you sign 7, which is 4+2+1.
00:24:30.990 --> 00:24:32.679
So what if you revealed now?
00:24:32.679 --> 00:24:35.510
You reveal the signature on that 8,
00:24:35.510 --> 00:24:38.090
so the 3rd bit you revealed
00:24:38.090 --> 00:24:41.330
a signature saying, "the 3rd bit is 1"
00:24:41.330 --> 00:24:43.390
as part of the signature of 11.
00:24:43.390 --> 00:24:45.350
But as part of the signature of 7,
00:24:45.350 --> 00:24:47.330
you revealed, you signed a message
00:24:47.330 --> 00:24:50.419
saying "the 3rd bit is 0".
00:24:50.419 --> 00:24:52.600
And now you can just mix and match
those messages,
00:24:52.600 --> 00:24:53.830
wherever the bits were different.
00:24:53.830 --> 00:24:56.120
So for instance if you take the top bit
from the 11
00:24:56.120 --> 00:24:58.970
and the bottom 3 bits from the 7
00:24:58.970 --> 00:25:00.830
then you end up signing 15.
00:25:00.830 --> 00:25:02.990
So this signature system,
00:25:02.990 --> 00:25:05.870
it's totally safe
if you're signing one message.
00:25:05.870 --> 00:25:07.200
But if you think about the data flow,
00:25:07.200 --> 00:25:09.510
what does it mean
to sign the individual bits
00:25:09.510 --> 00:25:11.270
of two different messages,
00:25:11.270 --> 00:25:12.669
then you can get in big trouble.
00:25:12.669 --> 00:25:15.809
So this is a one-time signature system.
00:25:15.809 --> 00:25:19.140
Alright. Here's how Lamport's
signature system
00:25:19.140 --> 00:25:21.110
works for one-time signatures
00:25:21.110 --> 00:25:22.919
of any length of message.
00:25:22.919 --> 00:25:26.559
First of all, you scale that 4 bits
up to 256 bits.
00:25:26.559 --> 00:25:28.600
And then, if you want to sign
whatever length of message,
00:25:28.600 --> 00:25:32.460
you just hash the message to 256 bits.
00:25:32.460 --> 00:25:34.690
And the code for it is very simple.
00:25:34.690 --> 00:25:36.299
This is not quite the state of the art
00:25:36.299 --> 00:25:37.540
for one-time signatures,
00:25:37.540 --> 00:25:38.630
there's fancier things you can do,
00:25:38.630 --> 00:25:41.160
you can sign with Winternitz signatures
00:25:41.160 --> 00:25:46.260
and get instead of something
like 256 or 512 hash values
00:25:46.260 --> 00:25:47.740
you can compress that down to like
00:25:47.740 --> 00:25:49.760
50 or even fewer hash values.
00:25:49.760 --> 00:25:52.410
There's all sorts of tricks to
trade space for time
00:25:52.410 --> 00:25:53.049
in these systems
00:25:53.049 --> 00:25:56.010
but it's totally feasible to deploy
Lamport signatures
00:25:56.010 --> 00:26:00.270
and, well, Winternitz makes it
even more practical.
00:26:00.270 --> 00:26:02.690
Alright. What about this
one-time restriction?
00:26:02.690 --> 00:26:04.110
So these last, the 4-bit,
00:26:04.110 --> 00:26:05.980
and the Lamport bigger message system,
00:26:05.980 --> 00:26:07.309
these are only usable for,
00:26:07.309 --> 00:26:08.790
you can only use your key
00:26:08.790 --> 00:26:10.620
to sign one message.
00:26:10.620 --> 00:26:13.030
And this was fixed by Merkle.
00:26:13.030 --> 00:26:14.690
What Merkle said was,
00:26:14.690 --> 00:26:18.980
you take 8 Lamport, for example 8,
it can be any number,
00:26:18.980 --> 00:26:20.299
here's how we'll make a public key
00:26:20.299 --> 00:26:22.510
that can sign 8 different messages.
00:26:22.510 --> 00:26:24.990
You make, well, 8 different Lamport keys
00:26:24.990 --> 00:26:26.620
and you concatenate them together
00:26:26.620 --> 00:26:28.299
and you use each one just once.
00:26:28.299 --> 00:26:31.410
But it's actually more space-efficient
than that sounds.
00:26:31.410 --> 00:26:33.130
So here's what you send along.
00:26:33.130 --> 00:26:38.780
You make 8 Ss there, those are the secret
Lamport keys,
00:26:38.780 --> 00:26:41.130
that are able to each sign one message,
00:26:41.130 --> 00:26:43.400
and then you have 8
corresponding public keys,
00:26:43.400 --> 00:26:45.490
P1 through P8,
00:26:45.490 --> 00:26:48.040
and then you hash together in a tree,
00:26:48.040 --> 00:26:52.049
you hash together P1 and P2,
and P3 and P4
00:26:52.049 --> 00:26:53.380
to form P9 and P10,
00:26:53.380 --> 00:26:55.059
and hash those together to get P13,
00:26:55.059 --> 00:26:58.510
and same over here to get
a final public key P15.
00:26:58.510 --> 00:27:01.330
So just one hash value, that's your whole
public key.
00:27:01.330 --> 00:27:03.679
And then you have to remember
lots of secrets,
00:27:03.679 --> 00:27:06.040
but, okay, nobody has to see
those secrets,
00:27:06.040 --> 00:27:08.150
you just keep them on your computer.
00:27:08.150 --> 00:27:09.270
And now what does it look like to,
00:27:09.270 --> 00:27:13.410
to hash, sorry, to sign one message?
00:27:13.410 --> 00:27:17.140
Well, here's what it looks like signing
the first message.
00:27:17.140 --> 00:27:18.760
That's when you use S1.
00:27:18.760 --> 00:27:21.059
Once you use S1, you cross it out,
00:27:21.059 --> 00:27:21.940
you never use it again,
00:27:21.940 --> 00:27:23.419
you kill the secret.
00:27:23.419 --> 00:27:25.910
You sign your message with S1,
00:27:25.910 --> 00:27:27.200
and somebody can verify,
00:27:27.200 --> 00:27:30.760
if they see the public key P1
for Lamport signatures.
00:27:30.760 --> 00:27:32.309
Or whatever one-time signature system
00:27:32.309 --> 00:27:33.709
you put at the top.
00:27:33.709 --> 00:27:36.870
But, well, your public key
in Merkle systems is P15.
00:27:36.870 --> 00:27:40.050
And how does somebody verify that
P1 and P15 are related?
00:27:40.050 --> 00:27:44.770
Well, you show them the P2 and the P10
and the P14
00:27:44.770 --> 00:27:47.049
that they need to hash together with P1
00:27:47.049 --> 00:27:49.990
to get your public key, P15.
00:27:49.990 --> 00:27:52.210
Alright, and that's as complicated
00:27:52.210 --> 00:27:53.809
as the Merkle signature system gets,
00:27:53.809 --> 00:27:55.880
if you want to be able to sign
a million messages,
00:27:55.880 --> 00:27:57.340
you have to have a million secrets,
00:27:57.340 --> 00:27:59.350
but, again, just put it on
your local hard drive,
00:27:59.350 --> 00:28:00.900
you're not worried about the space.
00:28:00.900 --> 00:28:03.580
It takes a few moments to generate the key,
00:28:03.580 --> 00:28:06.059
but that's also not a problem.
00:28:06.059 --> 00:28:07.620
Okay.
00:28:07.620 --> 00:28:09.160
Good things about hash-based signatures,
00:28:09.160 --> 00:28:10.490
and a few bad things.
00:28:10.490 --> 00:28:12.309
Good things: It's post-quantum secure,
00:28:12.309 --> 00:28:15.610
we totally understand what hash function
security looks like,
00:28:15.610 --> 00:28:19.080
after quantum computers
and before quantum computers,
00:28:19.080 --> 00:28:20.730
all you need is a good hash function,
00:28:20.730 --> 00:28:21.830
and there's lots of hash functions
00:28:21.830 --> 00:28:23.330
which have been thoroughly studied,
00:28:23.330 --> 00:28:25.110
so, we're confident they're secure,
00:28:25.110 --> 00:28:27.460
SHA-3 was the result of a long competition
00:28:27.460 --> 00:28:28.990
with lots of people bashing on it,
00:28:28.990 --> 00:28:30.850
and really has no problems.
00:28:30.850 --> 00:28:32.220
The public key is very small,
00:28:32.220 --> 00:28:34.419
just one hash value.
00:28:34.419 --> 00:28:37.360
The security, as I said,
is well-understood.
00:28:37.360 --> 00:28:39.840
All the computations are very fast,
00:28:39.840 --> 00:28:41.860
and you can already find
standard proposals
00:28:41.860 --> 00:28:42.900
for this system.
00:28:42.900 --> 00:28:45.679
This is going to be the first standardised
00:28:45.679 --> 00:28:50.470
and the first deployed
post-quantum public key system.
00:28:50.470 --> 00:28:54.000
On the other hand,
if you look at the signature size,
00:28:54.000 --> 00:28:55.380
it's kind of big,
00:28:55.380 --> 00:28:56.740
and then the more scary thing
00:28:56.740 --> 00:28:59.210
is the statefulness.
00:28:59.210 --> 00:29:01.030
That you can only use S1 once,
00:29:01.030 --> 00:29:02.850
and then you have to cross it out.
00:29:02.850 --> 00:29:05.039
You can only use S2 once, and you have to
cross it out.
00:29:05.039 --> 00:29:06.330
What if you clone your VM?
00:29:06.330 --> 00:29:08.220
What if you have a backup and restore?
00:29:08.220 --> 00:29:11.250
Then, you've forgotten that you've
used S2.
00:29:11.250 --> 00:29:12.179
And then you use it again,
00:29:12.179 --> 00:29:14.470
and then somebody can forge messages,
00:29:14.470 --> 00:29:17.010
just like I was saying before.
00:29:17.010 --> 00:29:18.760
Alright, so state is a problem,
00:29:18.760 --> 00:29:20.130
actually some of you I'm sure were
00:29:20.130 --> 00:29:22.289
in Rutkowska's talk earlier today
00:29:22.289 --> 00:29:24.520
you also heard that
state is harmful there.
00:29:24.520 --> 00:29:26.910
And the solution:
00:29:26.910 --> 00:29:29.969
Eliminate the state!
00:29:29.969 --> 00:29:36.360
applause
00:29:36.360 --> 00:29:38.360
I think I only have
about three minutes left
00:29:38.360 --> 00:29:41.210
for this, this section, well,
this slide,
00:29:41.210 --> 00:29:45.450
but, let me try to briefly say, the idea
for getting rid of the state
00:29:45.450 --> 00:29:47.929
is, you have, instead of signatures,
00:29:47.929 --> 00:29:49.860
you have certificate chains.
00:29:49.860 --> 00:29:53.110
So you have whole chain of CAs,
00:29:53.110 --> 00:29:55.730
like, as a signer, you build
a whole bunch of CAs,
00:29:55.730 --> 00:29:59.300
you build, say, 2^256
certificate authorities.
00:29:59.300 --> 00:30:00.990
Now, that's too much computation to do,
00:30:00.990 --> 00:30:03.010
but you do it on the fly,
as you need them.
00:30:03.010 --> 00:30:04.900
So you say, I'm going to sign
00:30:04.900 --> 00:30:08.450
using one of these bottom-level
certificate authorities,
00:30:08.450 --> 00:30:10.580
that will sign my actual message.
00:30:10.580 --> 00:30:13.200
And now, you don't have to know
anything about any of the others,
00:30:13.200 --> 00:30:16.809
you just pick one and use that to
sign your message.
00:30:16.809 --> 00:30:19.570
And then it has to be signed
by the parent CA,
00:30:19.570 --> 00:30:20.850
and that's signed by the next parent,
00:30:20.850 --> 00:30:22.870
and so on, up the tree, to the top level,
00:30:22.870 --> 00:30:24.460
only 256 levels.
00:30:24.460 --> 00:30:28.200
And then, okay, you have your
certificate chain,
00:30:28.200 --> 00:30:30.950
how do you manufacture these
certificate authorities?
00:30:30.950 --> 00:30:35.950
Well, a certificate authority is just
some bytes of code on disk,
00:30:35.950 --> 00:30:37.450
that's what real CAs are like,
00:30:37.450 --> 00:30:39.120
and you do the same thing signing,
00:30:39.120 --> 00:30:41.330
and, those bytes of code, you can,
00:30:41.330 --> 00:30:46.030
instead of storing the CA as a program
in a configuration file on disk,
00:30:46.030 --> 00:30:48.590
you just generate it on the fly
when you need it,
00:30:48.590 --> 00:30:52.370
by taking the position of the CA
within this huge tree
00:30:52.370 --> 00:30:56.210
and then hashing that together with
some long-term secret.
00:30:56.210 --> 00:30:59.419
That one long-term secret
is the only thing you remember.
00:30:59.419 --> 00:31:01.809
So you can manufacture CAs on demand
00:31:01.809 --> 00:31:03.100
in some huge tree
00:31:03.100 --> 00:31:05.570
and have them sign
certificates for each other
00:31:05.570 --> 00:31:08.020
only looking at a few CAs that you need
00:31:08.020 --> 00:31:11.000
for the particular signature
that you want.
00:31:11.000 --> 00:31:12.409
The reason for having this big tree
00:31:12.409 --> 00:31:14.030
is that then you're never going
00:31:14.030 --> 00:31:17.880
to randomly use the same CA
at the bottom twice.
00:31:17.880 --> 00:31:20.470
So the problem of having
one-time signatures
00:31:20.470 --> 00:31:21.690
is no longer a problem.
00:31:21.690 --> 00:31:24.690
Each CA will only sign one message.
00:31:24.690 --> 00:31:26.500
Okay, and this is something where
00:31:26.500 --> 00:31:30.309
the original proposal
from Goldreich in 87,
00:31:30.309 --> 00:31:32.440
if you use good one-time signatures,
00:31:32.440 --> 00:31:33.809
Winternitz and all that stuff,
00:31:33.809 --> 00:31:38.250
you get something like 0.6 megs
for a signature.
00:31:38.250 --> 00:31:40.760
Now that's a little bit inconvenient,
00:31:40.760 --> 00:31:43.130
for comparison, if you do an OS update,
00:31:43.130 --> 00:31:45.580
you look at the average
Debian packet size,
00:31:45.580 --> 00:31:47.700
then it's 1.2 megs.
00:31:47.700 --> 00:31:49.900
And then, there is some
number of signatures
00:31:49.900 --> 00:31:53.419
with each update, and some
of them are in packages,
00:31:53.419 --> 00:31:55.490
and well, it's not inconceivable
00:31:55.490 --> 00:31:57.460
to send 0.6 megs for each signature,
00:31:57.460 --> 00:31:58.799
but it's kind of big.
00:31:58.799 --> 00:32:00.940
And then if you look at, well,
00:32:00.940 --> 00:32:03.470
web pages, say the Alexa top
million web pages,
00:32:03.470 --> 00:32:06.860
that average is 1.8 megs.
00:32:06.860 --> 00:32:09.150
And again there's several
signatures on the web page,
00:32:09.150 --> 00:32:13.159
depending how many sites are providing
graphics for it and so on.
00:32:13.159 --> 00:32:14.860
So, 0.6 megs is maybe a problem.
00:32:14.860 --> 00:32:17.720
But, okay, we took a look at this and
00:32:17.720 --> 00:32:21.520
a bunch of people
made the signature a lot smaller,
00:32:21.520 --> 00:32:24.020
0.041 megabytes.
00:32:24.020 --> 00:32:27.059
You know how to make a 41-kilobyte
signature sound small:
00:32:27.059 --> 00:32:34.250
only 0.041 megabytes for a sphincs 2^128
post-quantum secure signature system.
00:32:34.250 --> 00:32:36.080
If you're interested in more about
what sphincs does,
00:32:36.080 --> 00:32:39.830
go to sphincs.cr.yp.to
00:32:39.830 --> 00:32:41.500
Lange: Alright, so.
00:32:41.500 --> 00:32:44.970
Now we have some idea of
how we can do signatures.
00:32:44.970 --> 00:32:46.819
And signature's just the thing
00:32:46.819 --> 00:32:48.760
that quantum crypto really
really can't do,
00:32:48.760 --> 00:32:51.549
I mean, also, locked briefcases,
00:32:51.549 --> 00:32:56.039
how do you trust that this is
actually your locked briefcase?
00:32:56.039 --> 00:32:58.940
But also, public key crypto is a problem.
00:32:58.940 --> 00:33:01.820
So, the one that we recommend
00:33:01.820 --> 00:33:03.340
is code-based cryptography,
00:33:03.340 --> 00:33:05.250
and code, in this context, is not like
00:33:05.250 --> 00:33:07.309
code as in writing a program
00:33:07.309 --> 00:33:10.220
but it comes from error-correcting codes.
00:33:10.220 --> 00:33:12.140
So when you think about,
say, your computer,
00:33:12.140 --> 00:33:13.960
you have RAM in there
00:33:13.960 --> 00:33:17.750
and this RAM might get cosmic radiation
00:33:17.750 --> 00:33:19.610
or just a bump somewhere,
00:33:19.610 --> 00:33:20.730
might forget something.
00:33:20.730 --> 00:33:22.280
Or, a more trivial example,
00:33:22.280 --> 00:33:25.090
if you order a book, or, nowadays,
00:33:25.090 --> 00:33:26.739
order any media,
00:33:26.739 --> 00:33:29.280
it has an ISBN number.
00:33:29.280 --> 00:33:32.950
This last digit is dependent on
the previous digits.
00:33:32.950 --> 00:33:35.080
So they can figure out whether any
of the digits before
00:33:35.080 --> 00:33:37.549
was mistransmitted
00:33:37.549 --> 00:33:39.360
then then go like, hmm,
00:33:39.360 --> 00:33:41.390
that number doesn't exist, try again.
00:33:41.390 --> 00:33:44.990
With your ECC RAM it's actually
a little more sophisticated.
00:33:44.990 --> 00:33:46.919
So you have your RAM sitting there,
00:33:46.919 --> 00:33:50.190
and it stores 64 bits.
00:33:50.190 --> 00:33:53.950
But it stores these 64 bits
with some redundancy.
00:33:53.950 --> 00:33:57.360
Internally, it has some extra check bits.
00:33:57.360 --> 00:34:00.600
It stores 8 extra bits
00:34:00.600 --> 00:34:02.080
and those 8 extra bits allow you
00:34:02.080 --> 00:34:05.850
to recover the 64
that you're interested in
00:34:05.850 --> 00:34:08.190
in case there was some error.
00:34:08.190 --> 00:34:09.339
Not in case of a massive error,
00:34:09.339 --> 00:34:12.619
not in case somebody
took a screwdriver and hit it,
00:34:12.619 --> 00:34:14.639
but if there was just one random bit flip,
00:34:14.639 --> 00:34:16.268
you can recover it.
00:34:16.268 --> 00:34:18.210
Also, if two bits flip,
00:34:18.210 --> 00:34:20.289
you can at least figure out
that there was something
00:34:20.289 --> 00:34:22.190
and raise a flag.
00:34:22.190 --> 00:34:24.079
So the common scenario in error correction
00:34:24.079 --> 00:34:30.319
is that we have a certain number, say, k
bits that we care about
00:34:30.319 --> 00:34:34.199
and then in order to be able
to recover those,
00:34:34.199 --> 00:34:35.199
to correct those,
00:34:35.199 --> 00:34:37.248
we add some redundancy.
00:34:37.248 --> 00:34:39.869
So we encapsulate, we encode those k bits
00:34:39.869 --> 00:34:41.569
into n bits.
00:34:41.569 --> 00:34:44.859
Now, we would like to have those n bits
00:34:44.859 --> 00:34:48.109
be not too much larger than k.
00:34:48.109 --> 00:34:50.029
We call those the parity check,
00:34:50.029 --> 00:34:52.239
so this is like from the old days
where you check
00:34:52.239 --> 00:34:55.599
"those two add up to zero,
zero zero zero...
00:34:55.599 --> 00:34:58.819
oops! there's one, aha, there must
have been one bit flip."
00:34:58.819 --> 00:35:03.630
So parity as in, it has to be
an even number at the end.
00:35:03.630 --> 00:35:04.960
If you're talking about more positions
00:35:04.960 --> 00:35:07.160
then it's obviously more
than just the parity
00:35:07.160 --> 00:35:10.479
but it's parity of some
more complicated equations.
00:35:10.479 --> 00:35:17.009
So, if no error occurred, if those 64 bits
in your ECC RAM are just fine,
00:35:17.009 --> 00:35:21.969
then all those extra n-k
checks will be okay.
00:35:21.969 --> 00:35:25.589
If there was an error,
then something will fail,
00:35:25.589 --> 00:35:26.309
raise a flag,
00:35:26.309 --> 00:35:29.180
1, 2, 3 of those will not be satisfied,
00:35:29.180 --> 00:35:32.170
and depending on this error pattern,
00:35:32.170 --> 00:35:36.619
you will be able to recover what
was going wrong in those bits.
00:35:36.619 --> 00:35:39.289
It might actually be that
it was your parity check bits.
00:35:39.289 --> 00:35:42.289
It might be that one of
those 8 extra bits flipped.
00:35:42.289 --> 00:35:45.729
In which case, your 64 bits were just fine
00:35:45.729 --> 00:35:49.649
but you don't know this when
you get the error message.
00:35:49.649 --> 00:35:51.759
And, if you have a good code,
00:35:51.759 --> 00:35:54.359
so the kind of code
that coding theorists study,
00:35:54.359 --> 00:35:55.339
then you would like to have
00:35:55.339 --> 00:35:59.890
your k pretty large, and the n
not too much larger.
00:35:59.890 --> 00:36:02.549
Because that's the amount of storage
00:36:02.549 --> 00:36:03.519
you actually have to afford
00:36:03.519 --> 00:36:07.339
for just getting this much data out of it.
00:36:07.339 --> 00:36:11.400
Now, we get some guarantees
when we design these,
00:36:11.400 --> 00:36:14.269
there's a guarantee of getting t errors,
00:36:14.269 --> 00:36:15.729
but for most of the codes that we know,
00:36:15.729 --> 00:36:17.489
the guarantees are actually worse
00:36:17.489 --> 00:36:19.029
than we get in practice,
00:36:19.029 --> 00:36:21.729
so if something guarantees you 100 errors,
00:36:21.729 --> 00:36:25.750
most of the time,
you can actually correct 203.
00:36:25.750 --> 00:36:27.249
Um, to get a little bit further
00:36:27.249 --> 00:36:32.930
we actually did to, um, represent
those equations with matrix,
00:36:32.930 --> 00:36:37.349
um, not quite this one, sorry.
00:36:37.349 --> 00:36:40.569
So, here's our equations.
00:36:40.569 --> 00:36:45.440
So, small example,
we would like to encode 4 bits,
00:36:45.440 --> 00:36:46.900
k is 4,
00:36:46.900 --> 00:36:49.479
and we're adding 3 extra bits.
00:36:49.479 --> 00:36:50.809
That's not very efficient,
00:36:50.809 --> 00:36:54.789
but it's a very nice example
that one can see.
00:36:54.789 --> 00:37:01.339
So, those rows there are
our parity equations.
00:37:01.339 --> 00:37:03.160
So let's assume we have those 7 bits,
00:37:03.160 --> 00:37:05.549
which add redundancy to it,
00:37:05.549 --> 00:37:07.499
then let's translate this first row,
00:37:07.499 --> 00:37:10.410
which is 1 0 0 1 1 0 1,
00:37:10.410 --> 00:37:13.130
that means we take the first bit,
00:37:13.130 --> 00:37:14.690
skip the second and third,
00:37:14.690 --> 00:37:16.769
so, have be 0,
00:37:16.769 --> 00:37:19.469
and then, bit 3, then the next bit is set
00:37:19.469 --> 00:37:23.119
so bit 4, and then bit 6.
00:37:23.119 --> 00:37:24.969
Second row, similarly,
we skip the first one,
00:37:24.969 --> 00:37:26.859
so there's no bit 0, there's a bit 1,
00:37:26.859 --> 00:37:28.479
no bit 2, there's a bit 3,
00:37:28.479 --> 00:37:30.759
it was a 1 1 0 column,
00:37:30.759 --> 00:37:32.979
and then bit 5 and bit 6,
00:37:32.979 --> 00:37:33.930
and similarly.
00:37:33.930 --> 00:37:38.279
So we have a nice diagonal
on the left-hand side,
00:37:38.279 --> 00:37:41.589
and then the rest is determined
by these equations.
00:37:41.589 --> 00:37:44.140
Now let's assume that
something went wrong.
00:37:44.140 --> 00:37:46.049
So we have our 7 bits here,
00:37:46.049 --> 00:37:48.509
and a few hours later we come back
00:37:48.509 --> 00:37:50.630
and want to look at those 7 bits,
00:37:50.630 --> 00:37:52.160
we check whether anything went wrong,
00:37:52.160 --> 00:37:55.619
we run through this parity check program,
00:37:55.619 --> 00:37:58.869
and we actually get a failure pattern.
00:37:58.869 --> 00:38:01.790
If everything was fine,
we would have gotten 0 0 0,
00:38:01.790 --> 00:38:05.900
but we're getting 1 0 1.
00:38:05.900 --> 00:38:08.229
So the first equation doesn't hold,
00:38:08.229 --> 00:38:10.219
the second one does hold,
00:38:10.219 --> 00:38:13.349
and the third one does not hold.
00:38:13.349 --> 00:38:17.239
Okay. Where could this come from?
00:38:17.239 --> 00:38:19.239
We're pretty sure that b1 is okay
00:38:19.239 --> 00:38:21.569
because otherwise the second
equation would be wrong
00:38:21.569 --> 00:38:24.509
because b1 only appears there,
00:38:24.509 --> 00:38:25.880
and we're also making the promise
00:38:25.880 --> 00:38:27.729
that it would be only one error.
00:38:27.729 --> 00:38:29.339
If you have two errors, three errors,
00:38:29.339 --> 00:38:31.420
then lots of other combinations
could occur.
00:38:31.420 --> 00:38:33.289
But it's much more likely that
one bit flipped
00:38:33.289 --> 00:38:36.319
than that a whole bunch
of bits flipped at once.
00:38:36.319 --> 00:38:39.779
Okay, so, tracing this
a little bit further,
00:38:39.779 --> 00:38:42.739
yes, so the b3 would get
the two first equations,
00:38:42.739 --> 00:38:45.059
b4, yes! b4 actually would get
00:38:45.059 --> 00:38:48.219
that the first and the third
equations are false.
00:38:48.219 --> 00:38:50.809
So by seeing the error pattern 1 0 1,
00:38:50.809 --> 00:38:53.229
we know it was b4.
00:38:53.229 --> 00:38:55.539
Now this is a very nice and small example,
00:38:55.539 --> 00:38:57.710
which doesn't even cover like the ECC RAM,
00:38:57.710 --> 00:39:00.680
but it gives you an idea of how to try it.
00:39:00.680 --> 00:39:02.089
On the other hand, it also gives you
00:39:02.089 --> 00:39:04.549
the idea that you need to do kind of
00:39:04.549 --> 00:39:07.369
brute force search it.
00:39:07.369 --> 00:39:10.549
So for just n=7, you have to
try up to 7 times.
00:39:10.549 --> 00:39:12.410
If you now have two errors,
00:39:12.410 --> 00:39:16.309
I would need to try every combination of 2
00:39:16.309 --> 00:39:18.090
out of those n.
00:39:18.090 --> 00:39:23.880
If I have a n which is like 2000 bits,
really long,
00:39:23.880 --> 00:39:27.229
and I tell you there's 100 errors,
00:39:27.229 --> 00:39:28.930
so you would need to try every combination
00:39:28.930 --> 00:39:31.089
of 100 positions in there.
00:39:31.089 --> 00:39:33.569
So that would be a huge number.
00:39:33.569 --> 00:39:36.599
That's obviously not a good way
of error correction,
00:39:36.599 --> 00:39:37.849
and that's certainly not how
00:39:37.849 --> 00:39:39.690
DVDs and whatever else works.
00:39:39.690 --> 00:39:41.859
Oh yeah, one bit of maths notation,
00:39:41.859 --> 00:39:46.449
so, we call these things,
the parentheses up there, matrix,
00:39:46.449 --> 00:39:47.869
and in order to have a shorthand,
00:39:47.869 --> 00:39:54.589
because I can't quite put my 2000 bits
times 1000 bits matrix on the page,
00:39:54.589 --> 00:39:57.480
I call this thing H,
00:39:57.480 --> 00:40:01.239
and boldface b is such a bit vector.
00:40:01.239 --> 00:40:04.839
So boldface b is that
bits that I'm storing,
00:40:04.839 --> 00:40:08.519
and the combination of
applying this matrix,
00:40:08.519 --> 00:40:11.130
wherever is 1, I take the variable,
00:40:11.130 --> 00:40:13.059
where there's a 0, I don't write it,
00:40:13.059 --> 00:40:15.380
that I write as H times b.
00:40:15.380 --> 00:40:16.499
So in maths, if you have seen this,
00:40:16.499 --> 00:40:19.549
this is just a matrix times
vector multiplication,
00:40:19.549 --> 00:40:24.069
otherwise, just take this as
the instruction of evaluating
00:40:24.069 --> 00:40:28.710
this, each row, as a set of equations.
00:40:28.710 --> 00:40:31.089
Alright, so, to give this some names,
00:40:31.089 --> 00:40:33.920
in coding theory we call c the code word,
00:40:33.920 --> 00:40:37.209
so that's an element
which is not compromised,
00:40:37.209 --> 00:40:38.299
which will give you 0,
00:40:38.299 --> 00:40:40.229
then there might be an error vector,
00:40:40.229 --> 00:40:42.180
that's the bits that flip,
00:40:42.180 --> 00:40:44.059
and so, when you retrieve the memory
00:40:44.059 --> 00:40:45.779
or when you have a transmission,
00:40:45.779 --> 00:40:47.089
we call this the received word,
00:40:47.089 --> 00:40:50.239
and that's my b from the previous slide.
00:40:50.239 --> 00:40:52.259
We do like to save on space,
00:40:52.259 --> 00:40:53.420
so when there's this diagonal
00:40:53.420 --> 00:40:55.779
which has all 0s down there
00:40:55.779 --> 00:40:58.019
we just skip it.
00:40:58.019 --> 00:41:05.959
So instead of writing a 7-by-3,
we just write 4 columns and 3 rows.
00:41:05.959 --> 00:41:08.200
Now there's lots of stuff
happening in coding theory,
00:41:08.200 --> 00:41:10.660
it's a, well, 65 years old topic,
00:41:10.660 --> 00:41:13.200
and we can go up to very large matrices,
00:41:13.200 --> 00:41:16.119
and for some special codes,
00:41:16.119 --> 00:41:17.799
these are the ones that coding theorists
come up with,
00:41:17.799 --> 00:41:19.799
we actually have efficient methods.
00:41:19.799 --> 00:41:23.359
Much much nicer than taking
every combination of 100 positions
00:41:23.359 --> 00:41:26.549
out of 2000 positions.
00:41:26.549 --> 00:41:29.200
Of course, if you get too many errors,
00:41:29.200 --> 00:41:29.859
you can't correct.
00:41:29.859 --> 00:41:32.680
You can only correct up to
whatever the promise is,
00:41:32.680 --> 00:41:34.640
plus maybe a little bit later.
00:41:34.640 --> 00:41:36.549
But if you don't know
any of the structure,
00:41:36.549 --> 00:41:39.380
if you don't know what
the coding theorists put into it,
00:41:39.380 --> 00:41:42.729
or if this H matrix got somewhat perturbed
00:41:42.729 --> 00:41:47.439
by me giving a slightly
different representation,
00:41:47.439 --> 00:41:50.709
I don't call this b1 anymore,
I call it now b17,
00:41:50.709 --> 00:41:52.150
and let's flip those and so on,
00:41:52.150 --> 00:41:55.250
suddenly it doesn't look like
the code that you're used to.
00:41:55.250 --> 00:41:58.289
If it's a random matrix,
00:41:58.289 --> 00:42:00.200
the best attacks are not quite as bad
00:42:00.200 --> 00:42:02.999
as picking 100 out of 2000,
00:42:02.999 --> 00:42:04.670
but they are close to that,
00:42:04.670 --> 00:42:05.980
they're pretty slow attacks,
00:42:05.980 --> 00:42:08.959
it's an exponential-time algorithm,
00:42:08.959 --> 00:42:11.279
if you have a random matrix.
00:42:11.279 --> 00:42:12.999
And so what we're doing
in code-based crypto
00:42:12.999 --> 00:42:16.009
is to use this difference for encryption.
00:42:16.009 --> 00:42:17.599
Now going back again to the 70s,
00:42:17.599 --> 00:42:21.009
so, basically, yes, the stuff that we're
really confident in
00:42:21.009 --> 00:42:22.829
that it will last another 100 years,
00:42:22.829 --> 00:42:25.299
is the stuff from the 70s that lots of
people have looked at,
00:42:25.299 --> 00:42:27.299
so, McEliece in 1978,
00:42:27.299 --> 00:42:29.779
so just the year after RSA,
00:42:29.779 --> 00:42:35.719
came up with a system
which is using encoding as encryption.
00:42:35.719 --> 00:42:38.369
So your method is,
00:42:38.369 --> 00:42:40.930
you just encode a vector, your message,
00:42:40.930 --> 00:42:42.900
and then you add some errors to it.
00:42:42.900 --> 00:42:44.880
And, if the other side doesn't have
00:42:44.880 --> 00:42:47.379
an efficient algorithm to decode,
00:42:47.379 --> 00:42:49.459
they actually can't break it.
00:42:49.459 --> 00:42:51.700
They're using a special code in there,
00:42:51.700 --> 00:42:53.449
so there's a code from Goppa
00:42:53.449 --> 00:42:56.059
from a few years earlier than that,
00:42:56.059 --> 00:42:58.029
and that code, so far, nobody has found
00:42:58.029 --> 00:43:00.819
any way to take the perturbed,
00:43:00.819 --> 00:43:03.119
this complicated way of representing it,
00:43:03.119 --> 00:43:06.549
and coming up with
efficient decoding algorithm.
00:43:06.549 --> 00:43:10.660
1986, Niederreither came up with
a version of McEliece
00:43:10.660 --> 00:43:13.359
which is smaller,
the code size is smaller,
00:43:13.359 --> 00:43:15.529
the public key size is smaller,
00:43:15.529 --> 00:43:19.180
and we have similar things to
00:43:19.180 --> 00:43:21.239
what you've seen before,
so we have those H matrix,
00:43:21.239 --> 00:43:22.619
we skip the diagonal,
00:43:22.619 --> 00:43:28.499
we just represent this H as our public key
as the remaining part of the matrix,
00:43:28.499 --> 00:43:33.139
the secret key, that's the algorithm
that only I know.
00:43:33.139 --> 00:43:34.769
It's a Goppa code,
00:43:34.769 --> 00:43:35.890
but it's a Goppa code
00:43:35.890 --> 00:43:39.259
and there's many many Goppa codes
for the same size.
00:43:39.259 --> 00:43:40.549
So that's something that Goppa says,
00:43:40.549 --> 00:43:41.829
well, if you want to have Goppa codes
00:43:41.829 --> 00:43:46.969
with 2000 bits
that can correct 200 errors,
00:43:46.969 --> 00:43:47.829
here's how you set it up,
00:43:47.829 --> 00:43:51.200
but there's lots and lots and lots
of choices in there.
00:43:51.200 --> 00:43:52.469
And your encryption is just,
00:43:52.469 --> 00:43:54.910
take an error vector,
00:43:54.910 --> 00:43:57.269
with a fixed number of bits,
00:43:57.269 --> 00:43:59.479
and send me the error pattern of it.
00:43:59.479 --> 00:44:04.049
So the outcome of multiplying H by this e.
00:44:04.049 --> 00:44:05.509
And then we want to use this in crypto,
00:44:05.509 --> 00:44:08.209
so we use the hash of this to encrypt it.
00:44:08.209 --> 00:44:12.329
Um, then Peter Schwabe and
Tung Chou, our PhD student,
00:44:12.329 --> 00:44:14.349
wrote a very efficient
implementation of this
00:44:14.349 --> 00:44:15.729
called mcbits,
00:44:15.729 --> 00:44:17.380
so if you want to have more detail
00:44:17.380 --> 00:44:19.619
on how you could really
use this in practice,
00:44:19.619 --> 00:44:21.350
then go to that url.
00:44:21.350 --> 00:44:23.339
Um, but let me talk a little bit
00:44:23.339 --> 00:44:26.130
about why we are confident in this.
00:44:26.130 --> 00:44:28.180
Code-based crypto is less obvious
than hash-based,
00:44:28.180 --> 00:44:30.420
I mean with hash-based it's like,
00:44:30.420 --> 00:44:32.079
the, all we're doing is, hash.
00:44:32.079 --> 00:44:35.569
A hash function by definition is
something which is one-way.
00:44:35.569 --> 00:44:39.559
For this code-based crypto,
you need to think a little more,
00:44:39.559 --> 00:44:41.170
to have people studying it
00:44:41.170 --> 00:44:44.630
to figure out why this
actually can be secure.
00:44:44.630 --> 00:44:47.619
Now, the attacks, if I may say so,
00:44:47.619 --> 00:44:49.390
started before the cryptosystem
was proposed,
00:44:49.390 --> 00:44:50.999
so it was another hard problem
00:44:50.999 --> 00:44:53.410
that coding theorists were
studying naturally,
00:44:53.410 --> 00:44:56.219
and then McEliece said, hey, we have
this hard problem here,
00:44:56.219 --> 00:44:58.940
decoding a random code is not easy,
00:44:58.940 --> 00:45:01.539
well, actually, afterwards, figuring out,
00:45:01.539 --> 00:45:05.039
well, if you have a really random code,
00:45:05.039 --> 00:45:07.569
even finding out whether there is
a smaller code word is NP-hard.
00:45:07.569 --> 00:45:12.240
And then, once it was a cryptosystem,
00:45:12.240 --> 00:45:14.890
so, Omura, Lee-Brickell, all of those,
00:45:14.890 --> 00:45:17.519
those come after
it was proposed for crypto.
00:45:17.519 --> 00:45:20.529
There's some which have an extra
parenthetic comment,
00:45:20.529 --> 00:45:23.930
those are papers which study
the security of McEliece
00:45:23.930 --> 00:45:25.420
if the attacker has a quantum computer,
00:45:25.420 --> 00:45:27.329
so there's been lots and lots of work
00:45:27.329 --> 00:45:30.420
for studying it
against a classical computer,
00:45:30.420 --> 00:45:31.849
and there's been some work
00:45:31.849 --> 00:45:33.719
studying it against quantum computers.
00:45:33.719 --> 00:45:36.170
It's pretty clear that we can't use Shor,
00:45:36.170 --> 00:45:37.390
but we can use Grover,
00:45:37.390 --> 00:45:42.180
and it's not so easily obvious
how much Grover can give us.
00:45:42.180 --> 00:45:44.359
However, the best that Grover can do
00:45:44.359 --> 00:45:46.519
is basically halve the bit size.
00:45:46.519 --> 00:45:49.140
So we had this AES-128,
leading to 64-bit security,
00:45:49.140 --> 00:45:50.769
so if you're conservative,
00:45:50.769 --> 00:45:54.430
if you want to be like really really
on the secure size,
00:45:54.430 --> 00:45:58.559
then let's assume that we want to go for
pre-quantum security at least 256
00:45:58.559 --> 00:46:02.469
in order to get post-quantum security 128.
00:46:02.469 --> 00:46:04.440
So here are some key sizes,
00:46:04.440 --> 00:46:07.759
so if you're okay with 1000 kilobytes,
00:46:07.759 --> 00:46:14.690
then you're getting something
which is at least 131 post-quantum secure,
00:46:14.690 --> 00:46:17.170
and that's actually very conservative,
00:46:17.170 --> 00:46:20.289
most likely we can go much down
on the key size.
00:46:20.289 --> 00:46:22.049
But that's where more research is needed.
00:46:22.049 --> 00:46:25.660
If you need something where you can get
a guarantee of 100 years security,
00:46:25.660 --> 00:46:27.349
take this one,
00:46:27.349 --> 00:46:28.809
it's not small,
00:46:28.809 --> 00:46:31.650
it's fast, but it's not small,
00:46:31.650 --> 00:46:34.479
and hopefully in 5 years,
less than 5 years,
00:46:34.479 --> 00:46:37.249
they can give you something
which is smaller
00:46:37.249 --> 00:46:39.669
and still as secure.
00:46:39.669 --> 00:46:40.380
djb: Okay.
00:46:40.380 --> 00:46:45.079
There are lots of possibilities for
what the smaller things might be,
00:46:45.079 --> 00:46:47.919
for instance, there's something
called QC-MDPC,
00:46:47.919 --> 00:46:48.930
there's actually lots and lots
00:46:48.930 --> 00:46:50.680
of variations of McEliece
00:46:50.680 --> 00:46:51.599
that people have proposed,
00:46:51.599 --> 00:46:53.849
and some of those variations have held up,
00:46:53.849 --> 00:46:55.109
some of them haven't.
00:46:55.109 --> 00:46:58.479
QC-MDPC is something that has
held up so far,
00:46:58.479 --> 00:47:00.339
but how many people've looked at it,
00:47:00.339 --> 00:47:03.539
and what's going to happen when
more attacks get optimised?
00:47:03.539 --> 00:47:06.039
You can't be trusting something which
00:47:06.039 --> 00:47:09.140
is new or hasn't been studied enough,
00:47:09.140 --> 00:47:10.849
or hasn't been studied
in the right directions,
00:47:10.849 --> 00:47:13.089
you also have to be sceptical
about crypto.
00:47:13.089 --> 00:47:14.949
There's, well, lots of proposals,
00:47:14.949 --> 00:47:17.759
QC-MDPC looks like one of the most
interesting ones,
00:47:17.759 --> 00:47:20.930
that nobody's been able to damage
its security,
00:47:20.930 --> 00:47:23.680
for 2^80 pre-quantum security,
00:47:23.680 --> 00:47:24.819
which is not very good,
00:47:24.819 --> 00:47:26.479
but, just as an example,
00:47:26.479 --> 00:47:30.160
they have 0.6 kilobytes, or 600 bytes,
00:47:30.160 --> 00:47:31.789
for the public key,
00:47:31.789 --> 00:47:34.329
and that's a very reasonable size
for a public key,
00:47:34.329 --> 00:47:35.449
not as small as ECC
00:47:35.449 --> 00:47:37.039
but it's quite tolerable.
00:47:37.039 --> 00:47:38.910
Um, lattice-based crypto,
00:47:38.910 --> 00:47:40.009
there's NTRU, for example,
00:47:40.009 --> 00:47:42.099
that's been around since the 1990s,
00:47:42.099 --> 00:47:44.729
and maybe that's enough time to start
getting confident,
00:47:44.729 --> 00:47:46.690
but, well, again, there's
lattice-based systems
00:47:46.690 --> 00:47:48.079
that get proposed and broken,
00:47:48.079 --> 00:47:52.009
for instance, there's a system from
Smart-Vercauteren in 2009,
00:47:52.009 --> 00:47:54.699
that was, it's not broken pre-quantum,
00:47:54.699 --> 00:47:58.749
but it was shown in 2014-2015,
some follow-up papers,
00:47:58.749 --> 00:48:02.029
to be broken in polynomial time
by a quantum computer.
00:48:02.029 --> 00:48:05.130
So, it's a lattice-based system which
sounded good at the beginning,
00:48:05.130 --> 00:48:08.469
but is definitely not going to be part of
post-quantum cryptography.
00:48:08.469 --> 00:48:09.529
There's multivariate-quadratic,
00:48:09.529 --> 00:48:12.150
now those have
the interesting feature that
00:48:12.150 --> 00:48:15.109
the signatures they provide
can be very very small,
00:48:15.109 --> 00:48:17.289
like, you can have 100-bit signatures
00:48:17.289 --> 00:48:19.239
and still get some reasonable security
00:48:19.239 --> 00:48:20.989
that nobody knows how to break these,
00:48:20.989 --> 00:48:22.759
well, there's lots and lots
of these proposals
00:48:22.759 --> 00:48:24.819
and some of them are broken,
some of them...
00:48:24.819 --> 00:48:27.680
HFEv-, that's a multivariate
quadratic system
00:48:27.680 --> 00:48:31.140
that's been unbroken for 20 years.
00:48:31.140 --> 00:48:32.489
Maybe it will continue holding up,
00:48:32.489 --> 00:48:34.190
but, well, how many people have looked?
00:48:34.190 --> 00:48:36.839
You have to make sure enough people
look at these things.
00:48:36.839 --> 00:48:39.469
The reason we like these
simple systems from the 70s is
00:48:39.469 --> 00:48:40.229
enough people have looked
00:48:40.229 --> 00:48:42.910
but maybe if you've got more serious
performance constraints
00:48:42.910 --> 00:48:44.319
you should look at these other things,
00:48:44.319 --> 00:48:46.359
and of course we are looking at
these other things,
00:48:46.359 --> 00:48:47.660
trying to figure out what's secure,
00:48:47.660 --> 00:48:51.799
and how well we can actually, er,
00:48:51.799 --> 00:48:54.179
choose among all these
different possibilities.
00:48:54.179 --> 00:48:56.139
Something else, just last mention here,
00:48:56.139 --> 00:48:57.299
is isogeny-based,
00:48:57.299 --> 00:48:59.469
this is for people who like
elliptic curves,
00:48:59.469 --> 00:49:02.930
that there is maybe a way to use
elliptic curves post-quantum,
00:49:02.930 --> 00:49:04.289
and this has the interesting feature
00:49:04.289 --> 00:49:07.690
that it does exactly the same data flows
as Diffie-Hellman.
00:49:07.690 --> 00:49:09.599
So everything you're used to doing
with Diffie-Hellman,
00:49:09.599 --> 00:49:11.709
and having, like, a secret key over here
00:49:11.709 --> 00:49:13.109
and a public key over there,
00:49:13.109 --> 00:49:15.940
agree on a shared secret,
00:49:15.940 --> 00:49:18.279
that you can also do with
isogeny-based systems,
00:49:18.279 --> 00:49:20.519
but only a few people
have studied the security
00:49:20.519 --> 00:49:21.999
and maybe this'll also get broken.
00:49:21.999 --> 00:49:25.000
So, a lots more work,
lots more possibilities.
00:49:25.000 --> 00:49:27.969
Last slide, if you're interested
in more information
00:49:27.969 --> 00:49:29.909
here are a few places to look,
00:49:29.909 --> 00:49:32.209
first of all you can go to pqcrypto.org,
00:49:32.209 --> 00:49:36.640
so this is our first survey site
for post-quantum cryptography,
00:49:36.640 --> 00:49:38.269
and the biggest chunk of information there
00:49:38.269 --> 00:49:42.369
is bibliography, and if anybody has
newer papers,
00:49:42.369 --> 00:49:45.539
if you happen to write papers on
post-quantum crypto,
00:49:45.539 --> 00:49:46.989
and you'd like us to add those,
00:49:46.989 --> 00:49:48.119
then just let us know,
00:49:48.119 --> 00:49:51.170
um, and then, well,
we also have on the front page
00:49:51.170 --> 00:49:53.849
things like pointers to all
the PQCrypto conferences,
00:49:53.849 --> 00:49:54.769
that's the main place to look,
00:49:54.769 --> 00:49:57.150
go to pqcrypto.org and follow links to,
00:49:57.150 --> 00:49:59.819
for instance, the February
Japan conference.
00:49:59.819 --> 00:50:02.390
Then pqcrypto.eu.org, that's the main page
00:50:02.390 --> 00:50:05.459
for the EU project that Tanja mentioned,
00:50:05.459 --> 00:50:08.229
which is putting out as it progresses,
00:50:08.229 --> 00:50:09.640
well, it just started this year, but
00:50:09.640 --> 00:50:13.499
it's putting out, soon, free libraries!
00:50:13.499 --> 00:50:16.439
Software libraries, for actually doing
post-quantum cryptography.
00:50:16.439 --> 00:50:18.309
And benchmarking results,
00:50:18.309 --> 00:50:19.199
so you can actually say
00:50:19.199 --> 00:50:21.420
"Yeah, I've got the following performance
constraints here,
00:50:21.420 --> 00:50:23.070
that's what I'm able to use."
00:50:23.070 --> 00:50:25.039
And then in 2017, there's going to be
00:50:25.039 --> 00:50:28.920
a workshop, and a summer school, maybe
it'll be a spring school, we'll see,
00:50:28.920 --> 00:50:34.239
if you're interested in the Twitter feed
for that, then twitter.com/pqc_eu
00:50:34.239 --> 00:50:37.190
and final resource on the slide is you.
00:50:37.190 --> 00:50:40.130
You have the responsibility
if you care about crypto,
00:50:40.130 --> 00:50:42.440
then you have to get used to this stuff.
00:50:42.440 --> 00:50:43.699
You have to learn about hash-based,
00:50:43.699 --> 00:50:47.029
code-based, maybe lattice-based,
multivariate quadratics,
00:50:47.029 --> 00:50:49.529
these are the things which will be
the future of crypto.
00:50:49.529 --> 00:50:53.819
In the future, all of crypto will be
post-quantum crypto,
00:50:53.819 --> 00:50:56.569
because eventually the attackers
will have quantum computers.
00:50:56.569 --> 00:50:58.479
If you want to adapt to that future,
00:50:58.479 --> 00:51:00.369
then, well, take a look at these sytems
00:51:00.369 --> 00:51:02.229
and see, maybe find improvements,
00:51:02.229 --> 00:51:03.519
then, cool, then let us know,
00:51:03.519 --> 00:51:05.539
and, you know, publish papers,
00:51:05.539 --> 00:51:08.299
integrate them into real applications,
networking applications,
00:51:08.299 --> 00:51:09.969
implement the things
that aren't implemented,
00:51:09.969 --> 00:51:10.779
speed them up,
00:51:10.779 --> 00:51:12.840
there's lots of work that
still has to be done.
00:51:12.840 --> 00:51:15.050
That's it, thank you for your attention.
00:51:15.050 --> 00:51:28.799
applause
00:51:28.799 --> 00:51:33.589
Herald: Wow. Now we'll have some
short questions please.
00:51:33.589 --> 00:51:35.660
Because we're a bit late on time.
00:51:35.660 --> 00:51:39.559
Questioners, go around ahead,
there's a mike there,
00:51:39.559 --> 00:51:41.749
talk into it please.
00:51:41.749 --> 00:51:42.910
Can we have mike 1?
00:51:42.910 --> 00:51:45.869
Q: Oh, okay. Uh, quick question.
00:51:45.869 --> 00:51:50.239
So there was this result of
Laszlo Babai that there's a,
00:51:50.239 --> 00:51:56.059
that graph isomorphism has a
quasipolynomial time algorithm,
00:51:56.059 --> 00:52:00.219
um, not really knowing the subject at all,
00:52:00.219 --> 00:52:04.260
there's some very, very
superficial similarities,
00:52:04.260 --> 00:52:08.709
like, that is a hidden subgroup
problem, basically.
00:52:08.709 --> 00:52:11.849
Um, is there going to be any, like,
00:52:11.849 --> 00:52:14.289
is there any indication that the methods
he used in that proof
00:52:14.289 --> 00:52:16.989
are relevant to breaking, like,
00:52:16.989 --> 00:52:20.279
to weakening NTRU or things like this?
00:52:20.279 --> 00:52:25.729
djb: That's a good question. So, the, um,
the graph isomorphism advance now,
00:52:25.729 --> 00:52:27.069
is basically saying,
00:52:27.069 --> 00:52:30.229
so, graph isomorphism is a problem
which was famous as being
00:52:30.229 --> 00:52:32.619
not know to be solvable in polynomial
00:52:32.619 --> 00:52:35.160
or even, like you said,
quasipolynomial time.
00:52:35.160 --> 00:52:38.209
Um, except there were some really good
software algorithms
00:52:38.209 --> 00:52:41.069
which would solve most cases of it,
really quickly.
00:52:41.069 --> 00:52:42.680
There were just some really weird,
00:52:42.680 --> 00:52:43.849
highly symmetric cases,
00:52:43.849 --> 00:52:44.630
that were hard to solve
00:52:44.630 --> 00:52:47.249
and that's what Babai managed
to completely kill now,
00:52:47.249 --> 00:52:49.349
so he's handled all the cases.
00:52:49.349 --> 00:52:51.949
But we try to stay away from
problems like that in crypto,
00:52:51.949 --> 00:52:54.660
so, an example that's very closely
analogous to that is
00:52:54.660 --> 00:52:56.589
what's called support splitting,
00:52:56.589 --> 00:52:58.640
which is a certain type of attack strategy
00:52:58.640 --> 00:53:00.599
against code-based crypto
00:53:00.599 --> 00:53:03.190
if somebody gives away lots of information
00:53:03.190 --> 00:53:05.039
from the legitimate user.
00:53:05.039 --> 00:53:07.199
And that's something where the
support-splitting algorithm
00:53:07.199 --> 00:53:09.420
works in most cases,
00:53:09.420 --> 00:53:12.529
but it kind of fails in some corner cases,
00:53:12.529 --> 00:53:16.079
and, well, we try to stay away from
thinking about this anyway,
00:53:16.079 --> 00:53:18.690
because you just don't want to give
somebody that extra information,
00:53:18.690 --> 00:53:23.249
but if you did, then maybe Babai's
technique could be useful there.
00:53:23.249 --> 00:53:25.739
Herald: Thank you. This talk is not over.
00:53:25.739 --> 00:53:30.009
If you're leaving, which is okay,
please be silent.
00:53:30.009 --> 00:53:33.670
Next question, number 3, no, number 1.
00:53:33.670 --> 00:53:35.779
Q: Uh, hello, thank you for the talk.
00:53:35.779 --> 00:53:40.430
Um, how are the chances to have something
like forward secrecy with that?
00:53:40.430 --> 00:53:43.729
I recognise the last algorithm
has a chance
00:53:43.729 --> 00:53:45.339
to reuse Diffie-Hellman,
00:53:45.339 --> 00:53:47.739
that's possibly the only one?
00:53:47.739 --> 00:53:51.619
Lange: So, if you think that
forward secrecy means Diffie-Hellman,
00:53:51.619 --> 00:53:55.759
you can have forward secrecy
from normal encryption algorithms,
00:53:55.759 --> 00:53:58.249
at the expense of generating
a new key each time.
00:53:58.249 --> 00:54:00.670
You can have forward secrecy with RSA,
00:54:00.670 --> 00:54:03.140
if Alice talking to Bob starts by saying
00:54:03.140 --> 00:54:06.440
"Okay, this is my one-time RSA key,
00:54:06.440 --> 00:54:08.459
and I send this to Bob,
00:54:08.459 --> 00:54:12.609
with a request to encrypt to this key."
00:54:12.609 --> 00:54:16.099
If Alice never reuses this key,
00:54:16.099 --> 00:54:18.170
then this method is forward-secure.
00:54:18.170 --> 00:54:21.039
And similar to how you can
do this with RSA keys,
00:54:21.039 --> 00:54:23.420
you can also do this with McEliece keys.
00:54:23.420 --> 00:54:25.489
At the moment, there is a difficulty
00:54:25.489 --> 00:54:29.449
that the keys are very large.
00:54:29.449 --> 00:54:32.719
It is inconvenient when you want
to start talking,
00:54:32.719 --> 00:54:35.849
"Hey, I'm a client, hello server,
please talk to me",
00:54:35.849 --> 00:54:37.289
and the first thing you have to do
00:54:37.289 --> 00:54:41.900
is transmit a megabyte of key.
00:54:41.900 --> 00:54:44.229
On the other hand, you can do it.
00:54:44.229 --> 00:54:47.719
It just requires you to engineer
your protocol to expect,
00:54:47.719 --> 00:54:50.999
yes, you have to send a few packages.
00:54:50.999 --> 00:54:53.959
And then it has all the
forward secrecy that you want.
00:54:53.959 --> 00:54:58.180
Q: But, uh, a way without
transferring the key,
00:54:58.180 --> 00:54:59.449
like Diffie-Hellman?
00:54:59.449 --> 00:55:02.509
Lange: But, Diffie-Hellman
is transferring a key.
00:55:02.509 --> 00:55:03.259
Q: Okay.
00:55:03.259 --> 00:55:04.989
Lange: I mean, you're basically
transferring
00:55:04.989 --> 00:55:07.349
the first part of a discrete log pair.
00:55:07.349 --> 00:55:10.299
If Alice sends a*p, and there is
some one-time key,
00:55:10.299 --> 00:55:12.219
she's sending a public key.
00:55:12.219 --> 00:55:16.029
It's just that the method of how
those two public keys interact
00:55:16.029 --> 00:55:19.279
is slightly different from how
RSA encryption works.
00:55:19.279 --> 00:55:20.980
Q: Okay, thank you.
00:55:20.980 --> 00:55:25.049
Herald: Thank you. Do we have
an Internet message? Question?
00:55:25.049 --> 00:55:30.170
Signal Angel: Actually, we do. There are
two questions that are somehow related.
00:55:30.170 --> 00:55:31.479
The first one is:
00:55:31.479 --> 00:55:37.299
Given that there is no actual working
quantum computer,
00:55:37.299 --> 00:55:40.619
how do you start developing
a crypto algorithm?
00:55:40.619 --> 00:55:42.410
Where do you start, how do you design it,
00:55:42.410 --> 00:55:46.140
how do you test it? Is there a way
to prove that it's secure?
00:55:46.140 --> 00:55:49.349
And the second question is related:
00:55:49.349 --> 00:55:55.079
The whole thing is based on the property
of the hash functions being one-way,
00:55:55.079 --> 00:55:57.969
how does one know that there is no
quantum algorithm
00:55:57.969 --> 00:55:59.920
that breaks this property?
00:55:59.920 --> 00:56:01.859
Can you prove this?
00:56:01.859 --> 00:56:03.729
djb: Okay. For both of these questions,
00:56:03.729 --> 00:56:06.079
the technique that the community
goes through,
00:56:06.079 --> 00:56:08.189
that we all go through,
is cryptanalysis.
00:56:08.189 --> 00:56:11.219
So we have as many smart people as
we can find
00:56:11.219 --> 00:56:12.989
focusing on these problems and saying
00:56:12.989 --> 00:56:16.549
"Can you find an algorithm which is
breaking these problems
00:56:16.549 --> 00:56:19.069
better than any previous algorithms can?"
00:56:19.069 --> 00:56:20.999
and we put as many incentives as we can
00:56:20.999 --> 00:56:23.099
so that we try to get as many smart people
00:56:23.099 --> 00:56:25.299
to stay ahead of the bad guys,
00:56:25.299 --> 00:56:27.299
and hopefully find the best algorithms.
00:56:27.299 --> 00:56:28.709
But there's no guarantees in this.
00:56:28.709 --> 00:56:30.449
And you do always have to be sceptical
00:56:30.449 --> 00:56:33.140
about whether people have
actually looked at, for instance
00:56:33.140 --> 00:56:35.359
quantum algorithms to attack systems.
00:56:35.359 --> 00:56:36.829
And there is that extra difficulty
00:56:36.829 --> 00:56:39.819
that the first part of the question,
at the beginning, was saying,
00:56:39.819 --> 00:56:41.809
that we don't have a quantum computer.
00:56:41.809 --> 00:56:45.339
So if we're trying to verify quantum
algorithms that we're developing,
00:56:45.339 --> 00:56:47.589
we don't get to experiment with them.
00:56:47.589 --> 00:56:50.549
That's the usual procedure for
making sure your algorithms work.
00:56:50.549 --> 00:56:52.559
In state-of-the-art cryptanalysis,
00:56:52.559 --> 00:56:55.029
like the number field sieve for factoring,
00:56:55.029 --> 00:56:57.880
that does not have a proof that
it works in any particular,
00:56:57.880 --> 00:56:59.789
well, at the speed that we think,
00:56:59.789 --> 00:57:01.349
it works out from experiment.
00:57:01.349 --> 00:57:03.329
So experiments are really important,
00:57:03.329 --> 00:57:05.829
because we don't have proofs
for state-of-the-art cryptanalysis,
00:57:05.829 --> 00:57:09.759
and that's something where it's actually
really tough for quantum computers.
00:57:09.759 --> 00:57:11.859
Of course eventually we'll all have
quantum computers,
00:57:11.859 --> 00:57:14.869
and there's ideas for simulating
quantum algorithms
00:57:14.869 --> 00:57:18.359
which have had some success
at verifying that algorithms work
00:57:18.359 --> 00:57:20.579
even though we can't actually
run them yet.
00:57:20.579 --> 00:57:25.050
That we're actually able to verify
a simulation of those algorithms.
00:57:25.050 --> 00:57:27.530
Lange: Let me do a second part of this.
00:57:27.530 --> 00:57:30.769
Um, when we use quantum cryptanalysis,
00:57:30.769 --> 00:57:33.189
for estimates, we usually go
for the worst-case estimate.
00:57:33.189 --> 00:57:39.230
So we say, well, McEliece, at worst,
gets broken to half the security level.
00:57:39.230 --> 00:57:41.380
Most likely it won't be that fast,
00:57:41.380 --> 00:57:45.609
but we're staying on the side
where we're very confident.
00:57:45.609 --> 00:57:48.349
Um, if I understood correctly
there was also the part of the question,
00:57:48.349 --> 00:57:50.099
how can we test the algorithms?
00:57:50.099 --> 00:57:52.670
If this is for
the constructive algorithms,
00:57:52.670 --> 00:57:54.369
then all the algorithms we analyse,
00:57:54.369 --> 00:57:56.900
all the algorithms we propose
for post-quantum crypto,
00:57:56.900 --> 00:57:59.939
are algorithms that you can run on
your normal computer.
00:57:59.939 --> 00:58:02.309
So, you can test those, you can run those,
00:58:02.309 --> 00:58:04.189
we have benchmarking numbers from those,
00:58:04.189 --> 00:58:07.219
on our current hardware.
00:58:07.219 --> 00:58:12.019
Herald: We'll do two more questions,
please. Number 1.
00:58:12.019 --> 00:58:15.630
Q: Yeah, I got a question on
the practicality of the attacks.
00:58:15.630 --> 00:58:19.150
So, um, if we assume there is
a quantum computer,
00:58:19.150 --> 00:58:21.729
how much time will it take in practice,
00:58:21.729 --> 00:58:22.900
order of magnitude,
00:58:22.900 --> 00:58:25.729
to break, let's say, RSA 2048-bit key?
00:58:25.729 --> 00:58:28.829
Is it on the order of hours,
weeks, months, years?
00:58:28.829 --> 00:58:31.169
Lange: snaps fingers Done.
00:58:31.169 --> 00:58:32.349
Q: Okay, thanks.
00:58:32.349 --> 00:58:32.939
laughter
00:58:32.939 --> 00:58:36.289
djb: That was easy!
Herald: Number 3.
00:58:36.289 --> 00:58:36.869
Q: Okay.
00:58:36.869 --> 00:58:38.599
Herald: Talk into the mike, please.
00:58:38.599 --> 00:58:41.369
Q: Thank you. So, it's very,
very nice to have
00:58:41.369 --> 00:58:45.789
both quantum encryption and signing,
00:58:45.789 --> 00:58:48.650
but do you know anything about
some other cryptographic primitives,
00:58:48.650 --> 00:58:52.499
such as zero-knowledge proofs?
00:58:52.499 --> 00:58:53.499
Lange: Well, I mean, zero-knowledge proofs
00:58:53.499 --> 00:58:56.920
are basically signatures
which are not interactive.
00:58:56.920 --> 00:58:59.580
So if you have something which is, um,
00:58:59.580 --> 00:59:02.249
a primitive for a signature is usually
very closely related
00:59:02.249 --> 00:59:03.789
to zero-knowledge proofs.
00:59:03.789 --> 00:59:05.739
So, there is work going on,
00:59:05.739 --> 00:59:07.680
we are focusing on
the most important things
00:59:07.680 --> 00:59:10.049
that we see on the Internet,
00:59:10.049 --> 00:59:12.579
but, that shouldn't mean that people
shouldn't do research on it.
00:59:12.579 --> 00:59:17.060
Please do research on
zero-knowledge proofs!
00:59:17.060 --> 00:59:21.539
Herald: Okay. Last question. Number 1.
00:59:21.539 --> 00:59:24.859
Q: So, why do you put so much emphasis
00:59:24.859 --> 00:59:28.549
on smaller key sizes and
on performance in encryption,
00:59:28.549 --> 00:59:34.529
um, especially in a delicate topic like
post-quantum computing?
00:59:34.529 --> 00:59:37.269
Why can't we just use 1-megabyte keys
00:59:37.269 --> 00:59:41.859
and why can't we just use a few seconds
instead of miliseconds
00:59:41.859 --> 00:59:43.599
to compute those?
Lange: So...
00:59:43.599 --> 00:59:44.949
Q: What's the the problem here?
00:59:44.949 --> 00:59:47.660
Lange: We are suggesting
to use a key of 1 megabyte.
00:59:47.660 --> 00:59:51.809
So, our recommendation that we have on
the Internet on the pqcrypto.org page
00:59:51.809 --> 00:59:56.180
are precisely using this system
which has a 1-megabyte key.
00:59:56.180 --> 00:59:58.329
The nice thing is, that actually
00:59:58.329 --> 01:00:02.449
encryption and decryption
are very efficient.
01:00:02.449 --> 01:00:03.579
But that was not our main goal,
01:00:03.579 --> 01:00:06.430
our main goal was to get something
which is very secure,
01:00:06.430 --> 01:00:11.329
and where we have a high confidence
that we actually understand the attack.
01:00:11.329 --> 01:00:14.009
And then, well, once we have this system,
01:00:14.009 --> 01:00:17.520
then you try to optimise
how to implement it,
01:00:17.520 --> 01:00:19.279
and the implementation,
when we looked at the numbers
01:00:19.279 --> 01:00:22.039
is actually faster than
elliptic curve implementations
01:00:22.039 --> 01:00:23.910
except for the size.
01:00:23.910 --> 01:00:26.329
So, you get a very nice speed,
01:00:26.329 --> 01:00:31.790
even though it was not our
target for optimisation.
01:00:31.790 --> 01:00:33.379
Herald: Okay, this is it.
01:00:33.379 --> 01:00:35.430
Thank you very much,
let's have a final hand
01:00:35.430 --> 01:00:38.479
for Tanja Lange and djb Bernstein!
01:00:38.479 --> 01:00:46.360
applause
01:00:46.360 --> 01:00:51.397
postroll music
01:00:51.397 --> 01:00:58.000
Untertitel erstellt von c3subtitles.de
im Jahr 2016. Mach mit und hilf uns!