1
00:00:00,000 --> 00:00:09,600
<i>preroll music</i>

2
00:00:09,600 --> 00:00:11,350
Herald: I did some research,

3
00:00:11,350 --> 00:00:12,880
and it was not, not easy

4
00:00:12,880 --> 00:00:15,510
that Diffie-Hellman key exchange

5
00:00:15,510 --> 00:00:17,539
is so much above my pay grade

6
00:00:17,539 --> 00:00:19,879
therefore, I'm going to keep it simple.

7
00:00:19,879 --> 00:00:21,079
Please welcome

8
00:00:21,079 --> 00:00:24,480
we have Alex Halderman from
the University of Michigan,

9
00:00:24,480 --> 00:00:28,799
and Nadia Heninger from
the University of Pennsylvania.

10
00:00:28,799 --> 00:00:32,759
<i>applause</i>

11
00:00:32,759 --> 00:00:37,270
AH: Thank you.

12
00:00:37,270 --> 00:00:38,710
Thank you all so much.

13
00:00:38,710 --> 00:00:43,519
It's wonderful to be back again in 32C3.

14
00:00:43,519 --> 00:00:46,429
I'm Alex Halderman from
the University of Michigan,

15
00:00:46,429 --> 00:00:49,379
here again this year with,

16
00:00:49,379 --> 00:00:51,309
with many of my students from my group

17
00:00:51,309 --> 00:00:54,070
here in the audience also speaking.

18
00:00:54,070 --> 00:00:57,110
We study security in the real world.

19
00:00:57,110 --> 00:01:00,960
So tonight, we have
a very special story to tell you

20
00:01:00,960 --> 00:01:03,670
that I'm very proud to be telling

21
00:01:03,670 --> 00:01:06,260
along with my colleague Nadia Heninger.

22
00:01:06,260 --> 00:01:07,660
We're going to be talking

23
00:01:07,660 --> 00:01:10,890
about discrete log, Diffie-Hellman

24
00:01:10,890 --> 00:01:13,770
and some of the, um,

25
00:01:13,770 --> 00:01:15,790
the research that we've done

26
00:01:15,790 --> 00:01:16,890
over the past year,

27
00:01:16,890 --> 00:01:19,500
try to understand how the NSA

28
00:01:19,500 --> 00:01:21,640
may be breaking so much of the crypto

29
00:01:21,640 --> 00:01:23,740
that we know they're breaking.

30
00:01:23,740 --> 00:01:25,680
Why do we...? So this work is

31
00:01:25,680 --> 00:01:28,840
joint work with a number of co-authors,

32
00:01:28,840 --> 00:01:30,750
with 12 other co-authors,

33
00:01:30,750 --> 00:01:33,570
3 of them are in this room right now,

34
00:01:33,570 --> 00:01:34,750
and I'd ask to stand up

35
00:01:34,750 --> 00:01:35,920
but they said they didn't want to

36
00:01:35,920 --> 00:01:38,210
so please, a quick round of applause

37
00:01:38,210 --> 00:01:39,790
for my co-authors as well.

38
00:01:39,790 --> 00:01:47,980
<i>applause</i>

39
00:01:47,980 --> 00:01:49,790
So, thank you.

40
00:01:49,790 --> 00:01:51,100
So in this very room,

41
00:01:51,100 --> 00:01:53,620
a year ago at 31C3,

42
00:01:53,620 --> 00:01:56,250
Jacob Appelbaum and Laura Poitras

43
00:01:56,250 --> 00:01:59,250
gave a talk, "Reconstructing Narratives",

44
00:01:59,250 --> 00:02:02,860
in which they announced some new results

45
00:02:02,860 --> 00:02:05,450
from the Snowden archives.

46
00:02:05,450 --> 00:02:08,780
They were able to tell us how the NSA,

47
00:02:08,780 --> 00:02:11,920
that the NSA was breaking cryptography

48
00:02:11,920 --> 00:02:15,320
used in widespread online communication.

49
00:02:15,320 --> 00:02:17,660
And, they later published

50
00:02:17,660 --> 00:02:20,890
an article in der Spiegel,

51
00:02:20,890 --> 00:02:23,610
in which the article included documents

52
00:02:23,610 --> 00:02:27,690
that showed indeed the scope of NSA

53
00:02:27,690 --> 00:02:30,410
breaking widely used encryption

54
00:02:30,410 --> 00:02:32,210
was significant.

55
00:02:32,210 --> 00:02:33,750
That NSA is breaking,

56
00:02:33,750 --> 00:02:35,560
maybe not all crypto,

57
00:02:35,560 --> 00:02:38,230
but they're able to break
widely used crypto

58
00:02:38,230 --> 00:02:40,250
from many of the different kinds

59
00:02:40,250 --> 00:02:44,540
of services and protocols we care about.

60
00:02:44,540 --> 00:02:46,400
What the leaks didn't answer

61
00:02:46,400 --> 00:02:49,440
is how NSA is breaking this cryptography

62
00:02:49,440 --> 00:02:51,210
and to a technologist,

63
00:02:51,210 --> 00:02:54,020
well, if we don't know
how they're breaking it,

64
00:02:54,020 --> 00:02:56,970
what can we do to stop it?

65
00:02:56,970 --> 00:02:59,760
So, Nadia and I and our co-authors set out

66
00:02:59,760 --> 00:03:00,780
earlier this year

67
00:03:00,780 --> 00:03:03,550
to try to, through our research,

68
00:03:03,550 --> 00:03:05,780
start answering those questions.

69
00:03:05,780 --> 00:03:08,110
How is NSA likely to be breaking

70
00:03:08,110 --> 00:03:10,100
likely used cryptography,

71
00:03:10,100 --> 00:03:13,330
and what can we and other researchers do

72
00:03:13,330 --> 00:03:15,170
to stop government from being able

73
00:03:15,170 --> 00:03:18,350
to attack the crypto
that all of us depend on?

74
00:03:18,350 --> 00:03:21,130
So, so...
<i>applause</i>

75
00:03:21,130 --> 00:03:24,240
Let's tell the story.

76
00:03:24,240 --> 00:03:28,030
Wait until you see how it ends!

77
00:03:28,030 --> 00:03:30,390
So if I were setting out as the attacker

78
00:03:30,390 --> 00:03:32,140
to break widely used crypto,

79
00:03:32,140 --> 00:03:35,990
well, there's a few different ways
that I could do it.

80
00:03:35,990 --> 00:03:38,040
One branch of the decision tree here

81
00:03:38,040 --> 00:03:40,269
is to attacking the implementations

82
00:03:40,269 --> 00:03:42,470
right, either finding vulnerabilities

83
00:03:42,470 --> 00:03:43,980
or introducing backdoors,

84
00:03:43,980 --> 00:03:46,850
we've all been witnessing over the past

85
00:03:46,850 --> 00:03:50,610
week or so with Juniper and their systems

86
00:03:50,610 --> 00:03:54,040
being compromised.

87
00:03:54,040 --> 00:03:57,290
On the other hand,
there's another prong you could take.

88
00:03:57,290 --> 00:03:59,980
You could try to attack the crypto
algorithms themselves,

89
00:03:59,980 --> 00:04:01,930
the underlying crypto.

90
00:04:01,930 --> 00:04:02,950
And the difference is,

91
00:04:02,950 --> 00:04:04,440
if you're attacking implementations,

92
00:04:04,440 --> 00:04:05,830
you have to make a big investment

93
00:04:05,830 --> 00:04:09,020
in every hardware device
and piece of software

94
00:04:09,020 --> 00:04:10,840
that you're trying to compromise.

95
00:04:10,840 --> 00:04:13,160
If you're attacking the underlying crypto,

96
00:04:13,160 --> 00:04:17,339
you have just one, a one-stop shop

97
00:04:17,339 --> 00:04:21,029
to gain access to,
potentially a very wide swath

98
00:04:21,029 --> 00:04:23,039
of all the crypto in use.

99
00:04:23,039 --> 00:04:25,139
So a small number of algorithms

100
00:04:25,139 --> 00:04:28,229
predominate for both
symmetric cryptography,

101
00:04:28,229 --> 00:04:30,590
things like AES and RC4,

102
00:04:30,590 --> 00:04:32,710
but those particular algorithms anyway,

103
00:04:32,710 --> 00:04:34,509
most cryptographers seem to think

104
00:04:34,509 --> 00:04:35,659
that breaking them,

105
00:04:35,659 --> 00:04:37,300
at least in the general case,

106
00:04:37,300 --> 00:04:39,470
is pretty hard right now.

107
00:04:39,470 --> 00:04:41,300
Instead though, we also have

108
00:04:41,300 --> 00:04:44,199
a very small number of
public key crypto algorithms

109
00:04:44,199 --> 00:04:46,559
that are also in use very widely

110
00:04:46,559 --> 00:04:50,339
for most or all of the protocols
and services we care about.

111
00:04:50,339 --> 00:04:53,059
Things like RSA and Diffie-Hellman.

112
00:04:53,059 --> 00:04:55,779
And here be dragons, as they say,

113
00:04:55,779 --> 00:04:59,520
this is the cryptography that we
and many other cryptographers

114
00:04:59,520 --> 00:05:02,610
think is most likely to be targeted.

115
00:05:02,610 --> 00:05:04,960
So, I'll hand it off to Nadia

116
00:05:04,960 --> 00:05:08,059
to talk about breaking public key.

117
00:05:08,059 --> 00:05:15,170
<i>applause</i>

118
00:05:15,170 --> 00:05:16,819
NH: So, in order to understand

119
00:05:16,819 --> 00:05:19,240
a little bit about
how cryptanalysis works,

120
00:05:19,240 --> 00:05:20,800
I'm going to go all the way back

121
00:05:20,800 --> 00:05:23,349
to the very beginning of
public key cryptography

122
00:05:23,349 --> 00:05:25,460
from the 70s,

123
00:05:25,460 --> 00:05:28,729
and I'll start by explaining
a little bit about RSA.

124
00:05:28,729 --> 00:05:31,670
This is Rivest, Shamir, and Adleman
up on the screen here,

125
00:05:31,670 --> 00:05:33,519
from the 70s, you can tell.

126
00:05:33,519 --> 00:05:35,780
And this is sort of the simple example,

127
00:05:35,780 --> 00:05:37,360
and then we'll talk a little bit more

128
00:05:37,360 --> 00:05:40,900
about the actual
Diffie-Hellman-based cryptanalysis

129
00:05:40,900 --> 00:05:43,270
that we're actually talking about.

130
00:05:43,270 --> 00:05:46,770
So, this the first public-key
crypto algorithm

131
00:05:46,770 --> 00:05:47,800
that was ever published,

132
00:05:47,800 --> 00:05:49,939
and it is still the most widely used

133
00:05:49,939 --> 00:05:52,680
cryptography, public key cryptography
algorithm out there.

134
00:05:52,680 --> 00:05:55,389
That shows you, I guess something
about the naturalness of ideas,

135
00:05:55,389 --> 00:05:56,749
or maybe the lack of progress

136
00:05:56,749 --> 00:05:59,049
that we've had in the past 40 years.

137
00:05:59,049 --> 00:06:03,529
So, here's sort of the textbook version
of RSA encryption,

138
00:06:03,529 --> 00:06:05,020
what we really care about is that...

139
00:06:05,020 --> 00:06:06,639
So, Alice and Bob, they want

140
00:06:06,639 --> 00:06:08,569
to bootstrap communication over

141
00:06:08,569 --> 00:06:09,759
an untrusted channel,

142
00:06:09,759 --> 00:06:12,009
so there's some eavesdropper
in between them

143
00:06:12,009 --> 00:06:13,430
who's intercepting their messages.

144
00:06:13,430 --> 00:06:15,860
And, in order to get around this,

145
00:06:15,860 --> 00:06:17,599
they need to somehow figure out

146
00:06:17,599 --> 00:06:20,979
how to share a key in order to

147
00:06:20,979 --> 00:06:23,129
actually encrypt their communications.

148
00:06:23,129 --> 00:06:25,080
And the way that RSA accomplishes this,

149
00:06:25,080 --> 00:06:30,240
is, Bob here on the right has a public key

150
00:06:30,240 --> 00:06:32,729
which in RSA is e modulus N

151
00:06:32,729 --> 00:06:35,479
which is the product of
two large prime factors,

152
00:06:35,479 --> 00:06:37,589
and he sends this over to Alice,

153
00:06:37,589 --> 00:06:39,339
and Alice uses Bob's public key

154
00:06:39,339 --> 00:06:41,650
to encrypt a message, like a session key,

155
00:06:41,650 --> 00:06:43,430
and send it back to Bob,

156
00:06:43,430 --> 00:06:45,189
and then Bob can decrypt the message,

157
00:06:45,189 --> 00:06:46,340
get the session key,

158
00:06:46,340 --> 00:06:47,860
and they can communicate using

159
00:06:47,860 --> 00:06:49,510
some other symmetric cipher.

160
00:06:49,510 --> 00:06:53,919
So, this is the big picture
of RSA encryption.

161
00:06:53,919 --> 00:06:55,229
The reason that we think

162
00:06:55,229 --> 00:06:58,099
that RSA is secure is because

163
00:06:58,099 --> 00:07:02,869
the best way that we know how to break
an RSA public key

164
00:07:02,869 --> 00:07:04,879
is to factor the modulus,

165
00:07:04,879 --> 00:07:08,159
and as far as we know,
factoring is not very easy.

166
00:07:08,159 --> 00:07:10,860
So, in particular, factoring is

167
00:07:10,860 --> 00:07:11,849
what we hope is something like

168
00:07:11,849 --> 00:07:13,179
a one-way function,

169
00:07:13,179 --> 00:07:14,610
multiplication is easy,

170
00:07:14,610 --> 00:07:17,050
factoring the number into
two pieces again is hard,

171
00:07:17,050 --> 00:07:18,199
in some sense.

172
00:07:18,199 --> 00:07:19,969
And the best algorithm that we have

173
00:07:19,969 --> 00:07:21,189
in the general case, of, say

174
00:07:21,189 --> 00:07:23,719
an RSA modulus that's well-generated,

175
00:07:23,719 --> 00:07:27,110
is called the number field sieve.

176
00:07:27,110 --> 00:07:28,699
So here is the...

177
00:07:28,699 --> 00:07:30,909
this is as bad as technical
as I'm going to get,

178
00:07:30,909 --> 00:07:32,789
and I'm waving my hands vigorously here,

179
00:07:32,789 --> 00:07:34,869
but here's something along the lines of

180
00:07:34,869 --> 00:07:36,419
what the number field sieve algorithm

181
00:07:36,419 --> 00:07:37,919
actually looks like,

182
00:07:37,919 --> 00:07:39,550
so it's a multi-stage algorithm,

183
00:07:39,550 --> 00:07:41,240
it's rather complex,

184
00:07:41,240 --> 00:07:43,479
some stages parallelise very well,

185
00:07:43,479 --> 00:07:44,679
embarrassingly well,

186
00:07:44,679 --> 00:07:47,990
other stages parallelise somewhat
less well,

187
00:07:47,990 --> 00:07:51,189
and so we've got these multiple stages
that we go through,

188
00:07:51,189 --> 00:07:53,479
and at the end of the algorithm,

189
00:07:53,479 --> 00:07:55,189
we discover, we hope, a prime factor

190
00:07:55,189 --> 00:07:59,929
of the number that we're trying to factor.

191
00:07:59,929 --> 00:08:01,579
So, how long does it take to factor?

192
00:08:01,579 --> 00:08:02,710
Here's one answer:

193
00:08:02,710 --> 00:08:04,159
if you ask a number theorist, this is

194
00:08:04,159 --> 00:08:05,589
the answer that they all give you,

195
00:08:05,589 --> 00:08:07,479
they all go through the optimisation,

196
00:08:07,479 --> 00:08:09,679
and they will tell you the answer is

197
00:08:09,679 --> 00:08:11,639
a sub-exponential function in the size

198
00:08:11,639 --> 00:08:13,380
of the number that we're trying to factor.

199
00:08:13,380 --> 00:08:14,559
That I think is not the answer

200
00:08:14,559 --> 00:08:16,740
that you guys are looking for.

201
00:08:16,740 --> 00:08:19,979
So, here's a slightly more
concrete answer.

202
00:08:19,979 --> 00:08:21,679
So, how long does it take to factor

203
00:08:21,679 --> 00:08:23,080
different sizes of keys?

204
00:08:23,080 --> 00:08:25,469
So, for 512-bit RSA,

205
00:08:25,469 --> 00:08:29,979
the first 512-bit RSA modulus
was factored in 1999

206
00:08:29,979 --> 00:08:30,779
by a group of academics,

207
00:08:30,779 --> 00:08:34,179
that took them 6 months
and a few supercomputers,

208
00:08:34,179 --> 00:08:36,789
now you can rent supercomputers
by the hour.

209
00:08:36,789 --> 00:08:38,099
So what does that do?

210
00:08:38,099 --> 00:08:39,679
Well, some students of mine

211
00:08:39,679 --> 00:08:44,099
actually were able to factor
a 512-bit RSA key

212
00:08:44,099 --> 00:08:48,980
for 4 hours and 75 dollars on Amazon EC2.

213
00:08:48,980 --> 00:08:50,830
If you would like to do this too...

214
00:08:50,830 --> 00:08:54,469
<i>applause</i>

215
00:08:54,469 --> 00:08:56,880
So, you can also do this too,

216
00:08:56,880 --> 00:08:59,730
code is online, right here, download it,

217
00:08:59,730 --> 00:09:02,560
send us bug reports, etc.

218
00:09:02,560 --> 00:09:05,370
So, as we go up in key sizes,

219
00:09:05,370 --> 00:09:07,540
768-bit RSA modulus,

220
00:09:07,540 --> 00:09:10,069
estimate, current estimate is

221
00:09:10,069 --> 00:09:12,470
less than 1000 core-years,

222
00:09:12,470 --> 00:09:15,050
and for sort of reasonable-size
academic clusters,

223
00:09:15,050 --> 00:09:19,270
that should take less than
a calendar year to finish, now.

224
00:09:19,270 --> 00:09:22,589
That was,
the first 768-bit RSA factorisation

225
00:09:22,589 --> 00:09:25,440
was done in public in 2009.

226
00:09:25,440 --> 00:09:28,459
So, that gives you some idea
of sort of the progress.

227
00:09:28,459 --> 00:09:31,019
For 1024-bit RSA, nobody has factored

228
00:09:31,019 --> 00:09:32,860
a key of that size in public,

229
00:09:32,860 --> 00:09:34,139
the estimate is probably,

230
00:09:34,139 --> 00:09:36,350
it's about a million core-years,

231
00:09:36,350 --> 00:09:37,610
which is certainly within range

232
00:09:37,610 --> 00:09:41,060
for a large government,

233
00:09:41,060 --> 00:09:43,480
so it is against better recommendations

234
00:09:43,480 --> 00:09:47,539
to use a 1024-bit RSA key size,
at this point.

235
00:09:47,539 --> 00:09:48,660
Current recommendation is to use

236
00:09:48,660 --> 00:09:50,810
a 2048-bit RSA modulus,

237
00:09:50,810 --> 00:09:52,600
with current algorithms,

238
00:09:52,600 --> 00:09:54,110
nobody should ever be able to factor

239
00:09:54,110 --> 00:09:55,360
something at this size,

240
00:09:55,360 --> 00:09:57,769
without some kind of major improvement.

241
00:09:57,769 --> 00:10:02,400
So, there's the big picture for you.

242
00:10:02,400 --> 00:10:05,040
Now move on to Diffie-Hellman.

243
00:10:05,040 --> 00:10:08,870
So, the paper that introduced
Diffie-Hellman

244
00:10:08,870 --> 00:10:11,440
was called "New Directions
in Cryptography",

245
00:10:11,440 --> 00:10:13,959
it's one of the seminal papers
of the 20th century,

246
00:10:13,959 --> 00:10:15,869
how many of you have read this paper?

247
00:10:15,869 --> 00:10:17,629
You should all go read it right now,

248
00:10:17,629 --> 00:10:20,750
I mean not right now, maybe after I talk.

249
00:10:20,750 --> 00:10:22,700
The first sentence of this paper,

250
00:10:22,700 --> 00:10:24,690
written in 1976,

251
00:10:24,690 --> 00:10:28,399
is "We stand today on the brink
of a revolution in cryptography".

252
00:10:28,399 --> 00:10:30,279
This is one of the best opening sentences

253
00:10:30,279 --> 00:10:32,360
of an academic paper I've ever read,

254
00:10:32,360 --> 00:10:36,170
and they were 100% right
about everything they put in the paper.

255
00:10:36,170 --> 00:10:37,860
They laid out the entire foundations

256
00:10:37,860 --> 00:10:41,089
of cryptographic research
for a couple decades,

257
00:10:41,089 --> 00:10:43,269
and to boot they came up with

258
00:10:43,269 --> 00:10:45,660
the first public key exchange,

259
00:10:45,660 --> 00:10:48,230
that is still one of the commonly used

260
00:10:48,230 --> 00:10:50,510
public key methods we

261
00:10:50,510 --> 00:10:51,850
have on the Internet.

262
00:10:51,850 --> 00:10:55,750
So, all that in one paper.

263
00:10:55,750 --> 00:10:58,759
So, the way that
textbook Diffie-Hellman works,

264
00:10:58,759 --> 00:11:00,910
is, you've got a couple of parameters,

265
00:11:00,910 --> 00:11:03,509
you've got a prime p,

266
00:11:03,509 --> 00:11:09,060
and some element g less than p,

267
00:11:09,060 --> 00:11:11,250
you can think,
for concreteness, g is 2.

268
00:11:11,250 --> 00:11:12,760
It's a good number.

269
00:11:12,760 --> 00:11:15,759
And p is some very large prime,

270
00:11:15,759 --> 00:11:18,620
say 1024, 2048-bit prime.

271
00:11:18,620 --> 00:11:20,579
And so Alice and Bob,

272
00:11:20,579 --> 00:11:21,800
same as our previous scenario,

273
00:11:21,800 --> 00:11:23,190
they want to bootstrap communication

274
00:11:23,190 --> 00:11:25,790
in the presence of
an untrusted eavesdropper.

275
00:11:25,790 --> 00:11:26,980
So what they're going to do,

276
00:11:26,980 --> 00:11:29,479
Alice will generate some secret value a,

277
00:11:29,479 --> 00:11:32,259
and she will compute g^a mod p,

278
00:11:32,259 --> 00:11:34,049
and send it over to Bob,

279
00:11:34,049 --> 00:11:36,920
and Bob will compute some secret value b,

280
00:11:36,920 --> 00:11:38,410
and compute g^b mod p,

281
00:11:38,410 --> 00:11:40,089
and send it over to Alice,

282
00:11:40,089 --> 00:11:43,870
the eavesdropper sees the values
g^a and g^b,

283
00:11:43,870 --> 00:11:45,720
can't derive anything useful from those,

284
00:11:45,720 --> 00:11:47,779
but Alice and Bob can individually

285
00:11:47,779 --> 00:11:48,790
take their secrets

286
00:11:48,790 --> 00:11:52,410
and derive the values g^ab mod p,

287
00:11:52,410 --> 00:11:53,819
both the same values.

288
00:11:53,819 --> 00:11:55,680
And that becomes a shared secret,

289
00:11:55,680 --> 00:11:58,250
which they can then use as a session key,

290
00:11:58,250 --> 00:11:59,860
and, you know, switch to AES

291
00:11:59,860 --> 00:12:02,550
and start symmetrically
encrypting their data.

292
00:12:02,550 --> 00:12:05,070
So, that's Diffie-Hellman key exchange.

293
00:12:05,070 --> 00:12:06,470
Used all over the Internet,

294
00:12:06,470 --> 00:12:09,389
one of the commonly used things possible.

295
00:12:09,389 --> 00:12:12,939
So, one of the reasons that people

296
00:12:12,939 --> 00:12:15,499
have been advocating
Diffie-Hellman key exchange recently

297
00:12:15,499 --> 00:12:17,189
over, say, RSA,

298
00:12:17,189 --> 00:12:20,319
is because it can be, it can provide

299
00:12:20,319 --> 00:12:22,470
the property of perfect forward secrecy.

300
00:12:22,470 --> 00:12:23,649
So assuming that Alice and Bob

301
00:12:23,649 --> 00:12:26,720
generate fresh random
secret values a and b

302
00:12:26,720 --> 00:12:28,639
for every single connection,

303
00:12:28,639 --> 00:12:32,600
then if, say, some large government agency

304
00:12:32,600 --> 00:12:34,740
is collecting all of their communications

305
00:12:34,740 --> 00:12:37,290
and later tries to hack into Alice or Bob,

306
00:12:37,290 --> 00:12:38,730
or break one of their keys,

307
00:12:38,730 --> 00:12:40,899
in order to decrypt their communication,

308
00:12:40,899 --> 00:12:44,029
they can't hack into Alice or
Bob's computer later,

309
00:12:44,029 --> 00:12:46,389
and then discover the key

310
00:12:46,389 --> 00:12:47,860
that Alice and Bob used

311
00:12:47,860 --> 00:12:51,080
to generate all the conversations
that they had,

312
00:12:51,080 --> 00:12:53,650
because Alice and Bob have
already forgotten

313
00:12:53,650 --> 00:12:55,160
the keys that they used.

314
00:12:55,160 --> 00:12:56,560
So, as long as Alice and Bob

315
00:12:56,560 --> 00:12:59,969
are generating fresh random
values every time,

316
00:12:59,969 --> 00:13:01,279
those values should reveal nothing

317
00:13:01,279 --> 00:13:04,719
about past or future communications.

318
00:13:04,719 --> 00:13:07,320
So, that's perfect forward secrecy.

319
00:13:07,320 --> 00:13:09,470
And, a lot of people have,

320
00:13:09,470 --> 00:13:11,090
who really know what
they're talking about,

321
00:13:11,090 --> 00:13:13,039
including, unfortunately, me,

322
00:13:13,039 --> 00:13:15,080
on this stage a couple years ago,

323
00:13:15,080 --> 00:13:19,920
have said, "you guys should always use
Diffie-Hellman over RSA key exchange

324
00:13:19,920 --> 00:13:22,590
because of this property of
perfect forward secrecy".

325
00:13:22,590 --> 00:13:24,670
So here's a selection of quotes

326
00:13:24,670 --> 00:13:25,939
that I found on the Internet,

327
00:13:25,939 --> 00:13:27,629
just from googling
"perfect forward secrecy"

328
00:13:27,629 --> 00:13:29,029
and "Diffie-Hellman key exchange",

329
00:13:29,029 --> 00:13:30,839
and you find people saying that

330
00:13:30,839 --> 00:13:33,100
this provides better security,

331
00:13:33,100 --> 00:13:35,699
the NSA can decrypt nothing,

332
00:13:35,699 --> 00:13:40,589
1024-bit Diffie-Hellman is arguably
better than 1024-bit RSA,

333
00:13:40,589 --> 00:13:45,829
and then 1024-bit Diffie-Hellman
is better than any key size for RSA.

334
00:13:45,829 --> 00:13:47,870
This is a selection of friends

335
00:13:47,870 --> 00:13:49,300
and people I respect,

336
00:13:49,300 --> 00:13:52,500
and some also, also some
random people on Stack Overflow,

337
00:13:52,500 --> 00:13:53,999
which is where...

338
00:13:53,999 --> 00:13:55,180
<i>laughter</i>

339
00:13:55,180 --> 00:13:56,149
where we know everybody's actually

340
00:13:56,149 --> 00:13:58,270
getting their recommendations from.

341
00:13:58,270 --> 00:14:00,980
So, there's been wide-scale advocacy

342
00:14:00,980 --> 00:14:03,419
of perfect forward secrecy as

343
00:14:03,419 --> 00:14:05,639
like, the reason that you should
use Diffie-Hellman.

344
00:14:05,639 --> 00:14:09,149
It will protect you against the NSA.

345
00:14:09,149 --> 00:14:13,049
I'm sorry. We were wrong.

346
00:14:13,049 --> 00:14:14,230
And, why were we wrong?

347
00:14:14,230 --> 00:14:15,339
I'm going to tell little bit more

348
00:14:15,339 --> 00:14:17,199
about what the cryptanalysis looks like

349
00:14:17,199 --> 00:14:18,379
for Diffie-Hellman.

350
00:14:18,379 --> 00:14:21,670
So, the underlying problem
that we hope is hard

351
00:14:21,670 --> 00:14:22,779
for the security of Diffie-Hellman

352
00:14:22,779 --> 00:14:24,110
is called discrete log,

353
00:14:24,110 --> 00:14:26,629
it is exactly sort of the problem of

354
00:14:26,629 --> 00:14:30,160
given one of the key exchange values g^a mod p

355
00:14:30,160 --> 00:14:33,059
compute, say, Alice's secret a.

356
00:14:33,059 --> 00:14:34,470
This would allow the attacker

357
00:14:34,470 --> 00:14:35,579
to compute the shared secret

358
00:14:35,579 --> 00:14:39,050
in the same way that Alice did.

359
00:14:39,050 --> 00:14:42,950
And, sort of similar to
factoring and multiplication,

360
00:14:42,950 --> 00:14:44,540
discrete log, we think it's much harder

361
00:14:44,540 --> 00:14:46,550
than modular exponentiation,

362
00:14:46,550 --> 00:14:48,420
the computation that actually

363
00:14:48,420 --> 00:14:50,519
gives you the value g^a mod p.

364
00:14:50,519 --> 00:14:52,810
And the best algorithm that we have

365
00:14:52,810 --> 00:14:54,720
is called the number field sieve.

366
00:14:54,720 --> 00:14:58,049
So, there's a lot of parallels going on here.

367
00:14:58,049 --> 00:14:59,259
So what does the number field sieve

368
00:14:59,259 --> 00:15:00,939
for discrete log look like?

369
00:15:00,939 --> 00:15:05,030
Hopefully this diagram is somewhat
familiar to you by now,

370
00:15:05,030 --> 00:15:06,600
it's a multi-stage algorithm,

371
00:15:06,600 --> 00:15:10,490
it has many of the same
stages as factoring,

372
00:15:10,490 --> 00:15:12,699
you can sort of line them up in parallel,

373
00:15:12,699 --> 00:15:14,949
the last bit looks a little bit different,

374
00:15:14,949 --> 00:15:17,090
but we can sort of ignore that
for the moment.

375
00:15:17,090 --> 00:15:20,160
Okay. So, we have some pictures

376
00:15:20,160 --> 00:15:22,829
of what the number field sieve looks like.

377
00:15:22,829 --> 00:15:24,699
How long does it take?

378
00:15:24,699 --> 00:15:28,720
Answer number 1:
The same answer as factoring.

379
00:15:28,720 --> 00:15:31,379
In case you didn't remember,
here it is again.

380
00:15:31,379 --> 00:15:33,420
This is kind of why everybody
has been saying

381
00:15:33,420 --> 00:15:35,260
"Okay, the security of, you know,

382
00:15:35,260 --> 00:15:36,829
1024-bit Diffie-Hellman key exchange

383
00:15:36,829 --> 00:15:38,959
is about the same as the security of

384
00:15:38,959 --> 00:15:41,059
a 1024-bit RSA key."

385
00:15:41,059 --> 00:15:44,809
It's because we have the same
complicated formula that tells us

386
00:15:44,809 --> 00:15:47,730
how hard it is to break.

387
00:15:47,730 --> 00:15:49,779
The sort of more subtle answer for...

388
00:15:49,779 --> 00:15:51,699
or, not more subtle,
but the more practical answer

389
00:15:51,699 --> 00:15:53,070
for, how secure is it,

390
00:15:53,070 --> 00:15:55,769
is, we can say, well, how long do we think

391
00:15:55,769 --> 00:15:56,959
it will take to actually compute

392
00:15:56,959 --> 00:15:59,910
a discrete log for
commonly used key sizes,

393
00:15:59,910 --> 00:16:01,089
and the answer is,

394
00:16:01,089 --> 00:16:04,600
slightly longer than factoring an
RSA key of equivalent size,

395
00:16:04,600 --> 00:16:09,479
but, not so much longer than an RSA key.

396
00:16:09,479 --> 00:16:12,160
And, the minimum recommended key size

397
00:16:12,160 --> 00:16:14,759
today is 2048 bits.

398
00:16:14,759 --> 00:16:18,019
Okay, so, 2048-bit Diffie-Hellman,

399
00:16:18,019 --> 00:16:22,219
we're good. Great! We can all go home.

400
00:16:22,219 --> 00:16:24,499
Okay. However, okay,

401
00:16:24,499 --> 00:16:26,350
what if you want to break many connections

402
00:16:26,350 --> 00:16:28,829
that use the same public parameter p?

403
00:16:28,829 --> 00:16:30,749
Do you have to go through

404
00:16:30,749 --> 00:16:33,569
this whole computation,

405
00:16:33,569 --> 00:16:35,269
every single, for every single connection

406
00:16:35,269 --> 00:16:36,569
that you want to break?

407
00:16:36,569 --> 00:16:41,100
That was kind of the justification

408
00:16:41,100 --> 00:16:42,550
for perfect forward secrecy,

409
00:16:42,550 --> 00:16:43,949
that every single connection

410
00:16:43,949 --> 00:16:45,920
should be as hard as factoring an RSA key

411
00:16:45,920 --> 00:16:48,259
of the equivalent size.

412
00:16:48,259 --> 00:16:50,489
Except that's not quite the case.

413
00:16:50,489 --> 00:16:51,850
Because if you look at where

414
00:16:51,850 --> 00:16:54,360
the actual target that
we're trying to compute

415
00:16:54,360 --> 00:16:56,730
appears in this plot,

416
00:16:56,730 --> 00:16:58,620
it's only at the very last stage.

417
00:16:58,620 --> 00:17:00,410
So all of this only depends

418
00:17:00,410 --> 00:17:01,979
on the prime p.

419
00:17:01,979 --> 00:17:05,720
So we can actually divide up
the algorithm in two pieces:

420
00:17:05,720 --> 00:17:09,579
A few stages that depend only
on the prime p that we're using,

421
00:17:09,579 --> 00:17:11,640
and then the final computation

422
00:17:11,640 --> 00:17:14,480
that takes the output of this
first precomputation stage,

423
00:17:14,480 --> 00:17:15,520
and that's the only stage

424
00:17:15,520 --> 00:17:17,280
that actually matters,

425
00:17:17,280 --> 00:17:19,450
that actually depends on the target

426
00:17:19,450 --> 00:17:22,610
of our discrete log computation.

427
00:17:22,610 --> 00:17:27,459
So, we're in trouble.

428
00:17:27,459 --> 00:17:29,550
In particular, that means that

429
00:17:29,550 --> 00:17:33,390
if many connections are using
this same prime p,

430
00:17:33,390 --> 00:17:35,650
you can do the precomputation once,

431
00:17:35,650 --> 00:17:37,470
spend a huge amount of effort,

432
00:17:37,470 --> 00:17:39,490
and then the actual effort required

433
00:17:39,490 --> 00:17:43,260
to break individual connections
using those primes

434
00:17:43,260 --> 00:17:46,060
is much, much smaller.

435
00:17:46,060 --> 00:17:48,300
So here's our current estimates,

436
00:17:48,300 --> 00:17:50,430
these are actually somewhat new
from our paper,

437
00:17:50,430 --> 00:17:54,120
of how long the individual log stage
takes in practice,

438
00:17:54,120 --> 00:17:55,810
if you push the primer as far as you can

439
00:17:55,810 --> 00:17:57,680
to make this as fast as possible.

440
00:17:57,680 --> 00:17:59,330
And the answer is basically,

441
00:17:59,330 --> 00:18:01,810
if you're worried about a government,

442
00:18:01,810 --> 00:18:03,540
you better start worrying

443
00:18:03,540 --> 00:18:08,650
for reasonable key sizes
that people are using.

444
00:18:08,650 --> 00:18:11,380
See, so I'll let Alex continue

445
00:18:11,380 --> 00:18:14,520
with the next part of our talk.

446
00:18:14,520 --> 00:18:21,800
<i>applause</i>

447
00:18:21,800 --> 00:18:24,830
So this fact that Nadia just told us

448
00:18:24,830 --> 00:18:27,290
about Diffie-Hellman

449
00:18:27,290 --> 00:18:29,150
and the number field sieve,

450
00:18:29,150 --> 00:18:33,600
this was something that the
mathematical crypto people knew about,

451
00:18:33,600 --> 00:18:35,970
but most of us who did system security,

452
00:18:35,970 --> 00:18:37,610
people like me,

453
00:18:37,610 --> 00:18:40,030
didn't ever get the memo.

454
00:18:40,030 --> 00:18:43,880
So, it's, I'm here in part to apologise

455
00:18:43,880 --> 00:18:45,290
to everyone I've taught

456
00:18:45,290 --> 00:18:48,290
about Diffie-Hellman and cryptanalysis

457
00:18:48,290 --> 00:18:50,010
who didn't get to hear about this,

458
00:18:50,010 --> 00:18:51,000
as we were talking about

459
00:18:51,000 --> 00:18:52,490
perfect forward secrecy.

460
00:18:52,490 --> 00:18:54,840
Right, this fact about the cryptanalysis

461
00:18:54,840 --> 00:18:56,910
and how well it can apply in exactly

462
00:18:56,910 --> 00:18:58,670
the scenario that we're worried about,

463
00:18:58,670 --> 00:19:02,090
this kind of situation
involving mass surveillance,

464
00:19:02,090 --> 00:19:04,670
was news to many of those.

465
00:19:04,670 --> 00:19:06,320
But now that we have that fact,

466
00:19:06,320 --> 00:19:08,040
how can we exploit it,

467
00:19:08,040 --> 00:19:09,870
to try to break Diffie-Hellman,

468
00:19:09,870 --> 00:19:12,080
in scenarios that we all care about?

469
00:19:12,080 --> 00:19:13,020
And we're going to talk about

470
00:19:13,020 --> 00:19:15,960
two scenarios in the talk today.

471
00:19:15,960 --> 00:19:19,130
The first one applies to HTTPS,

472
00:19:19,130 --> 00:19:21,720
to encrypted web connections,

473
00:19:21,720 --> 00:19:24,960
and it applies not only
to government agencies,

474
00:19:24,960 --> 00:19:27,750
but also just to normal
everyday attackers,

475
00:19:27,750 --> 00:19:29,020
with maybe the same resources

476
00:19:29,020 --> 00:19:31,030
that you or I have.

477
00:19:31,030 --> 00:19:35,280
Right, this is a down-to-earth
kind of attack on HTTPS,

478
00:19:35,280 --> 00:19:37,630
and we call it Logjam.

479
00:19:37,630 --> 00:19:39,870
Logjam allows us to break

480
00:19:39,870 --> 00:19:41,740
the HTTPS connections

481
00:19:41,740 --> 00:19:44,070
to many, many popular websites

482
00:19:44,070 --> 00:19:45,800
in modern browsers,

483
00:19:45,800 --> 00:19:48,610
by fooling those browsers into using

484
00:19:48,610 --> 00:19:53,310
1990s-era backdoored crypto.

485
00:19:53,310 --> 00:19:55,680
So where does this backdoored
crypto come from?

486
00:19:55,680 --> 00:19:57,650
This is from the first crypto wars,

487
00:19:57,650 --> 00:19:59,040
back in the 90s,

488
00:19:59,040 --> 00:20:01,330
when my country, the US,

489
00:20:01,330 --> 00:20:04,110
had restrictions on what kind and strength

490
00:20:04,110 --> 00:20:06,680
of cryptography could be exported,

491
00:20:06,680 --> 00:20:08,690
and used by people abroad.

492
00:20:08,690 --> 00:20:10,580
So US companies were prohibited

493
00:20:10,580 --> 00:20:12,570
from exporting products that contained

494
00:20:12,570 --> 00:20:15,960
cryptography that had greater
than a certain strength.

495
00:20:15,960 --> 00:20:18,020
For RSA, that was that the key size

496
00:20:18,020 --> 00:20:21,250
had to be less than or equal to 512 bits,

497
00:20:21,250 --> 00:20:22,840
and for Diffie-Hellman it was that

498
00:20:22,840 --> 00:20:27,400
basically the prime had to be
512 bits or less.

499
00:20:27,400 --> 00:20:28,540
So back in the 90s,

500
00:20:28,540 --> 00:20:29,970
these were constants,

501
00:20:29,970 --> 00:20:31,380
these were strengths of crypto

502
00:20:31,380 --> 00:20:33,730
that were chosen presumably because

503
00:20:33,730 --> 00:20:37,740
they were easy for NSA to break.

504
00:20:37,740 --> 00:20:39,690
So, if you were an American company

505
00:20:39,690 --> 00:20:42,170
making products, like let's say

506
00:20:42,170 --> 00:20:44,830
Netscape Navigator, the web browser

507
00:20:44,830 --> 00:20:50,980
that initiated the first SSL protocol,

508
00:20:50,980 --> 00:20:53,000
you needed some way to be able

509
00:20:53,000 --> 00:20:54,980
to communicate with,

510
00:20:54,980 --> 00:20:56,920
from servers in the US,

511
00:20:56,920 --> 00:20:59,360
to clients, including your own browser,

512
00:20:59,360 --> 00:21:01,070
that you would ship to people abroad,

513
00:21:01,070 --> 00:21:03,120
say, here in Germany.

514
00:21:03,120 --> 00:21:04,870
And so they came up with a way

515
00:21:04,870 --> 00:21:10,660
to use, to have HTTPS automatically select

516
00:21:10,660 --> 00:21:12,880
the appropriate key strength

517
00:21:12,880 --> 00:21:14,430
depending on whether the browser

518
00:21:14,430 --> 00:21:17,470
was able to support
the full-strength cryptography,

519
00:21:17,470 --> 00:21:18,740
or the weakened version

520
00:21:18,740 --> 00:21:20,530
for deployment abroad.

521
00:21:20,530 --> 00:21:22,290
And the way that they did that

522
00:21:22,290 --> 00:21:23,350
was something called

523
00:21:23,350 --> 00:21:26,210
export-grade cipher suites.

524
00:21:26,210 --> 00:21:27,090
So when your browser,

525
00:21:27,090 --> 00:21:29,080
whenever it starts a TLS connection

526
00:21:29,080 --> 00:21:31,380
for an HTTPS URL,

527
00:21:31,380 --> 00:21:32,800
one of the first thing that it does

528
00:21:32,800 --> 00:21:35,540
is, the browser will send to the server

529
00:21:35,540 --> 00:21:37,480
a list of the kinds of cryptography

530
00:21:37,480 --> 00:21:38,930
that it can speak,

531
00:21:38,930 --> 00:21:40,950
these are called cipher suites,

532
00:21:40,950 --> 00:21:44,150
and then the server selects one of those,

533
00:21:44,150 --> 00:21:46,240
that is compatible with
whatever cryptography

534
00:21:46,240 --> 00:21:48,190
the server has available,

535
00:21:48,190 --> 00:21:50,450
and then that negotiated cipher suite

536
00:21:50,450 --> 00:21:53,540
is what's used for the connection.

537
00:21:53,540 --> 00:21:55,210
Now the way that they supported

538
00:21:55,210 --> 00:21:57,890
the 90s-era backdoor crypto

539
00:21:57,890 --> 00:22:01,380
was by having browsers shipped abroad

540
00:22:01,380 --> 00:22:03,370
from the United States that could only

541
00:22:03,370 --> 00:22:06,140
speak a certain subset
of crypto algorithms,

542
00:22:06,140 --> 00:22:07,520
that were limited in strength

543
00:22:07,520 --> 00:22:09,880
to 512 bits or less,

544
00:22:09,880 --> 00:22:11,730
those were the export-grade cipher suites

545
00:22:11,730 --> 00:22:13,870
with the names you see here.

546
00:22:13,870 --> 00:22:18,930
Now, even though no
browser has been shipped

547
00:22:18,930 --> 00:22:21,740
that is limited to only these suites,

548
00:22:21,740 --> 00:22:24,340
since probably 2000-sometime,

549
00:22:24,340 --> 00:22:27,520
when the US relaxed
its export regulations,

550
00:22:27,520 --> 00:22:29,440
there wasn't just any one day

551
00:22:29,440 --> 00:22:33,060
when all of those old browsers

552
00:22:33,060 --> 00:22:35,490
from before that era went away.

553
00:22:35,490 --> 00:22:38,830
So, servers, even now, many servers

554
00:22:38,830 --> 00:22:42,630
will still accept and speak
these weakened cipher suites,

555
00:22:42,630 --> 00:22:45,450
if that's all the browser has available.

556
00:22:45,450 --> 00:22:47,550
Like if you're running an e-commerce site,

557
00:22:47,550 --> 00:22:49,760
right, I'm sure you still want to be able

558
00:22:49,760 --> 00:22:51,430
to speak to any customers

559
00:22:51,430 --> 00:22:54,670
who have 1998-era
Netspace Navigator involved,

560
00:22:54,670 --> 00:22:57,030
otherwise you'd lose some sales, right?

561
00:22:57,030 --> 00:22:59,010
So there was no reason to turn them off,

562
00:22:59,010 --> 00:23:02,050
because no modern browser any more,

563
00:23:02,050 --> 00:23:03,900
now that those restrictions are lifted,

564
00:23:03,900 --> 00:23:06,690
would choose these weakened suites.

565
00:23:06,690 --> 00:23:09,450
Well, that's what we thought, anyway.

566
00:23:09,450 --> 00:23:13,360
So, in, over this past year,

567
00:23:13,360 --> 00:23:15,740
there were two attacks that exploited

568
00:23:15,740 --> 00:23:17,290
these weakened cipher suites,

569
00:23:17,290 --> 00:23:20,710
that found ways to convince
modern browsers

570
00:23:20,710 --> 00:23:23,990
to speak them instead of
full-strength cryptography.

571
00:23:23,990 --> 00:23:26,500
The first was the FREAK attack,

572
00:23:26,500 --> 00:23:28,800
which was revealed in early 2015

573
00:23:28,800 --> 00:23:32,040
by a separate group of authors,

574
00:23:32,040 --> 00:23:34,980
and the FREAK attack was
an implementation flaw

575
00:23:34,980 --> 00:23:38,850
in many modern browsers.

576
00:23:38,850 --> 00:23:40,370
In order to exploit it,

577
00:23:40,370 --> 00:23:42,150
all you need to do is to be able

578
00:23:42,150 --> 00:23:44,220
to relatively inexpensively

579
00:23:44,220 --> 00:23:48,340
factor a 512-bit RSA key.

580
00:23:48,340 --> 00:23:50,070
And, as Nadia has told you,

581
00:23:50,070 --> 00:23:52,760
this is now a matter of maybe 4 hours,

582
00:23:52,760 --> 00:23:55,250
maybe 75 dollars, something like that,

583
00:23:55,250 --> 00:23:57,230
and if you did that, you'd able to break

584
00:23:57,230 --> 00:23:59,640
all the connections coming into

585
00:23:59,640 --> 00:24:01,920
a weak server for a long period of time,

586
00:24:01,920 --> 00:24:06,150
to a server that still spoke
these cipher suites.

587
00:24:06,150 --> 00:24:08,030
So this affected most modern browsers,

588
00:24:08,030 --> 00:24:14,440
and just shy of 10% of Alexa
top million sites that speak HTTPS.

589
00:24:14,440 --> 00:24:16,880
Now that left the Diffie-Hellman

590
00:24:16,880 --> 00:24:18,650
export-grade cipher suites,

591
00:24:18,650 --> 00:24:21,000
which were not affected by FREAK.

592
00:24:21,000 --> 00:24:25,780
But we came up with a paper
in May of this year,

593
00:24:25,780 --> 00:24:27,570
that showed a separate attack,

594
00:24:27,570 --> 00:24:29,180
the Logjam attack,

595
00:24:29,180 --> 00:24:32,000
which is a protocol flaw in TLS,

596
00:24:32,000 --> 00:24:34,450
and affects all modern browsers,

597
00:24:34,450 --> 00:24:38,370
and, similarly, allows you
to downgrade connections

598
00:24:38,370 --> 00:24:40,580
to export-grade Diffie-Hellman,

599
00:24:40,580 --> 00:24:43,010
and then intercept or modify the contents,

600
00:24:43,010 --> 00:24:46,840
if the server speaks and still supports

601
00:24:46,840 --> 00:24:50,840
these export-grade Diffie-Hellman
cipher suites.

602
00:24:50,840 --> 00:24:52,290
So now let me give you

603
00:24:52,290 --> 00:24:55,030
the hopefully brief technical overview

604
00:24:55,030 --> 00:24:57,090
of how the Logjam attack works.

605
00:24:57,090 --> 00:24:59,080
If you've been curious about this,

606
00:24:59,080 --> 00:25:02,840
this is the chance to see it.

607
00:25:02,840 --> 00:25:04,920
So, Logjam is a problem that happens

608
00:25:04,920 --> 00:25:08,460
during the TLS connection handshake.

609
00:25:08,460 --> 00:25:10,200
And the first thing that happens
in the handshake,

610
00:25:10,200 --> 00:25:11,610
at the top of this diagram,

611
00:25:11,610 --> 00:25:13,430
so this is just your browser connecting

612
00:25:13,430 --> 00:25:16,600
to some website, some server
there on the right,

613
00:25:16,600 --> 00:25:19,580
maybe Alice connecting to
her favourite website here.

614
00:25:19,580 --> 00:25:21,560
So the first stage is this client hello,

615
00:25:21,560 --> 00:25:24,520
where, you know, a normal client
is going to say,

616
00:25:24,520 --> 00:25:26,790
I speak various kinds of cryptography,

617
00:25:26,790 --> 00:25:29,650
including full-strength Diffie-Hellman.

618
00:25:29,650 --> 00:25:31,350
The server at that point is going to

619
00:25:31,350 --> 00:25:35,720
respond by picking some cipher suite,

620
00:25:35,720 --> 00:25:37,560
let's say Diffie-Hellman,

621
00:25:37,560 --> 00:25:40,610
and then sending over
its certificate chain,

622
00:25:40,610 --> 00:25:45,280
as well as its Diffie-Hellman
public parameters,

623
00:25:45,280 --> 00:25:47,990
p and g, the server gets to choose them,

624
00:25:47,990 --> 00:25:49,260
as well as g^a.

625
00:25:49,260 --> 00:25:50,820
And then it's going to use

626
00:25:50,820 --> 00:25:54,760
its long-term RSA key that is the thing

627
00:25:54,760 --> 00:25:56,810
that is signed in its certificate,

628
00:25:56,810 --> 00:26:00,210
in order to make a signature on
those Diffie-Hellman parameters.

629
00:26:00,210 --> 00:26:02,130
Okay, then it's going to do...

630
00:26:02,130 --> 00:26:05,390
complete the negotiation, and so on.

631
00:26:05,390 --> 00:26:06,820
In the Logjam attack,

632
00:26:06,820 --> 00:26:08,610
we have a man-in-the-middle attacker,

633
00:26:08,610 --> 00:26:10,970
who's able to modify some
of these messages

634
00:26:10,970 --> 00:26:13,030
as they're going by.

635
00:26:13,030 --> 00:26:14,960
So the first thing the attacker does,

636
00:26:14,960 --> 00:26:17,460
he modifies the client hello message,

637
00:26:17,460 --> 00:26:19,710
to replace all of the different
kinds of cryptography

638
00:26:19,710 --> 00:26:21,640
the client says it supports,

639
00:26:21,640 --> 00:26:24,560
and just put in export-grade
Diffie-Hellman.

640
00:26:24,560 --> 00:26:27,240
Ah, the 90s are here again.

641
00:26:27,240 --> 00:26:29,920
Alright, so then, you know, the server

642
00:26:29,920 --> 00:26:32,790
will get that, and if the server supports

643
00:26:32,790 --> 00:26:34,850
export-grade Diffie-Hellman,

644
00:26:34,850 --> 00:26:39,180
as about 10% or so of servers

645
00:26:39,180 --> 00:26:41,070
still support export grade Diffie-Hellman,

646
00:26:41,070 --> 00:26:43,670
it's going to respond and say,

647
00:26:43,670 --> 00:26:46,110
okay, that's what you asked for,
I'll take it,

648
00:26:46,110 --> 00:26:49,100
and it's going to send over its side

649
00:26:49,100 --> 00:26:51,270
of the Diffie-Hellman key exchange,

650
00:26:51,270 --> 00:26:54,170
but using a 512-bit prime,

651
00:26:54,170 --> 00:26:56,550
because that's what is required under

652
00:26:56,550 --> 00:26:59,500
these export-grade suites.

653
00:26:59,500 --> 00:27:02,400
Now, at that point, the browser would

654
00:27:02,400 --> 00:27:04,600
normally reject this message,

655
00:27:04,600 --> 00:27:06,540
because it didn't ask for export-grade,

656
00:27:06,540 --> 00:27:09,770
it really asked for full-strength,

657
00:27:09,770 --> 00:27:11,540
so instead, the man in the middle has to

658
00:27:11,540 --> 00:27:15,500
modify the server's hello message,

659
00:27:15,500 --> 00:27:18,270
and say that this is full-strength
Diffie-Hellman,

660
00:27:18,270 --> 00:27:19,630
well, if it's full-strength,

661
00:27:19,630 --> 00:27:22,970
why is it only a 512-bit prime
that's being used?

662
00:27:22,970 --> 00:27:25,780
Well, there's actually no limitation,

663
00:27:25,780 --> 00:27:27,820
and no distinction between the messages

664
00:27:27,820 --> 00:27:33,550
that the server would send
in that space with p and g,

665
00:27:33,550 --> 00:27:35,980
that says normal-grade Diffie-Hellman

666
00:27:35,980 --> 00:27:38,410
has to be more than 512 bits.

667
00:27:38,410 --> 00:27:41,110
In fact we found a handful of real sites

668
00:27:41,110 --> 00:27:43,480
that even for normal-strength 
Diffie-Hellman

669
00:27:43,480 --> 00:27:48,540
just happened to use 512-bit
or even weaker cryptography.

670
00:27:48,540 --> 00:27:50,960
So, as long as we modify
this earlier message,

671
00:27:50,960 --> 00:27:52,680
the server's hello message,

672
00:27:52,680 --> 00:27:55,240
and make it say, "normal-strength
Diffie-Hellman",

673
00:27:55,240 --> 00:27:57,460
there's no way for the client to tell

674
00:27:57,460 --> 00:27:59,420
from just the structure of the protocol,

675
00:27:59,420 --> 00:28:01,460
that anything is amiss.

676
00:28:01,460 --> 00:28:04,570
So, at this point, there is one last place

677
00:28:04,570 --> 00:28:06,130
that we could catch the problem,

678
00:28:06,130 --> 00:28:07,850
that the client or the server could see

679
00:28:07,850 --> 00:28:09,670
that something's wrong,

680
00:28:09,670 --> 00:28:12,800
which is that each side sends
the other a finished message,

681
00:28:12,800 --> 00:28:15,010
here at the end,

682
00:28:15,010 --> 00:28:22,100
that says, basically, has, uses
the session secrets

683
00:28:22,100 --> 00:28:25,020
to add an authentication code

684
00:28:25,020 --> 00:28:27,750
to a dialogue of all of the
protocol messages

685
00:28:27,750 --> 00:28:30,370
that match the handshake dialogue,

686
00:28:30,370 --> 00:28:34,090
all the messages going back
in each direction so far

687
00:28:34,090 --> 00:28:37,280
have to be the same from each side of you.

688
00:28:37,280 --> 00:28:40,300
However, in our case, in Logjam,

689
00:28:40,300 --> 00:28:43,170
the attacker is able to spoof
these messages,

690
00:28:43,170 --> 00:28:45,730
to make them look correct to each side.

691
00:28:45,730 --> 00:28:48,370
He's able to modify that dialogue why?

692
00:28:48,370 --> 00:28:52,900
Well, because we're using this
512-bit Diffie-Hellman

693
00:28:52,900 --> 00:28:58,150
that we know from using
the number field sieve,

694
00:28:58,150 --> 00:29:00,270
we are able to efficiently break.

695
00:29:00,270 --> 00:29:02,730
So, if the attacker is able to quickly

696
00:29:02,730 --> 00:29:03,990
perform the discrete log

697
00:29:03,990 --> 00:29:08,560
on the Diffie-Hellman key exchange

698
00:29:08,560 --> 00:29:11,430
that's going by at 512-bit strength,

699
00:29:11,430 --> 00:29:14,610
then he can fix up the client
and server hello messages,

700
00:29:14,610 --> 00:29:17,380
and neither side will notice
that anything went wrong.

701
00:29:17,380 --> 00:29:19,290
So that's Logjam in a nutshell.

702
00:29:19,290 --> 00:29:21,790
I'm sorry, it's a little bit complicated.

703
00:29:21,790 --> 00:29:24,680
So, how widely shared are

704
00:29:24,680 --> 00:29:27,500
these Diffie-Hellman public parameters?

705
00:29:27,500 --> 00:29:30,850
Well, we used Internet-wide
scanning to find out.

706
00:29:30,850 --> 00:29:33,640
So, my group, we also made
something called zmap,

707
00:29:33,640 --> 00:29:35,810
that I talked about here
a couple of years ago,

708
00:29:35,810 --> 00:29:39,010
which lets us quickly probe
everything on the Internet,

709
00:29:39,010 --> 00:29:42,210
and so we did this and tried to make

710
00:29:42,210 --> 00:29:44,480
connections to each HTTPS server

711
00:29:44,480 --> 00:29:46,850
in the public IPv4 address space,

712
00:29:46,850 --> 00:29:49,590
and found out what key exchange methods

713
00:29:49,590 --> 00:29:52,280
were supported and with what primes.

714
00:29:52,280 --> 00:29:56,120
And what we find is that 97% of hosts

715
00:29:56,120 --> 00:29:58,470
that support export-grade Diffie-Hellman

716
00:29:58,470 --> 00:30:01,130
use one of only 3 512-bit primes.

717
00:30:01,130 --> 00:30:02,930
They're that widely-shared.

718
00:30:02,930 --> 00:30:04,840
Why is this? Because those parameters

719
00:30:04,840 --> 00:30:06,720
are very often either hard-coded

720
00:30:06,720 --> 00:30:08,160
or encoded in standards

721
00:30:08,160 --> 00:30:10,040
that different people implement.

722
00:30:10,040 --> 00:30:11,680
The most common of these,

723
00:30:11,680 --> 00:30:15,100
used by 80% of hosts that support
export-grade Diffie-Hellman,

724
00:30:15,100 --> 00:30:20,760
is a public parameter that's
hardcoded into Apache 2.2.

725
00:30:20,760 --> 00:30:23,160
So, it's actually there,
embedded in the source,

726
00:30:23,160 --> 00:30:26,100
you have to recompile Apache to change it.

727
00:30:26,100 --> 00:30:28,500
13% of hosts supported something,

728
00:30:28,500 --> 00:30:31,850
a second prime that has also 512 bits,

729
00:30:31,850 --> 00:30:34,770
that's hardcoded in mod_ssl,

730
00:30:34,770 --> 00:30:37,260
and the next most popular, 4%,

731
00:30:37,260 --> 00:30:40,050
was in the Sun JDK.

732
00:30:40,050 --> 00:30:43,270
Only 10 primes accounted for 99%

733
00:30:43,270 --> 00:30:45,270
of all the hosts we found in
the public address space

734
00:30:45,270 --> 00:30:49,090
that supported export-grade
Diffie-Hellman.

735
00:30:49,090 --> 00:30:54,370
So, if we would like to compromise these,

736
00:30:54,370 --> 00:30:56,900
well, Nadia just told you about

737
00:30:56,900 --> 00:31:01,870
how long it takes to use
the number field sieve

738
00:31:01,870 --> 00:31:05,050
to break 512-bit discrete log,

739
00:31:05,050 --> 00:31:08,480
well, we actually went and did
the precomputation

740
00:31:08,480 --> 00:31:13,140
for all 3 of these most widely used
Diffie-Hellman primes,

741
00:31:13,140 --> 00:31:18,760
and our colleagues who make a tool
called CADO-NFS

742
00:31:18,760 --> 00:31:22,180
where able to implement the code

743
00:31:22,180 --> 00:31:28,450
for that piece of the discrete log version
of the number field sieve

744
00:31:28,450 --> 00:31:30,960
and they ran the algorithm on these primes

745
00:31:30,960 --> 00:31:34,080
on a cluster they just happened
to have lying around,

746
00:31:34,080 --> 00:31:37,800
it took about a week of time
on the cluster

747
00:31:37,800 --> 00:31:39,570
for each of these primes.

748
00:31:39,570 --> 00:31:41,980
After which, using an optimised version

749
00:31:41,980 --> 00:31:45,040
of the last portion of
the number field sieve,

750
00:31:45,040 --> 00:31:47,530
it takes about 70 seconds for us to break

751
00:31:47,530 --> 00:31:49,470
any individual connection

752
00:31:49,470 --> 00:31:54,330
that uses any one of these
3 most popular primes.

753
00:31:54,330 --> 00:31:57,090
So, Logjam and our precomputations

754
00:31:57,090 --> 00:31:59,100
now allow us to break any connection

755
00:31:59,100 --> 00:32:04,670
to about 8% of the top million
HTTPS sites from Alexa

756
00:32:04,670 --> 00:32:07,920
and when we came up with this attack,

757
00:32:07,920 --> 00:32:10,950
it worked in all modern browsers.

758
00:32:10,950 --> 00:32:12,530
So, mitigation!

759
00:32:12,530 --> 00:32:19,280
<i>applause</i>

760
00:32:19,280 --> 00:32:21,770
This is bad, everyone, this is the crypto

761
00:32:21,770 --> 00:32:24,740
all of us are using.

762
00:32:24,740 --> 00:32:26,560
So we do have some mitigations.

763
00:32:26,560 --> 00:32:28,340
This is the actual positive part,

764
00:32:28,340 --> 00:32:29,840
is that the browser makers have now

765
00:32:29,840 --> 00:32:32,900
started to increase the minimum strength

766
00:32:32,900 --> 00:32:34,860
of Diffie-Hellman they will accept.

767
00:32:34,860 --> 00:32:37,010
So IE, Chrome, and Firefox will reject

768
00:32:37,010 --> 00:32:38,750
primes less than 1024 bits

769
00:32:38,750 --> 00:32:41,200
and Safari less than 768.

770
00:32:41,200 --> 00:32:43,980
And the new draft of TLS 1.3 is including

771
00:32:43,980 --> 00:32:45,200
an anti-downgrade flag

772
00:32:45,200 --> 00:32:46,690
that will make it even harder

773
00:32:46,690 --> 00:32:49,750
for such attacks to take place
in the future.

774
00:32:49,750 --> 00:32:52,140
Now back to Nadia.

775
00:32:52,140 --> 00:32:54,240
NH: So we promised in our abstract...

776
00:32:54,240 --> 00:32:59,600
<i>applause</i>

777
00:32:59,600 --> 00:33:02,190
...that there would be a hands-on
portion of this talk.

778
00:33:02,190 --> 00:33:03,570
So, you have a couple options,

779
00:33:03,570 --> 00:33:05,580
number 1 is, if you're really into this,

780
00:33:05,580 --> 00:33:08,230
you can do and download
CADO-NFS yourselves,

781
00:33:08,230 --> 00:33:11,770
cado-nfs.gforge.inria.fr

782
00:33:11,770 --> 00:33:16,440
and, you know, run
discrete log algorithms yourselves

783
00:33:16,440 --> 00:33:17,790
for any prime you wish

784
00:33:17,790 --> 00:33:20,030
and then you can compute
arbitrary discrete logs.

785
00:33:20,030 --> 00:33:21,700
However, since we have already done

786
00:33:21,700 --> 00:33:22,820
some of the computations,

787
00:33:22,820 --> 00:33:25,200
we figured that we would make
them available for you guys

788
00:33:25,200 --> 00:33:26,930
if you wanted to play with them.

789
00:33:26,930 --> 00:33:32,590
So...
<i>applause</i>

790
00:33:32,590 --> 00:33:36,170
We have done so through the Twitter API,

791
00:33:36,170 --> 00:33:39,150
so we have a bot running on Twitter

792
00:33:39,150 --> 00:33:40,580
and if you would like to compute

793
00:33:40,580 --> 00:33:45,110
discrete logs for any of these
widely-used parameters,

794
00:33:45,110 --> 00:33:48,240
this bot will do so for you.

795
00:33:48,240 --> 00:33:52,910
So here is the group generator
and the primes in hexadecimal,

796
00:33:52,910 --> 00:33:56,910
for the 3 groups that we
did the precomputation for.

797
00:33:56,910 --> 00:33:59,290
And if you wanted to test out,

798
00:33:59,290 --> 00:34:00,590
you would do something like this,

799
00:34:00,590 --> 00:34:01,810
so this using Sage,

800
00:34:01,810 --> 00:34:04,910
which is a Python-based open source
mathematics package,

801
00:34:04,910 --> 00:34:06,760
that does a lot of algebra
and number theory,

802
00:34:06,760 --> 00:34:08,290
if you like playing with the stuff,

803
00:34:08,290 --> 00:34:09,429
sage is super cool,

804
00:34:09,429 --> 00:34:15,500
so, I said, say, my prime m
is this last value in hex there,

805
00:34:15,500 --> 00:34:16,860
the mod_ssl prime,

806
00:34:16,860 --> 00:34:23,780
then I take 2 and raise it to
the 0x1337 power mod m,

807
00:34:23,780 --> 00:34:26,189
and then I print it out in hexadecimal,

808
00:34:26,189 --> 00:34:35,230
and I get this value, then I can
copy-paste it into a tweet @DLogBot

809
00:34:35,230 --> 00:34:39,050
then some comp stuff happens
on our back end,

810
00:34:39,050 --> 00:34:40,889
this is running on one of
the machines in my lab,

811
00:34:40,889 --> 00:34:43,530
so please don't break it,

812
00:34:43,530 --> 00:34:46,550
and after a minute or two,

813
00:34:46,550 --> 00:34:49,019
you should get back an answer.

814
00:34:49,019 --> 00:34:58,310
<i>applause</i>

815
00:34:58,310 --> 00:35:01,520
So, there's a queue,
only one thing can run at a time,

816
00:35:01,520 --> 00:35:02,990
median time is 70 seconds,

817
00:35:02,990 --> 00:35:06,260
it can vary between
30 seconds and 3 minutes,

818
00:35:06,260 --> 00:35:08,830
so, you know, if it doesn't respond to you

819
00:35:08,830 --> 00:35:12,470
within like, you know, an hour
or something,

820
00:35:12,470 --> 00:35:15,760
then send us a ping and we'll see
if it's still running.

821
00:35:15,760 --> 00:35:18,300
Okay. So, have fun.

822
00:35:18,300 --> 00:35:21,480
Please don't actually use this for malice.

823
00:35:21,480 --> 00:35:27,540
<i>applause</i>

824
00:35:27,540 --> 00:35:30,230
We already have some satisfied customers.

825
00:35:30,230 --> 00:35:33,970
<i>laughter</i>

826
00:35:33,970 --> 00:35:35,790
AH: Alright, so we promised there were

827
00:35:35,790 --> 00:35:39,400
two exploits that have to do with
weakened Diffie-Hellman,

828
00:35:39,400 --> 00:35:41,750
and the first, Logjam, right, anyone can

829
00:35:41,750 --> 00:35:43,410
use backdoors from the 90s

830
00:35:43,410 --> 00:35:45,480
to pwn modern browsers,

831
00:35:45,480 --> 00:35:49,200
well, the second one is
a little bit more widespread.

832
00:35:49,200 --> 00:35:50,810
So, we're going to talk about

833
00:35:50,810 --> 00:35:53,330
how Diffie-Hellman weaknesses

834
00:35:53,330 --> 00:35:56,150
can be used for mass surveillance.

835
00:35:56,150 --> 00:35:58,280
We believe that governments can probably

836
00:35:58,280 --> 00:36:03,280
already right now, exploit
1024-bit discrete log

837
00:36:03,280 --> 00:36:08,050
to break Diffie-Hellman for
wide-scale passive decryption

838
00:36:08,050 --> 00:36:10,850
of Internet communications.

839
00:36:10,850 --> 00:36:13,970
So, is breaking 1024-bit Diffie-Hellman

840
00:36:13,970 --> 00:36:15,390
within the reach of governments,

841
00:36:15,390 --> 00:36:17,970
let's look back at these numbers quickly.

842
00:36:17,970 --> 00:36:22,300
So we can see that for 512-bit RSA
and Diffie-Hellman,

843
00:36:22,300 --> 00:36:26,090
they're both really in reach of
basically any effort right now,

844
00:36:26,090 --> 00:36:27,670
any one of you can probably,

845
00:36:27,670 --> 00:36:30,210
most of the resources to do this.

846
00:36:30,210 --> 00:36:34,970
For 768-bit RSA or Diffie-Hellman,

847
00:36:34,970 --> 00:36:37,460
well, we think this is now in the reach

848
00:36:37,460 --> 00:36:41,330
of a concerted academic effort.

849
00:36:41,330 --> 00:36:44,820
For 1024, it's a little bit
more complicated,

850
00:36:44,820 --> 00:36:46,710
because the number field sieve algorithm

851
00:36:46,710 --> 00:36:48,090
is complicated enough that even

852
00:36:48,090 --> 00:36:52,500
making estimates of the runtime
at this size and larger

853
00:36:52,500 --> 00:36:54,690
is very, very complicated

854
00:36:54,690 --> 00:36:58,200
and having a high-confidence estimate
is difficult.

855
00:36:58,200 --> 00:37:01,260
But we've tried to do the math
conservatively,

856
00:37:01,260 --> 00:37:03,490
and we believe that
a conservative estimate,

857
00:37:03,490 --> 00:37:05,920
at least for 1024-bit Diffie-Hellman

858
00:37:05,920 --> 00:37:08,200
is to break, to do those precomputations

859
00:37:08,200 --> 00:37:10,630
for a single prime p,

860
00:37:10,630 --> 00:37:13,480
would take about 45 million core-years.

861
00:37:13,480 --> 00:37:18,190
Now 45 million core-years
sounds like a hell of a lot.

862
00:37:18,190 --> 00:37:20,520
But, when you start to think about it,

863
00:37:20,520 --> 00:37:22,640
if you're going to do
an effort that large,

864
00:37:22,640 --> 00:37:26,050
there are some optimisations
you could start doing,

865
00:37:26,050 --> 00:37:28,920
and, for instance, maybe instead of

866
00:37:28,920 --> 00:37:31,690
running this on general-purpose PCs,

867
00:37:31,690 --> 00:37:33,040
like these estimates show,

868
00:37:33,040 --> 00:37:35,140
if you're going to do
an effort on this scale,

869
00:37:35,140 --> 00:37:37,560
maybe you're going to tape out some chips,

870
00:37:37,560 --> 00:37:39,800
maybe you're going to use custom hardware.

871
00:37:39,800 --> 00:37:42,520
And if we do the math and look at
what kind of gains

872
00:37:42,520 --> 00:37:44,380
we can get from custom hardware

873
00:37:44,380 --> 00:37:47,840
in other applications that
are similar to this,

874
00:37:47,840 --> 00:37:49,320
we estimate that we can get

875
00:37:49,320 --> 00:37:51,890
maybe a speedup of 80 times

876
00:37:51,890 --> 00:37:54,160
just by doing it in custom hardware.

877
00:37:54,160 --> 00:37:57,450
Okay, and then we ask what's
that's going to cost,

878
00:37:57,450 --> 00:38:00,670
well, we estimate that for...

879
00:38:00,670 --> 00:38:02,080
to build a machine that could break

880
00:38:02,080 --> 00:38:07,610
one 1024-bit p, precompute for
one 1024-bit p every year,

881
00:38:07,610 --> 00:38:09,070
would cost somewhere in the neighbourhood

882
00:38:09,070 --> 00:38:11,390
of low hundreds of millions of dollars,

883
00:38:11,390 --> 00:38:12,810
in a one-time investment.

884
00:38:12,810 --> 00:38:14,820
As a result of this, you can churn out

885
00:38:14,820 --> 00:38:16,630
precomputations once a year

886
00:38:16,630 --> 00:38:19,410
that will let you break efficiently

887
00:38:19,410 --> 00:38:22,600
every connection that uses that p.

888
00:38:22,600 --> 00:38:24,630
Now, individual logs then are going to be

889
00:38:24,630 --> 00:38:26,230
close to real-time, and in fact you can

890
00:38:26,230 --> 00:38:28,270
re-use much of the same hardware

891
00:38:28,270 --> 00:38:32,370
to do the computations for
individual logs very quickly.

892
00:38:32,370 --> 00:38:34,590
So, um, oh shit.

893
00:38:34,590 --> 00:38:37,550
This is what the estimates look like.

894
00:38:37,550 --> 00:38:44,050
Now is NSA actually doing this?

895
00:38:44,050 --> 00:38:45,030
NH: This is where we get into

896
00:38:45,030 --> 00:38:47,730
the conspiracy theories.

897
00:38:47,730 --> 00:38:52,720
<i>applause</i>

898
00:38:52,720 --> 00:38:55,010
So, there have been rumours flying around

899
00:38:55,010 --> 00:38:56,930
for many years, I mean
for decades, really,

900
00:38:56,930 --> 00:38:59,720
but sort of credible rumours
for many years,

901
00:38:59,720 --> 00:39:02,810
of some large cryptanalytic breakthrough

902
00:39:02,810 --> 00:39:04,130
that the NSA made.

903
00:39:04,130 --> 00:39:05,890
So here's an article from James Bamford,

904
00:39:05,890 --> 00:39:09,310
one of the, you know, world experts
in open ???

905
00:39:09,310 --> 00:39:11,350
of what the NSA's activities are

906
00:39:11,350 --> 00:39:13,820
and he wrote an article in 2012

907
00:39:13,820 --> 00:39:15,530
saying very clearly that he had talked

908
00:39:15,530 --> 00:39:17,290
to multiple government officials

909
00:39:17,290 --> 00:39:19,980
who said that the NSA made
some enormous breakthrough

910
00:39:19,980 --> 00:39:21,260
several years ago.

911
00:39:21,260 --> 00:39:22,770
Everybody's a target,

912
00:39:22,770 --> 00:39:24,730
everybody with communication is a target,

913
00:39:24,730 --> 00:39:25,960
and this computing breakthrough

914
00:39:25,960 --> 00:39:27,320
is going to give them the ability

915
00:39:27,320 --> 00:39:29,480
to crack current public encryption.

916
00:39:29,480 --> 00:39:31,960
And it was so secret that no oversight,

917
00:39:31,960 --> 00:39:35,150
anybody had sort of access
to the details of it.

918
00:39:35,150 --> 00:39:38,770
But whatever it was,
it was major and massive.

919
00:39:38,770 --> 00:39:40,250
Of course, you know, after we saw this,

920
00:39:40,250 --> 00:39:41,530
we said, oh my god, you know,

921
00:39:41,530 --> 00:39:42,470
what could it possibly be,

922
00:39:42,470 --> 00:39:44,370
are they breaking RSA?

923
00:39:44,370 --> 00:39:46,090
Bamford actually goes on in this article

924
00:39:46,090 --> 00:39:48,960
to speculate that it's
something about AES,

925
00:39:48,960 --> 00:39:51,170
which at least to my mind
seems less likely

926
00:39:51,170 --> 00:39:54,510
than some kind of major
public key breakthrough.

927
00:39:54,510 --> 00:39:56,480
So clearly we have sort of these rumours

928
00:39:56,480 --> 00:40:02,200
of large breakthroughs by the NSA's
tens of thousands of mathematicians.

929
00:40:02,200 --> 00:40:04,980
Simultaneously, we can say, you know,

930
00:40:04,980 --> 00:40:07,910
we know the NSA is clearly
interested in cryptanalysis,

931
00:40:07,910 --> 00:40:11,390
is cryptanalysis on the scale
of hundreds of millions of dollars

932
00:40:11,390 --> 00:40:13,630
within their reach?

933
00:40:13,630 --> 00:40:17,260
The answer, thanks to Snowden, is yes.

934
00:40:17,260 --> 00:40:18,920
We have some of their budgets

935
00:40:18,920 --> 00:40:21,700
and they spend billions of dollars a year

936
00:40:21,700 --> 00:40:23,650
on computer network operations,

937
00:40:23,650 --> 00:40:25,560
they spend hundred of millions of dollars

938
00:40:25,560 --> 00:40:28,110
on cryptanalytic IT systems,

939
00:40:28,110 --> 00:40:31,490
cybercryptanalysis,
exploitation solutions,

940
00:40:31,490 --> 00:40:33,980
in fact, a couple years ago there was even

941
00:40:33,980 --> 00:40:41,830
an increase of hundreds of millions of
dollars in their budget for cryptanalysis.

942
00:40:41,830 --> 00:40:42,950
Interesting.

943
00:40:42,950 --> 00:40:45,360
So, a hundred million dollars of
special-purpose hardware

944
00:40:45,360 --> 00:40:51,880
is certainly within range
of a government the size of ours.

945
00:40:51,880 --> 00:40:53,630
Additionally, we can ask,

946
00:40:53,630 --> 00:40:55,860
what would the impact of doing one of

947
00:40:55,860 --> 00:40:57,600
these single precomputations

948
00:40:57,600 --> 00:41:01,670
for a discrete log
for a single prime would be,

949
00:41:01,670 --> 00:41:04,590
and the answer is actually
surprisingly large.

950
00:41:04,590 --> 00:41:06,150
So if you did this precomputation

951
00:41:06,150 --> 00:41:08,750
for a single 1024-bit prime,

952
00:41:08,750 --> 00:41:10,619
that would allow passive decryption

953
00:41:10,619 --> 00:41:13,290
of connections to 66% of VPN servers

954
00:41:13,290 --> 00:41:16,020
and 26% of SSH servers.

955
00:41:16,020 --> 00:41:18,180
This is from Internet-wide scanning,

956
00:41:18,180 --> 00:41:19,520
we connected to all of these

957
00:41:19,520 --> 00:41:21,380
and we said "we would like to speak

958
00:41:21,380 --> 00:41:24,120
Diffie-Hellman with you,
what parameters do you prefer?"

959
00:41:24,120 --> 00:41:26,780
and these are the servers that preferred

960
00:41:26,780 --> 00:41:32,060
a single 1024-bit prime over
every other parameter in key size.

961
00:41:32,060 --> 00:41:33,770
A second 1024-bit prime would allow

962
00:41:33,770 --> 00:41:38,630
passive decryption for 18%
of the top million HTTPS domains.

963
00:41:38,630 --> 00:41:40,080
These are domains that prefer

964
00:41:40,080 --> 00:41:45,670
to speak Diffie-Hellman
with this fixed prime.

965
00:41:45,670 --> 00:41:47,720
And, the final piece of evidence

966
00:41:47,720 --> 00:41:49,840
for something like this being within range

967
00:41:49,840 --> 00:41:52,280
and at least being worth worrying about

968
00:41:52,280 --> 00:41:57,630
is actually some of the slides
that were release last year,

969
00:41:57,630 --> 00:41:59,050
by der Spiegel,

970
00:41:59,050 --> 00:42:01,780
and in particular they have
a large amount of detail

971
00:42:01,780 --> 00:42:06,530
about passive decryptions of VPN traffic.

972
00:42:06,530 --> 00:42:08,230
So here's an example,

973
00:42:08,230 --> 00:42:09,510
it is clear from the slides that

974
00:42:09,510 --> 00:42:10,580
whatever the NSA is doing,

975
00:42:10,580 --> 00:42:12,420
they have the ability to passively decrypt

976
00:42:12,420 --> 00:42:15,280
VPN connections on a large scale.

977
00:42:15,280 --> 00:42:18,900
And they're very happy about it.

978
00:42:18,900 --> 00:42:21,480
I think this is my favourite
Snowden slide ever.

979
00:42:21,480 --> 00:42:22,620
<i>laughter</i>

980
00:42:22,620 --> 00:42:25,010
I feel this way when I decrypt things too.

981
00:42:25,010 --> 00:42:27,089
<i>laughter</i>

982
00:42:27,089 --> 00:42:29,580
So, if we take a look at what,

983
00:42:29,580 --> 00:42:33,540
and these slides are specifically
talking about IPsec VPNs,

984
00:42:33,540 --> 00:42:39,100
if we take a look at what the
key exchange looks like for IPsec VPNs,

985
00:42:39,100 --> 00:42:41,260
what happens is, we have two hosts

986
00:42:41,260 --> 00:42:45,400
who want to make a VPN
connection with each other,

987
00:42:45,400 --> 00:42:50,950
the key exchange actually uses a
fixed set of parameters

988
00:42:50,950 --> 00:42:54,080
from a small list of possibilities,

989
00:42:54,080 --> 00:42:55,619
and so Alice and Bob will negotiate

990
00:42:55,619 --> 00:42:58,040
which parameters they're going
to use from this list,

991
00:42:58,040 --> 00:43:00,050
and then they will do a
Diffie-Hellman key exchange,

992
00:43:00,050 --> 00:43:03,240
from that they will have
a shared secret, g^ab,

993
00:43:03,240 --> 00:43:05,550
and then they, in the most
commonly used mode,

994
00:43:05,550 --> 00:43:07,140
they also have some pre-shared key,

995
00:43:07,140 --> 00:43:09,400
like a password that has been shared

996
00:43:09,400 --> 00:43:11,250
over some other channel.

997
00:43:11,250 --> 00:43:14,010
And that Diffie-Hellman secret

998
00:43:14,010 --> 00:43:16,020
that was negotiated together
with the pre-shared key

999
00:43:16,020 --> 00:43:19,370
or mixed together to generate
the session key.

1000
00:43:19,370 --> 00:43:22,300
So, if somebody wanted to

1001
00:43:22,300 --> 00:43:24,330
break a connection of this type,

1002
00:43:24,330 --> 00:43:26,080
one option would be to, say,

1003
00:43:26,080 --> 00:43:28,010
steal the pre-shared key
through some other mechanism

1004
00:43:28,010 --> 00:43:29,380
and then break Diffie-Hellman.

1005
00:43:29,380 --> 00:43:32,559
That would be a possibility.

1006
00:43:32,559 --> 00:43:35,500
So, if we look what the
NSA's requirements are

1007
00:43:35,500 --> 00:43:38,920
for their mass-scale decryption efforts,

1008
00:43:38,920 --> 00:43:42,369
they require finding out what
the pre-shared key is,

1009
00:43:42,369 --> 00:43:44,990
getting both sides of the connection,

1010
00:43:44,990 --> 00:43:47,690
getting both the asymmetric key exchange

1011
00:43:47,690 --> 00:43:50,350
and the symmetrically encrypted data,

1012
00:43:50,350 --> 00:43:52,589
and then having some metadata.

1013
00:43:52,589 --> 00:43:56,240
These are the requirements for them
to get decryption.

1014
00:43:56,240 --> 00:43:58,210
And we can also take a closer look

1015
00:43:58,210 --> 00:44:04,260
at what their decryption flow
actually looks like,

1016
00:44:04,260 --> 00:44:06,290
this is somewhat complicated,

1017
00:44:06,290 --> 00:44:07,850
but in this diagram,

1018
00:44:07,850 --> 00:44:10,840
so they're getting the IK exchange,

1019
00:44:10,840 --> 00:44:12,990
and the symmetric data,

1020
00:44:12,990 --> 00:44:17,130
they're sending it into
one system that they have,

1021
00:44:17,130 --> 00:44:19,230
they're sending the IKE messages through

1022
00:44:19,230 --> 00:44:21,880
out to some high-performance
computing resources,

1023
00:44:21,880 --> 00:44:23,619
and then they get sent back with

1024
00:44:23,619 --> 00:44:28,690
some data from stored
databases of information

1025
00:44:28,690 --> 00:44:32,910
that returns the actual decrypted data.

1026
00:44:32,910 --> 00:44:34,840
So that's what the decryption
flow looks like.

1027
00:44:34,840 --> 00:44:37,130
We don't have any details
of the cryptanalysis,

1028
00:44:37,130 --> 00:44:39,480
but we have details from
the sysadmin's perspective

1029
00:44:39,480 --> 00:44:43,190
of how the systems
that do the cryptanalysis

1030
00:44:43,190 --> 00:44:44,670
are hooked together.

1031
00:44:44,670 --> 00:44:46,000
And they're doing something

1032
00:44:46,000 --> 00:44:48,280
that requires high-performance computing,

1033
00:44:48,280 --> 00:44:49,700
that takes in key exchanges

1034
00:44:49,700 --> 00:44:54,040
and hands out decrypted data.

1035
00:44:54,040 --> 00:44:59,740
So, we can line up sort of the NSA's
on-demand IKE decryption

1036
00:44:59,740 --> 00:45:03,710
with what a discrete log decryption
would actually look like,

1037
00:45:03,710 --> 00:45:05,619
and they're very close,

1038
00:45:05,619 --> 00:45:07,640
so they would both require
the pre-shared key,

1039
00:45:07,640 --> 00:45:09,490
both sides of the handshake,

1040
00:45:09,490 --> 00:45:12,440
both the handshake and the symmetric data,

1041
00:45:12,440 --> 00:45:13,450
and they would send off the data

1042
00:45:13,450 --> 00:45:16,090
to high-performance computing.

1043
00:45:16,090 --> 00:45:17,990
So in the same set of slides,

1044
00:45:17,990 --> 00:45:20,770
they also discuss targeted implants

1045
00:45:20,770 --> 00:45:23,040
against particular implementations,

1046
00:45:23,040 --> 00:45:26,890
if you were going to design a
backdoor to make your life easy,

1047
00:45:26,890 --> 00:45:30,360
you would have fewer
requirements than this.

1048
00:45:30,360 --> 00:45:31,320
Potentially.

1049
00:45:31,320 --> 00:45:33,090
There are many kinds of backdoors
that you could design,

1050
00:45:33,090 --> 00:45:35,190
but if you were being clever about it,

1051
00:45:35,190 --> 00:45:38,090
you might try to make it
a little bit easier on yourself

1052
00:45:38,090 --> 00:45:41,100
to decrypt the mess.

1053
00:45:41,100 --> 00:45:43,750
So I will let Alex finish with this.

1054
00:45:43,750 --> 00:45:51,090
<i>applause</i>

1055
00:45:51,090 --> 00:45:53,890
So to wrap up,

1056
00:45:53,890 --> 00:45:55,520
what we've seen today

1057
00:45:55,520 --> 00:46:00,150
through the cryptanalysis
of Diffie-Hellman

1058
00:46:00,150 --> 00:46:05,330
is probably a mass surveillance dream.

1059
00:46:05,330 --> 00:46:08,180
The algorithms that we've talked about

1060
00:46:08,180 --> 00:46:11,400
would let a government with
sufficient resources

1061
00:46:11,400 --> 00:46:15,010
to invest in these precomputation attacks

1062
00:46:15,010 --> 00:46:18,840
break connections on an almost
unheard-of scale,

1063
00:46:18,840 --> 00:46:23,950
across almost every widely-used
crypto protocol on the Internet.

1064
00:46:23,950 --> 00:46:25,530
Here are some numbers again,

1065
00:46:25,530 --> 00:46:28,490
for HTTPS, the top million sites,

1066
00:46:28,490 --> 00:46:29,960
we're looking at a device like

1067
00:46:29,960 --> 00:46:32,480
the ones we hypothesised

1068
00:46:32,480 --> 00:46:38,150
breaking connections to maybe
56% of them passively.

1069
00:46:38,150 --> 00:46:42,900
For IKE, for Internet key
exchange v1 and v2,

1070
00:46:42,900 --> 00:46:46,090
we're looking at in the 60%s of servers

1071
00:46:46,090 --> 00:46:48,240
are potentially compromisable

1072
00:46:48,240 --> 00:46:50,750
using this same hardware.

1073
00:46:50,750 --> 00:47:00,290
For SSH, for IMAP with secure encrypted
connections, for SMTP with STARTTLS,

1074
00:47:00,290 --> 00:47:02,259
the encrypted mail transports,

1075
00:47:02,259 --> 00:47:05,570
all of these protocols are
potentially jeopardised

1076
00:47:05,570 --> 00:47:07,390
by the same kind of attack,

1077
00:47:07,390 --> 00:47:09,490
because everyone fundamentally,

1078
00:47:09,490 --> 00:47:11,110
so many people fundamentally

1079
00:47:11,110 --> 00:47:14,400
rely on the same underlying cryptography,

1080
00:47:14,400 --> 00:47:17,050
often with the very same public parameters

1081
00:47:17,050 --> 00:47:19,560
that are so widely shared.

1082
00:47:19,560 --> 00:47:21,850
So what can we do about this?

1083
00:47:21,850 --> 00:47:24,820
So first, let's go back to the
Logjam attack again,

1084
00:47:24,820 --> 00:47:27,490
using 90s-era backdoored crypto

1085
00:47:27,490 --> 00:47:30,930
that lets any of us break connections
to modern browsers.

1086
00:47:30,930 --> 00:47:32,760
Luckily, browsers have already started

1087
00:47:32,760 --> 00:47:34,490
to mitigate this, as I said,

1088
00:47:34,490 --> 00:47:35,990
by increasing the minimum strength

1089
00:47:35,990 --> 00:47:37,470
of Diffie-Hellman they support,

1090
00:47:37,470 --> 00:47:39,650
although there's still a way to go there,

1091
00:47:39,650 --> 00:47:43,350
since they're all still accepting
1024-bit key exchange.

1092
00:47:43,350 --> 00:47:45,760
Our biggest recommendation
under here though,

1093
00:47:45,760 --> 00:47:49,160
I think the lesson is:
don't backdoor crypto!

1094
00:47:49,160 --> 00:47:50,810
Right, because the backdoored crypto

1095
00:47:50,810 --> 00:47:52,840
of 20 years ago is now coming back

1096
00:47:52,840 --> 00:47:54,510
to bite everyone.

1097
00:47:54,510 --> 00:47:59,440
<i>applause</i>

1098
00:47:59,440 --> 00:48:01,630
And then, we have the second attack,

1099
00:48:01,630 --> 00:48:03,510
the 1024-bit case that enables

1100
00:48:03,510 --> 00:48:05,220
so much mass surveillance.

1101
00:48:05,220 --> 00:48:06,970
Well, to get around this,

1102
00:48:06,970 --> 00:48:09,570
we're going to have to do some upgrades.

1103
00:48:09,570 --> 00:48:11,440
Probably the easiest thing to do,

1104
00:48:11,440 --> 00:48:12,859
and the thing that almost

1105
00:48:12,859 --> 00:48:15,420
every cryptographer that we talked to

1106
00:48:15,420 --> 00:48:16,590
recommends now,

1107
00:48:16,590 --> 00:48:18,690
is to move to elliptic-curve crypto.

1108
00:48:18,690 --> 00:48:19,950
Yes, there's been talk

1109
00:48:19,950 --> 00:48:22,530
about whether the specific NIST curves

1110
00:48:22,530 --> 00:48:25,790
may have been backdoored by NSA,

1111
00:48:25,790 --> 00:48:27,470
but by and large, we think that

1112
00:48:27,470 --> 00:48:29,590
elliptic curve is the most sound choice

1113
00:48:29,590 --> 00:48:31,550
we have for now.

1114
00:48:31,550 --> 00:48:33,119
Now if elliptic curve isn't an option,

1115
00:48:33,119 --> 00:48:35,490
and there's technical reasons
why it might not be,

1116
00:48:35,490 --> 00:48:38,570
at the very least use
a Diffie-Hellman prime

1117
00:48:38,570 --> 00:48:41,410
that's 2048 bits or longer.

1118
00:48:41,410 --> 00:48:43,480
If even that isn't an option,

1119
00:48:43,480 --> 00:48:45,970
you're using legacy systems
for some reason,

1120
00:48:45,970 --> 00:48:49,610
well, or Java yes, thanks,

1121
00:48:49,610 --> 00:48:52,709
if there's anyone there who works for Sun,

1122
00:48:52,709 --> 00:48:58,340
please, please tell them
to fix the crypto in Java!

1123
00:48:58,340 --> 00:49:04,920
<i>applause</i>

1124
00:49:04,920 --> 00:49:06,740
But if that's not an option,

1125
00:49:06,740 --> 00:49:07,660
if that's not an option,

1126
00:49:07,660 --> 00:49:09,359
the fallback is you can generate,

1127
00:49:09,359 --> 00:49:13,890
at least generate your own 1024-bit prime.

1128
00:49:13,890 --> 00:49:17,000
Mind you, there various tricks
that you have to make sure you do

1129
00:49:17,000 --> 00:49:20,310
when generating a prime,
it must be a safe prime,

1130
00:49:20,310 --> 00:49:22,450
but there are implementations
of doing this,

1131
00:49:22,450 --> 00:49:27,100
so it's not exactly free to generate
your own 1024-bit prime,

1132
00:49:27,100 --> 00:49:28,300
but it's inexpensive,

1133
00:49:28,300 --> 00:49:29,810
and if you have no other option,

1134
00:49:29,810 --> 00:49:32,950
at least so that this large
government adversary

1135
00:49:32,950 --> 00:49:35,000
has to spend a lot of precomputation,

1136
00:49:35,000 --> 00:49:37,990
a year perhaps, targeting
you individually,

1137
00:49:37,990 --> 00:49:40,330
and they can't just get this for free.

1138
00:49:40,330 --> 00:49:43,360
Alright, so, that is our talk for tonight,

1139
00:49:43,360 --> 00:49:45,950
we're saving a lot of time for questions,

1140
00:49:45,950 --> 00:49:49,040
thank you all very very much.

1141
00:49:49,040 --> 00:50:00,410
<i>applause</i>

1142
00:50:00,410 --> 00:50:05,300
Herald: Nadia. Nadia and Alex,
thank you very much.

1143
00:50:05,300 --> 00:50:07,350
We installed some microphones
here in the room,

1144
00:50:07,350 --> 00:50:09,290
so please queue up, but first,

1145
00:50:09,290 --> 00:50:11,890
signal angel, do we have
some questions from the net?

1146
00:50:11,890 --> 00:50:14,810
Signal Angel: Yes, we have a lot of questions.

1147
00:50:14,810 --> 00:50:16,160
First question is,

1148
00:50:16,160 --> 00:50:17,780
do you think it's possible that the NSA

1149
00:50:17,780 --> 00:50:19,890
uses quantum Shor factorisation

1150
00:50:19,890 --> 00:50:24,790
for 1024 or bigger keys already?

1151
00:50:24,790 --> 00:50:27,520
NH: I would believe it is much more likely

1152
00:50:27,520 --> 00:50:29,720
that they're using classical cryptanalysis

1153
00:50:29,720 --> 00:50:31,480
for 1024-bit keys than than they have

1154
00:50:31,480 --> 00:50:34,770
a quantum computer that
nobody has heard about.

1155
00:50:34,770 --> 00:50:37,230
Herald: And another one?

1156
00:50:37,230 --> 00:50:38,760
Signal Angel: Another one... Is it thinkable

1157
00:50:38,760 --> 00:50:41,490
that the NSA solved the P=NP problem

1158
00:50:41,490 --> 00:50:43,210
but keeps quiet?

1159
00:50:43,210 --> 00:50:45,780
<i>laughter</i>

1160
00:50:45,780 --> 00:50:47,670
AH: Probably not, but if they have,

1161
00:50:47,670 --> 00:50:50,539
yes, I think they'd want to
keep quiet about it.

1162
00:50:50,539 --> 00:50:52,000
NH: I hope they would tell us!

1163
00:50:52,000 --> 00:50:53,570
AH: I hope they would tell us too,

1164
00:50:53,570 --> 00:50:56,010
but I doubt it.

1165
00:50:56,010 --> 00:50:59,930
Herald: Okay, and over to
number 1, please.

1166
00:50:59,930 --> 00:51:01,540
Q: Two questions.

1167
00:51:01,540 --> 00:51:05,600
First, is it reasonable to think that,

1168
00:51:05,600 --> 00:51:09,200
is it possible they are attacking
individual RSA keys,

1169
00:51:09,200 --> 00:51:11,320
that they can fetch individual RSA keys

1170
00:51:11,320 --> 00:51:13,530
in about a week with custom hardware,

1171
00:51:13,530 --> 00:51:17,580
and two, NSA Suite B came out 2005

1172
00:51:17,580 --> 00:51:19,160
and they don't use Diffie-Hellman,

1173
00:51:19,160 --> 00:51:22,670
so NSA themselves, they told us in 2005,

1174
00:51:22,670 --> 00:51:24,730
"we won't use Diffie-Hellman",

1175
00:51:24,730 --> 00:51:26,570
so is it reasonable that,

1176
00:51:26,570 --> 00:51:28,400
when they changed the requirement

1177
00:51:28,400 --> 00:51:30,730
for top secret, we should follow?

1178
00:51:30,730 --> 00:51:33,470
AH: Well, to the first part
of your question,

1179
00:51:33,470 --> 00:51:35,859
about whether they're factoring RSA,

1180
00:51:35,859 --> 00:51:38,580
I think the answer for 1024,

1181
00:51:38,580 --> 00:51:40,600
is very likely, yes they are,

1182
00:51:40,600 --> 00:51:42,320
for high-value targets.

1183
00:51:42,320 --> 00:51:45,020
So if you're a major website at least

1184
00:51:45,020 --> 00:51:48,090
and you're using a 1024-bit RSA key,

1185
00:51:48,090 --> 00:51:53,000
well, it's long past time to change
to a higher strength.

1186
00:51:53,000 --> 00:51:56,480
NH: If the NSA has not factored
a 1024-bit key,

1187
00:51:56,480 --> 00:51:58,050
I'm going to be very disappointed,

1188
00:51:58,050 --> 00:52:00,930
I'm going to ask where
my tax dollars are going.

1189
00:52:00,930 --> 00:52:07,370
<i>laughter, applause</i>

1190
00:52:07,370 --> 00:52:09,440
And also I think actually,

1191
00:52:09,440 --> 00:52:11,000
the point of sort of watching

1192
00:52:11,000 --> 00:52:12,830
what the defensive side of the NSA

1193
00:52:12,830 --> 00:52:15,200
is advocating in terms of recommendations

1194
00:52:15,200 --> 00:52:17,180
is actually a wise thing to do,

1195
00:52:17,180 --> 00:52:20,160
because as far as we know,

1196
00:52:20,160 --> 00:52:22,140
at least the public recommendations

1197
00:52:22,140 --> 00:52:26,450
defensively should... I mean,

1198
00:52:26,450 --> 00:52:27,580
making recommendations for people

1199
00:52:27,580 --> 00:52:31,000
who are building systems that are
going to be handling classified data,

1200
00:52:31,000 --> 00:52:32,780
so they should be solid recommendations

1201
00:52:32,780 --> 00:52:33,960
as far as we know.

1202
00:52:33,960 --> 00:52:35,280
AH: What the NSA has told me

1203
00:52:35,280 --> 00:52:37,580
about those recommendations, by the way,

1204
00:52:37,580 --> 00:52:40,280
is that as long as you
follow them exactly,

1205
00:52:40,280 --> 00:52:41,609
you're going to be okay,

1206
00:52:41,609 --> 00:52:44,160
but if you deviate in any
small way whatsoever,

1207
00:52:44,160 --> 00:52:46,960
then they make no guarantees whatsoever.

1208
00:52:46,960 --> 00:52:50,040
So, think about what that might mean

1209
00:52:50,040 --> 00:52:52,220
in terms of your implementation

1210
00:52:52,220 --> 00:52:55,630
the next time you read through
those particular recommendations

1211
00:52:55,630 --> 00:52:58,470
that they make.

1212
00:52:58,470 --> 00:53:01,280
Herald: Okay. Then we hop over to
microphone 3, please.

1213
00:53:01,280 --> 00:53:03,549
Q: So, for the moment, is

1214
00:53:03,549 --> 00:53:07,380
elliptic-curve-based
Diffie-Hellman secure?

1215
00:53:07,380 --> 00:53:09,860
NH: I hope so.

1216
00:53:09,860 --> 00:53:13,650
AH: It doesn't suffer from
the same shape of attack

1217
00:53:13,650 --> 00:53:14,900
that we've described here.

1218
00:53:14,900 --> 00:53:16,770
As far as we know, there's not a way

1219
00:53:16,770 --> 00:53:19,020
to do this same kind of precomputation

1220
00:53:19,020 --> 00:53:20,710
for elliptic-curve Diffie-Hellman.

1221
00:53:20,710 --> 00:53:22,530
NH: So what we didn't mention in the talk

1222
00:53:22,530 --> 00:53:24,630
is, so, one of the reasons that

1223
00:53:24,630 --> 00:53:27,300
elliptic curve keys are so much shorter

1224
00:53:27,300 --> 00:53:30,730
than, say, finite-field
Diffie-Hellman or RSA

1225
00:53:30,730 --> 00:53:35,350
is because we have this
superpowerful index calculus

1226
00:53:35,350 --> 00:53:37,410
number field sieve-type algorithms

1227
00:53:37,410 --> 00:53:41,270
for factoring and for discrete log
over finite fields,

1228
00:53:41,270 --> 00:53:43,040
and those don't seem,

1229
00:53:43,040 --> 00:53:44,310
we don't actually have equivalents

1230
00:53:44,310 --> 00:53:47,890
of those algorithms for
properly generated elliptic curves.

1231
00:53:47,890 --> 00:53:50,580
So, that's why those key sizes are shorter

1232
00:53:50,580 --> 00:53:54,020
and that's why we think
they seem to be more secure.

1233
00:53:54,020 --> 00:53:57,109
Herald: Then we take another one
from microphone 3, please.

1234
00:53:57,109 --> 00:54:01,310
Q: Yes, you said that when doing
the precomputations

1235
00:54:01,310 --> 00:54:04,820
for commonly-used primes,

1236
00:54:04,820 --> 00:54:08,330
you can reduce the effort you have to put

1237
00:54:08,330 --> 00:54:11,280
in a single connection
to about 70 seconds.

1238
00:54:11,280 --> 00:54:12,830
How is that usable?

1239
00:54:12,830 --> 00:54:15,850
If my TLS handshake is delayed 70 seconds,

1240
00:54:15,850 --> 00:54:18,420
I already ran away.

1241
00:54:18,420 --> 00:54:20,480
AH: Ah! So we refer you to the paper

1242
00:54:20,480 --> 00:54:22,090
for the full answer to that,

1243
00:54:22,090 --> 00:54:23,680
but it turns out there's a bunch of tricks

1244
00:54:23,680 --> 00:54:28,520
that you can do to keep
a session handshake open

1245
00:54:28,520 --> 00:54:30,210
for at least 70 seconds.

1246
00:54:30,210 --> 00:54:32,240
So, this may not be what you want to do

1247
00:54:32,240 --> 00:54:35,330
to the connection, say, in a web browser

1248
00:54:35,330 --> 00:54:37,770
that's loading index.html,

1249
00:54:37,770 --> 00:54:39,530
but whichever one is loading, say,

1250
00:54:39,530 --> 00:54:44,619
the, I don't know, the 1-pixel
tracking image in the background,

1251
00:54:44,619 --> 00:54:46,349
that nobody sees,

1252
00:54:46,349 --> 00:54:48,710
which is also getting the same
session cookie,

1253
00:54:48,710 --> 00:54:51,060
that one you can hold open
for 70 seconds

1254
00:54:51,060 --> 00:54:52,840
without the user noticing.

1255
00:54:52,840 --> 00:54:54,070
So what we've been able to do

1256
00:54:54,070 --> 00:54:56,369
is show a variety of ways
that we can trick

1257
00:54:56,369 --> 00:54:58,020
browsers and other implementations

1258
00:54:58,020 --> 00:55:00,840
into holding the connection
open long enough.

1259
00:55:00,840 --> 00:55:03,490
Also, 70 seconds is just
what we were able to do

1260
00:55:03,490 --> 00:55:07,040
with a few weeks of hacking
around and optimisation,

1261
00:55:07,040 --> 00:55:10,660
we think that with
not that much more effort

1262
00:55:10,660 --> 00:55:13,239
we could get that number
down quite a bit more.

1263
00:55:13,239 --> 00:55:16,280
But 70 seconds we think
already is not so bad,

1264
00:55:16,280 --> 00:55:18,240
and there's plenty of ways
that we can exploit it.

1265
00:55:18,240 --> 00:55:21,489
NH: Proof of concept.

1266
00:55:21,489 --> 00:55:24,230
Herald: Okay. Do we have
something from the net?

1267
00:55:24,230 --> 00:55:26,780
Signal Angel: How long do you estimate the security

1268
00:55:26,780 --> 00:55:29,490
of RSA-DHE to sustain,

1269
00:55:29,490 --> 00:55:31,030
and do you have any idea if and when

1270
00:55:31,030 --> 00:55:33,680
there's any quantum encryption algorithms

1271
00:55:33,680 --> 00:55:35,320
that will soon be available to be used

1272
00:55:35,320 --> 00:55:36,850
by a broad public?

1273
00:55:36,850 --> 00:55:38,950
AH: Oh, quantum encryption algorithms.

1274
00:55:38,950 --> 00:55:41,150
NH: You should watch Dan
and Tanja's talk from yesterday.

1275
00:55:41,150 --> 00:55:44,070
AH: Yeah, last night was the time
to hear about that.

1276
00:55:44,070 --> 00:55:46,170
NH: The dangers of quantum cryptography.

1277
00:55:46,170 --> 00:55:48,220
I mean, the short answer is

1278
00:55:48,220 --> 00:55:49,750
that people who know
what they're talking about

1279
00:55:49,750 --> 00:55:51,830
have said we should start worrying now

1280
00:55:51,830 --> 00:55:53,930
because we may see quantum computers

1281
00:55:53,930 --> 00:55:56,740
within the next 15 years, maybe.

1282
00:55:56,740 --> 00:55:59,220
But it's really hard to speculate about

1283
00:55:59,220 --> 00:56:05,030
advances in physics that
may be pretty far off.

1284
00:56:05,030 --> 00:56:06,770
Herald: Do we have another one?

1285
00:56:06,770 --> 00:56:09,550
Signal angel: Sure. What's your
opinion on the NIST curves,

1286
00:56:09,550 --> 00:56:10,890
especially with the current rumours

1287
00:56:10,890 --> 00:56:15,530
about the curve parameters
having a backdoor?

1288
00:56:15,530 --> 00:56:18,310
NH: There are no known ways

1289
00:56:18,310 --> 00:56:20,710
that the curves could have been backdoored

1290
00:56:20,710 --> 00:56:23,460
with the given parameters.

1291
00:56:23,460 --> 00:56:25,630
AH: But if you don't trust them,

1292
00:56:25,630 --> 00:56:28,160
you know Dan Bernstein
has a curve you can use too.

1293
00:56:28,160 --> 00:56:30,120
NH: So...

1294
00:56:30,120 --> 00:56:32,230
<i>applause</i>

1295
00:56:32,230 --> 00:56:35,250
NH: Do you trust Dan,
or do you trust the NSA?

1296
00:56:35,250 --> 00:56:37,250
<i>laughter</i>

1297
00:56:37,250 --> 00:56:38,859
Herald: Over to 2, please.

1298
00:56:38,859 --> 00:56:41,800
Q: Some of the little bit
that you recommend,

1299
00:56:41,800 --> 00:56:46,249
you say Diffie-Hellman is worse
than RSA now,

1300
00:56:46,249 --> 00:56:49,930
so, does it mean I should switch back

1301
00:56:49,930 --> 00:56:54,370
to RSA, preferring it instead
of Diffie-Hellman?

1302
00:56:54,370 --> 00:56:57,070
AH: With equivalent key sizes,

1303
00:56:57,070 --> 00:56:59,980
equivalent sizes of your primes,

1304
00:56:59,980 --> 00:57:02,670
or your RSA modulus,

1305
00:57:02,670 --> 00:57:05,020
yes, we are saying that.

1306
00:57:05,020 --> 00:57:06,940
That in the 1024-bit case,

1307
00:57:06,940 --> 00:57:10,109
there's strong reasons that you should

1308
00:57:10,109 --> 00:57:14,160
distrust the very common repeated primes

1309
00:57:14,160 --> 00:57:15,690
for Diffie-Hellman.

1310
00:57:15,690 --> 00:57:17,750
But that's not the whole story.

1311
00:57:17,750 --> 00:57:26,510
Right, so for longer sizes of modulus,

1312
00:57:26,510 --> 00:57:27,790
larger strengths of crypto,

1313
00:57:27,790 --> 00:57:31,680
RSA is probably still okay.

1314
00:57:31,680 --> 00:57:34,369
But I think either way,

1315
00:57:34,369 --> 00:57:37,750
switching to elliptic curve
for key exchange

1316
00:57:37,750 --> 00:57:39,980
is probably the thing to do right now.

1317
00:57:39,980 --> 00:57:42,320
NH: I think the precise statement
that we can make

1318
00:57:42,320 --> 00:57:44,619
is, if you're comparing 1024-bit
Diffie-Hellman

1319
00:57:44,619 --> 00:57:47,430
to a 1024-bit RSA key,

1320
00:57:47,430 --> 00:57:48,730
that if you're using Diffie-Hellman

1321
00:57:48,730 --> 00:57:50,980
with the most commonly used parameters,

1322
00:57:50,980 --> 00:57:52,690
say, the Oakley group 2

1323
00:57:52,690 --> 00:57:55,070
that everybody on the Internet is using,

1324
00:57:55,070 --> 00:57:57,460
and you think it is likely that
a large government agency

1325
00:57:57,460 --> 00:58:00,700
has already done the
precomputation for that prime,

1326
00:58:00,700 --> 00:58:05,359
then breaking an individual
connection using that prime

1327
00:58:05,359 --> 00:58:06,750
with Diffie-Hellman key exchange

1328
00:58:06,750 --> 00:58:08,849
would be much, much, much less effort

1329
00:58:08,849 --> 00:58:14,720
than factoring a freshly generated
1024-bit RSA key that is unique to you.

1330
00:58:14,720 --> 00:58:17,720
Even if that 1024-bit RSA factorisation

1331
00:58:17,720 --> 00:58:20,460
is within range of the NSA,

1332
00:58:20,460 --> 00:58:21,490
it may not be worth their while

1333
00:58:21,490 --> 00:58:23,420
to actually factor your key.

1334
00:58:23,420 --> 00:58:25,810
Whereas breaking a
Diffie-Hellman key exchange,

1335
00:58:25,810 --> 00:58:27,180
they've already done the hard work

1336
00:58:27,180 --> 00:58:28,500
to break everybody on the Internet,

1337
00:58:28,500 --> 00:58:31,250
so, you're just one more fish.

1338
00:58:31,250 --> 00:58:32,000
That's the precise statement

1339
00:58:32,000 --> 00:58:33,590
that we can make about the security.

1340
00:58:33,590 --> 00:58:35,430
The real answer: use elliptic curves,

1341
00:58:35,430 --> 00:58:41,990
or, to use 2048-bit
Diffie-Hellman: probably fine.

1342
00:58:41,990 --> 00:58:43,849
Herald: And, over to number 1, please.

1343
00:58:43,849 --> 00:58:47,230
Q: How realistic is it to use, or to create

1344
00:58:47,230 --> 00:58:50,210
a new prime for every exchange

1345
00:58:50,210 --> 00:58:52,990
or at least every few exchanges?

1346
00:58:52,990 --> 00:58:55,840
NH: So, unfortunately, the properties

1347
00:58:55,840 --> 00:59:01,039
that you need for discrete log to be hard,

1348
00:59:01,039 --> 00:59:02,470
you need to have a safe prime

1349
00:59:02,470 --> 00:59:05,720
and you would hopefully like it
not to be backdoored,

1350
00:59:05,720 --> 00:59:09,430
generating safe primes is
still kind of effortful

1351
00:59:09,430 --> 00:59:10,609
on modern hardware,

1352
00:59:10,609 --> 00:59:12,010
I mean if you try to do it on your laptop

1353
00:59:12,010 --> 00:59:15,170
it will probably take like, I don't know,
a minute or something.

1354
00:59:15,170 --> 00:59:16,940
So, it's actually a lot of effort

1355
00:59:16,940 --> 00:59:20,230
to generate a new safe prime all the time.

1356
00:59:20,230 --> 00:59:24,490
Just use a larger safe prime
and you'll be better.

1357
00:59:24,490 --> 00:59:26,090
Herald: So we're running out of time,

1358
00:59:26,090 --> 00:59:28,730
but let's... with number 2.

1359
00:59:28,730 --> 00:59:32,060
Q: You said that elliptic
curve cryptography

1360
00:59:32,060 --> 00:59:36,930
is not susceptible to
this precomputation attack,

1361
00:59:36,930 --> 00:59:43,750
is that luck, or is it
engineered to be that way?

1362
00:59:43,750 --> 00:59:44,300
<i>AH laughs</i>

1363
00:59:44,300 --> 00:59:45,520
NH: ...luck?

1364
00:59:45,520 --> 00:59:46,940
AH: In part!

1365
00:59:46,940 --> 00:59:48,010
NH: I mean, a combination of both, but

1366
00:59:48,010 --> 00:59:49,160
so as far as we know, I mean, you can't do

1367
00:59:49,160 --> 00:59:50,980
precomputation with elliptic curves,

1368
00:59:50,980 --> 00:59:53,570
so, you know, sort of generically,

1369
00:59:53,570 --> 00:59:54,560
the best thing that you can say

1370
00:59:54,560 --> 00:59:58,500
is you can do a lot of precomputation

1371
00:59:58,500 --> 01:00:00,720
but you still have to do a lot of effort

1372
01:00:00,720 --> 01:00:03,290
for each individual value,

1373
01:00:03,290 --> 01:00:05,849
so you could do, you know, generically

1374
01:00:05,849 --> 01:00:06,920
if you want to break an elliptic curve

1375
01:00:06,920 --> 01:00:08,880
you could do like,
a square-root-of-n attack

1376
01:00:08,880 --> 01:00:10,830
against the key size,

1377
01:00:10,830 --> 01:00:13,599
you could do, say, n^2/3 precomputation

1378
01:00:13,599 --> 01:00:17,540
and then you would have n^1/3 online work

1379
01:00:17,540 --> 01:00:19,369
if that makes sense to you.

1380
01:00:19,369 --> 01:00:22,820
But you get less effort as far as we know.

1381
01:00:22,820 --> 01:00:24,610
Less benefit.

1382
01:00:24,610 --> 01:00:28,490
Herald: Sorry. We're going to finalise
then, with number 4.

1383
01:00:28,490 --> 01:00:31,060
Q: What do you think about blacklisting
these common primes,

1384
01:00:31,060 --> 01:00:32,460
just in the modern browsers?

1385
01:00:32,460 --> 01:00:34,920
Will this get rid of this issue?

1386
01:00:34,920 --> 01:00:36,920
AH: Just blacklisting the common primes,

1387
01:00:36,920 --> 01:00:39,109
well, if you blacklist the common primes,

1388
01:00:39,109 --> 01:00:41,030
if you blacklisted the common primes

1389
01:00:41,030 --> 01:00:43,230
when we first came up with this,

1390
01:00:43,230 --> 01:00:47,480
you'd immediately break
about 10% of websites

1391
01:00:47,480 --> 01:00:49,670
because there's not a good
fallback mechanism

1392
01:00:49,670 --> 01:00:52,420
if you don't like the prime you got

1393
01:00:52,420 --> 01:00:54,730
during key negotiation.

1394
01:00:54,730 --> 01:00:56,730
What the browsers are more likely to do

1395
01:00:56,730 --> 01:01:01,920
is to phase out this kind of
finite-field Diffie-Hellman entirely,

1396
01:01:01,920 --> 01:01:04,550
over the next larger number of years.

1397
01:01:04,550 --> 01:01:06,580
So first they're going to
start rejecting things

1398
01:01:06,580 --> 01:01:09,390
that use unusually weak primes,

1399
01:01:09,390 --> 01:01:11,580
that's what they're doing already today,

1400
01:01:11,580 --> 01:01:13,060
but I think in the long term

1401
01:01:13,060 --> 01:01:16,810
they're going to encourage the use
of elliptic curves as an alternative,

1402
01:01:16,810 --> 01:01:18,410
if you want forward secrecy,

1403
01:01:18,410 --> 01:01:22,020
elliptic curves will be the way to get it.

1404
01:01:22,020 --> 01:01:24,560
Herald: Nadia, Alex, once again,

1405
01:01:24,560 --> 01:01:25,700
thank you so much.

1406
01:01:25,700 --> 01:01:26,790
AH: Thank you.

1407
01:01:26,790 --> 01:01:32,570
<i>applause</i>

1408
01:01:32,570 --> 01:01:36,601
<i>postroll music</i>

1409
01:01:36,601 --> 01:01:44,000
subtitles created by c3subtitles.de
in the year 2016. Join, and help us!