1
00:00:00,000 --> 00:00:10,064
preroll music
2
00:00:10,064 --> 00:00:12,189
Herald: Tanja Lange and djb,
3
00:00:12,189 --> 00:00:15,519
or, Daniel Bernstein,
4
00:00:15,519 --> 00:00:19,980
came from the elliptic curve
5
00:00:19,980 --> 00:00:21,710
are gonna talk today also about
6
00:00:21,710 --> 00:00:24,380
the McEliece crypto where they took us.
7
00:00:24,380 --> 00:00:25,759
They're both in the steering committee
8
00:00:25,759 --> 00:00:28,219
for the PQCrypt
9
00:00:28,219 --> 00:00:30,259
and I've talked to other people
in the community
10
00:00:30,259 --> 00:00:31,239
and they said,
11
00:00:31,239 --> 00:00:32,390
especially about Tanja,
12
00:00:32,390 --> 00:00:37,739
she is the one that brings practice
and reality into all this theoretical mess
13
00:00:37,739 --> 00:00:44,420
so let's please have a hand for
Tanja Lange and Daniel Bernstein.
14
00:00:44,420 --> 00:00:55,260
applause
15
00:00:55,260 --> 00:00:58,769
djb: Okay. Am I on? I apparently am.
16
00:00:58,769 --> 00:01:01,980
Welcome to a late night show,
with Dan and Tanja.
17
00:01:01,980 --> 00:01:05,570
laughter
There's a lot of crypto talks out there
18
00:01:05,570 --> 00:01:09,560
where you'll get the idea that
crypto has problems.
19
00:01:09,560 --> 00:01:12,340
Crypto has massive usability problems,
20
00:01:12,340 --> 00:01:13,890
has performance problems,
21
00:01:13,890 --> 00:01:15,460
has pitfalls for implementors,
22
00:01:15,460 --> 00:01:17,750
has crazy complexity in implementation,
23
00:01:17,750 --> 00:01:19,729
stupid standards,
24
00:01:19,729 --> 00:01:21,920
millions of lines of unauditable code,
25
00:01:21,920 --> 00:01:23,320
and then all of these problems
26
00:01:23,320 --> 00:01:27,189
are combined into a
grand unified clusterfuck
27
00:01:27,189 --> 00:01:30,030
called transport layer security.
28
00:01:30,030 --> 00:01:38,030
laughter, applause
29
00:01:38,030 --> 00:01:41,449
But, actually, the situation is worse.
30
00:01:41,449 --> 00:01:43,510
laughter
31
00:01:43,510 --> 00:01:45,790
Because of what's coming, namely,
32
00:01:45,790 --> 00:01:49,260
quantum computers.
33
00:01:49,260 --> 00:01:51,610
These typical talks will give you the idea
34
00:01:51,610 --> 00:01:54,829
that the core of crypto,
the basic cryptographic primitives
35
00:01:54,829 --> 00:01:57,280
like elliptic curve crypto, ECC,
36
00:01:57,280 --> 00:01:59,240
that those are just fine,
and all the problems
37
00:01:59,240 --> 00:02:01,229
are integration into applications,
38
00:02:01,229 --> 00:02:03,100
that's where the security problems happen.
39
00:02:03,100 --> 00:02:06,609
But quantum computers will break ECC.
40
00:02:06,609 --> 00:02:09,258
This has been know since the 1990s.
41
00:02:09,258 --> 00:02:11,500
For people who don't recognise
the picture here,
42
00:02:11,500 --> 00:02:17,040
this is a mathematician named Peter Shor,
20 years ago.
43
00:02:17,040 --> 00:02:25,769
laughter, applause
44
00:02:25,769 --> 00:02:27,640
20 years ago he wrote a paper saying
45
00:02:27,640 --> 00:02:29,340
that a big quantum computer would be
46
00:02:29,340 --> 00:02:33,300
able to factor big integers
in polynomial time.
47
00:02:33,300 --> 00:02:34,770
Now, if you like doing attacks,
48
00:02:34,770 --> 00:02:36,259
and you hear about something like this,
49
00:02:36,259 --> 00:02:37,190
then your first thought is
50
00:02:37,190 --> 00:02:39,080
"Ooh, I wanna quantum computer!"
51
00:02:39,080 --> 00:02:41,430
"I want a big quantum computer
so I can run this attack!"
52
00:02:41,430 --> 00:02:43,350
"And, where is it? Does anybody have one?"
53
00:02:43,350 --> 00:02:44,620
"Can anybody gimme one?"
54
00:02:44,620 --> 00:02:46,610
"Oh, it isn't there yet?
Well, what's the progress?"
55
00:02:46,610 --> 00:02:48,670
"Are we there yet?
Can I have one, please?"
56
00:02:48,670 --> 00:02:50,470
And, well, in the news, you now hear
57
00:02:50,470 --> 00:02:53,669
about this D-wave quantum computer,
58
00:02:53,669 --> 00:02:56,879
which, okay, there's some very good
quantum engineering
59
00:02:56,879 --> 00:02:58,180
that goes into this machine.
60
00:02:58,180 --> 00:02:59,420
It's pretty clear that it's quantum,
61
00:02:59,420 --> 00:03:01,800
I mean, it's actually doing the quantum
stuff they say it does.
62
00:03:01,800 --> 00:03:04,920
And there's some fantastic
marketing in this machine.
63
00:03:04,920 --> 00:03:06,230
But, unfortunately,
64
00:03:06,230 --> 00:03:07,650
it's not actually useful.
65
00:03:07,650 --> 00:03:09,780
So the D-wave quantum computer
66
00:03:09,780 --> 00:03:11,690
doesn't do the basic things
67
00:03:11,690 --> 00:03:14,830
that we expect a universal
quantum computer to do.
68
00:03:14,830 --> 00:03:18,159
It can only do very limited
kinds of quantum computation.
69
00:03:18,159 --> 00:03:20,480
It cannot maintain qubits,
70
00:03:20,480 --> 00:03:22,520
do error correction on qubits for a while,
71
00:03:22,520 --> 00:03:23,750
hold on to them to be able to do
72
00:03:23,750 --> 00:03:25,659
basic qubit computations.
73
00:03:25,659 --> 00:03:27,739
It can't even do those computations,
74
00:03:27,739 --> 00:03:29,769
even if it could hold on to the qubits.
75
00:03:29,769 --> 00:03:31,299
It can't do Shor's algorithm.
76
00:03:31,299 --> 00:03:32,939
Can't factor big numbers.
77
00:03:32,939 --> 00:03:35,390
Can't do other quantum algorithms
that we care about.
78
00:03:35,390 --> 00:03:38,080
Now, the D-wave company says that's
not the point,
79
00:03:38,080 --> 00:03:39,519
there's some other computations
80
00:03:39,519 --> 00:03:41,799
that we designed this machine to do.
81
00:03:41,799 --> 00:03:43,549
But they cherry-picked the computations
82
00:03:43,549 --> 00:03:45,280
for this machine, saying basically
83
00:03:45,280 --> 00:03:48,769
Here is the problem of
simulating this machine
84
00:03:48,769 --> 00:03:51,129
simulating the quantum
thing that it's doing,
85
00:03:51,129 --> 00:03:53,400
and of course the machine is very good
at simulating itself,
86
00:03:53,400 --> 00:03:54,610
by just running,
87
00:03:54,610 --> 00:03:57,909
whereas a normal laptop, they compared to
88
00:03:57,909 --> 00:04:00,189
sort of standard programs
on a normal laptop,
89
00:04:00,189 --> 00:04:02,439
and latest results, 10^8 times faster
90
00:04:02,439 --> 00:04:06,129
except, well, there's a much
more optimised program
91
00:04:06,129 --> 00:04:07,780
that somebody put out last year,
92
00:04:07,780 --> 00:04:10,159
which basically is the same speed
as the D-wave machine
93
00:04:10,159 --> 00:04:12,049
and like ten thousand times cheaper.
94
00:04:12,049 --> 00:04:15,630
So, the D-wave machine is not,
for the moment, something useful.
95
00:04:15,630 --> 00:04:18,360
Lange: Well, if this makes you
kind of comfortable,
96
00:04:18,360 --> 00:04:22,440
so, no Shor monster coming,
97
00:04:22,440 --> 00:04:23,720
there is progress.
98
00:04:23,720 --> 00:04:25,760
There will be a universal
quantum computer,
99
00:04:25,760 --> 00:04:28,000
so, something that can run
Shor's algorithm,
100
00:04:28,000 --> 00:04:30,020
and there's a lot of research effort
going into this,
101
00:04:30,020 --> 00:04:32,120
so if you track, like, spending on crypto
102
00:04:32,120 --> 00:04:33,320
and you can spend...
103
00:04:33,320 --> 00:04:36,450
and track spending on quantum computers,
104
00:04:36,450 --> 00:04:37,670
that is a lot of money.
105
00:04:37,670 --> 00:04:39,850
And there's a lot of institutions
and companies
106
00:04:39,850 --> 00:04:41,700
and of course governments
all over the world
107
00:04:41,700 --> 00:04:43,090
building stuff.
108
00:04:43,090 --> 00:04:44,250
And we do see progress, so
109
00:04:44,250 --> 00:04:45,730
we're keeping track on this,
110
00:04:45,730 --> 00:04:48,300
and, go to the Wikipedia page here
111
00:04:48,300 --> 00:04:50,270
so we see over the last few years
112
00:04:50,270 --> 00:04:53,980
a huge progress in stability of qubits,
113
00:04:53,980 --> 00:04:56,430
so these things usually
forget what they had,
114
00:04:56,430 --> 00:04:57,930
they decay,
115
00:04:57,930 --> 00:04:59,890
but they get more stable,
116
00:04:59,890 --> 00:05:01,730
there's better error correction,
117
00:05:01,730 --> 00:05:03,040
and there's better communication.
118
00:05:03,040 --> 00:05:06,900
So the latest was that
even silicon-based qubits can communicate.
119
00:05:06,900 --> 00:05:08,530
So something is happening.
120
00:05:08,530 --> 00:05:12,970
Um, IBM has
on the record of Mark Ketchen
121
00:05:12,970 --> 00:05:15,390
who's their CEO saying
122
00:05:15,390 --> 00:05:19,640
"We actually do things that make us think
like, hey, this isn't 50 years off"
123
00:05:19,640 --> 00:05:23,260
"This is maybe just 10 or 15 years off.
It's within reach."
124
00:05:23,260 --> 00:05:24,590
So IBM is leaning out the window
125
00:05:24,590 --> 00:05:27,510
and saying, yup, we're gonna be there
pretty damn soon.
126
00:05:27,510 --> 00:05:31,560
They said that in 2012, so
let's fast-forward by 10 to 15 years
127
00:05:31,560 --> 00:05:34,930
so it's now 2022 or 2027
128
00:05:34,930 --> 00:05:37,990
and so there is a universal
quantum computer.
129
00:05:37,990 --> 00:05:42,220
The effect this has on the Internet crypto
130
00:05:42,220 --> 00:05:45,320
is that RSA, which is still the majority
131
00:05:45,320 --> 00:05:46,650
of all the connections today,
132
00:05:46,650 --> 00:05:49,760
RSA is broken. RSA is dead.
133
00:05:49,760 --> 00:05:51,820
Discrete logs in finite fields.
134
00:05:51,820 --> 00:05:53,250
You might have thought a lot about it
135
00:05:53,250 --> 00:05:55,000
earlier this year about Logjam.
136
00:05:55,000 --> 00:05:57,740
But Logjam just breaks the very small one.
137
00:05:57,740 --> 00:06:00,210
This is breaking any big one.
138
00:06:00,210 --> 00:06:03,250
So, discrete logs in finite fields
is totally dead as well.
139
00:06:03,250 --> 00:06:05,810
Elliptic curves, that I already mentioned,
ECC is dead.
140
00:06:05,810 --> 00:06:11,030
So this breaks all public-key crypto
on the Internet.
141
00:06:11,030 --> 00:06:13,460
There's another algorithm due to Grover,
142
00:06:13,460 --> 00:06:16,190
which is somewhat better under control,
143
00:06:16,190 --> 00:06:18,360
somewhat less scary for crypto,
144
00:06:18,360 --> 00:06:19,820
but it still has quite an effect,
145
00:06:19,820 --> 00:06:22,250
so if you believe in the security of AES
146
00:06:22,250 --> 00:06:26,010
and go like, well, AES-128 seems just fine,
147
00:06:26,010 --> 00:06:27,200
has been not getting any
148
00:06:27,200 --> 00:06:30,300
big progress in cryptanalysis,
149
00:06:30,300 --> 00:06:33,850
but it halves the security,
so AES 128-bit keys
150
00:06:33,850 --> 00:06:36,800
are only 64-bit secure.
151
00:06:36,800 --> 00:06:40,460
However, you can go to 256 bits.
152
00:06:40,460 --> 00:06:43,470
djb: Okay, so, the AES situation:
not so bad,
153
00:06:43,470 --> 00:06:45,530
but all this public key stuff is broken.
154
00:06:45,530 --> 00:06:46,470
So what do we do?
155
00:06:46,470 --> 00:06:48,370
Well, you could bury
your head in the sand,
156
00:06:48,370 --> 00:06:50,870
you could hope that quantum computers
don't come along,
157
00:06:50,870 --> 00:06:55,800
you could deploy
a physically secure crypto.
158
00:06:55,800 --> 00:06:59,100
You could take a locked briefcase
and chain it to your wrist,
159
00:06:59,100 --> 00:07:01,090
or you could do quantum key distribution.
160
00:07:01,090 --> 00:07:04,000
Now these things, obviously,
are very very expensive.
161
00:07:04,000 --> 00:07:07,610
This is crypto, information protection
for rich people.
162
00:07:07,610 --> 00:07:11,980
Or, quantum key distribution is crypto
for even richer people.
163
00:07:11,980 --> 00:07:15,370
You, obviously, aren't going to be able
to democratically give this
164
00:07:15,370 --> 00:07:16,840
to everybody who has a laptop.
165
00:07:16,840 --> 00:07:19,210
But, well, okay, imagine that
you have enough money,
166
00:07:19,210 --> 00:07:20,490
that you don't mind this.
167
00:07:20,490 --> 00:07:23,830
There's a bigger problem
with physical cryptography,
168
00:07:23,830 --> 00:07:25,290
which is the security.
169
00:07:25,290 --> 00:07:26,950
Now these things are always advertised
170
00:07:26,950 --> 00:07:30,100
as provably secure, guaranteed secure.
171
00:07:30,100 --> 00:07:31,760
Nobody can get into this briefcase!
172
00:07:31,760 --> 00:07:34,300
Nobody can get into this
quantum key distribution system!
173
00:07:34,300 --> 00:07:36,340
Assuming, of course, blah blah blah.
174
00:07:36,340 --> 00:07:37,550
And then you look at the assumptions
175
00:07:37,550 --> 00:07:38,410
and you start saying
176
00:07:38,410 --> 00:07:40,570
"Wait a minute, is that actually true?"
177
00:07:40,570 --> 00:07:43,440
And then it turns out that when people try
attacking these systems,
178
00:07:43,440 --> 00:07:44,770
the assumptions are not true.
179
00:07:44,770 --> 00:07:47,520
And the systems get broken
again and again and again
180
00:07:47,520 --> 00:07:50,380
for a very reasonable attack cost.
181
00:07:50,380 --> 00:07:54,270
Okay. Even if you have a system
where you think it's secure,
182
00:07:54,270 --> 00:07:55,770
which nobody's managed to build yet,
183
00:07:55,770 --> 00:07:59,080
even if you had that, the design of
this physical security system
184
00:07:59,080 --> 00:08:01,590
is incredibly difficult to audit.
185
00:08:01,590 --> 00:08:03,700
It's something where, if somebody wants
to slip in a backdoor,
186
00:08:03,700 --> 00:08:05,020
it's really easy.
187
00:08:05,020 --> 00:08:06,260
But there's an even worse problem
188
00:08:06,260 --> 00:08:07,860
with physical cryptography,
189
00:08:07,860 --> 00:08:10,480
which is that it doesn't
do very much crypto.
190
00:08:10,480 --> 00:08:14,860
Typically these systems do about
the same thing that AES does.
191
00:08:14,860 --> 00:08:17,000
You start with a shared secret,
192
00:08:17,000 --> 00:08:18,310
and then from that shared secret
193
00:08:18,310 --> 00:08:20,560
you can authenticate more secrets
194
00:08:20,560 --> 00:08:24,590
that you transmit through this
physically secure communication mechanism.
195
00:08:24,590 --> 00:08:26,050
For instance, quantum key distribution
196
00:08:26,050 --> 00:08:28,520
starts with some way,
some pre-existing way
197
00:08:28,520 --> 00:08:30,190
of authenticating.
198
00:08:30,190 --> 00:08:33,070
But that's just like AES starts with
a, a secret key
199
00:08:33,070 --> 00:08:34,450
which is then used to generate
200
00:08:34,450 --> 00:08:36,529
more and more secret data.
201
00:08:36,529 --> 00:08:38,330
And quantum key distribution says
202
00:08:38,330 --> 00:08:40,610
well, it's provably secure under
certain assumptions,
203
00:08:40,610 --> 00:08:42,770
instead of AES which, well,
204
00:08:42,770 --> 00:08:44,860
we just heard AES may be a little affected
205
00:08:44,860 --> 00:08:46,260
by quantum computers, but
206
00:08:46,260 --> 00:08:48,160
AES-256 is not broken.
207
00:08:48,160 --> 00:08:50,030
Nobody has any idea how to break it.
208
00:08:50,030 --> 00:08:52,200
So this physical cryptography
209
00:08:52,200 --> 00:08:54,570
isn't actually serving
the needs that we want.
210
00:08:54,570 --> 00:08:58,470
Imagine trying to distribute
operating system updates
211
00:08:58,470 --> 00:09:00,550
through locked briefcases.
212
00:09:00,550 --> 00:09:01,810
It's just not going to happen.
213
00:09:01,810 --> 00:09:04,330
Microsoft sending out billions
of locked briefcases
214
00:09:04,330 --> 00:09:05,800
to all of its customers.
215
00:09:05,800 --> 00:09:07,020
If you think that's realistic,
216
00:09:07,020 --> 00:09:11,150
or if you think that,
just, lasers are cool,
217
00:09:11,150 --> 00:09:13,450
then there's a talk about quantum crypto
218
00:09:13,450 --> 00:09:15,340
tomorrow, I believe.
219
00:09:15,340 --> 00:09:20,010
Back in the real world, we obviously
need to do something better with crypto.
220
00:09:20,010 --> 00:09:22,770
Lange: Alright, so,
let me take, momentarily,
221
00:09:22,770 --> 00:09:24,770
a slightly more optimistic perspective.
222
00:09:24,770 --> 00:09:26,370
Is there any hope? Yes.
223
00:09:26,370 --> 00:09:29,180
So, the title of this talk, PQCHacks,
224
00:09:29,180 --> 00:09:31,310
comes from post-quantum crypto,
225
00:09:31,310 --> 00:09:32,860
and that's the term Dan coined
226
00:09:32,860 --> 00:09:34,510
back in 2003
227
00:09:34,510 --> 00:09:36,290
for crypto that remains secure
228
00:09:36,290 --> 00:09:38,840
even if the adversary has
a quantum computer.
229
00:09:38,840 --> 00:09:42,500
So you, the normal people,
me, him, the normal people,
230
00:09:42,500 --> 00:09:44,290
the Internet, all the connections,
231
00:09:44,290 --> 00:09:46,740
we have normal computers.
232
00:09:46,740 --> 00:09:49,080
The adversary has a quantum computer.
233
00:09:49,080 --> 00:09:50,700
We, today, encrypt something.
234
00:09:50,700 --> 00:09:51,970
Adversary has all the time in the world
235
00:09:51,970 --> 00:09:53,450
to build the quantum computer,
236
00:09:53,450 --> 00:09:56,390
break us now or break us in the future.
237
00:09:56,390 --> 00:09:57,370
And so this took off,
238
00:09:57,370 --> 00:09:58,550
and there's been the first workshop
239
00:09:58,550 --> 00:10:02,370
on post-quantum crypto,
called PQCrypto2006
240
00:10:02,370 --> 00:10:03,770
and then there's been
a series of workshops
241
00:10:03,770 --> 00:10:04,850
you can see here.
242
00:10:04,850 --> 00:10:07,270
These are the attendees
of the last edition
243
00:10:07,270 --> 00:10:09,580
which was in Waterloo.
It's more than a hundred people,
244
00:10:09,580 --> 00:10:11,390
going like, yes,
this is an important topic,
245
00:10:11,390 --> 00:10:13,490
let's do some research on it.
246
00:10:13,490 --> 00:10:15,740
So something is happening.
247
00:10:15,740 --> 00:10:17,500
If you're curious what's happening,
248
00:10:17,500 --> 00:10:20,620
next there's a workshop in Japan
in February
249
00:10:20,620 --> 00:10:23,420
and then in the Netherlands
in 2017,
250
00:10:23,420 --> 00:10:26,630
and we also got a project through
from the EU
251
00:10:26,630 --> 00:10:28,810
to support research on post-quantum.
252
00:10:28,810 --> 00:10:30,320
So something is happening.
253
00:10:30,320 --> 00:10:34,260
Actually, um, did I forget somebody?
Yes.
254
00:10:34,260 --> 00:10:38,280
Um, the NSA is also saying,
let's do something.
255
00:10:38,280 --> 00:10:44,400
So, on August 11 the NSA posted
on their Suite B... page
256
00:10:44,400 --> 00:10:47,540
saying, "The Information Assurance
Director (so, IAD)
257
00:10:47,540 --> 00:10:51,640
recognizes that there will be a move, in
the not distant future, to a
258
00:10:51,640 --> 00:10:53,480
quantum resistant algorithm suite."
259
00:10:53,480 --> 00:10:56,180
Oh my god! Somebody is doing something!
260
00:10:56,180 --> 00:10:58,210
The public has realised
we have to do something!
261
00:10:58,210 --> 00:11:00,510
Quick, quick,
let's put out a press release!
262
00:11:00,510 --> 00:11:02,590
Um.
263
00:11:02,590 --> 00:11:05,560
Looks like they kind of realised
it was embarrassing.
264
00:11:05,560 --> 00:11:09,690
So, eight days later they pushed
a new release, saying
265
00:11:09,690 --> 00:11:15,210
"IAD will initiate a transition to quantum
resistant algorithms in the not distant future."
266
00:11:15,210 --> 00:11:19,910
So, NSA will lead us to a bright and
glorious future.
267
00:11:19,910 --> 00:11:22,760
djb: America, fuck yeah.
268
00:11:22,760 --> 00:11:30,790
laughter, applause
269
00:11:30,790 --> 00:11:34,510
Lange: But if you thought that,
so far, this was bad,
270
00:11:34,510 --> 00:11:38,340
it actually takes a lot of time
to build crypto.
271
00:11:38,340 --> 00:11:41,810
With let's say, NSA
all ask the researchers
272
00:11:41,810 --> 00:11:44,000
If you have some idea of
what could be secure
273
00:11:44,000 --> 00:11:45,510
against a quantum computer,
274
00:11:45,510 --> 00:11:47,120
say AES-256,
275
00:11:47,120 --> 00:11:48,590
the reason that you have confidence in it
276
00:11:48,590 --> 00:11:51,250
is we had more than ten years of people
277
00:11:51,250 --> 00:11:53,000
trying to break it,
278
00:11:53,000 --> 00:11:54,570
trying all kinds of approaches
279
00:11:54,570 --> 00:11:55,870
and not getting anywhere.
280
00:11:55,870 --> 00:12:00,350
It takes a lot of time to explore
the space of cryptosystems.
281
00:12:00,350 --> 00:12:01,540
Once you have figured out
282
00:12:01,540 --> 00:12:02,880
what could be actually doable,
283
00:12:02,880 --> 00:12:05,230
you want to figure
what the best attacks are,
284
00:12:05,230 --> 00:12:06,940
you want to focus on the security system,
285
00:12:06,940 --> 00:12:09,430
you want to figure out
how to implement them,
286
00:12:09,430 --> 00:12:10,380
how to implement them securely,
287
00:12:10,380 --> 00:12:13,570
that is a whole lot of work
that needs to be done
288
00:12:13,570 --> 00:12:15,860
before you can say, well,
this is actually practical.
289
00:12:15,860 --> 00:12:18,060
We can actually use this.
290
00:12:18,060 --> 00:12:22,680
Or sometimes, this is as practical
as we can get it.
291
00:12:22,680 --> 00:12:27,210
And then, you have this tiny little
crypto primitive,
292
00:12:27,210 --> 00:12:28,410
and then you have to build the hooks
293
00:12:28,410 --> 00:12:31,200
and connections to get it into TLS.
294
00:12:31,200 --> 00:12:32,670
Then we said at the beginning
295
00:12:32,670 --> 00:12:33,910
that maybe you believe
296
00:12:33,910 --> 00:12:36,670
that the cute little crypto cores
are all secure
297
00:12:36,670 --> 00:12:37,600
and it's just the connections
298
00:12:37,600 --> 00:12:39,500
with the AES, sorry, with the TLS
299
00:12:39,500 --> 00:12:42,029
in other world that is the problem.
300
00:12:42,029 --> 00:12:44,620
That still needs to be done
for post-quantum as well.
301
00:12:44,620 --> 00:12:46,500
And, the side-channel attacks,
302
00:12:46,500 --> 00:12:48,260
there's, uh, as an example,
303
00:12:48,260 --> 00:12:52,370
ECC was introduced back in 85,
304
00:12:52,370 --> 00:12:54,100
and now 30 years later,
305
00:12:54,100 --> 00:12:57,460
we're seeing that ECC is actually
getting deployed on the Internet,
306
00:12:57,460 --> 00:13:02,340
that now the IETF, having called
for having elliptic curve crypto,
307
00:13:02,340 --> 00:13:05,560
because people start saying, yes,
we would like to use this.
308
00:13:05,560 --> 00:13:08,440
So we cannot wait until
there's a quantum computer
309
00:13:08,440 --> 00:13:10,670
in order to start research on it.
310
00:13:10,670 --> 00:13:14,770
If you remember what 85 looked like
311
00:13:14,770 --> 00:13:18,770
That's a while ago.
312
00:13:18,770 --> 00:13:21,970
Now, if that sounded bad,
313
00:13:21,970 --> 00:13:23,170
it's actually worse.
314
00:13:23,170 --> 00:13:26,400
It's not just that, in 15 years from now,
315
00:13:26,400 --> 00:13:29,259
whatever you send then will be broken.
316
00:13:29,259 --> 00:13:33,420
There's some indication that some entities
317
00:13:33,420 --> 00:13:40,690
might be recording your traffic.
318
00:13:40,690 --> 00:13:42,700
We've given a talk like this in 2012
319
00:13:42,700 --> 00:13:44,220
which was "Crypto for the Paranoid",
320
00:13:44,220 --> 00:13:45,400
everybody thought it was, like,
321
00:13:45,400 --> 00:13:46,960
pfft, you're crazy,
322
00:13:46,960 --> 00:13:48,720
now it goes like
"well, there might be an entity"
323
00:13:48,720 --> 00:13:52,960
and everybody goes like, yeah, hmm, yeah.
324
00:13:52,960 --> 00:13:54,560
So, let's assume that this entity
325
00:13:54,560 --> 00:13:57,020
has the records of all the connections,
326
00:13:57,020 --> 00:14:01,220
and, that in ten years, you're going
to be an interesting person.
327
00:14:01,220 --> 00:14:04,540
Maybe you're a politician,
maybe you've become rich,
328
00:14:04,540 --> 00:14:07,880
maybe you associate with the wrong people,
or so they think,
329
00:14:07,880 --> 00:14:12,630
and so somehow they go back to
the 27th of December 2015,
330
00:14:12,630 --> 00:14:16,000
and figure out what you
were emailing during the talks,
331
00:14:16,000 --> 00:14:18,279
because they have all the connections here
332
00:14:18,279 --> 00:14:20,410
so they can go back in time
333
00:14:20,410 --> 00:14:26,050
just by the metadata,
and of course the real data.
334
00:14:26,050 --> 00:14:28,630
From the metadata, they can decrypt it,
335
00:14:28,630 --> 00:14:31,670
because this metadata is using RSA or ECC
336
00:14:31,670 --> 00:14:33,090
which are broken.
337
00:14:33,090 --> 00:14:34,550
And then they get the same key
338
00:14:34,550 --> 00:14:38,180
than you're currently using with your
other side to communicate.
339
00:14:38,180 --> 00:14:42,920
And so they can go and decrypt this.
340
00:14:42,920 --> 00:14:45,529
So it's not only that we can't wait for
quantum computers to come,
341
00:14:45,529 --> 00:14:51,320
we might already be too late.
342
00:14:51,320 --> 00:14:53,359
Well, on the next slide,
343
00:14:53,359 --> 00:14:56,190
here's a bunch of people who are getting
together in this EU project,
344
00:14:56,190 --> 00:14:59,720
and we have come up with
what we're currently thinking
345
00:14:59,720 --> 00:15:02,290
are good recommendations.
346
00:15:02,290 --> 00:15:04,080
We think it's necessary for people
347
00:15:04,080 --> 00:15:07,190
who really care about the security
of their connections,
348
00:15:07,190 --> 00:15:08,480
and when I say people I include myself,
349
00:15:08,480 --> 00:15:10,740
I care about the security of
my connections,
350
00:15:10,740 --> 00:15:12,330
we would like to have something
351
00:15:12,330 --> 00:15:15,050
that we believe is secure
for the next hundred years.
352
00:15:15,050 --> 00:15:17,310
And so we put out
a list of recommendations.
353
00:15:17,310 --> 00:15:19,910
So, for symmetric, it's relatively easy.
354
00:15:19,910 --> 00:15:22,500
You want something which is at least
a 256-bit key
355
00:15:22,500 --> 00:15:25,110
and is sufficiently well understood
356
00:15:25,110 --> 00:15:29,129
so there we have Salsa20,
and we have AES-256.
357
00:15:29,129 --> 00:15:32,990
Then, for authentication in symmetric,
358
00:15:32,990 --> 00:15:35,430
there, we don't actually have any decrease
359
00:15:35,430 --> 00:15:36,750
from a quantum computer, because
360
00:15:36,750 --> 00:15:38,899
these are already
information-theoretically secure.
361
00:15:38,899 --> 00:15:40,899
So these are the nice part.
362
00:15:40,899 --> 00:15:44,220
These two talk items is where we go like
363
00:15:44,220 --> 00:15:47,690
"Pff. We might be okay on those."
364
00:15:47,690 --> 00:15:49,880
We can do better,
we can have nice research
365
00:15:49,880 --> 00:15:51,740
and get something which is even
better protected,
366
00:15:51,740 --> 00:15:54,010
even faster under the new scenario,
367
00:15:54,010 --> 00:15:55,740
but it's not so dire.
368
00:15:55,740 --> 00:15:59,240
The bottom two, these are
the public key systems.
369
00:15:59,240 --> 00:16:03,399
That's public key encryption
and public key signatures.
370
00:16:03,399 --> 00:16:05,220
That's what we're going to
focus on in this talk.
371
00:16:05,220 --> 00:16:07,750
So, for public key encryption,
we're recommending
372
00:16:07,750 --> 00:16:10,620
the McEliece cryptosystem
with Goppa codes
373
00:16:10,620 --> 00:16:13,250
for a certain parameter size,
374
00:16:13,250 --> 00:16:15,240
and then for signatures,
375
00:16:15,240 --> 00:16:17,959
the recommendation is to use hash-based.
376
00:16:17,959 --> 00:16:19,170
djb: Okay, so...
377
00:16:19,170 --> 00:16:23,240
Let me dive into
the hash-based part of this.
378
00:16:23,240 --> 00:16:26,220
This is something which goes back
even further than the 80s.
379
00:16:26,220 --> 00:16:28,720
It goes back to the 1970s. Lamport.
380
00:16:28,720 --> 00:16:32,810
So here's a way to use hashes
to do one-time signatures.
381
00:16:32,810 --> 00:16:34,300
Which are, we'll see in a few minutes,
382
00:16:34,300 --> 00:16:35,700
signatures that you can use
383
00:16:35,700 --> 00:16:38,460
to sign one message under a given key.
384
00:16:38,460 --> 00:16:40,660
And then, well, that's a little bit
inconvenient
385
00:16:40,660 --> 00:16:41,910
that you can't sign more messages
386
00:16:41,910 --> 00:16:43,470
so then Merkle came along
387
00:16:43,470 --> 00:16:45,100
and said, you can sign more messages
388
00:16:45,100 --> 00:16:46,339
by modifying the system,
389
00:16:46,339 --> 00:16:47,730
and we'll also take a look at that.
390
00:16:47,730 --> 00:16:50,890
The only thing you need
for these public-key signature systems
391
00:16:50,890 --> 00:16:52,130
is a good hash function.
392
00:16:52,130 --> 00:16:54,690
And, okay, that's something where
historically,
393
00:16:54,690 --> 00:16:57,740
some hash functions designed in like, 1991
394
00:16:57,740 --> 00:16:58,580
had trouble.
395
00:16:58,580 --> 00:17:00,920
But, now, we have some good hash functions
396
00:17:00,920 --> 00:17:03,660
so, for instance, SHA-3 has
some great hash functions,
397
00:17:03,660 --> 00:17:05,790
even SHA-2, there's no sign of trouble,
398
00:17:05,790 --> 00:17:07,400
of those things being broken.
399
00:17:07,400 --> 00:17:10,119
And then after these original systems
from Lamport and Merkle,
400
00:17:10,119 --> 00:17:11,859
there's lots and lots of improvements,
401
00:17:11,859 --> 00:17:14,020
but all of these hash-based systems,
402
00:17:14,020 --> 00:17:16,670
it's really easy to
understand the security.
403
00:17:16,670 --> 00:17:18,329
It's something where the basic idea
404
00:17:18,329 --> 00:17:19,589
is really, really simple,
405
00:17:19,589 --> 00:17:21,280
and the security analysis also ends up
406
00:17:21,280 --> 00:17:22,869
being very straightforward.
407
00:17:22,869 --> 00:17:24,679
You have to be careful about some things,
408
00:17:24,679 --> 00:17:26,589
but, when you're careful about those,
409
00:17:26,589 --> 00:17:28,790
and there's nothing subtle
about it, nothing tricky,
410
00:17:28,790 --> 00:17:32,110
then we understand exactly
what security we get from these.
411
00:17:32,110 --> 00:17:35,130
So let's dive into a signature scheme
412
00:17:35,130 --> 00:17:37,820
that can only sign empty messages.
413
00:17:37,820 --> 00:17:40,690
Now, this sounds kind of, like,
wait a minute,
414
00:17:40,690 --> 00:17:42,760
what do you mean,
"can only sign empty messages?"
415
00:17:42,760 --> 00:17:44,600
There's only one empty string,
416
00:17:44,600 --> 00:17:46,290
and that's the only thing you can sign.
417
00:17:46,290 --> 00:17:49,550
But imagine that you want
to have a panic button,
418
00:17:49,550 --> 00:17:51,000
like, your revocation key,
419
00:17:51,000 --> 00:17:52,000
you want to be able to say,
420
00:17:52,000 --> 00:17:56,290
"Here's a message that says,
my house, my computer's been compromised,
421
00:17:56,290 --> 00:17:58,290
don't trust anything from this anymore".
422
00:17:58,290 --> 00:18:00,750
It's this one message
that you want to sign,
423
00:18:00,750 --> 00:18:01,500
under a certain key,
424
00:18:01,500 --> 00:18:03,750
and if anybody has that public key,
425
00:18:03,750 --> 00:18:06,800
then they should be able to verify
that you sent that message,
426
00:18:06,800 --> 00:18:08,350
and nobody should be able to forge that,
427
00:18:08,350 --> 00:18:10,000
because it's really bad
if somebody can forge
428
00:18:10,000 --> 00:18:10,880
your panic message.
429
00:18:10,880 --> 00:18:12,960
So, being able to sign just one message
430
00:18:12,960 --> 00:18:15,550
is not actually such a useless thing,
431
00:18:15,550 --> 00:18:16,790
and we'll also see that it builds up
432
00:18:16,790 --> 00:18:19,550
to the rest of hash-based crypto.
433
00:18:19,550 --> 00:18:23,040
Okay. Let's look at
some Python stuff here,
434
00:18:23,040 --> 00:18:25,650
simple SHA-3 you can get online
435
00:18:25,650 --> 00:18:29,580
under Ubuntu or Debian
do install python-pip and python-dev
436
00:18:29,580 --> 00:18:31,360
because it's a C library actually,
437
00:18:31,360 --> 00:18:33,840
and then, pip install simplesha3,
438
00:18:33,840 --> 00:18:36,210
that will give you SHA3-256,
439
00:18:36,210 --> 00:18:38,000
and then to generate a keypair
440
00:18:38,000 --> 00:18:41,140
in this empty-message signature system,
441
00:18:41,140 --> 00:18:43,850
all you do is you make 32 bytes
of random data
442
00:18:43,850 --> 00:18:45,070
and just hash it again,
443
00:18:45,070 --> 00:18:49,740
just in in case... urandom is not
too well-reviewed...
444
00:18:49,740 --> 00:18:51,770
I mean, we should trust urandom,
445
00:18:51,770 --> 00:18:54,090
but it's really cheap
to put an extra hash on it.
446
00:18:54,090 --> 00:18:57,140
So that's your secret key,
it's a 32-byte hash.
447
00:18:57,140 --> 00:18:58,530
And then the public key is,
448
00:18:58,530 --> 00:18:59,890
hash that secret again.
449
00:18:59,890 --> 00:19:03,040
So the public key is simply
a hash of the secret key.
450
00:19:03,040 --> 00:19:05,120
And then return the public key
and the secret key,
451
00:19:05,120 --> 00:19:06,640
of course the public key
will get published,
452
00:19:06,640 --> 00:19:08,860
and the secret key you keep for yourself.
453
00:19:08,860 --> 00:19:11,370
As an example of doing this, well, um,
454
00:19:11,370 --> 00:19:12,600
you just get random-looking data
455
00:19:12,600 --> 00:19:15,000
coming out from your public key
at the bottom
456
00:19:15,000 --> 00:19:17,910
your secret key right at the bottom
and public key above that.
457
00:19:17,910 --> 00:19:19,870
And you can check that one
of them's a hash of the other
458
00:19:19,870 --> 00:19:21,290
if you know the secret key,
459
00:19:21,290 --> 00:19:22,730
you can hash it to get the public.
460
00:19:22,730 --> 00:19:25,000
Okay, now, how do you sign a message?
461
00:19:25,000 --> 00:19:27,380
Well, this maybe sort of spelled out
462
00:19:27,380 --> 00:19:29,230
in more steps than it has to be.
463
00:19:29,230 --> 00:19:32,260
The API here, this is, I would say,
464
00:19:32,260 --> 00:19:33,910
getting to be a pretty popular API
465
00:19:33,910 --> 00:19:36,790
for signatures and for verification,
466
00:19:36,790 --> 00:19:40,010
where you include the signature
and the message together,
467
00:19:40,010 --> 00:19:41,230
as a signed message.
468
00:19:41,230 --> 00:19:44,940
And to emphasise that, here's a returned
signed message from the sign function.
469
00:19:44,940 --> 00:19:48,730
Now, the signed message
will be later on verified,
470
00:19:48,730 --> 00:19:50,450
and you get a message out of it,
471
00:19:50,450 --> 00:19:52,080
where the only possible message
472
00:19:52,080 --> 00:19:53,670
to be signed is the empty string,
473
00:19:53,670 --> 00:19:55,610
and you can see that the top there
474
00:19:55,610 --> 00:19:57,540
of the signature is checking
475
00:19:57,540 --> 00:19:59,530
if the message is anything
other than the empty string
476
00:19:59,530 --> 00:20:01,750
then you're not allowed to sign it.
477
00:20:01,750 --> 00:20:04,740
Um, if you have the empty string coming in
478
00:20:04,740 --> 00:20:09,600
then the signature is simply
your secret key.
479
00:20:09,600 --> 00:20:11,780
So you reveal your secret key
480
00:20:11,780 --> 00:20:13,610
and the whole idea of hash-based crypto
481
00:20:13,610 --> 00:20:16,160
is that somebody can publicly check
482
00:20:16,160 --> 00:20:18,650
the hashes of something that you reveal
483
00:20:18,650 --> 00:20:22,220
to sign, in this case, the empty message.
484
00:20:22,220 --> 00:20:23,860
And we'll see later how
you can use the same idea
485
00:20:23,860 --> 00:20:25,390
to sign lots more.
486
00:20:25,390 --> 00:20:27,030
And then, okay, verification,
487
00:20:27,030 --> 00:20:29,270
you simply checked that signedmessage,
488
00:20:29,270 --> 00:20:31,340
which is supposed to be the secret key,
489
00:20:31,340 --> 00:20:32,480
check its hash
490
00:20:32,480 --> 00:20:34,480
and see if that matches the public key.
491
00:20:34,480 --> 00:20:36,120
What would somebody have to do
to attack this?
492
00:20:36,120 --> 00:20:37,360
He would have to,
493
00:20:37,360 --> 00:20:39,549
if you haven't actually signed a message,
494
00:20:39,549 --> 00:20:40,540
the one message,
495
00:20:40,540 --> 00:20:41,710
then he would have to figure out
496
00:20:41,710 --> 00:20:45,010
some string that, when you hash it,
497
00:20:45,010 --> 00:20:46,510
gives this public key.
498
00:20:46,510 --> 00:20:48,460
And, well, that public key,
499
00:20:48,460 --> 00:20:50,260
this is a preimage problem,
500
00:20:50,260 --> 00:20:51,760
inverting the hash function.
501
00:20:51,760 --> 00:20:53,580
The hash is supposed to be one-way,
502
00:20:53,580 --> 00:20:55,460
if the input were low-entropy,
503
00:20:55,460 --> 00:20:56,860
then this would be doable,
504
00:20:56,860 --> 00:20:59,140
but the input was a 32-byte random string,
505
00:20:59,140 --> 00:21:00,760
so nobody will be able to guess that,
506
00:21:00,760 --> 00:21:03,730
or find any other string that passes this.
507
00:21:03,730 --> 00:21:05,410
And then you return the message
508
00:21:05,410 --> 00:21:06,660
and you can try this out
509
00:21:06,660 --> 00:21:08,240
and see that it works.
510
00:21:08,240 --> 00:21:09,610
Alright, let's move on.
511
00:21:09,610 --> 00:21:11,470
We've managed to sign empty messages.
512
00:21:11,470 --> 00:21:13,790
How about signing 0 or 1?
513
00:21:13,790 --> 00:21:15,929
So now we'll make a signature system
514
00:21:15,929 --> 00:21:18,270
where your key can sign 0
515
00:21:18,270 --> 00:21:19,730
and your key can sign 1.
516
00:21:19,730 --> 00:21:22,400
And, well, this is going
to be kind of stupid,
517
00:21:22,400 --> 00:21:24,850
what you do is, you make two keys,
518
00:21:24,850 --> 00:21:26,480
one of them is signing 0,
519
00:21:26,480 --> 00:21:28,370
and the other one is signing 1.
520
00:21:28,370 --> 00:21:31,600
You can see how complicated
this hash-based signature stuff is,
521
00:21:31,600 --> 00:21:34,460
it's, okay, you put two keys together,
522
00:21:34,460 --> 00:21:36,450
you make one key that will sign 0,
523
00:21:36,450 --> 00:21:37,470
one key that will sign 1,
524
00:21:37,470 --> 00:21:38,610
concatenate the public keys,
525
00:21:38,610 --> 00:21:40,130
concatenate the secret keys,
526
00:21:40,130 --> 00:21:42,520
the p0+p1, s0+s1,
527
00:21:42,520 --> 00:21:43,880
and then if you want to sign, then,
528
00:21:43,880 --> 00:21:45,860
well, if you're signing 0,
529
00:21:45,860 --> 00:21:48,020
now the messages being signed
are integers now
530
00:21:48,020 --> 00:21:49,490
instead the empty string,
531
00:21:49,490 --> 00:21:50,670
if you want to sign 0,
532
00:21:50,670 --> 00:21:51,940
then the signed message will be
533
00:21:51,940 --> 00:21:55,830
the string "0", followed by the 32 bytes,
534
00:21:55,830 --> 00:21:59,059
well, this is again more complicated
than it has to be,
535
00:21:59,059 --> 00:22:01,400
but think of this as
signing the empty message
536
00:22:01,400 --> 00:22:03,460
with the empty signature system,
537
00:22:03,460 --> 00:22:06,540
which is just copying the 32 bytes
of the secret key.
538
00:22:06,540 --> 00:22:08,410
And then if you want to sign message 1,
539
00:22:08,410 --> 00:22:12,240
then you do that with the other 32 bytes
of the secret key.
540
00:22:12,240 --> 00:22:13,770
And then, to verify it,
541
00:22:13,770 --> 00:22:16,100
well, just whether the
signed message is 0 or 1,
542
00:22:16,100 --> 00:22:18,150
just do the obvious thing.
543
00:22:18,150 --> 00:22:19,950
Maybe I should emphasise this code
544
00:22:19,950 --> 00:22:22,440
was written just for this talk,
545
00:22:22,440 --> 00:22:24,179
it has not been reviewed,
546
00:22:24,179 --> 00:22:25,860
and you should audit everything.
547
00:22:25,860 --> 00:22:26,809
You know, you might feel like
548
00:22:26,809 --> 00:22:28,990
six lines of code,
you can't possibly screw it up,
549
00:22:28,990 --> 00:22:32,530
but, don't ever
use code like that in crypto.
550
00:22:32,530 --> 00:22:34,760
So, this is just meant for
you to understand
551
00:22:34,760 --> 00:22:35,700
what this is supposed to be doing,
552
00:22:35,700 --> 00:22:36,860
this has not passed review.
553
00:22:36,860 --> 00:22:39,640
But, I like to think it would pass review.
554
00:22:39,640 --> 00:22:41,650
Um, okay, if you try
555
00:22:41,650 --> 00:22:44,570
signing the 1 message, for example,
556
00:22:44,570 --> 00:22:47,549
and take the signed 1 message
and open that signed message,
557
00:22:47,549 --> 00:22:49,360
you do get the integer 1 back.
558
00:22:49,360 --> 00:22:50,470
And if you try forging it,
559
00:22:50,470 --> 00:22:51,600
you're again faced with this problem
560
00:22:51,600 --> 00:22:53,980
of coming up with some 32-byte string
561
00:22:53,980 --> 00:22:56,580
that hashes to a particular result.
562
00:22:56,580 --> 00:22:59,790
Alright, let's move on to 4-bit messages!
563
00:22:59,790 --> 00:23:02,440
So, I promise I won't do
every possible length.
564
00:23:02,440 --> 00:23:04,610
But, 4 bits, this will make
an important point
565
00:23:04,610 --> 00:23:06,600
that you don't see from 1 bit.
566
00:23:06,600 --> 00:23:08,720
Let's try to sign a 4-bit message
567
00:23:08,720 --> 00:23:11,150
by signing each of the four bits.
568
00:23:11,150 --> 00:23:13,960
This all scales up to signing 1000 bits
if you want.
569
00:23:13,960 --> 00:23:17,950
Um, so, okay, let's make
4 sign-bit keypairs
570
00:23:17,950 --> 00:23:21,179
where each of those was
two 32-byte hashes,
571
00:23:21,179 --> 00:23:25,590
I mean, each secret key is
two 32-byte random strings
572
00:23:25,590 --> 00:23:29,380
and each of the public keys is the hash
of those 32-byte random strings.
573
00:23:29,380 --> 00:23:31,970
Make 4 of those pairs
and concatenate them
574
00:23:31,970 --> 00:23:34,950
to make some new public keys
and secret keys.
575
00:23:34,950 --> 00:23:38,489
Alright, and now to sign a message, well,
you look at the message
576
00:23:38,489 --> 00:23:41,179
and check,
is it an integer between 0 and 15,
577
00:23:41,179 --> 00:23:42,580
and reject otherwise,
578
00:23:42,580 --> 00:23:44,960
and then sign each bit of the message.
579
00:23:44,960 --> 00:23:47,850
You can see m shifted right by 0, 1, 2, 3,
580
00:23:47,850 --> 00:23:49,750
extract the bottom bit of each of those,
581
00:23:49,750 --> 00:23:51,690
and then sign each of those bits,
582
00:23:51,690 --> 00:23:53,730
and then concatenate the signatures
583
00:23:53,730 --> 00:23:56,970
to get, well, signatures of the four bits
of the message.
584
00:23:56,970 --> 00:24:00,200
And then verification works the way
you expect
585
00:24:00,200 --> 00:24:02,750
and I'll just skip that.
586
00:24:02,750 --> 00:24:04,290
Alright, this has a problem.
587
00:24:04,290 --> 00:24:06,919
That if you use this signature system
588
00:24:06,919 --> 00:24:09,960
to sign two different messages,
589
00:24:09,960 --> 00:24:13,360
then you might actually allow forgeries.
590
00:24:13,360 --> 00:24:14,620
So let's look, for example,
591
00:24:14,620 --> 00:24:18,100
suppose you sign 11 and you sign 7.
592
00:24:18,100 --> 00:24:20,200
Now what is that signature of 11,
593
00:24:20,200 --> 00:24:22,799
11, uh-oh, I have to do 11 in binary now,
594
00:24:22,799 --> 00:24:27,260
so 11 sounds like 8+2+1.
595
00:24:27,260 --> 00:24:30,990
And you sign 7, which is 4+2+1.
596
00:24:30,990 --> 00:24:32,679
So what if you revealed now?
597
00:24:32,679 --> 00:24:35,510
You reveal the signature on that 8,
598
00:24:35,510 --> 00:24:38,090
so the 3rd bit you revealed
599
00:24:38,090 --> 00:24:41,330
a signature saying, "the 3rd bit is 1"
600
00:24:41,330 --> 00:24:43,390
as part of the signature of 11.
601
00:24:43,390 --> 00:24:45,350
But as part of the signature of 7,
602
00:24:45,350 --> 00:24:47,330
you revealed, you signed a message
603
00:24:47,330 --> 00:24:50,419
saying "the 3rd bit is 0".
604
00:24:50,419 --> 00:24:52,600
And now you can just mix and match
those messages,
605
00:24:52,600 --> 00:24:53,830
wherever the bits were different.
606
00:24:53,830 --> 00:24:56,120
So for instance if you take the top bit
from the 11
607
00:24:56,120 --> 00:24:58,970
and the bottom 3 bits from the 7
608
00:24:58,970 --> 00:25:00,830
then you end up signing 15.
609
00:25:00,830 --> 00:25:02,990
So this signature system,
610
00:25:02,990 --> 00:25:05,870
it's totally safe
if you're signing one message.
611
00:25:05,870 --> 00:25:07,200
But if you think about the data flow,
612
00:25:07,200 --> 00:25:09,510
what does it mean
to sign the individual bits
613
00:25:09,510 --> 00:25:11,270
of two different messages,
614
00:25:11,270 --> 00:25:12,669
then you can get in big trouble.
615
00:25:12,669 --> 00:25:15,809
So this is a one-time signature system.
616
00:25:15,809 --> 00:25:19,140
Alright. Here's how Lamport's
signature system
617
00:25:19,140 --> 00:25:21,110
works for one-time signatures
618
00:25:21,110 --> 00:25:22,919
of any length of message.
619
00:25:22,919 --> 00:25:26,559
First of all, you scale that 4 bits
up to 256 bits.
620
00:25:26,559 --> 00:25:28,600
And then, if you want to sign
whatever length of message,
621
00:25:28,600 --> 00:25:32,460
you just hash the message to 256 bits.
622
00:25:32,460 --> 00:25:34,690
And the code for it is very simple.
623
00:25:34,690 --> 00:25:36,299
This is not quite the state of the art
624
00:25:36,299 --> 00:25:37,540
for one-time signatures,
625
00:25:37,540 --> 00:25:38,630
there's fancier things you can do,
626
00:25:38,630 --> 00:25:41,160
you can sign with Winternitz signatures
627
00:25:41,160 --> 00:25:46,260
and get instead of something
like 256 or 512 hash values
628
00:25:46,260 --> 00:25:47,740
you can compress that down to like
629
00:25:47,740 --> 00:25:49,760
50 or even fewer hash values.
630
00:25:49,760 --> 00:25:52,410
There's all sorts of tricks to
trade space for time
631
00:25:52,410 --> 00:25:53,049
in these systems
632
00:25:53,049 --> 00:25:56,010
but it's totally feasible to deploy
Lamport signatures
633
00:25:56,010 --> 00:26:00,270
and, well, Winternitz makes it
even more practical.
634
00:26:00,270 --> 00:26:02,690
Alright. What about this
one-time restriction?
635
00:26:02,690 --> 00:26:04,110
So these last, the 4-bit,
636
00:26:04,110 --> 00:26:05,980
and the Lamport bigger message system,
637
00:26:05,980 --> 00:26:07,309
these are only usable for,
638
00:26:07,309 --> 00:26:08,790
you can only use your key
639
00:26:08,790 --> 00:26:10,620
to sign one message.
640
00:26:10,620 --> 00:26:13,030
And this was fixed by Merkle.
641
00:26:13,030 --> 00:26:14,690
What Merkle said was,
642
00:26:14,690 --> 00:26:18,980
you take 8 Lamport, for example 8,
it can be any number,
643
00:26:18,980 --> 00:26:20,299
here's how we'll make a public key
644
00:26:20,299 --> 00:26:22,510
that can sign 8 different messages.
645
00:26:22,510 --> 00:26:24,990
You make, well, 8 different Lamport keys
646
00:26:24,990 --> 00:26:26,620
and you concatenate them together
647
00:26:26,620 --> 00:26:28,299
and you use each one just once.
648
00:26:28,299 --> 00:26:31,410
But it's actually more space-efficient
than that sounds.
649
00:26:31,410 --> 00:26:33,130
So here's what you send along.
650
00:26:33,130 --> 00:26:38,780
You make 8 Ss there, those are the secret
Lamport keys,
651
00:26:38,780 --> 00:26:41,130
that are able to each sign one message,
652
00:26:41,130 --> 00:26:43,400
and then you have 8
corresponding public keys,
653
00:26:43,400 --> 00:26:45,490
P1 through P8,
654
00:26:45,490 --> 00:26:48,040
and then you hash together in a tree,
655
00:26:48,040 --> 00:26:52,049
you hash together P1 and P2,
and P3 and P4
656
00:26:52,049 --> 00:26:53,380
to form P9 and P10,
657
00:26:53,380 --> 00:26:55,059
and hash those together to get P13,
658
00:26:55,059 --> 00:26:58,510
and same over here to get
a final public key P15.
659
00:26:58,510 --> 00:27:01,330
So just one hash value, that's your whole
public key.
660
00:27:01,330 --> 00:27:03,679
And then you have to remember
lots of secrets,
661
00:27:03,679 --> 00:27:06,040
but, okay, nobody has to see
those secrets,
662
00:27:06,040 --> 00:27:08,150
you just keep them on your computer.
663
00:27:08,150 --> 00:27:09,270
And now what does it look like to,
664
00:27:09,270 --> 00:27:13,410
to hash, sorry, to sign one message?
665
00:27:13,410 --> 00:27:17,140
Well, here's what it looks like signing
the first message.
666
00:27:17,140 --> 00:27:18,760
That's when you use S1.
667
00:27:18,760 --> 00:27:21,059
Once you use S1, you cross it out,
668
00:27:21,059 --> 00:27:21,940
you never use it again,
669
00:27:21,940 --> 00:27:23,419
you kill the secret.
670
00:27:23,419 --> 00:27:25,910
You sign your message with S1,
671
00:27:25,910 --> 00:27:27,200
and somebody can verify,
672
00:27:27,200 --> 00:27:30,760
if they see the public key P1
for Lamport signatures.
673
00:27:30,760 --> 00:27:32,309
Or whatever one-time signature system
674
00:27:32,309 --> 00:27:33,709
you put at the top.
675
00:27:33,709 --> 00:27:36,870
But, well, your public key
in Merkle systems is P15.
676
00:27:36,870 --> 00:27:40,050
And how does somebody verify that
P1 and P15 are related?
677
00:27:40,050 --> 00:27:44,770
Well, you show them the P2 and the P10
and the P14
678
00:27:44,770 --> 00:27:47,049
that they need to hash together with P1
679
00:27:47,049 --> 00:27:49,990
to get your public key, P15.
680
00:27:49,990 --> 00:27:52,210
Alright, and that's as complicated
681
00:27:52,210 --> 00:27:53,809
as the Merkle signature system gets,
682
00:27:53,809 --> 00:27:55,880
if you want to be able to sign
a million messages,
683
00:27:55,880 --> 00:27:57,340
you have to have a million secrets,
684
00:27:57,340 --> 00:27:59,350
but, again, just put it on
your local hard drive,
685
00:27:59,350 --> 00:28:00,900
you're not worried about the space.
686
00:28:00,900 --> 00:28:03,580
It takes a few moments to generate the key,
687
00:28:03,580 --> 00:28:06,059
but that's also not a problem.
688
00:28:06,059 --> 00:28:07,620
Okay.
689
00:28:07,620 --> 00:28:09,160
Good things about hash-based signatures,
690
00:28:09,160 --> 00:28:10,490
and a few bad things.
691
00:28:10,490 --> 00:28:12,309
Good things: It's post-quantum secure,
692
00:28:12,309 --> 00:28:15,610
we totally understand what hash function
security looks like,
693
00:28:15,610 --> 00:28:19,080
after quantum computers
and before quantum computers,
694
00:28:19,080 --> 00:28:20,730
all you need is a good hash function,
695
00:28:20,730 --> 00:28:21,830
and there's lots of hash functions
696
00:28:21,830 --> 00:28:23,330
which have been thoroughly studied,
697
00:28:23,330 --> 00:28:25,110
so, we're confident they're secure,
698
00:28:25,110 --> 00:28:27,460
SHA-3 was the result of a long competition
699
00:28:27,460 --> 00:28:28,990
with lots of people bashing on it,
700
00:28:28,990 --> 00:28:30,850
and really has no problems.
701
00:28:30,850 --> 00:28:32,220
The public key is very small,
702
00:28:32,220 --> 00:28:34,419
just one hash value.
703
00:28:34,419 --> 00:28:37,360
The security, as I said,
is well-understood.
704
00:28:37,360 --> 00:28:39,840
All the computations are very fast,
705
00:28:39,840 --> 00:28:41,860
and you can already find
standard proposals
706
00:28:41,860 --> 00:28:42,900
for this system.
707
00:28:42,900 --> 00:28:45,679
This is going to be the first standardised
708
00:28:45,679 --> 00:28:50,470
and the first deployed
post-quantum public key system.
709
00:28:50,470 --> 00:28:54,000
On the other hand,
if you look at the signature size,
710
00:28:54,000 --> 00:28:55,380
it's kind of big,
711
00:28:55,380 --> 00:28:56,740
and then the more scary thing
712
00:28:56,740 --> 00:28:59,210
is the statefulness.
713
00:28:59,210 --> 00:29:01,030
That you can only use S1 once,
714
00:29:01,030 --> 00:29:02,850
and then you have to cross it out.
715
00:29:02,850 --> 00:29:05,039
You can only use S2 once, and you have to
cross it out.
716
00:29:05,039 --> 00:29:06,330
What if you clone your VM?
717
00:29:06,330 --> 00:29:08,220
What if you have a backup and restore?
718
00:29:08,220 --> 00:29:11,250
Then, you've forgotten that you've
used S2.
719
00:29:11,250 --> 00:29:12,179
And then you use it again,
720
00:29:12,179 --> 00:29:14,470
and then somebody can forge messages,
721
00:29:14,470 --> 00:29:17,010
just like I was saying before.
722
00:29:17,010 --> 00:29:18,760
Alright, so state is a problem,
723
00:29:18,760 --> 00:29:20,130
actually some of you I'm sure were
724
00:29:20,130 --> 00:29:22,289
in Rutkowska's talk earlier today
725
00:29:22,289 --> 00:29:24,520
you also heard that
state is harmful there.
726
00:29:24,520 --> 00:29:26,910
And the solution:
727
00:29:26,910 --> 00:29:29,969
Eliminate the state!
728
00:29:29,969 --> 00:29:36,360
applause
729
00:29:36,360 --> 00:29:38,360
I think I only have
about three minutes left
730
00:29:38,360 --> 00:29:41,210
for this, this section, well,
this slide,
731
00:29:41,210 --> 00:29:45,450
but, let me try to briefly say, the idea
for getting rid of the state
732
00:29:45,450 --> 00:29:47,929
is, you have, instead of signatures,
733
00:29:47,929 --> 00:29:49,860
you have certificate chains.
734
00:29:49,860 --> 00:29:53,110
So you have whole chain of CAs,
735
00:29:53,110 --> 00:29:55,730
like, as a signer, you build
a whole bunch of CAs,
736
00:29:55,730 --> 00:29:59,300
you build, say, 2^256
certificate authorities.
737
00:29:59,300 --> 00:30:00,990
Now, that's too much computation to do,
738
00:30:00,990 --> 00:30:03,010
but you do it on the fly,
as you need them.
739
00:30:03,010 --> 00:30:04,900
So you say, I'm going to sign
740
00:30:04,900 --> 00:30:08,450
using one of these bottom-level
certificate authorities,
741
00:30:08,450 --> 00:30:10,580
that will sign my actual message.
742
00:30:10,580 --> 00:30:13,200
And now, you don't have to know
anything about any of the others,
743
00:30:13,200 --> 00:30:16,809
you just pick one and use that to
sign your message.
744
00:30:16,809 --> 00:30:19,570
And then it has to be signed
by the parent CA,
745
00:30:19,570 --> 00:30:20,850
and that's signed by the next parent,
746
00:30:20,850 --> 00:30:22,870
and so on, up the tree, to the top level,
747
00:30:22,870 --> 00:30:24,460
only 256 levels.
748
00:30:24,460 --> 00:30:28,200
And then, okay, you have your
certificate chain,
749
00:30:28,200 --> 00:30:30,950
how do you manufacture these
certificate authorities?
750
00:30:30,950 --> 00:30:35,950
Well, a certificate authority is just
some bytes of code on disk,
751
00:30:35,950 --> 00:30:37,450
that's what real CAs are like,
752
00:30:37,450 --> 00:30:39,120
and you do the same thing signing,
753
00:30:39,120 --> 00:30:41,330
and, those bytes of code, you can,
754
00:30:41,330 --> 00:30:46,030
instead of storing the CA as a program
in a configuration file on disk,
755
00:30:46,030 --> 00:30:48,590
you just generate it on the fly
when you need it,
756
00:30:48,590 --> 00:30:52,370
by taking the position of the CA
within this huge tree
757
00:30:52,370 --> 00:30:56,210
and then hashing that together with
some long-term secret.
758
00:30:56,210 --> 00:30:59,419
That one long-term secret
is the only thing you remember.
759
00:30:59,419 --> 00:31:01,809
So you can manufacture CAs on demand
760
00:31:01,809 --> 00:31:03,100
in some huge tree
761
00:31:03,100 --> 00:31:05,570
and have them sign
certificates for each other
762
00:31:05,570 --> 00:31:08,020
only looking at a few CAs that you need
763
00:31:08,020 --> 00:31:11,000
for the particular signature
that you want.
764
00:31:11,000 --> 00:31:12,409
The reason for having this big tree
765
00:31:12,409 --> 00:31:14,030
is that then you're never going
766
00:31:14,030 --> 00:31:17,880
to randomly use the same CA
at the bottom twice.
767
00:31:17,880 --> 00:31:20,470
So the problem of having
one-time signatures
768
00:31:20,470 --> 00:31:21,690
is no longer a problem.
769
00:31:21,690 --> 00:31:24,690
Each CA will only sign one message.
770
00:31:24,690 --> 00:31:26,500
Okay, and this is something where
771
00:31:26,500 --> 00:31:30,309
the original proposal
from Goldreich in 87,
772
00:31:30,309 --> 00:31:32,440
if you use good one-time signatures,
773
00:31:32,440 --> 00:31:33,809
Winternitz and all that stuff,
774
00:31:33,809 --> 00:31:38,250
you get something like 0.6 megs
for a signature.
775
00:31:38,250 --> 00:31:40,760
Now that's a little bit inconvenient,
776
00:31:40,760 --> 00:31:43,130
for comparison, if you do an OS update,
777
00:31:43,130 --> 00:31:45,580
you look at the average
Debian packet size,
778
00:31:45,580 --> 00:31:47,700
then it's 1.2 megs.
779
00:31:47,700 --> 00:31:49,900
And then, there is some
number of signatures
780
00:31:49,900 --> 00:31:53,419
with each update, and some
of them are in packages,
781
00:31:53,419 --> 00:31:55,490
and well, it's not inconceivable
782
00:31:55,490 --> 00:31:57,460
to send 0.6 megs for each signature,
783
00:31:57,460 --> 00:31:58,799
but it's kind of big.
784
00:31:58,799 --> 00:32:00,940
And then if you look at, well,
785
00:32:00,940 --> 00:32:03,470
web pages, say the Alexa top
million web pages,
786
00:32:03,470 --> 00:32:06,860
that average is 1.8 megs.
787
00:32:06,860 --> 00:32:09,150
And again there's several
signatures on the web page,
788
00:32:09,150 --> 00:32:13,159
depending how many sites are providing
graphics for it and so on.
789
00:32:13,159 --> 00:32:14,860
So, 0.6 megs is maybe a problem.
790
00:32:14,860 --> 00:32:17,720
But, okay, we took a look at this and
791
00:32:17,720 --> 00:32:21,520
a bunch of people
made the signature a lot smaller,
792
00:32:21,520 --> 00:32:24,020
0.041 megabytes.
793
00:32:24,020 --> 00:32:27,059
You know how to make a 41-kilobyte
signature sound small:
794
00:32:27,059 --> 00:32:34,250
only 0.041 megabytes for a sphincs 2^128
post-quantum secure signature system.
795
00:32:34,250 --> 00:32:36,080
If you're interested in more about
what sphincs does,
796
00:32:36,080 --> 00:32:39,830
go to sphincs.cr.yp.to
797
00:32:39,830 --> 00:32:41,500
Lange: Alright, so.
798
00:32:41,500 --> 00:32:44,970
Now we have some idea of
how we can do signatures.
799
00:32:44,970 --> 00:32:46,819
And signature's just the thing
800
00:32:46,819 --> 00:32:48,760
that quantum crypto really
really can't do,
801
00:32:48,760 --> 00:32:51,549
I mean, also, locked briefcases,
802
00:32:51,549 --> 00:32:56,039
how do you trust that this is
actually your locked briefcase?
803
00:32:56,039 --> 00:32:58,940
But also, public key crypto is a problem.
804
00:32:58,940 --> 00:33:01,820
So, the one that we recommend
805
00:33:01,820 --> 00:33:03,340
is code-based cryptography,
806
00:33:03,340 --> 00:33:05,250
and code, in this context, is not like
807
00:33:05,250 --> 00:33:07,309
code as in writing a program
808
00:33:07,309 --> 00:33:10,220
but it comes from error-correcting codes.
809
00:33:10,220 --> 00:33:12,140
So when you think about,
say, your computer,
810
00:33:12,140 --> 00:33:13,960
you have RAM in there
811
00:33:13,960 --> 00:33:17,750
and this RAM might get cosmic radiation
812
00:33:17,750 --> 00:33:19,610
or just a bump somewhere,
813
00:33:19,610 --> 00:33:20,730
might forget something.
814
00:33:20,730 --> 00:33:22,280
Or, a more trivial example,
815
00:33:22,280 --> 00:33:25,090
if you order a book, or, nowadays,
816
00:33:25,090 --> 00:33:26,739
order any media,
817
00:33:26,739 --> 00:33:29,280
it has an ISBN number.
818
00:33:29,280 --> 00:33:32,950
This last digit is dependent on
the previous digits.
819
00:33:32,950 --> 00:33:35,080
So they can figure out whether any
of the digits before
820
00:33:35,080 --> 00:33:37,549
was mistransmitted
821
00:33:37,549 --> 00:33:39,360
then then go like, hmm,
822
00:33:39,360 --> 00:33:41,390
that number doesn't exist, try again.
823
00:33:41,390 --> 00:33:44,990
With your ECC RAM it's actually
a little more sophisticated.
824
00:33:44,990 --> 00:33:46,919
So you have your RAM sitting there,
825
00:33:46,919 --> 00:33:50,190
and it stores 64 bits.
826
00:33:50,190 --> 00:33:53,950
But it stores these 64 bits
with some redundancy.
827
00:33:53,950 --> 00:33:57,360
Internally, it has some extra check bits.
828
00:33:57,360 --> 00:34:00,600
It stores 8 extra bits
829
00:34:00,600 --> 00:34:02,080
and those 8 extra bits allow you
830
00:34:02,080 --> 00:34:05,850
to recover the 64
that you're interested in
831
00:34:05,850 --> 00:34:08,190
in case there was some error.
832
00:34:08,190 --> 00:34:09,339
Not in case of a massive error,
833
00:34:09,339 --> 00:34:12,619
not in case somebody
took a screwdriver and hit it,
834
00:34:12,619 --> 00:34:14,639
but if there was just one random bit flip,
835
00:34:14,639 --> 00:34:16,268
you can recover it.
836
00:34:16,268 --> 00:34:18,210
Also, if two bits flip,
837
00:34:18,210 --> 00:34:20,289
you can at least figure out
that there was something
838
00:34:20,289 --> 00:34:22,190
and raise a flag.
839
00:34:22,190 --> 00:34:24,079
So the common scenario in error correction
840
00:34:24,079 --> 00:34:30,319
is that we have a certain number, say, k
bits that we care about
841
00:34:30,319 --> 00:34:34,199
and then in order to be able
to recover those,
842
00:34:34,199 --> 00:34:35,199
to correct those,
843
00:34:35,199 --> 00:34:37,248
we add some redundancy.
844
00:34:37,248 --> 00:34:39,869
So we encapsulate, we encode those k bits
845
00:34:39,869 --> 00:34:41,569
into n bits.
846
00:34:41,569 --> 00:34:44,859
Now, we would like to have those n bits
847
00:34:44,859 --> 00:34:48,109
be not too much larger than k.
848
00:34:48,109 --> 00:34:50,029
We call those the parity check,
849
00:34:50,029 --> 00:34:52,239
so this is like from the old days
where you check
850
00:34:52,239 --> 00:34:55,599
"those two add up to zero,
zero zero zero...
851
00:34:55,599 --> 00:34:58,819
oops! there's one, aha, there must
have been one bit flip."
852
00:34:58,819 --> 00:35:03,630
So parity as in, it has to be
an even number at the end.
853
00:35:03,630 --> 00:35:04,960
If you're talking about more positions
854
00:35:04,960 --> 00:35:07,160
then it's obviously more
than just the parity
855
00:35:07,160 --> 00:35:10,479
but it's parity of some
more complicated equations.
856
00:35:10,479 --> 00:35:17,009
So, if no error occurred, if those 64 bits
in your ECC RAM are just fine,
857
00:35:17,009 --> 00:35:21,969
then all those extra n-k
checks will be okay.
858
00:35:21,969 --> 00:35:25,589
If there was an error,
then something will fail,
859
00:35:25,589 --> 00:35:26,309
raise a flag,
860
00:35:26,309 --> 00:35:29,180
1, 2, 3 of those will not be satisfied,
861
00:35:29,180 --> 00:35:32,170
and depending on this error pattern,
862
00:35:32,170 --> 00:35:36,619
you will be able to recover what
was going wrong in those bits.
863
00:35:36,619 --> 00:35:39,289
It might actually be that
it was your parity check bits.
864
00:35:39,289 --> 00:35:42,289
It might be that one of
those 8 extra bits flipped.
865
00:35:42,289 --> 00:35:45,729
In which case, your 64 bits were just fine
866
00:35:45,729 --> 00:35:49,649
but you don't know this when
you get the error message.
867
00:35:49,649 --> 00:35:51,759
And, if you have a good code,
868
00:35:51,759 --> 00:35:54,359
so the kind of code
that coding theorists study,
869
00:35:54,359 --> 00:35:55,339
then you would like to have
870
00:35:55,339 --> 00:35:59,890
your k pretty large, and the n
not too much larger.
871
00:35:59,890 --> 00:36:02,549
Because that's the amount of storage
872
00:36:02,549 --> 00:36:03,519
you actually have to afford
873
00:36:03,519 --> 00:36:07,339
for just getting this much data out of it.
874
00:36:07,339 --> 00:36:11,400
Now, we get some guarantees
when we design these,
875
00:36:11,400 --> 00:36:14,269
there's a guarantee of getting t errors,
876
00:36:14,269 --> 00:36:15,729
but for most of the codes that we know,
877
00:36:15,729 --> 00:36:17,489
the guarantees are actually worse
878
00:36:17,489 --> 00:36:19,029
than we get in practice,
879
00:36:19,029 --> 00:36:21,729
so if something guarantees you 100 errors,
880
00:36:21,729 --> 00:36:25,750
most of the time,
you can actually correct 203.
881
00:36:25,750 --> 00:36:27,249
Um, to get a little bit further
882
00:36:27,249 --> 00:36:32,930
we actually did to, um, represent
those equations with matrix,
883
00:36:32,930 --> 00:36:37,349
um, not quite this one, sorry.
884
00:36:37,349 --> 00:36:40,569
So, here's our equations.
885
00:36:40,569 --> 00:36:45,440
So, small example,
we would like to encode 4 bits,
886
00:36:45,440 --> 00:36:46,900
k is 4,
887
00:36:46,900 --> 00:36:49,479
and we're adding 3 extra bits.
888
00:36:49,479 --> 00:36:50,809
That's not very efficient,
889
00:36:50,809 --> 00:36:54,789
but it's a very nice example
that one can see.
890
00:36:54,789 --> 00:37:01,339
So, those rows there are
our parity equations.
891
00:37:01,339 --> 00:37:03,160
So let's assume we have those 7 bits,
892
00:37:03,160 --> 00:37:05,549
which add redundancy to it,
893
00:37:05,549 --> 00:37:07,499
then let's translate this first row,
894
00:37:07,499 --> 00:37:10,410
which is 1 0 0 1 1 0 1,
895
00:37:10,410 --> 00:37:13,130
that means we take the first bit,
896
00:37:13,130 --> 00:37:14,690
skip the second and third,
897
00:37:14,690 --> 00:37:16,769
so, have be 0,
898
00:37:16,769 --> 00:37:19,469
and then, bit 3, then the next bit is set
899
00:37:19,469 --> 00:37:23,119
so bit 4, and then bit 6.
900
00:37:23,119 --> 00:37:24,969
Second row, similarly,
we skip the first one,
901
00:37:24,969 --> 00:37:26,859
so there's no bit 0, there's a bit 1,
902
00:37:26,859 --> 00:37:28,479
no bit 2, there's a bit 3,
903
00:37:28,479 --> 00:37:30,759
it was a 1 1 0 column,
904
00:37:30,759 --> 00:37:32,979
and then bit 5 and bit 6,
905
00:37:32,979 --> 00:37:33,930
and similarly.
906
00:37:33,930 --> 00:37:38,279
So we have a nice diagonal
on the left-hand side,
907
00:37:38,279 --> 00:37:41,589
and then the rest is determined
by these equations.
908
00:37:41,589 --> 00:37:44,140
Now let's assume that
something went wrong.
909
00:37:44,140 --> 00:37:46,049
So we have our 7 bits here,
910
00:37:46,049 --> 00:37:48,509
and a few hours later we come back
911
00:37:48,509 --> 00:37:50,630
and want to look at those 7 bits,
912
00:37:50,630 --> 00:37:52,160
we check whether anything went wrong,
913
00:37:52,160 --> 00:37:55,619
we run through this parity check program,
914
00:37:55,619 --> 00:37:58,869
and we actually get a failure pattern.
915
00:37:58,869 --> 00:38:01,790
If everything was fine,
we would have gotten 0 0 0,
916
00:38:01,790 --> 00:38:05,900
but we're getting 1 0 1.
917
00:38:05,900 --> 00:38:08,229
So the first equation doesn't hold,
918
00:38:08,229 --> 00:38:10,219
the second one does hold,
919
00:38:10,219 --> 00:38:13,349
and the third one does not hold.
920
00:38:13,349 --> 00:38:17,239
Okay. Where could this come from?
921
00:38:17,239 --> 00:38:19,239
We're pretty sure that b1 is okay
922
00:38:19,239 --> 00:38:21,569
because otherwise the second
equation would be wrong
923
00:38:21,569 --> 00:38:24,509
because b1 only appears there,
924
00:38:24,509 --> 00:38:25,880
and we're also making the promise
925
00:38:25,880 --> 00:38:27,729
that it would be only one error.
926
00:38:27,729 --> 00:38:29,339
If you have two errors, three errors,
927
00:38:29,339 --> 00:38:31,420
then lots of other combinations
could occur.
928
00:38:31,420 --> 00:38:33,289
But it's much more likely that
one bit flipped
929
00:38:33,289 --> 00:38:36,319
than that a whole bunch
of bits flipped at once.
930
00:38:36,319 --> 00:38:39,779
Okay, so, tracing this
a little bit further,
931
00:38:39,779 --> 00:38:42,739
yes, so the b3 would get
the two first equations,
932
00:38:42,739 --> 00:38:45,059
b4, yes! b4 actually would get
933
00:38:45,059 --> 00:38:48,219
that the first and the third
equations are false.
934
00:38:48,219 --> 00:38:50,809
So by seeing the error pattern 1 0 1,
935
00:38:50,809 --> 00:38:53,229
we know it was b4.
936
00:38:53,229 --> 00:38:55,539
Now this is a very nice and small example,
937
00:38:55,539 --> 00:38:57,710
which doesn't even cover like the ECC RAM,
938
00:38:57,710 --> 00:39:00,680
but it gives you an idea of how to try it.
939
00:39:00,680 --> 00:39:02,089
On the other hand, it also gives you
940
00:39:02,089 --> 00:39:04,549
the idea that you need to do kind of
941
00:39:04,549 --> 00:39:07,369
brute force search it.
942
00:39:07,369 --> 00:39:10,549
So for just n=7, you have to
try up to 7 times.
943
00:39:10,549 --> 00:39:12,410
If you now have two errors,
944
00:39:12,410 --> 00:39:16,309
I would need to try every combination of 2
945
00:39:16,309 --> 00:39:18,090
out of those n.
946
00:39:18,090 --> 00:39:23,880
If I have a n which is like 2000 bits,
really long,
947
00:39:23,880 --> 00:39:27,229
and I tell you there's 100 errors,
948
00:39:27,229 --> 00:39:28,930
so you would need to try every combination
949
00:39:28,930 --> 00:39:31,089
of 100 positions in there.
950
00:39:31,089 --> 00:39:33,569
So that would be a huge number.
951
00:39:33,569 --> 00:39:36,599
That's obviously not a good way
of error correction,
952
00:39:36,599 --> 00:39:37,849
and that's certainly not how
953
00:39:37,849 --> 00:39:39,690
DVDs and whatever else works.
954
00:39:39,690 --> 00:39:41,859
Oh yeah, one bit of maths notation,
955
00:39:41,859 --> 00:39:46,449
so, we call these things,
the parentheses up there, matrix,
956
00:39:46,449 --> 00:39:47,869
and in order to have a shorthand,
957
00:39:47,869 --> 00:39:54,589
because I can't quite put my 2000 bits
times 1000 bits matrix on the page,
958
00:39:54,589 --> 00:39:57,480
I call this thing H,
959
00:39:57,480 --> 00:40:01,239
and boldface b is such a bit vector.
960
00:40:01,239 --> 00:40:04,839
So boldface b is that
bits that I'm storing,
961
00:40:04,839 --> 00:40:08,519
and the combination of
applying this matrix,
962
00:40:08,519 --> 00:40:11,130
wherever is 1, I take the variable,
963
00:40:11,130 --> 00:40:13,059
where there's a 0, I don't write it,
964
00:40:13,059 --> 00:40:15,380
that I write as H times b.
965
00:40:15,380 --> 00:40:16,499
So in maths, if you have seen this,
966
00:40:16,499 --> 00:40:19,549
this is just a matrix times
vector multiplication,
967
00:40:19,549 --> 00:40:24,069
otherwise, just take this as
the instruction of evaluating
968
00:40:24,069 --> 00:40:28,710
this, each row, as a set of equations.
969
00:40:28,710 --> 00:40:31,089
Alright, so, to give this some names,
970
00:40:31,089 --> 00:40:33,920
in coding theory we call c the code word,
971
00:40:33,920 --> 00:40:37,209
so that's an element
which is not compromised,
972
00:40:37,209 --> 00:40:38,299
which will give you 0,
973
00:40:38,299 --> 00:40:40,229
then there might be an error vector,
974
00:40:40,229 --> 00:40:42,180
that's the bits that flip,
975
00:40:42,180 --> 00:40:44,059
and so, when you retrieve the memory
976
00:40:44,059 --> 00:40:45,779
or when you have a transmission,
977
00:40:45,779 --> 00:40:47,089
we call this the received word,
978
00:40:47,089 --> 00:40:50,239
and that's my b from the previous slide.
979
00:40:50,239 --> 00:40:52,259
We do like to save on space,
980
00:40:52,259 --> 00:40:53,420
so when there's this diagonal
981
00:40:53,420 --> 00:40:55,779
which has all 0s down there
982
00:40:55,779 --> 00:40:58,019
we just skip it.
983
00:40:58,019 --> 00:41:05,959
So instead of writing a 7-by-3,
we just write 4 columns and 3 rows.
984
00:41:05,959 --> 00:41:08,200
Now there's lots of stuff
happening in coding theory,
985
00:41:08,200 --> 00:41:10,660
it's a, well, 65 years old topic,
986
00:41:10,660 --> 00:41:13,200
and we can go up to very large matrices,
987
00:41:13,200 --> 00:41:16,119
and for some special codes,
988
00:41:16,119 --> 00:41:17,799
these are the ones that coding theorists
come up with,
989
00:41:17,799 --> 00:41:19,799
we actually have efficient methods.
990
00:41:19,799 --> 00:41:23,359
Much much nicer than taking
every combination of 100 positions
991
00:41:23,359 --> 00:41:26,549
out of 2000 positions.
992
00:41:26,549 --> 00:41:29,200
Of course, if you get too many errors,
993
00:41:29,200 --> 00:41:29,859
you can't correct.
994
00:41:29,859 --> 00:41:32,680
You can only correct up to
whatever the promise is,
995
00:41:32,680 --> 00:41:34,640
plus maybe a little bit later.
996
00:41:34,640 --> 00:41:36,549
But if you don't know
any of the structure,
997
00:41:36,549 --> 00:41:39,380
if you don't know what
the coding theorists put into it,
998
00:41:39,380 --> 00:41:42,729
or if this H matrix got somewhat perturbed
999
00:41:42,729 --> 00:41:47,439
by me giving a slightly
different representation,
1000
00:41:47,439 --> 00:41:50,709
I don't call this b1 anymore,
I call it now b17,
1001
00:41:50,709 --> 00:41:52,150
and let's flip those and so on,
1002
00:41:52,150 --> 00:41:55,250
suddenly it doesn't look like
the code that you're used to.
1003
00:41:55,250 --> 00:41:58,289
If it's a random matrix,
1004
00:41:58,289 --> 00:42:00,200
the best attacks are not quite as bad
1005
00:42:00,200 --> 00:42:02,999
as picking 100 out of 2000,
1006
00:42:02,999 --> 00:42:04,670
but they are close to that,
1007
00:42:04,670 --> 00:42:05,980
they're pretty slow attacks,
1008
00:42:05,980 --> 00:42:08,959
it's an exponential-time algorithm,
1009
00:42:08,959 --> 00:42:11,279
if you have a random matrix.
1010
00:42:11,279 --> 00:42:12,999
And so what we're doing
in code-based crypto
1011
00:42:12,999 --> 00:42:16,009
is to use this difference for encryption.
1012
00:42:16,009 --> 00:42:17,599
Now going back again to the 70s,
1013
00:42:17,599 --> 00:42:21,009
so, basically, yes, the stuff that we're
really confident in
1014
00:42:21,009 --> 00:42:22,829
that it will last another 100 years,
1015
00:42:22,829 --> 00:42:25,299
is the stuff from the 70s that lots of
people have looked at,
1016
00:42:25,299 --> 00:42:27,299
so, McEliece in 1978,
1017
00:42:27,299 --> 00:42:29,779
so just the year after RSA,
1018
00:42:29,779 --> 00:42:35,719
came up with a system
which is using encoding as encryption.
1019
00:42:35,719 --> 00:42:38,369
So your method is,
1020
00:42:38,369 --> 00:42:40,930
you just encode a vector, your message,
1021
00:42:40,930 --> 00:42:42,900
and then you add some errors to it.
1022
00:42:42,900 --> 00:42:44,880
And, if the other side doesn't have
1023
00:42:44,880 --> 00:42:47,379
an efficient algorithm to decode,
1024
00:42:47,379 --> 00:42:49,459
they actually can't break it.
1025
00:42:49,459 --> 00:42:51,700
They're using a special code in there,
1026
00:42:51,700 --> 00:42:53,449
so there's a code from Goppa
1027
00:42:53,449 --> 00:42:56,059
from a few years earlier than that,
1028
00:42:56,059 --> 00:42:58,029
and that code, so far, nobody has found
1029
00:42:58,029 --> 00:43:00,819
any way to take the perturbed,
1030
00:43:00,819 --> 00:43:03,119
this complicated way of representing it,
1031
00:43:03,119 --> 00:43:06,549
and coming up with
efficient decoding algorithm.
1032
00:43:06,549 --> 00:43:10,660
1986, Niederreither came up with
a version of McEliece
1033
00:43:10,660 --> 00:43:13,359
which is smaller,
the code size is smaller,
1034
00:43:13,359 --> 00:43:15,529
the public key size is smaller,
1035
00:43:15,529 --> 00:43:19,180
and we have similar things to
1036
00:43:19,180 --> 00:43:21,239
what you've seen before,
so we have those H matrix,
1037
00:43:21,239 --> 00:43:22,619
we skip the diagonal,
1038
00:43:22,619 --> 00:43:28,499
we just represent this H as our public key
as the remaining part of the matrix,
1039
00:43:28,499 --> 00:43:33,139
the secret key, that's the algorithm
that only I know.
1040
00:43:33,139 --> 00:43:34,769
It's a Goppa code,
1041
00:43:34,769 --> 00:43:35,890
but it's a Goppa code
1042
00:43:35,890 --> 00:43:39,259
and there's many many Goppa codes
for the same size.
1043
00:43:39,259 --> 00:43:40,549
So that's something that Goppa says,
1044
00:43:40,549 --> 00:43:41,829
well, if you want to have Goppa codes
1045
00:43:41,829 --> 00:43:46,969
with 2000 bits
that can correct 200 errors,
1046
00:43:46,969 --> 00:43:47,829
here's how you set it up,
1047
00:43:47,829 --> 00:43:51,200
but there's lots and lots and lots
of choices in there.
1048
00:43:51,200 --> 00:43:52,469
And your encryption is just,
1049
00:43:52,469 --> 00:43:54,910
take an error vector,
1050
00:43:54,910 --> 00:43:57,269
with a fixed number of bits,
1051
00:43:57,269 --> 00:43:59,479
and send me the error pattern of it.
1052
00:43:59,479 --> 00:44:04,049
So the outcome of multiplying H by this e.
1053
00:44:04,049 --> 00:44:05,509
And then we want to use this in crypto,
1054
00:44:05,509 --> 00:44:08,209
so we use the hash of this to encrypt it.
1055
00:44:08,209 --> 00:44:12,329
Um, then Peter Schwabe and
Tung Chou, our PhD student,
1056
00:44:12,329 --> 00:44:14,349
wrote a very efficient
implementation of this
1057
00:44:14,349 --> 00:44:15,729
called mcbits,
1058
00:44:15,729 --> 00:44:17,380
so if you want to have more detail
1059
00:44:17,380 --> 00:44:19,619
on how you could really
use this in practice,
1060
00:44:19,619 --> 00:44:21,350
then go to that url.
1061
00:44:21,350 --> 00:44:23,339
Um, but let me talk a little bit
1062
00:44:23,339 --> 00:44:26,130
about why we are confident in this.
1063
00:44:26,130 --> 00:44:28,180
Code-based crypto is less obvious
than hash-based,
1064
00:44:28,180 --> 00:44:30,420
I mean with hash-based it's like,
1065
00:44:30,420 --> 00:44:32,079
the, all we're doing is, hash.
1066
00:44:32,079 --> 00:44:35,569
A hash function by definition is
something which is one-way.
1067
00:44:35,569 --> 00:44:39,559
For this code-based crypto,
you need to think a little more,
1068
00:44:39,559 --> 00:44:41,170
to have people studying it
1069
00:44:41,170 --> 00:44:44,630
to figure out why this
actually can be secure.
1070
00:44:44,630 --> 00:44:47,619
Now, the attacks, if I may say so,
1071
00:44:47,619 --> 00:44:49,390
started before the cryptosystem
was proposed,
1072
00:44:49,390 --> 00:44:50,999
so it was another hard problem
1073
00:44:50,999 --> 00:44:53,410
that coding theorists were
studying naturally,
1074
00:44:53,410 --> 00:44:56,219
and then McEliece said, hey, we have
this hard problem here,
1075
00:44:56,219 --> 00:44:58,940
decoding a random code is not easy,
1076
00:44:58,940 --> 00:45:01,539
well, actually, afterwards, figuring out,
1077
00:45:01,539 --> 00:45:05,039
well, if you have a really random code,
1078
00:45:05,039 --> 00:45:07,569
even finding out whether there is
a smaller code word is NP-hard.
1079
00:45:07,569 --> 00:45:12,240
And then, once it was a cryptosystem,
1080
00:45:12,240 --> 00:45:14,890
so, Omura, Lee-Brickell, all of those,
1081
00:45:14,890 --> 00:45:17,519
those come after
it was proposed for crypto.
1082
00:45:17,519 --> 00:45:20,529
There's some which have an extra
parenthetic comment,
1083
00:45:20,529 --> 00:45:23,930
those are papers which study
the security of McEliece
1084
00:45:23,930 --> 00:45:25,420
if the attacker has a quantum computer,
1085
00:45:25,420 --> 00:45:27,329
so there's been lots and lots of work
1086
00:45:27,329 --> 00:45:30,420
for studying it
against a classical computer,
1087
00:45:30,420 --> 00:45:31,849
and there's been some work
1088
00:45:31,849 --> 00:45:33,719
studying it against quantum computers.
1089
00:45:33,719 --> 00:45:36,170
It's pretty clear that we can't use Shor,
1090
00:45:36,170 --> 00:45:37,390
but we can use Grover,
1091
00:45:37,390 --> 00:45:42,180
and it's not so easily obvious
how much Grover can give us.
1092
00:45:42,180 --> 00:45:44,359
However, the best that Grover can do
1093
00:45:44,359 --> 00:45:46,519
is basically halve the bit size.
1094
00:45:46,519 --> 00:45:49,140
So we had this AES-128,
leading to 64-bit security,
1095
00:45:49,140 --> 00:45:50,769
so if you're conservative,
1096
00:45:50,769 --> 00:45:54,430
if you want to be like really really
on the secure size,
1097
00:45:54,430 --> 00:45:58,559
then let's assume that we want to go for
pre-quantum security at least 256
1098
00:45:58,559 --> 00:46:02,469
in order to get post-quantum security 128.
1099
00:46:02,469 --> 00:46:04,440
So here are some key sizes,
1100
00:46:04,440 --> 00:46:07,759
so if you're okay with 1000 kilobytes,
1101
00:46:07,759 --> 00:46:14,690
then you're getting something
which is at least 131 post-quantum secure,
1102
00:46:14,690 --> 00:46:17,170
and that's actually very conservative,
1103
00:46:17,170 --> 00:46:20,289
most likely we can go much down
on the key size.
1104
00:46:20,289 --> 00:46:22,049
But that's where more research is needed.
1105
00:46:22,049 --> 00:46:25,660
If you need something where you can get
a guarantee of 100 years security,
1106
00:46:25,660 --> 00:46:27,349
take this one,
1107
00:46:27,349 --> 00:46:28,809
it's not small,
1108
00:46:28,809 --> 00:46:31,650
it's fast, but it's not small,
1109
00:46:31,650 --> 00:46:34,479
and hopefully in 5 years,
less than 5 years,
1110
00:46:34,479 --> 00:46:37,249
they can give you something
which is smaller
1111
00:46:37,249 --> 00:46:39,669
and still as secure.
1112
00:46:39,669 --> 00:46:40,380
djb: Okay.
1113
00:46:40,380 --> 00:46:45,079
There are lots of possibilities for
what the smaller things might be,
1114
00:46:45,079 --> 00:46:47,919
for instance, there's something
called QC-MDPC,
1115
00:46:47,919 --> 00:46:48,930
there's actually lots and lots
1116
00:46:48,930 --> 00:46:50,680
of variations of McEliece
1117
00:46:50,680 --> 00:46:51,599
that people have proposed,
1118
00:46:51,599 --> 00:46:53,849
and some of those variations have held up,
1119
00:46:53,849 --> 00:46:55,109
some of them haven't.
1120
00:46:55,109 --> 00:46:58,479
QC-MDPC is something that has
held up so far,
1121
00:46:58,479 --> 00:47:00,339
but how many people've looked at it,
1122
00:47:00,339 --> 00:47:03,539
and what's going to happen when
more attacks get optimised?
1123
00:47:03,539 --> 00:47:06,039
You can't be trusting something which
1124
00:47:06,039 --> 00:47:09,140
is new or hasn't been studied enough,
1125
00:47:09,140 --> 00:47:10,849
or hasn't been studied
in the right directions,
1126
00:47:10,849 --> 00:47:13,089
you also have to be sceptical
about crypto.
1127
00:47:13,089 --> 00:47:14,949
There's, well, lots of proposals,
1128
00:47:14,949 --> 00:47:17,759
QC-MDPC looks like one of the most
interesting ones,
1129
00:47:17,759 --> 00:47:20,930
that nobody's been able to damage
its security,
1130
00:47:20,930 --> 00:47:23,680
for 2^80 pre-quantum security,
1131
00:47:23,680 --> 00:47:24,819
which is not very good,
1132
00:47:24,819 --> 00:47:26,479
but, just as an example,
1133
00:47:26,479 --> 00:47:30,160
they have 0.6 kilobytes, or 600 bytes,
1134
00:47:30,160 --> 00:47:31,789
for the public key,
1135
00:47:31,789 --> 00:47:34,329
and that's a very reasonable size
for a public key,
1136
00:47:34,329 --> 00:47:35,449
not as small as ECC
1137
00:47:35,449 --> 00:47:37,039
but it's quite tolerable.
1138
00:47:37,039 --> 00:47:38,910
Um, lattice-based crypto,
1139
00:47:38,910 --> 00:47:40,009
there's NTRU, for example,
1140
00:47:40,009 --> 00:47:42,099
that's been around since the 1990s,
1141
00:47:42,099 --> 00:47:44,729
and maybe that's enough time to start
getting confident,
1142
00:47:44,729 --> 00:47:46,690
but, well, again, there's
lattice-based systems
1143
00:47:46,690 --> 00:47:48,079
that get proposed and broken,
1144
00:47:48,079 --> 00:47:52,009
for instance, there's a system from
Smart-Vercauteren in 2009,
1145
00:47:52,009 --> 00:47:54,699
that was, it's not broken pre-quantum,
1146
00:47:54,699 --> 00:47:58,749
but it was shown in 2014-2015,
some follow-up papers,
1147
00:47:58,749 --> 00:48:02,029
to be broken in polynomial time
by a quantum computer.
1148
00:48:02,029 --> 00:48:05,130
So, it's a lattice-based system which
sounded good at the beginning,
1149
00:48:05,130 --> 00:48:08,469
but is definitely not going to be part of
post-quantum cryptography.
1150
00:48:08,469 --> 00:48:09,529
There's multivariate-quadratic,
1151
00:48:09,529 --> 00:48:12,150
now those have
the interesting feature that
1152
00:48:12,150 --> 00:48:15,109
the signatures they provide
can be very very small,
1153
00:48:15,109 --> 00:48:17,289
like, you can have 100-bit signatures
1154
00:48:17,289 --> 00:48:19,239
and still get some reasonable security
1155
00:48:19,239 --> 00:48:20,989
that nobody knows how to break these,
1156
00:48:20,989 --> 00:48:22,759
well, there's lots and lots
of these proposals
1157
00:48:22,759 --> 00:48:24,819
and some of them are broken,
some of them...
1158
00:48:24,819 --> 00:48:27,680
HFEv-, that's a multivariate
quadratic system
1159
00:48:27,680 --> 00:48:31,140
that's been unbroken for 20 years.
1160
00:48:31,140 --> 00:48:32,489
Maybe it will continue holding up,
1161
00:48:32,489 --> 00:48:34,190
but, well, how many people have looked?
1162
00:48:34,190 --> 00:48:36,839
You have to make sure enough people
look at these things.
1163
00:48:36,839 --> 00:48:39,469
The reason we like these
simple systems from the 70s is
1164
00:48:39,469 --> 00:48:40,229
enough people have looked
1165
00:48:40,229 --> 00:48:42,910
but maybe if you've got more serious
performance constraints
1166
00:48:42,910 --> 00:48:44,319
you should look at these other things,
1167
00:48:44,319 --> 00:48:46,359
and of course we are looking at
these other things,
1168
00:48:46,359 --> 00:48:47,660
trying to figure out what's secure,
1169
00:48:47,660 --> 00:48:51,799
and how well we can actually, er,
1170
00:48:51,799 --> 00:48:54,179
choose among all these
different possibilities.
1171
00:48:54,179 --> 00:48:56,139
Something else, just last mention here,
1172
00:48:56,139 --> 00:48:57,299
is isogeny-based,
1173
00:48:57,299 --> 00:48:59,469
this is for people who like
elliptic curves,
1174
00:48:59,469 --> 00:49:02,930
that there is maybe a way to use
elliptic curves post-quantum,
1175
00:49:02,930 --> 00:49:04,289
and this has the interesting feature
1176
00:49:04,289 --> 00:49:07,690
that it does exactly the same data flows
as Diffie-Hellman.
1177
00:49:07,690 --> 00:49:09,599
So everything you're used to doing
with Diffie-Hellman,
1178
00:49:09,599 --> 00:49:11,709
and having, like, a secret key over here
1179
00:49:11,709 --> 00:49:13,109
and a public key over there,
1180
00:49:13,109 --> 00:49:15,940
agree on a shared secret,
1181
00:49:15,940 --> 00:49:18,279
that you can also do with
isogeny-based systems,
1182
00:49:18,279 --> 00:49:20,519
but only a few people
have studied the security
1183
00:49:20,519 --> 00:49:21,999
and maybe this'll also get broken.
1184
00:49:21,999 --> 00:49:25,000
So, a lots more work,
lots more possibilities.
1185
00:49:25,000 --> 00:49:27,969
Last slide, if you're interested
in more information
1186
00:49:27,969 --> 00:49:29,909
here are a few places to look,
1187
00:49:29,909 --> 00:49:32,209
first of all you can go to pqcrypto.org,
1188
00:49:32,209 --> 00:49:36,640
so this is our first survey site
for post-quantum cryptography,
1189
00:49:36,640 --> 00:49:38,269
and the biggest chunk of information there
1190
00:49:38,269 --> 00:49:42,369
is bibliography, and if anybody has
newer papers,
1191
00:49:42,369 --> 00:49:45,539
if you happen to write papers on
post-quantum crypto,
1192
00:49:45,539 --> 00:49:46,989
and you'd like us to add those,
1193
00:49:46,989 --> 00:49:48,119
then just let us know,
1194
00:49:48,119 --> 00:49:51,170
um, and then, well,
we also have on the front page
1195
00:49:51,170 --> 00:49:53,849
things like pointers to all
the PQCrypto conferences,
1196
00:49:53,849 --> 00:49:54,769
that's the main place to look,
1197
00:49:54,769 --> 00:49:57,150
go to pqcrypto.org and follow links to,
1198
00:49:57,150 --> 00:49:59,819
for instance, the February
Japan conference.
1199
00:49:59,819 --> 00:50:02,390
Then pqcrypto.eu.org, that's the main page
1200
00:50:02,390 --> 00:50:05,459
for the EU project that Tanja mentioned,
1201
00:50:05,459 --> 00:50:08,229
which is putting out as it progresses,
1202
00:50:08,229 --> 00:50:09,640
well, it just started this year, but
1203
00:50:09,640 --> 00:50:13,499
it's putting out, soon, free libraries!
1204
00:50:13,499 --> 00:50:16,439
Software libraries, for actually doing
post-quantum cryptography.
1205
00:50:16,439 --> 00:50:18,309
And benchmarking results,
1206
00:50:18,309 --> 00:50:19,199
so you can actually say
1207
00:50:19,199 --> 00:50:21,420
"Yeah, I've got the following performance
constraints here,
1208
00:50:21,420 --> 00:50:23,070
that's what I'm able to use."
1209
00:50:23,070 --> 00:50:25,039
And then in 2017, there's going to be
1210
00:50:25,039 --> 00:50:28,920
a workshop, and a summer school, maybe
it'll be a spring school, we'll see,
1211
00:50:28,920 --> 00:50:34,239
if you're interested in the Twitter feed
for that, then twitter.com/pqc_eu
1212
00:50:34,239 --> 00:50:37,190
and final resource on the slide is you.
1213
00:50:37,190 --> 00:50:40,130
You have the responsibility
if you care about crypto,
1214
00:50:40,130 --> 00:50:42,440
then you have to get used to this stuff.
1215
00:50:42,440 --> 00:50:43,699
You have to learn about hash-based,
1216
00:50:43,699 --> 00:50:47,029
code-based, maybe lattice-based,
multivariate quadratics,
1217
00:50:47,029 --> 00:50:49,529
these are the things which will be
the future of crypto.
1218
00:50:49,529 --> 00:50:53,819
In the future, all of crypto will be
post-quantum crypto,
1219
00:50:53,819 --> 00:50:56,569
because eventually the attackers
will have quantum computers.
1220
00:50:56,569 --> 00:50:58,479
If you want to adapt to that future,
1221
00:50:58,479 --> 00:51:00,369
then, well, take a look at these sytems
1222
00:51:00,369 --> 00:51:02,229
and see, maybe find improvements,
1223
00:51:02,229 --> 00:51:03,519
then, cool, then let us know,
1224
00:51:03,519 --> 00:51:05,539
and, you know, publish papers,
1225
00:51:05,539 --> 00:51:08,299
integrate them into real applications,
networking applications,
1226
00:51:08,299 --> 00:51:09,969
implement the things
that aren't implemented,
1227
00:51:09,969 --> 00:51:10,779
speed them up,
1228
00:51:10,779 --> 00:51:12,840
there's lots of work that
still has to be done.
1229
00:51:12,840 --> 00:51:15,050
That's it, thank you for your attention.
1230
00:51:15,050 --> 00:51:28,799
applause
1231
00:51:28,799 --> 00:51:33,589
Herald: Wow. Now we'll have some
short questions please.
1232
00:51:33,589 --> 00:51:35,660
Because we're a bit late on time.
1233
00:51:35,660 --> 00:51:39,559
Questioners, go around ahead,
there's a mike there,
1234
00:51:39,559 --> 00:51:41,749
talk into it please.
1235
00:51:41,749 --> 00:51:42,910
Can we have mike 1?
1236
00:51:42,910 --> 00:51:45,869
Q: Oh, okay. Uh, quick question.
1237
00:51:45,869 --> 00:51:50,239
So there was this result of
Laszlo Babai that there's a,
1238
00:51:50,239 --> 00:51:56,059
that graph isomorphism has a
quasipolynomial time algorithm,
1239
00:51:56,059 --> 00:52:00,219
um, not really knowing the subject at all,
1240
00:52:00,219 --> 00:52:04,260
there's some very, very
superficial similarities,
1241
00:52:04,260 --> 00:52:08,709
like, that is a hidden subgroup
problem, basically.
1242
00:52:08,709 --> 00:52:11,849
Um, is there going to be any, like,
1243
00:52:11,849 --> 00:52:14,289
is there any indication that the methods
he used in that proof
1244
00:52:14,289 --> 00:52:16,989
are relevant to breaking, like,
1245
00:52:16,989 --> 00:52:20,279
to weakening NTRU or things like this?
1246
00:52:20,279 --> 00:52:25,729
djb: That's a good question. So, the, um,
the graph isomorphism advance now,
1247
00:52:25,729 --> 00:52:27,069
is basically saying,
1248
00:52:27,069 --> 00:52:30,229
so, graph isomorphism is a problem
which was famous as being
1249
00:52:30,229 --> 00:52:32,619
not know to be solvable in polynomial
1250
00:52:32,619 --> 00:52:35,160
or even, like you said,
quasipolynomial time.
1251
00:52:35,160 --> 00:52:38,209
Um, except there were some really good
software algorithms
1252
00:52:38,209 --> 00:52:41,069
which would solve most cases of it,
really quickly.
1253
00:52:41,069 --> 00:52:42,680
There were just some really weird,
1254
00:52:42,680 --> 00:52:43,849
highly symmetric cases,
1255
00:52:43,849 --> 00:52:44,630
that were hard to solve
1256
00:52:44,630 --> 00:52:47,249
and that's what Babai managed
to completely kill now,
1257
00:52:47,249 --> 00:52:49,349
so he's handled all the cases.
1258
00:52:49,349 --> 00:52:51,949
But we try to stay away from
problems like that in crypto,
1259
00:52:51,949 --> 00:52:54,660
so, an example that's very closely
analogous to that is
1260
00:52:54,660 --> 00:52:56,589
what's called support splitting,
1261
00:52:56,589 --> 00:52:58,640
which is a certain type of attack strategy
1262
00:52:58,640 --> 00:53:00,599
against code-based crypto
1263
00:53:00,599 --> 00:53:03,190
if somebody gives away lots of information
1264
00:53:03,190 --> 00:53:05,039
from the legitimate user.
1265
00:53:05,039 --> 00:53:07,199
And that's something where the
support-splitting algorithm
1266
00:53:07,199 --> 00:53:09,420
works in most cases,
1267
00:53:09,420 --> 00:53:12,529
but it kind of fails in some corner cases,
1268
00:53:12,529 --> 00:53:16,079
and, well, we try to stay away from
thinking about this anyway,
1269
00:53:16,079 --> 00:53:18,690
because you just don't want to give
somebody that extra information,
1270
00:53:18,690 --> 00:53:23,249
but if you did, then maybe Babai's
technique could be useful there.
1271
00:53:23,249 --> 00:53:25,739
Herald: Thank you. This talk is not over.
1272
00:53:25,739 --> 00:53:30,009
If you're leaving, which is okay,
please be silent.
1273
00:53:30,009 --> 00:53:33,670
Next question, number 3, no, number 1.
1274
00:53:33,670 --> 00:53:35,779
Q: Uh, hello, thank you for the talk.
1275
00:53:35,779 --> 00:53:40,430
Um, how are the chances to have something
like forward secrecy with that?
1276
00:53:40,430 --> 00:53:43,729
I recognise the last algorithm
has a chance
1277
00:53:43,729 --> 00:53:45,339
to reuse Diffie-Hellman,
1278
00:53:45,339 --> 00:53:47,739
that's possibly the only one?
1279
00:53:47,739 --> 00:53:51,619
Lange: So, if you think that
forward secrecy means Diffie-Hellman,
1280
00:53:51,619 --> 00:53:55,759
you can have forward secrecy
from normal encryption algorithms,
1281
00:53:55,759 --> 00:53:58,249
at the expense of generating
a new key each time.
1282
00:53:58,249 --> 00:54:00,670
You can have forward secrecy with RSA,
1283
00:54:00,670 --> 00:54:03,140
if Alice talking to Bob starts by saying
1284
00:54:03,140 --> 00:54:06,440
"Okay, this is my one-time RSA key,
1285
00:54:06,440 --> 00:54:08,459
and I send this to Bob,
1286
00:54:08,459 --> 00:54:12,609
with a request to encrypt to this key."
1287
00:54:12,609 --> 00:54:16,099
If Alice never reuses this key,
1288
00:54:16,099 --> 00:54:18,170
then this method is forward-secure.
1289
00:54:18,170 --> 00:54:21,039
And similar to how you can
do this with RSA keys,
1290
00:54:21,039 --> 00:54:23,420
you can also do this with McEliece keys.
1291
00:54:23,420 --> 00:54:25,489
At the moment, there is a difficulty
1292
00:54:25,489 --> 00:54:29,449
that the keys are very large.
1293
00:54:29,449 --> 00:54:32,719
It is inconvenient when you want
to start talking,
1294
00:54:32,719 --> 00:54:35,849
"Hey, I'm a client, hello server,
please talk to me",
1295
00:54:35,849 --> 00:54:37,289
and the first thing you have to do
1296
00:54:37,289 --> 00:54:41,900
is transmit a megabyte of key.
1297
00:54:41,900 --> 00:54:44,229
On the other hand, you can do it.
1298
00:54:44,229 --> 00:54:47,719
It just requires you to engineer
your protocol to expect,
1299
00:54:47,719 --> 00:54:50,999
yes, you have to send a few packages.
1300
00:54:50,999 --> 00:54:53,959
And then it has all the
forward secrecy that you want.
1301
00:54:53,959 --> 00:54:58,180
Q: But, uh, a way without
transferring the key,
1302
00:54:58,180 --> 00:54:59,449
like Diffie-Hellman?
1303
00:54:59,449 --> 00:55:02,509
Lange: But, Diffie-Hellman
is transferring a key.
1304
00:55:02,509 --> 00:55:03,259
Q: Okay.
1305
00:55:03,259 --> 00:55:04,989
Lange: I mean, you're basically
transferring
1306
00:55:04,989 --> 00:55:07,349
the first part of a discrete log pair.
1307
00:55:07,349 --> 00:55:10,299
If Alice sends a*p, and there is
some one-time key,
1308
00:55:10,299 --> 00:55:12,219
she's sending a public key.
1309
00:55:12,219 --> 00:55:16,029
It's just that the method of how
those two public keys interact
1310
00:55:16,029 --> 00:55:19,279
is slightly different from how
RSA encryption works.
1311
00:55:19,279 --> 00:55:20,980
Q: Okay, thank you.
1312
00:55:20,980 --> 00:55:25,049
Herald: Thank you. Do we have
an Internet message? Question?
1313
00:55:25,049 --> 00:55:30,170
Signal Angel: Actually, we do. There are
two questions that are somehow related.
1314
00:55:30,170 --> 00:55:31,479
The first one is:
1315
00:55:31,479 --> 00:55:37,299
Given that there is no actual working
quantum computer,
1316
00:55:37,299 --> 00:55:40,619
how do you start developing
a crypto algorithm?
1317
00:55:40,619 --> 00:55:42,410
Where do you start, how do you design it,
1318
00:55:42,410 --> 00:55:46,140
how do you test it? Is there a way
to prove that it's secure?
1319
00:55:46,140 --> 00:55:49,349
And the second question is related:
1320
00:55:49,349 --> 00:55:55,079
The whole thing is based on the property
of the hash functions being one-way,
1321
00:55:55,079 --> 00:55:57,969
how does one know that there is no
quantum algorithm
1322
00:55:57,969 --> 00:55:59,920
that breaks this property?
1323
00:55:59,920 --> 00:56:01,859
Can you prove this?
1324
00:56:01,859 --> 00:56:03,729
djb: Okay. For both of these questions,
1325
00:56:03,729 --> 00:56:06,079
the technique that the community
goes through,
1326
00:56:06,079 --> 00:56:08,189
that we all go through,
is cryptanalysis.
1327
00:56:08,189 --> 00:56:11,219
So we have as many smart people as
we can find
1328
00:56:11,219 --> 00:56:12,989
focusing on these problems and saying
1329
00:56:12,989 --> 00:56:16,549
"Can you find an algorithm which is
breaking these problems
1330
00:56:16,549 --> 00:56:19,069
better than any previous algorithms can?"
1331
00:56:19,069 --> 00:56:20,999
and we put as many incentives as we can
1332
00:56:20,999 --> 00:56:23,099
so that we try to get as many smart people
1333
00:56:23,099 --> 00:56:25,299
to stay ahead of the bad guys,
1334
00:56:25,299 --> 00:56:27,299
and hopefully find the best algorithms.
1335
00:56:27,299 --> 00:56:28,709
But there's no guarantees in this.
1336
00:56:28,709 --> 00:56:30,449
And you do always have to be sceptical
1337
00:56:30,449 --> 00:56:33,140
about whether people have
actually looked at, for instance
1338
00:56:33,140 --> 00:56:35,359
quantum algorithms to attack systems.
1339
00:56:35,359 --> 00:56:36,829
And there is that extra difficulty
1340
00:56:36,829 --> 00:56:39,819
that the first part of the question,
at the beginning, was saying,
1341
00:56:39,819 --> 00:56:41,809
that we don't have a quantum computer.
1342
00:56:41,809 --> 00:56:45,339
So if we're trying to verify quantum
algorithms that we're developing,
1343
00:56:45,339 --> 00:56:47,589
we don't get to experiment with them.
1344
00:56:47,589 --> 00:56:50,549
That's the usual procedure for
making sure your algorithms work.
1345
00:56:50,549 --> 00:56:52,559
In state-of-the-art cryptanalysis,
1346
00:56:52,559 --> 00:56:55,029
like the number field sieve for factoring,
1347
00:56:55,029 --> 00:56:57,880
that does not have a proof that
it works in any particular,
1348
00:56:57,880 --> 00:56:59,789
well, at the speed that we think,
1349
00:56:59,789 --> 00:57:01,349
it works out from experiment.
1350
00:57:01,349 --> 00:57:03,329
So experiments are really important,
1351
00:57:03,329 --> 00:57:05,829
because we don't have proofs
for state-of-the-art cryptanalysis,
1352
00:57:05,829 --> 00:57:09,759
and that's something where it's actually
really tough for quantum computers.
1353
00:57:09,759 --> 00:57:11,859
Of course eventually we'll all have
quantum computers,
1354
00:57:11,859 --> 00:57:14,869
and there's ideas for simulating
quantum algorithms
1355
00:57:14,869 --> 00:57:18,359
which have had some success
at verifying that algorithms work
1356
00:57:18,359 --> 00:57:20,579
even though we can't actually
run them yet.
1357
00:57:20,579 --> 00:57:25,050
That we're actually able to verify
a simulation of those algorithms.
1358
00:57:25,050 --> 00:57:27,530
Lange: Let me do a second part of this.
1359
00:57:27,530 --> 00:57:30,769
Um, when we use quantum cryptanalysis,
1360
00:57:30,769 --> 00:57:33,189
for estimates, we usually go
for the worst-case estimate.
1361
00:57:33,189 --> 00:57:39,230
So we say, well, McEliece, at worst,
gets broken to half the security level.
1362
00:57:39,230 --> 00:57:41,380
Most likely it won't be that fast,
1363
00:57:41,380 --> 00:57:45,609
but we're staying on the side
where we're very confident.
1364
00:57:45,609 --> 00:57:48,349
Um, if I understood correctly
there was also the part of the question,
1365
00:57:48,349 --> 00:57:50,099
how can we test the algorithms?
1366
00:57:50,099 --> 00:57:52,670
If this is for
the constructive algorithms,
1367
00:57:52,670 --> 00:57:54,369
then all the algorithms we analyse,
1368
00:57:54,369 --> 00:57:56,900
all the algorithms we propose
for post-quantum crypto,
1369
00:57:56,900 --> 00:57:59,939
are algorithms that you can run on
your normal computer.
1370
00:57:59,939 --> 00:58:02,309
So, you can test those, you can run those,
1371
00:58:02,309 --> 00:58:04,189
we have benchmarking numbers from those,
1372
00:58:04,189 --> 00:58:07,219
on our current hardware.
1373
00:58:07,219 --> 00:58:12,019
Herald: We'll do two more questions,
please. Number 1.
1374
00:58:12,019 --> 00:58:15,630
Q: Yeah, I got a question on
the practicality of the attacks.
1375
00:58:15,630 --> 00:58:19,150
So, um, if we assume there is
a quantum computer,
1376
00:58:19,150 --> 00:58:21,729
how much time will it take in practice,
1377
00:58:21,729 --> 00:58:22,900
order of magnitude,
1378
00:58:22,900 --> 00:58:25,729
to break, let's say, RSA 2048-bit key?
1379
00:58:25,729 --> 00:58:28,829
Is it on the order of hours,
weeks, months, years?
1380
00:58:28,829 --> 00:58:31,169
Lange: snaps fingers Done.
1381
00:58:31,169 --> 00:58:32,349
Q: Okay, thanks.
1382
00:58:32,349 --> 00:58:32,939
laughter
1383
00:58:32,939 --> 00:58:36,289
djb: That was easy!
Herald: Number 3.
1384
00:58:36,289 --> 00:58:36,869
Q: Okay.
1385
00:58:36,869 --> 00:58:38,599
Herald: Talk into the mike, please.
1386
00:58:38,599 --> 00:58:41,369
Q: Thank you. So, it's very,
very nice to have
1387
00:58:41,369 --> 00:58:45,789
both quantum encryption and signing,
1388
00:58:45,789 --> 00:58:48,650
but do you know anything about
some other cryptographic primitives,
1389
00:58:48,650 --> 00:58:52,499
such as zero-knowledge proofs?
1390
00:58:52,499 --> 00:58:53,499
Lange: Well, I mean, zero-knowledge proofs
1391
00:58:53,499 --> 00:58:56,920
are basically signatures
which are not interactive.
1392
00:58:56,920 --> 00:58:59,580
So if you have something which is, um,
1393
00:58:59,580 --> 00:59:02,249
a primitive for a signature is usually
very closely related
1394
00:59:02,249 --> 00:59:03,789
to zero-knowledge proofs.
1395
00:59:03,789 --> 00:59:05,739
So, there is work going on,
1396
00:59:05,739 --> 00:59:07,680
we are focusing on
the most important things
1397
00:59:07,680 --> 00:59:10,049
that we see on the Internet,
1398
00:59:10,049 --> 00:59:12,579
but, that shouldn't mean that people
shouldn't do research on it.
1399
00:59:12,579 --> 00:59:17,060
Please do research on
zero-knowledge proofs!
1400
00:59:17,060 --> 00:59:21,539
Herald: Okay. Last question. Number 1.
1401
00:59:21,539 --> 00:59:24,859
Q: So, why do you put so much emphasis
1402
00:59:24,859 --> 00:59:28,549
on smaller key sizes and
on performance in encryption,
1403
00:59:28,549 --> 00:59:34,529
um, especially in a delicate topic like
post-quantum computing?
1404
00:59:34,529 --> 00:59:37,269
Why can't we just use 1-megabyte keys
1405
00:59:37,269 --> 00:59:41,859
and why can't we just use a few seconds
instead of miliseconds
1406
00:59:41,859 --> 00:59:43,599
to compute those?
Lange: So...
1407
00:59:43,599 --> 00:59:44,949
Q: What's the the problem here?
1408
00:59:44,949 --> 00:59:47,660
Lange: We are suggesting
to use a key of 1 megabyte.
1409
00:59:47,660 --> 00:59:51,809
So, our recommendation that we have on
the Internet on the pqcrypto.org page
1410
00:59:51,809 --> 00:59:56,180
are precisely using this system
which has a 1-megabyte key.
1411
00:59:56,180 --> 00:59:58,329
The nice thing is, that actually
1412
00:59:58,329 --> 01:00:02,449
encryption and decryption
are very efficient.
1413
01:00:02,449 --> 01:00:03,579
But that was not our main goal,
1414
01:00:03,579 --> 01:00:06,430
our main goal was to get something
which is very secure,
1415
01:00:06,430 --> 01:00:11,329
and where we have a high confidence
that we actually understand the attack.
1416
01:00:11,329 --> 01:00:14,009
And then, well, once we have this system,
1417
01:00:14,009 --> 01:00:17,520
then you try to optimise
how to implement it,
1418
01:00:17,520 --> 01:00:19,279
and the implementation,
when we looked at the numbers
1419
01:00:19,279 --> 01:00:22,039
is actually faster than
elliptic curve implementations
1420
01:00:22,039 --> 01:00:23,910
except for the size.
1421
01:00:23,910 --> 01:00:26,329
So, you get a very nice speed,
1422
01:00:26,329 --> 01:00:31,790
even though it was not our
target for optimisation.
1423
01:00:31,790 --> 01:00:33,379
Herald: Okay, this is it.
1424
01:00:33,379 --> 01:00:35,430
Thank you very much,
let's have a final hand
1425
01:00:35,430 --> 01:00:38,479
for Tanja Lange and djb Bernstein!
1426
01:00:38,479 --> 01:00:46,360
applause
1427
01:00:46,360 --> 01:00:51,397
postroll music
1428
01:00:51,397 --> 01:00:58,000
Untertitel erstellt von c3subtitles.de
im Jahr 2016. Mach mit und hilf uns!