WEBVTT
00:00:00.000 --> 00:00:09.600
preroll music
00:00:09.600 --> 00:00:11.350
Herald: I did some research,
00:00:11.350 --> 00:00:12.880
and it was not, not easy
00:00:12.880 --> 00:00:15.510
that Diffie-Hellman key exchange
00:00:15.510 --> 00:00:17.539
is so much above my pay grade
00:00:17.539 --> 00:00:19.879
therefore, I'm going to keep it simple.
00:00:19.879 --> 00:00:21.079
Please welcome
00:00:21.079 --> 00:00:24.480
we have Alex Halderman from
the University of Michigan,
00:00:24.480 --> 00:00:28.799
and Nadia Heninger from
the University of Pennsylvania.
00:00:28.799 --> 00:00:32.759
applause
00:00:32.759 --> 00:00:37.270
AH: Thank you.
00:00:37.270 --> 00:00:38.710
Thank you all so much.
00:00:38.710 --> 00:00:43.519
It's wonderful to be back again in 32C3.
00:00:43.519 --> 00:00:46.429
I'm Alex Halderman from
the University of Michigan,
00:00:46.429 --> 00:00:49.379
here again this year with,
00:00:49.379 --> 00:00:51.309
with many of my students from my group
00:00:51.309 --> 00:00:54.070
here in the audience also speaking.
00:00:54.070 --> 00:00:57.110
We study security in the real world.
00:00:57.110 --> 00:01:00.960
So tonight, we have
a very special story to tell you
00:01:00.960 --> 00:01:03.670
that I'm very proud to be telling
00:01:03.670 --> 00:01:06.260
along with my colleague Nadia Heninger.
00:01:06.260 --> 00:01:07.660
We're going to be talking
00:01:07.660 --> 00:01:10.890
about discrete log, Diffie-Hellman
00:01:10.890 --> 00:01:13.770
and some of the, um,
00:01:13.770 --> 00:01:15.790
the research that we've done
00:01:15.790 --> 00:01:16.890
over the past year,
00:01:16.890 --> 00:01:19.500
try to understand how the NSA
00:01:19.500 --> 00:01:21.640
may be breaking so much of the crypto
00:01:21.640 --> 00:01:23.740
that we know they're breaking.
00:01:23.740 --> 00:01:25.680
Why do we...? So this work is
00:01:25.680 --> 00:01:28.840
joint work with a number of co-authors,
00:01:28.840 --> 00:01:30.750
with 12 other co-authors,
00:01:30.750 --> 00:01:33.570
3 of them are in this room right now,
00:01:33.570 --> 00:01:34.750
and I'd ask to stand up
00:01:34.750 --> 00:01:35.920
but they said they didn't want to
00:01:35.920 --> 00:01:38.210
so please, a quick round of applause
00:01:38.210 --> 00:01:39.790
for my co-authors as well.
00:01:39.790 --> 00:01:47.980
applause
00:01:47.980 --> 00:01:49.790
So, thank you.
00:01:49.790 --> 00:01:51.100
So in this very room,
00:01:51.100 --> 00:01:53.620
a year ago at 31C3,
00:01:53.620 --> 00:01:56.250
Jacob Appelbaum and Laura Poitras
00:01:56.250 --> 00:01:59.250
gave a talk, "Reconstructing Narratives",
00:01:59.250 --> 00:02:02.860
in which they announced some new results
00:02:02.860 --> 00:02:05.450
from the Snowden archives.
00:02:05.450 --> 00:02:08.780
They were able to tell us how the NSA,
00:02:08.780 --> 00:02:11.920
that the NSA was breaking cryptography
00:02:11.920 --> 00:02:15.320
used in widespread online communication.
00:02:15.320 --> 00:02:17.660
And, they later published
00:02:17.660 --> 00:02:20.890
an article in der Spiegel,
00:02:20.890 --> 00:02:23.610
in which the article included documents
00:02:23.610 --> 00:02:27.690
that showed indeed the scope of NSA
00:02:27.690 --> 00:02:30.410
breaking widely used encryption
00:02:30.410 --> 00:02:32.210
was significant.
00:02:32.210 --> 00:02:33.750
That NSA is breaking,
00:02:33.750 --> 00:02:35.560
maybe not all crypto,
00:02:35.560 --> 00:02:38.230
but they're able to break
widely used crypto
00:02:38.230 --> 00:02:40.250
from many of the different kinds
00:02:40.250 --> 00:02:44.540
of services and protocols we care about.
00:02:44.540 --> 00:02:46.400
What the leaks didn't answer
00:02:46.400 --> 00:02:49.440
is how NSA is breaking this cryptography
00:02:49.440 --> 00:02:51.210
and to a technologist,
00:02:51.210 --> 00:02:54.020
well, if we don't know
how they're breaking it,
00:02:54.020 --> 00:02:56.970
what can we do to stop it?
00:02:56.970 --> 00:02:59.760
So, Nadia and I and our co-authors set out
00:02:59.760 --> 00:03:00.780
earlier this year
00:03:00.780 --> 00:03:03.550
to try to, through our research,
00:03:03.550 --> 00:03:05.780
start answering those questions.
00:03:05.780 --> 00:03:08.110
How is NSA likely to be breaking
00:03:08.110 --> 00:03:10.100
likely used cryptography,
00:03:10.100 --> 00:03:13.330
and what can we and other researchers do
00:03:13.330 --> 00:03:15.170
to stop government from being able
00:03:15.170 --> 00:03:18.350
to attack the crypto
that all of us depend on?
00:03:18.350 --> 00:03:21.130
So, so...
applause
00:03:21.130 --> 00:03:24.240
Let's tell the story.
00:03:24.240 --> 00:03:28.030
Wait until you see how it ends!
00:03:28.030 --> 00:03:30.390
So if I were setting out as the attacker
00:03:30.390 --> 00:03:32.140
to break widely used crypto,
00:03:32.140 --> 00:03:35.990
well, there's a few different ways
that I could do it.
00:03:35.990 --> 00:03:38.040
One branch of the decision tree here
00:03:38.040 --> 00:03:40.269
is to attacking the implementations
00:03:40.269 --> 00:03:42.470
right, either finding vulnerabilities
00:03:42.470 --> 00:03:43.980
or introducing backdoors,
00:03:43.980 --> 00:03:46.850
we've all been witnessing over the past
00:03:46.850 --> 00:03:50.610
week or so with Juniper and their systems
00:03:50.610 --> 00:03:54.040
being compromised.
00:03:54.040 --> 00:03:57.290
On the other hand,
there's another prong you could take.
00:03:57.290 --> 00:03:59.980
You could try to attack the crypto
algorithms themselves,
00:03:59.980 --> 00:04:01.930
the underlying crypto.
00:04:01.930 --> 00:04:02.950
And the difference is,
00:04:02.950 --> 00:04:04.440
if you're attacking implementations,
00:04:04.440 --> 00:04:05.830
you have to make a big investment
00:04:05.830 --> 00:04:09.020
in every hardware device
and piece of software
00:04:09.020 --> 00:04:10.840
that you're trying to compromise.
00:04:10.840 --> 00:04:13.160
If you're attacking the underlying crypto,
00:04:13.160 --> 00:04:17.339
you have just one, a one-stop shop
00:04:17.339 --> 00:04:21.029
to gain access to,
potentially a very wide swath
00:04:21.029 --> 00:04:23.039
of all the crypto in use.
00:04:23.039 --> 00:04:25.139
So a small number of algorithms
00:04:25.139 --> 00:04:28.229
predominate for both
symmetric cryptography,
00:04:28.229 --> 00:04:30.590
things like AES and RC4,
00:04:30.590 --> 00:04:32.710
but those particular algorithms anyway,
00:04:32.710 --> 00:04:34.509
most cryptographers seem to think
00:04:34.509 --> 00:04:35.659
that breaking them,
00:04:35.659 --> 00:04:37.300
at least in the general case,
00:04:37.300 --> 00:04:39.470
is pretty hard right now.
00:04:39.470 --> 00:04:41.300
Instead though, we also have
00:04:41.300 --> 00:04:44.199
a very small number of
public key crypto algorithms
00:04:44.199 --> 00:04:46.559
that are also in use very widely
00:04:46.559 --> 00:04:50.339
for most or all of the protocols
and services we care about.
00:04:50.339 --> 00:04:53.059
Things like RSA and Diffie-Hellman.
00:04:53.059 --> 00:04:55.779
And here be dragons, as they say,
00:04:55.779 --> 00:04:59.520
this is the cryptography that we
and many other cryptographers
00:04:59.520 --> 00:05:02.610
think is most likely to be targeted.
00:05:02.610 --> 00:05:04.960
So, I'll hand it off to Nadia
00:05:04.960 --> 00:05:08.059
to talk about breaking public key.
00:05:08.059 --> 00:05:15.170
applause
00:05:15.170 --> 00:05:16.819
NH: So, in order to understand
00:05:16.819 --> 00:05:19.240
a little bit about
how cryptanalysis works,
00:05:19.240 --> 00:05:20.800
I'm going to go all the way back
00:05:20.800 --> 00:05:23.349
to the very beginning of
public key cryptography
00:05:23.349 --> 00:05:25.460
from the 70s,
00:05:25.460 --> 00:05:28.729
and I'll start by explaining
a little bit about RSA.
00:05:28.729 --> 00:05:31.670
This is Rivest, Shamir, and Adleman
up on the screen here,
00:05:31.670 --> 00:05:33.519
from the 70s, you can tell.
00:05:33.519 --> 00:05:35.780
And this is sort of the simple example,
00:05:35.780 --> 00:05:37.360
and then we'll talk a little bit more
00:05:37.360 --> 00:05:40.900
about the actual
Diffie-Hellman-based cryptanalysis
00:05:40.900 --> 00:05:43.270
that we're actually talking about.
00:05:43.270 --> 00:05:46.770
So, this the first public-key
crypto algorithm
00:05:46.770 --> 00:05:47.800
that was ever published,
00:05:47.800 --> 00:05:49.939
and it is still the most widely used
00:05:49.939 --> 00:05:52.680
cryptography, public key cryptography
algorithm out there.
00:05:52.680 --> 00:05:55.389
That shows you, I guess something
about the naturalness of ideas,
00:05:55.389 --> 00:05:56.749
or maybe the lack of progress
00:05:56.749 --> 00:05:59.049
that we've had in the past 40 years.
00:05:59.049 --> 00:06:03.529
So, here's sort of the textbook version
of RSA encryption,
00:06:03.529 --> 00:06:05.020
what we really care about is that...
00:06:05.020 --> 00:06:06.639
So, Alice and Bob, they want
00:06:06.639 --> 00:06:08.569
to bootstrap communication over
00:06:08.569 --> 00:06:09.759
an untrusted channel,
00:06:09.759 --> 00:06:12.009
so there's some eavesdropper
in between them
00:06:12.009 --> 00:06:13.430
who's intercepting their messages.
00:06:13.430 --> 00:06:15.860
And, in order to get around this,
00:06:15.860 --> 00:06:17.599
they need to somehow figure out
00:06:17.599 --> 00:06:20.979
how to share a key in order to
00:06:20.979 --> 00:06:23.129
actually encrypt their communications.
00:06:23.129 --> 00:06:25.080
And the way that RSA accomplishes this,
00:06:25.080 --> 00:06:30.240
is, Bob here on the right has a public key
00:06:30.240 --> 00:06:32.729
which in RSA is e modulus N
00:06:32.729 --> 00:06:35.479
which is the product of
two large prime factors,
00:06:35.479 --> 00:06:37.589
and he sends this over to Alice,
00:06:37.589 --> 00:06:39.339
and Alice uses Bob's public key
00:06:39.339 --> 00:06:41.650
to encrypt a message, like a session key,
00:06:41.650 --> 00:06:43.430
and send it back to Bob,
00:06:43.430 --> 00:06:45.189
and then Bob can decrypt the message,
00:06:45.189 --> 00:06:46.340
get the session key,
00:06:46.340 --> 00:06:47.860
and they can communicate using
00:06:47.860 --> 00:06:49.510
some other symmetric cipher.
00:06:49.510 --> 00:06:53.919
So, this is the big picture
of RSA encryption.
00:06:53.919 --> 00:06:55.229
The reason that we think
00:06:55.229 --> 00:06:58.099
that RSA is secure is because
00:06:58.099 --> 00:07:02.869
the best way that we know how to break
an RSA public key
00:07:02.869 --> 00:07:04.879
is to factor the modulus,
00:07:04.879 --> 00:07:08.159
and as far as we know,
factoring is not very easy.
00:07:08.159 --> 00:07:10.860
So, in particular, factoring is
00:07:10.860 --> 00:07:11.849
what we hope is something like
00:07:11.849 --> 00:07:13.179
a one-way function,
00:07:13.179 --> 00:07:14.610
multiplication is easy,
00:07:14.610 --> 00:07:17.050
factoring the number into
two pieces again is hard,
00:07:17.050 --> 00:07:18.199
in some sense.
00:07:18.199 --> 00:07:19.969
And the best algorithm that we have
00:07:19.969 --> 00:07:21.189
in the general case, of, say
00:07:21.189 --> 00:07:23.719
an RSA modulus that's well-generated,
00:07:23.719 --> 00:07:27.110
is called the number field sieve.
00:07:27.110 --> 00:07:28.699
So here is the...
00:07:28.699 --> 00:07:30.909
this is as bad as technical
as I'm going to get,
00:07:30.909 --> 00:07:32.789
and I'm waving my hands vigorously here,
00:07:32.789 --> 00:07:34.869
but here's something along the lines of
00:07:34.869 --> 00:07:36.419
what the number field sieve algorithm
00:07:36.419 --> 00:07:37.919
actually looks like,
00:07:37.919 --> 00:07:39.550
so it's a multi-stage algorithm,
00:07:39.550 --> 00:07:41.240
it's rather complex,
00:07:41.240 --> 00:07:43.479
some stages parallelise very well,
00:07:43.479 --> 00:07:44.679
embarrassingly well,
00:07:44.679 --> 00:07:47.990
other stages parallelise somewhat
less well,
00:07:47.990 --> 00:07:51.189
and so we've got these multiple stages
that we go through,
00:07:51.189 --> 00:07:53.479
and at the end of the algorithm,
00:07:53.479 --> 00:07:55.189
we discover, we hope, a prime factor
00:07:55.189 --> 00:07:59.929
of the number that we're trying to factor.
00:07:59.929 --> 00:08:01.579
So, how long does it take to factor?
00:08:01.579 --> 00:08:02.710
Here's one answer:
00:08:02.710 --> 00:08:04.159
if you ask a number theorist, this is
00:08:04.159 --> 00:08:05.589
the answer that they all give you,
00:08:05.589 --> 00:08:07.479
they all go through the optimisation,
00:08:07.479 --> 00:08:09.679
and they will tell you the answer is
00:08:09.679 --> 00:08:11.639
a sub-exponential function in the size
00:08:11.639 --> 00:08:13.380
of the number that we're trying to factor.
00:08:13.380 --> 00:08:14.559
That I think is not the answer
00:08:14.559 --> 00:08:16.740
that you guys are looking for.
00:08:16.740 --> 00:08:19.979
So, here's a slightly more
concrete answer.
00:08:19.979 --> 00:08:21.679
So, how long does it take to factor
00:08:21.679 --> 00:08:23.080
different sizes of keys?
00:08:23.080 --> 00:08:25.469
So, for 512-bit RSA,
00:08:25.469 --> 00:08:29.979
the first 512-bit RSA modulus
was factored in 1999
00:08:29.979 --> 00:08:30.779
by a group of academics,
00:08:30.779 --> 00:08:34.179
that took them 6 months
and a few supercomputers,
00:08:34.179 --> 00:08:36.789
now you can rent supercomputers
by the hour.
00:08:36.789 --> 00:08:38.099
So what does that do?
00:08:38.099 --> 00:08:39.679
Well, some students of mine
00:08:39.679 --> 00:08:44.099
actually were able to factor
a 512-bit RSA key
00:08:44.099 --> 00:08:48.980
for 4 hours and 75 dollars on Amazon EC2.
00:08:48.980 --> 00:08:50.830
If you would like to do this too...
00:08:50.830 --> 00:08:54.469
applause
00:08:54.469 --> 00:08:56.880
So, you can also do this too,
00:08:56.880 --> 00:08:59.730
code is online, right here, download it,
00:08:59.730 --> 00:09:02.560
send us bug reports, etc.
00:09:02.560 --> 00:09:05.370
So, as we go up in key sizes,
00:09:05.370 --> 00:09:07.540
768-bit RSA modulus,
00:09:07.540 --> 00:09:10.069
estimate, current estimate is
00:09:10.069 --> 00:09:12.470
less than 1000 core-years,
00:09:12.470 --> 00:09:15.050
and for sort of reasonable-size
academic clusters,
00:09:15.050 --> 00:09:19.270
that should take less than
a calendar year to finish, now.
00:09:19.270 --> 00:09:22.589
That was,
the first 768-bit RSA factorisation
00:09:22.589 --> 00:09:25.440
was done in public in 2009.
00:09:25.440 --> 00:09:28.459
So, that gives you some idea
of sort of the progress.
00:09:28.459 --> 00:09:31.019
For 1024-bit RSA, nobody has factored
00:09:31.019 --> 00:09:32.860
a key of that size in public,
00:09:32.860 --> 00:09:34.139
the estimate is probably,
00:09:34.139 --> 00:09:36.350
it's about a million core-years,
00:09:36.350 --> 00:09:37.610
which is certainly within range
00:09:37.610 --> 00:09:41.060
for a large government,
00:09:41.060 --> 00:09:43.480
so it is against better recommendations
00:09:43.480 --> 00:09:47.539
to use a 1024-bit RSA key size,
at this point.
00:09:47.539 --> 00:09:48.660
Current recommendation is to use
00:09:48.660 --> 00:09:50.810
a 2048-bit RSA modulus,
00:09:50.810 --> 00:09:52.600
with current algorithms,
00:09:52.600 --> 00:09:54.110
nobody should ever be able to factor
00:09:54.110 --> 00:09:55.360
something at this size,
00:09:55.360 --> 00:09:57.769
without some kind of major improvement.
00:09:57.769 --> 00:10:02.400
So, there's the big picture for you.
00:10:02.400 --> 00:10:05.040
Now move on to Diffie-Hellman.
00:10:05.040 --> 00:10:08.870
So, the paper that introduced
Diffie-Hellman
00:10:08.870 --> 00:10:11.440
was called "New Directions
in Cryptography",
00:10:11.440 --> 00:10:13.959
it's one of the seminal papers
of the 20th century,
00:10:13.959 --> 00:10:15.869
how many of you have read this paper?
00:10:15.869 --> 00:10:17.629
You should all go read it right now,
00:10:17.629 --> 00:10:20.750
I mean not right now, maybe after I talk.
00:10:20.750 --> 00:10:22.700
The first sentence of this paper,
00:10:22.700 --> 00:10:24.690
written in 1976,
00:10:24.690 --> 00:10:28.399
is "We stand today on the brink
of a revolution in cryptography".
00:10:28.399 --> 00:10:30.279
This is one of the best opening sentences
00:10:30.279 --> 00:10:32.360
of an academic paper I've ever read,
00:10:32.360 --> 00:10:36.170
and they were 100% right
about everything they put in the paper.
00:10:36.170 --> 00:10:37.860
They laid out the entire foundations
00:10:37.860 --> 00:10:41.089
of cryptographic research
for a couple decades,
00:10:41.089 --> 00:10:43.269
and to boot they came up with
00:10:43.269 --> 00:10:45.660
the first public key exchange,
00:10:45.660 --> 00:10:48.230
that is still one of the commonly used
00:10:48.230 --> 00:10:50.510
public key methods we
00:10:50.510 --> 00:10:51.850
have on the Internet.
00:10:51.850 --> 00:10:55.750
So, all that in one paper.
00:10:55.750 --> 00:10:58.759
So, the way that
textbook Diffie-Hellman works,
00:10:58.759 --> 00:11:00.910
is, you've got a couple of parameters,
00:11:00.910 --> 00:11:03.509
you've got a prime p,
00:11:03.509 --> 00:11:09.060
and some element g less than p,
00:11:09.060 --> 00:11:11.250
you can think,
for concreteness, g is 2.
00:11:11.250 --> 00:11:12.760
It's a good number.
00:11:12.760 --> 00:11:15.759
And p is some very large prime,
00:11:15.759 --> 00:11:18.620
say 1024, 2048-bit prime.
00:11:18.620 --> 00:11:20.579
And so Alice and Bob,
00:11:20.579 --> 00:11:21.800
same as our previous scenario,
00:11:21.800 --> 00:11:23.190
they want to bootstrap communication
00:11:23.190 --> 00:11:25.790
in the presence of
an untrusted eavesdropper.
00:11:25.790 --> 00:11:26.980
So what they're going to do,
00:11:26.980 --> 00:11:29.479
Alice will generate some secret value a,
00:11:29.479 --> 00:11:32.259
and she will compute g^a mod p,
00:11:32.259 --> 00:11:34.049
and send it over to Bob,
00:11:34.049 --> 00:11:36.920
and Bob will compute some secret value b,
00:11:36.920 --> 00:11:38.410
and compute g^b mod p,
00:11:38.410 --> 00:11:40.089
and send it over to Alice,
00:11:40.089 --> 00:11:43.870
the eavesdropper sees the values
g^a and g^b,
00:11:43.870 --> 00:11:45.720
can't derive anything useful from those,
00:11:45.720 --> 00:11:47.779
but Alice and Bob can individually
00:11:47.779 --> 00:11:48.790
take their secrets
00:11:48.790 --> 00:11:52.410
and derive the values g^ab mod p,
00:11:52.410 --> 00:11:53.819
both the same values.
00:11:53.819 --> 00:11:55.680
And that becomes a shared secret,
00:11:55.680 --> 00:11:58.250
which they can then use as a session key,
00:11:58.250 --> 00:11:59.860
and, you know, switch to AES
00:11:59.860 --> 00:12:02.550
and start symmetrically
encrypting their data.
00:12:02.550 --> 00:12:05.070
So, that's Diffie-Hellman key exchange.
00:12:05.070 --> 00:12:06.470
Used all over the Internet,
00:12:06.470 --> 00:12:09.389
one of the commonly used things possible.
00:12:09.389 --> 00:12:12.939
So, one of the reasons that people
00:12:12.939 --> 00:12:15.499
have been advocating
Diffie-Hellman key exchange recently
00:12:15.499 --> 00:12:17.189
over, say, RSA,
00:12:17.189 --> 00:12:20.319
is because it can be, it can provide
00:12:20.319 --> 00:12:22.470
the property of perfect forward secrecy.
00:12:22.470 --> 00:12:23.649
So assuming that Alice and Bob
00:12:23.649 --> 00:12:26.720
generate fresh random
secret values a and b
00:12:26.720 --> 00:12:28.639
for every single connection,
00:12:28.639 --> 00:12:32.600
then if, say, some large government agency
00:12:32.600 --> 00:12:34.740
is collecting all of their communications
00:12:34.740 --> 00:12:37.290
and later tries to hack into Alice or Bob,
00:12:37.290 --> 00:12:38.730
or break one of their keys,
00:12:38.730 --> 00:12:40.899
in order to decrypt their communication,
00:12:40.899 --> 00:12:44.029
they can't hack into Alice or
Bob's computer later,
00:12:44.029 --> 00:12:46.389
and then discover the key
00:12:46.389 --> 00:12:47.860
that Alice and Bob used
00:12:47.860 --> 00:12:51.080
to generate all the conversations
that they had,
00:12:51.080 --> 00:12:53.650
because Alice and Bob have
already forgotten
00:12:53.650 --> 00:12:55.160
the keys that they used.
00:12:55.160 --> 00:12:56.560
So, as long as Alice and Bob
00:12:56.560 --> 00:12:59.969
are generating fresh random
values every time,
00:12:59.969 --> 00:13:01.279
those values should reveal nothing
00:13:01.279 --> 00:13:04.719
about past or future communications.
00:13:04.719 --> 00:13:07.320
So, that's perfect forward secrecy.
00:13:07.320 --> 00:13:09.470
And, a lot of people have,
00:13:09.470 --> 00:13:11.090
who really know what
they're talking about,
00:13:11.090 --> 00:13:13.039
including, unfortunately, me,
00:13:13.039 --> 00:13:15.080
on this stage a couple years ago,
00:13:15.080 --> 00:13:19.920
have said, "you guys should always use
Diffie-Hellman over RSA key exchange
00:13:19.920 --> 00:13:22.590
because of this property of
perfect forward secrecy".
00:13:22.590 --> 00:13:24.670
So here's a selection of quotes
00:13:24.670 --> 00:13:25.939
that I found on the Internet,
00:13:25.939 --> 00:13:27.629
just from googling
"perfect forward secrecy"
00:13:27.629 --> 00:13:29.029
and "Diffie-Hellman key exchange",
00:13:29.029 --> 00:13:30.839
and you find people saying that
00:13:30.839 --> 00:13:33.100
this provides better security,
00:13:33.100 --> 00:13:35.699
the NSA can decrypt nothing,
00:13:35.699 --> 00:13:40.589
1024-bit Diffie-Hellman is arguably
better than 1024-bit RSA,
00:13:40.589 --> 00:13:45.829
and then 1024-bit Diffie-Hellman
is better than any key size for RSA.
00:13:45.829 --> 00:13:47.870
This is a selection of friends
00:13:47.870 --> 00:13:49.300
and people I respect,
00:13:49.300 --> 00:13:52.500
and some also, also some
random people on Stack Overflow,
00:13:52.500 --> 00:13:53.999
which is where...
00:13:53.999 --> 00:13:55.180
laughter
00:13:55.180 --> 00:13:56.149
where we know everybody's actually
00:13:56.149 --> 00:13:58.270
getting their recommendations from.
00:13:58.270 --> 00:14:00.980
So, there's been wide-scale advocacy
00:14:00.980 --> 00:14:03.419
of perfect forward secrecy as
00:14:03.419 --> 00:14:05.639
like, the reason that you should
use Diffie-Hellman.
00:14:05.639 --> 00:14:09.149
It will protect you against the NSA.
00:14:09.149 --> 00:14:13.049
I'm sorry. We were wrong.
00:14:13.049 --> 00:14:14.230
And, why were we wrong?
00:14:14.230 --> 00:14:15.339
I'm going to tell little bit more
00:14:15.339 --> 00:14:17.199
about what the cryptanalysis looks like
00:14:17.199 --> 00:14:18.379
for Diffie-Hellman.
00:14:18.379 --> 00:14:21.670
So, the underlying problem
that we hope is hard
00:14:21.670 --> 00:14:22.779
for the security of Diffie-Hellman
00:14:22.779 --> 00:14:24.110
is called discrete log,
00:14:24.110 --> 00:14:26.629
it is exactly sort of the problem of
00:14:26.629 --> 00:14:30.160
given one of the key exchange values g^a mod p
00:14:30.160 --> 00:14:33.059
compute, say, Alice's secret a.
00:14:33.059 --> 00:14:34.470
This would allow the attacker
00:14:34.470 --> 00:14:35.579
to compute the shared secret
00:14:35.579 --> 00:14:39.050
in the same way that Alice did.
00:14:39.050 --> 00:14:42.950
And, sort of similar to
factoring and multiplication,
00:14:42.950 --> 00:14:44.540
discrete log, we think it's much harder
00:14:44.540 --> 00:14:46.550
than modular exponentiation,
00:14:46.550 --> 00:14:48.420
the computation that actually
00:14:48.420 --> 00:14:50.519
gives you the value g^a mod p.
00:14:50.519 --> 00:14:52.810
And the best algorithm that we have
00:14:52.810 --> 00:14:54.720
is called the number field sieve.
00:14:54.720 --> 00:14:58.049
So, there's a lot of parallels going on here.
00:14:58.049 --> 00:14:59.259
So what does the number field sieve
00:14:59.259 --> 00:15:00.939
for discrete log look like?
00:15:00.939 --> 00:15:05.030
Hopefully this diagram is somewhat
familiar to you by now,
00:15:05.030 --> 00:15:06.600
it's a multi-stage algorithm,
00:15:06.600 --> 00:15:10.490
it has many of the same
stages as factoring,
00:15:10.490 --> 00:15:12.699
you can sort of line them up in parallel,
00:15:12.699 --> 00:15:14.949
the last bit looks a little bit different,
00:15:14.949 --> 00:15:17.090
but we can sort of ignore that
for the moment.
00:15:17.090 --> 00:15:20.160
Okay. So, we have some pictures
00:15:20.160 --> 00:15:22.829
of what the number field sieve looks like.
00:15:22.829 --> 00:15:24.699
How long does it take?
00:15:24.699 --> 00:15:28.720
Answer number 1:
The same answer as factoring.
00:15:28.720 --> 00:15:31.379
In case you didn't remember,
here it is again.
00:15:31.379 --> 00:15:33.420
This is kind of why everybody
has been saying
00:15:33.420 --> 00:15:35.260
"Okay, the security of, you know,
00:15:35.260 --> 00:15:36.829
1024-bit Diffie-Hellman key exchange
00:15:36.829 --> 00:15:38.959
is about the same as the security of
00:15:38.959 --> 00:15:41.059
a 1024-bit RSA key."
00:15:41.059 --> 00:15:44.809
It's because we have the same
complicated formula that tells us
00:15:44.809 --> 00:15:47.730
how hard it is to break.
00:15:47.730 --> 00:15:49.779
The sort of more subtle answer for...
00:15:49.779 --> 00:15:51.699
or, not more subtle,
but the more practical answer
00:15:51.699 --> 00:15:53.070
for, how secure is it,
00:15:53.070 --> 00:15:55.769
is, we can say, well, how long do we think
00:15:55.769 --> 00:15:56.959
it will take to actually compute
00:15:56.959 --> 00:15:59.910
a discrete log for
commonly used key sizes,
00:15:59.910 --> 00:16:01.089
and the answer is,
00:16:01.089 --> 00:16:04.600
slightly longer than factoring an
RSA key of equivalent size,
00:16:04.600 --> 00:16:09.479
but, not so much longer than an RSA key.
00:16:09.479 --> 00:16:12.160
And, the minimum recommended key size
00:16:12.160 --> 00:16:14.759
today is 2048 bits.
00:16:14.759 --> 00:16:18.019
Okay, so, 2048-bit Diffie-Hellman,
00:16:18.019 --> 00:16:22.219
we're good. Great! We can all go home.
00:16:22.219 --> 00:16:24.499
Okay. However, okay,
00:16:24.499 --> 00:16:26.350
what if you want to break many connections
00:16:26.350 --> 00:16:28.829
that use the same public parameter p?
00:16:28.829 --> 00:16:30.749
Do you have to go through
00:16:30.749 --> 00:16:33.569
this whole computation,
00:16:33.569 --> 00:16:35.269
every single, for every single connection
00:16:35.269 --> 00:16:36.569
that you want to break?
00:16:36.569 --> 00:16:41.100
That was kind of the justification
00:16:41.100 --> 00:16:42.550
for perfect forward secrecy,
00:16:42.550 --> 00:16:43.949
that every single connection
00:16:43.949 --> 00:16:45.920
should be as hard as factoring an RSA key
00:16:45.920 --> 00:16:48.259
of the equivalent size.
00:16:48.259 --> 00:16:50.489
Except that's not quite the case.
00:16:50.489 --> 00:16:51.850
Because if you look at where
00:16:51.850 --> 00:16:54.360
the actual target that
we're trying to compute
00:16:54.360 --> 00:16:56.730
appears in this plot,
00:16:56.730 --> 00:16:58.620
it's only at the very last stage.
00:16:58.620 --> 00:17:00.410
So all of this only depends
00:17:00.410 --> 00:17:01.979
on the prime p.
00:17:01.979 --> 00:17:05.720
So we can actually divide up
the algorithm in two pieces:
00:17:05.720 --> 00:17:09.579
A few stages that depend only
on the prime p that we're using,
00:17:09.579 --> 00:17:11.640
and then the final computation
00:17:11.640 --> 00:17:14.480
that takes the output of this
first precomputation stage,
00:17:14.480 --> 00:17:15.520
and that's the only stage
00:17:15.520 --> 00:17:17.280
that actually matters,
00:17:17.280 --> 00:17:19.450
that actually depends on the target
00:17:19.450 --> 00:17:22.610
of our discrete log computation.
00:17:22.610 --> 00:17:27.459
So, we're in trouble.
00:17:27.459 --> 00:17:29.550
In particular, that means that
00:17:29.550 --> 00:17:33.390
if many connections are using
this same prime p,
00:17:33.390 --> 00:17:35.650
you can do the precomputation once,
00:17:35.650 --> 00:17:37.470
spend a huge amount of effort,
00:17:37.470 --> 00:17:39.490
and then the actual effort required
00:17:39.490 --> 00:17:43.260
to break individual connections
using those primes
00:17:43.260 --> 00:17:46.060
is much, much smaller.
00:17:46.060 --> 00:17:48.300
So here's our current estimates,
00:17:48.300 --> 00:17:50.430
these are actually somewhat new
from our paper,
00:17:50.430 --> 00:17:54.120
of how long the individual log stage
takes in practice,
00:17:54.120 --> 00:17:55.810
if you push the primer as far as you can
00:17:55.810 --> 00:17:57.680
to make this as fast as possible.
00:17:57.680 --> 00:17:59.330
And the answer is basically,
00:17:59.330 --> 00:18:01.810
if you're worried about a government,
00:18:01.810 --> 00:18:03.540
you better start worrying
00:18:03.540 --> 00:18:08.650
for reasonable key sizes
that people are using.
00:18:08.650 --> 00:18:11.380
See, so I'll let Alex continue
00:18:11.380 --> 00:18:14.520
with the next part of our talk.
00:18:14.520 --> 00:18:21.800
applause
00:18:21.800 --> 00:18:24.830
So this fact that Nadia just told us
00:18:24.830 --> 00:18:27.290
about Diffie-Hellman
00:18:27.290 --> 00:18:29.150
and the number field sieve,
00:18:29.150 --> 00:18:33.600
this was something that the
mathematical crypto people knew about,
00:18:33.600 --> 00:18:35.970
but most of us who did system security,
00:18:35.970 --> 00:18:37.610
people like me,
00:18:37.610 --> 00:18:40.030
didn't ever get the memo.
00:18:40.030 --> 00:18:43.880
So, it's, I'm here in part to apologise
00:18:43.880 --> 00:18:45.290
to everyone I've taught
00:18:45.290 --> 00:18:48.290
about Diffie-Hellman and cryptanalysis
00:18:48.290 --> 00:18:50.010
who didn't get to hear about this,
00:18:50.010 --> 00:18:51.000
as we were talking about
00:18:51.000 --> 00:18:52.490
perfect forward secrecy.
00:18:52.490 --> 00:18:54.840
Right, this fact about the cryptanalysis
00:18:54.840 --> 00:18:56.910
and how well it can apply in exactly
00:18:56.910 --> 00:18:58.670
the scenario that we're worried about,
00:18:58.670 --> 00:19:02.090
this kind of situation
involving mass surveillance,
00:19:02.090 --> 00:19:04.670
was news to many of those.
00:19:04.670 --> 00:19:06.320
But now that we have that fact,
00:19:06.320 --> 00:19:08.040
how can we exploit it,
00:19:08.040 --> 00:19:09.870
to try to break Diffie-Hellman,
00:19:09.870 --> 00:19:12.080
in scenarios that we all care about?
00:19:12.080 --> 00:19:13.020
And we're going to talk about
00:19:13.020 --> 00:19:15.960
two scenarios in the talk today.
00:19:15.960 --> 00:19:19.130
The first one applies to HTTPS,
00:19:19.130 --> 00:19:21.720
to encrypted web connections,
00:19:21.720 --> 00:19:24.960
and it applies not only
to government agencies,
00:19:24.960 --> 00:19:27.750
but also just to normal
everyday attackers,
00:19:27.750 --> 00:19:29.020
with maybe the same resources
00:19:29.020 --> 00:19:31.030
that you or I have.
00:19:31.030 --> 00:19:35.280
Right, this is a down-to-earth
kind of attack on HTTPS,
00:19:35.280 --> 00:19:37.630
and we call it Logjam.
00:19:37.630 --> 00:19:39.870
Logjam allows us to break
00:19:39.870 --> 00:19:41.740
the HTTPS connections
00:19:41.740 --> 00:19:44.070
to many, many popular websites
00:19:44.070 --> 00:19:45.800
in modern browsers,
00:19:45.800 --> 00:19:48.610
by fooling those browsers into using
00:19:48.610 --> 00:19:53.310
1990s-era backdoored crypto.
00:19:53.310 --> 00:19:55.680
So where does this backdoored
crypto come from?
00:19:55.680 --> 00:19:57.650
This is from the first crypto wars,
00:19:57.650 --> 00:19:59.040
back in the 90s,
00:19:59.040 --> 00:20:01.330
when my country, the US,
00:20:01.330 --> 00:20:04.110
had restrictions on what kind and strength
00:20:04.110 --> 00:20:06.680
of cryptography could be exported,
00:20:06.680 --> 00:20:08.690
and used by people abroad.
00:20:08.690 --> 00:20:10.580
So US companies were prohibited
00:20:10.580 --> 00:20:12.570
from exporting products that contained
00:20:12.570 --> 00:20:15.960
cryptography that had greater
than a certain strength.
00:20:15.960 --> 00:20:18.020
For RSA, that was that the key size
00:20:18.020 --> 00:20:21.250
had to be less than or equal to 512 bits,
00:20:21.250 --> 00:20:22.840
and for Diffie-Hellman it was that
00:20:22.840 --> 00:20:27.400
basically the prime had to be
512 bits or less.
00:20:27.400 --> 00:20:28.540
So back in the 90s,
00:20:28.540 --> 00:20:29.970
these were constants,
00:20:29.970 --> 00:20:31.380
these were strengths of crypto
00:20:31.380 --> 00:20:33.730
that were chosen presumably because
00:20:33.730 --> 00:20:37.740
they were easy for NSA to break.
00:20:37.740 --> 00:20:39.690
So, if you were an American company
00:20:39.690 --> 00:20:42.170
making products, like let's say
00:20:42.170 --> 00:20:44.830
Netscape Navigator, the web browser
00:20:44.830 --> 00:20:50.980
that initiated the first SSL protocol,
00:20:50.980 --> 00:20:53.000
you needed some way to be able
00:20:53.000 --> 00:20:54.980
to communicate with,
00:20:54.980 --> 00:20:56.920
from servers in the US,
00:20:56.920 --> 00:20:59.360
to clients, including your own browser,
00:20:59.360 --> 00:21:01.070
that you would ship to people abroad,
00:21:01.070 --> 00:21:03.120
say, here in Germany.
00:21:03.120 --> 00:21:04.870
And so they came up with a way
00:21:04.870 --> 00:21:10.660
to use, to have HTTPS automatically select
00:21:10.660 --> 00:21:12.880
the appropriate key strength
00:21:12.880 --> 00:21:14.430
depending on whether the browser
00:21:14.430 --> 00:21:17.470
was able to support
the full-strength cryptography,
00:21:17.470 --> 00:21:18.740
or the weakened version
00:21:18.740 --> 00:21:20.530
for deployment abroad.
00:21:20.530 --> 00:21:22.290
And the way that they did that
00:21:22.290 --> 00:21:23.350
was something called
00:21:23.350 --> 00:21:26.210
export-grade cipher suites.
00:21:26.210 --> 00:21:27.090
So when your browser,
00:21:27.090 --> 00:21:29.080
whenever it starts a TLS connection
00:21:29.080 --> 00:21:31.380
for an HTTPS URL,
00:21:31.380 --> 00:21:32.800
one of the first thing that it does
00:21:32.800 --> 00:21:35.540
is, the browser will send to the server
00:21:35.540 --> 00:21:37.480
a list of the kinds of cryptography
00:21:37.480 --> 00:21:38.930
that it can speak,
00:21:38.930 --> 00:21:40.950
these are called cipher suites,
00:21:40.950 --> 00:21:44.150
and then the server selects one of those,
00:21:44.150 --> 00:21:46.240
that is compatible with
whatever cryptography
00:21:46.240 --> 00:21:48.190
the server has available,
00:21:48.190 --> 00:21:50.450
and then that negotiated cipher suite
00:21:50.450 --> 00:21:53.540
is what's used for the connection.
00:21:53.540 --> 00:21:55.210
Now the way that they supported
00:21:55.210 --> 00:21:57.890
the 90s-era backdoor crypto
00:21:57.890 --> 00:22:01.380
was by having browsers shipped abroad
00:22:01.380 --> 00:22:03.370
from the United States that could only
00:22:03.370 --> 00:22:06.140
speak a certain subset
of crypto algorithms,
00:22:06.140 --> 00:22:07.520
that were limited in strength
00:22:07.520 --> 00:22:09.880
to 512 bits or less,
00:22:09.880 --> 00:22:11.730
those were the export-grade cipher suites
00:22:11.730 --> 00:22:13.870
with the names you see here.
00:22:13.870 --> 00:22:18.930
Now, even though no
browser has been shipped
00:22:18.930 --> 00:22:21.740
that is limited to only these suites,
00:22:21.740 --> 00:22:24.340
since probably 2000-sometime,
00:22:24.340 --> 00:22:27.520
when the US relaxed
its export regulations,
00:22:27.520 --> 00:22:29.440
there wasn't just any one day
00:22:29.440 --> 00:22:33.060
when all of those old browsers
00:22:33.060 --> 00:22:35.490
from before that era went away.
00:22:35.490 --> 00:22:38.830
So, servers, even now, many servers
00:22:38.830 --> 00:22:42.630
will still accept and speak
these weakened cipher suites,
00:22:42.630 --> 00:22:45.450
if that's all the browser has available.
00:22:45.450 --> 00:22:47.550
Like if you're running an e-commerce site,
00:22:47.550 --> 00:22:49.760
right, I'm sure you still want to be able
00:22:49.760 --> 00:22:51.430
to speak to any customers
00:22:51.430 --> 00:22:54.670
who have 1998-era
Netspace Navigator involved,
00:22:54.670 --> 00:22:57.030
otherwise you'd lose some sales, right?
00:22:57.030 --> 00:22:59.010
So there was no reason to turn them off,
00:22:59.010 --> 00:23:02.050
because no modern browser any more,
00:23:02.050 --> 00:23:03.900
now that those restrictions are lifted,
00:23:03.900 --> 00:23:06.690
would choose these weakened suites.
00:23:06.690 --> 00:23:09.450
Well, that's what we thought, anyway.
00:23:09.450 --> 00:23:13.360
So, in, over this past year,
00:23:13.360 --> 00:23:15.740
there were two attacks that exploited
00:23:15.740 --> 00:23:17.290
these weakened cipher suites,
00:23:17.290 --> 00:23:20.710
that found ways to convince
modern browsers
00:23:20.710 --> 00:23:23.990
to speak them instead of
full-strength cryptography.
00:23:23.990 --> 00:23:26.500
The first was the FREAK attack,
00:23:26.500 --> 00:23:28.800
which was revealed in early 2015
00:23:28.800 --> 00:23:32.040
by a separate group of authors,
00:23:32.040 --> 00:23:34.980
and the FREAK attack was
an implementation flaw
00:23:34.980 --> 00:23:38.850
in many modern browsers.
00:23:38.850 --> 00:23:40.370
In order to exploit it,
00:23:40.370 --> 00:23:42.150
all you need to do is to be able
00:23:42.150 --> 00:23:44.220
to relatively inexpensively
00:23:44.220 --> 00:23:48.340
factor a 512-bit RSA key.
00:23:48.340 --> 00:23:50.070
And, as Nadia has told you,
00:23:50.070 --> 00:23:52.760
this is now a matter of maybe 4 hours,
00:23:52.760 --> 00:23:55.250
maybe 75 dollars, something like that,
00:23:55.250 --> 00:23:57.230
and if you did that, you'd able to break
00:23:57.230 --> 00:23:59.640
all the connections coming into
00:23:59.640 --> 00:24:01.920
a weak server for a long period of time,
00:24:01.920 --> 00:24:06.150
to a server that still spoke
these cipher suites.
00:24:06.150 --> 00:24:08.030
So this affected most modern browsers,
00:24:08.030 --> 00:24:14.440
and just shy of 10% of Alexa
top million sites that speak HTTPS.
00:24:14.440 --> 00:24:16.880
Now that left the Diffie-Hellman
00:24:16.880 --> 00:24:18.650
export-grade cipher suites,
00:24:18.650 --> 00:24:21.000
which were not affected by FREAK.
00:24:21.000 --> 00:24:25.780
But we came up with a paper
in May of this year,
00:24:25.780 --> 00:24:27.570
that showed a separate attack,
00:24:27.570 --> 00:24:29.180
the Logjam attack,
00:24:29.180 --> 00:24:32.000
which is a protocol flaw in TLS,
00:24:32.000 --> 00:24:34.450
and affects all modern browsers,
00:24:34.450 --> 00:24:38.370
and, similarly, allows you
to downgrade connections
00:24:38.370 --> 00:24:40.580
to export-grade Diffie-Hellman,
00:24:40.580 --> 00:24:43.010
and then intercept or modify the contents,
00:24:43.010 --> 00:24:46.840
if the server speaks and still supports
00:24:46.840 --> 00:24:50.840
these export-grade Diffie-Hellman
cipher suites.
00:24:50.840 --> 00:24:52.290
So now let me give you
00:24:52.290 --> 00:24:55.030
the hopefully brief technical overview
00:24:55.030 --> 00:24:57.090
of how the Logjam attack works.
00:24:57.090 --> 00:24:59.080
If you've been curious about this,
00:24:59.080 --> 00:25:02.840
this is the chance to see it.
00:25:02.840 --> 00:25:04.920
So, Logjam is a problem that happens
00:25:04.920 --> 00:25:08.460
during the TLS connection handshake.
00:25:08.460 --> 00:25:10.200
And the first thing that happens
in the handshake,
00:25:10.200 --> 00:25:11.610
at the top of this diagram,
00:25:11.610 --> 00:25:13.430
so this is just your browser connecting
00:25:13.430 --> 00:25:16.600
to some website, some server
there on the right,
00:25:16.600 --> 00:25:19.580
maybe Alice connecting to
her favourite website here.
00:25:19.580 --> 00:25:21.560
So the first stage is this client hello,
00:25:21.560 --> 00:25:24.520
where, you know, a normal client
is going to say,
00:25:24.520 --> 00:25:26.790
I speak various kinds of cryptography,
00:25:26.790 --> 00:25:29.650
including full-strength Diffie-Hellman.
00:25:29.650 --> 00:25:31.350
The server at that point is going to
00:25:31.350 --> 00:25:35.720
respond by picking some cipher suite,
00:25:35.720 --> 00:25:37.560
let's say Diffie-Hellman,
00:25:37.560 --> 00:25:40.610
and then sending over
its certificate chain,
00:25:40.610 --> 00:25:45.280
as well as its Diffie-Hellman
public parameters,
00:25:45.280 --> 00:25:47.990
p and g, the server gets to choose them,
00:25:47.990 --> 00:25:49.260
as well as g^a.
00:25:49.260 --> 00:25:50.820
And then it's going to use
00:25:50.820 --> 00:25:54.760
its long-term RSA key that is the thing
00:25:54.760 --> 00:25:56.810
that is signed in its certificate,
00:25:56.810 --> 00:26:00.210
in order to make a signature on
those Diffie-Hellman parameters.
00:26:00.210 --> 00:26:02.130
Okay, then it's going to do...
00:26:02.130 --> 00:26:05.390
complete the negotiation, and so on.
00:26:05.390 --> 00:26:06.820
In the Logjam attack,
00:26:06.820 --> 00:26:08.610
we have a man-in-the-middle attacker,
00:26:08.610 --> 00:26:10.970
who's able to modify some
of these messages
00:26:10.970 --> 00:26:13.030
as they're going by.
00:26:13.030 --> 00:26:14.960
So the first thing the attacker does,
00:26:14.960 --> 00:26:17.460
he modifies the client hello message,
00:26:17.460 --> 00:26:19.710
to replace all of the different
kinds of cryptography
00:26:19.710 --> 00:26:21.640
the client says it supports,
00:26:21.640 --> 00:26:24.560
and just put in export-grade
Diffie-Hellman.
00:26:24.560 --> 00:26:27.240
Ah, the 90s are here again.
00:26:27.240 --> 00:26:29.920
Alright, so then, you know, the server
00:26:29.920 --> 00:26:32.790
will get that, and if the server supports
00:26:32.790 --> 00:26:34.850
export-grade Diffie-Hellman,
00:26:34.850 --> 00:26:39.180
as about 10% or so of servers
00:26:39.180 --> 00:26:41.070
still support export grade Diffie-Hellman,
00:26:41.070 --> 00:26:43.670
it's going to respond and say,
00:26:43.670 --> 00:26:46.110
okay, that's what you asked for,
I'll take it,
00:26:46.110 --> 00:26:49.100
and it's going to send over its side
00:26:49.100 --> 00:26:51.270
of the Diffie-Hellman key exchange,
00:26:51.270 --> 00:26:54.170
but using a 512-bit prime,
00:26:54.170 --> 00:26:56.550
because that's what is required under
00:26:56.550 --> 00:26:59.500
these export-grade suites.
00:26:59.500 --> 00:27:02.400
Now, at that point, the browser would
00:27:02.400 --> 00:27:04.600
normally reject this message,
00:27:04.600 --> 00:27:06.540
because it didn't ask for export-grade,
00:27:06.540 --> 00:27:09.770
it really asked for full-strength,
00:27:09.770 --> 00:27:11.540
so instead, the man in the middle has to
00:27:11.540 --> 00:27:15.500
modify the server's hello message,
00:27:15.500 --> 00:27:18.270
and say that this is full-strength
Diffie-Hellman,
00:27:18.270 --> 00:27:19.630
well, if it's full-strength,
00:27:19.630 --> 00:27:22.970
why is it only a 512-bit prime
that's being used?
00:27:22.970 --> 00:27:25.780
Well, there's actually no limitation,
00:27:25.780 --> 00:27:27.820
and no distinction between the messages
00:27:27.820 --> 00:27:33.550
that the server would send
in that space with p and g,
00:27:33.550 --> 00:27:35.980
that says normal-grade Diffie-Hellman
00:27:35.980 --> 00:27:38.410
has to be more than 512 bits.
00:27:38.410 --> 00:27:41.110
In fact we found a handful of real sites
00:27:41.110 --> 00:27:43.480
that even for normal-strength
Diffie-Hellman
00:27:43.480 --> 00:27:48.540
just happened to use 512-bit
or even weaker cryptography.
00:27:48.540 --> 00:27:50.960
So, as long as we modify
this earlier message,
00:27:50.960 --> 00:27:52.680
the server's hello message,
00:27:52.680 --> 00:27:55.240
and make it say, "normal-strength
Diffie-Hellman",
00:27:55.240 --> 00:27:57.460
there's no way for the client to tell
00:27:57.460 --> 00:27:59.420
from just the structure of the protocol,
00:27:59.420 --> 00:28:01.460
that anything is amiss.
00:28:01.460 --> 00:28:04.570
So, at this point, there is one last place
00:28:04.570 --> 00:28:06.130
that we could catch the problem,
00:28:06.130 --> 00:28:07.850
that the client or the server could see
00:28:07.850 --> 00:28:09.670
that something's wrong,
00:28:09.670 --> 00:28:12.800
which is that each side sends
the other a finished message,
00:28:12.800 --> 00:28:15.010
here at the end,
00:28:15.010 --> 00:28:22.100
that says, basically, has, uses
the session secrets
00:28:22.100 --> 00:28:25.020
to add an authentication code
00:28:25.020 --> 00:28:27.750
to a dialogue of all of the
protocol messages
00:28:27.750 --> 00:28:30.370
that match the handshake dialogue,
00:28:30.370 --> 00:28:34.090
all the messages going back
in each direction so far
00:28:34.090 --> 00:28:37.280
have to be the same from each side of you.
00:28:37.280 --> 00:28:40.300
However, in our case, in Logjam,
00:28:40.300 --> 00:28:43.170
the attacker is able to spoof
these messages,
00:28:43.170 --> 00:28:45.730
to make them look correct to each side.
00:28:45.730 --> 00:28:48.370
He's able to modify that dialogue why?
00:28:48.370 --> 00:28:52.900
Well, because we're using this
512-bit Diffie-Hellman
00:28:52.900 --> 00:28:58.150
that we know from using
the number field sieve,
00:28:58.150 --> 00:29:00.270
we are able to efficiently break.
00:29:00.270 --> 00:29:02.730
So, if the attacker is able to quickly
00:29:02.730 --> 00:29:03.990
perform the discrete log
00:29:03.990 --> 00:29:08.560
on the Diffie-Hellman key exchange
00:29:08.560 --> 00:29:11.430
that's going by at 512-bit strength,
00:29:11.430 --> 00:29:14.610
then he can fix up the client
and server hello messages,
00:29:14.610 --> 00:29:17.380
and neither side will notice
that anything went wrong.
00:29:17.380 --> 00:29:19.290
So that's Logjam in a nutshell.
00:29:19.290 --> 00:29:21.790
I'm sorry, it's a little bit complicated.
00:29:21.790 --> 00:29:24.680
So, how widely shared are
00:29:24.680 --> 00:29:27.500
these Diffie-Hellman public parameters?
00:29:27.500 --> 00:29:30.850
Well, we used Internet-wide
scanning to find out.
00:29:30.850 --> 00:29:33.640
So, my group, we also made
something called zmap,
00:29:33.640 --> 00:29:35.810
that I talked about here
a couple of years ago,
00:29:35.810 --> 00:29:39.010
which lets us quickly probe
everything on the Internet,
00:29:39.010 --> 00:29:42.210
and so we did this and tried to make
00:29:42.210 --> 00:29:44.480
connections to each HTTPS server
00:29:44.480 --> 00:29:46.850
in the public IPv4 address space,
00:29:46.850 --> 00:29:49.590
and found out what key exchange methods
00:29:49.590 --> 00:29:52.280
were supported and with what primes.
00:29:52.280 --> 00:29:56.120
And what we find is that 97% of hosts
00:29:56.120 --> 00:29:58.470
that support export-grade Diffie-Hellman
00:29:58.470 --> 00:30:01.130
use one of only 3 512-bit primes.
00:30:01.130 --> 00:30:02.930
They're that widely-shared.
00:30:02.930 --> 00:30:04.840
Why is this? Because those parameters
00:30:04.840 --> 00:30:06.720
are very often either hard-coded
00:30:06.720 --> 00:30:08.160
or encoded in standards
00:30:08.160 --> 00:30:10.040
that different people implement.
00:30:10.040 --> 00:30:11.680
The most common of these,
00:30:11.680 --> 00:30:15.100
used by 80% of hosts that support
export-grade Diffie-Hellman,
00:30:15.100 --> 00:30:20.760
is a public parameter that's
hardcoded into Apache 2.2.
00:30:20.760 --> 00:30:23.160
So, it's actually there,
embedded in the source,
00:30:23.160 --> 00:30:26.100
you have to recompile Apache to change it.
00:30:26.100 --> 00:30:28.500
13% of hosts supported something,
00:30:28.500 --> 00:30:31.850
a second prime that has also 512 bits,
00:30:31.850 --> 00:30:34.770
that's hardcoded in mod_ssl,
00:30:34.770 --> 00:30:37.260
and the next most popular, 4%,
00:30:37.260 --> 00:30:40.050
was in the Sun JDK.
00:30:40.050 --> 00:30:43.270
Only 10 primes accounted for 99%
00:30:43.270 --> 00:30:45.270
of all the hosts we found in
the public address space
00:30:45.270 --> 00:30:49.090
that supported export-grade
Diffie-Hellman.
00:30:49.090 --> 00:30:54.370
So, if we would like to compromise these,
00:30:54.370 --> 00:30:56.900
well, Nadia just told you about
00:30:56.900 --> 00:31:01.870
how long it takes to use
the number field sieve
00:31:01.870 --> 00:31:05.050
to break 512-bit discrete log,
00:31:05.050 --> 00:31:08.480
well, we actually went and did
the precomputation
00:31:08.480 --> 00:31:13.140
for all 3 of these most widely used
Diffie-Hellman primes,
00:31:13.140 --> 00:31:18.760
and our colleagues who make a tool
called CADO-NFS
00:31:18.760 --> 00:31:22.180
where able to implement the code
00:31:22.180 --> 00:31:28.450
for that piece of the discrete log version
of the number field sieve
00:31:28.450 --> 00:31:30.960
and they ran the algorithm on these primes
00:31:30.960 --> 00:31:34.080
on a cluster they just happened
to have lying around,
00:31:34.080 --> 00:31:37.800
it took about a week of time
on the cluster
00:31:37.800 --> 00:31:39.570
for each of these primes.
00:31:39.570 --> 00:31:41.980
After which, using an optimised version
00:31:41.980 --> 00:31:45.040
of the last portion of
the number field sieve,
00:31:45.040 --> 00:31:47.530
it takes about 70 seconds for us to break
00:31:47.530 --> 00:31:49.470
any individual connection
00:31:49.470 --> 00:31:54.330
that uses any one of these
3 most popular primes.
00:31:54.330 --> 00:31:57.090
So, Logjam and our precomputations
00:31:57.090 --> 00:31:59.100
now allow us to break any connection
00:31:59.100 --> 00:32:04.670
to about 8% of the top million
HTTPS sites from Alexa
00:32:04.670 --> 00:32:07.920
and when we came up with this attack,
00:32:07.920 --> 00:32:10.950
it worked in all modern browsers.
00:32:10.950 --> 00:32:12.530
So, mitigation!
00:32:12.530 --> 00:32:19.280
applause
00:32:19.280 --> 00:32:21.770
This is bad, everyone, this is the crypto
00:32:21.770 --> 00:32:24.740
all of us are using.
00:32:24.740 --> 00:32:26.560
So we do have some mitigations.
00:32:26.560 --> 00:32:28.340
This is the actual positive part,
00:32:28.340 --> 00:32:29.840
is that the browser makers have now
00:32:29.840 --> 00:32:32.900
started to increase the minimum strength
00:32:32.900 --> 00:32:34.860
of Diffie-Hellman they will accept.
00:32:34.860 --> 00:32:37.010
So IE, Chrome, and Firefox will reject
00:32:37.010 --> 00:32:38.750
primes less than 1024 bits
00:32:38.750 --> 00:32:41.200
and Safari less than 768.
00:32:41.200 --> 00:32:43.980
And the new draft of TLS 1.3 is including
00:32:43.980 --> 00:32:45.200
an anti-downgrade flag
00:32:45.200 --> 00:32:46.690
that will make it even harder
00:32:46.690 --> 00:32:49.750
for such attacks to take place
in the future.
00:32:49.750 --> 00:32:52.140
Now back to Nadia.
00:32:52.140 --> 00:32:54.240
NH: So we promised in our abstract...
00:32:54.240 --> 00:32:59.600
applause
00:32:59.600 --> 00:33:02.190
...that there would be a hands-on
portion of this talk.
00:33:02.190 --> 00:33:03.570
So, you have a couple options,
00:33:03.570 --> 00:33:05.580
number 1 is, if you're really into this,
00:33:05.580 --> 00:33:08.230
you can do and download
CADO-NFS yourselves,
00:33:08.230 --> 00:33:11.770
cado-nfs.gforge.inria.fr
00:33:11.770 --> 00:33:16.440
and, you know, run
discrete log algorithms yourselves
00:33:16.440 --> 00:33:17.790
for any prime you wish
00:33:17.790 --> 00:33:20.030
and then you can compute
arbitrary discrete logs.
00:33:20.030 --> 00:33:21.700
However, since we have already done
00:33:21.700 --> 00:33:22.820
some of the computations,
00:33:22.820 --> 00:33:25.200
we figured that we would make
them available for you guys
00:33:25.200 --> 00:33:26.930
if you wanted to play with them.
00:33:26.930 --> 00:33:32.590
So...
applause
00:33:32.590 --> 00:33:36.170
We have done so through the Twitter API,
00:33:36.170 --> 00:33:39.150
so we have a bot running on Twitter
00:33:39.150 --> 00:33:40.580
and if you would like to compute
00:33:40.580 --> 00:33:45.110
discrete logs for any of these
widely-used parameters,
00:33:45.110 --> 00:33:48.240
this bot will do so for you.
00:33:48.240 --> 00:33:52.910
So here is the group generator
and the primes in hexadecimal,
00:33:52.910 --> 00:33:56.910
for the 3 groups that we
did the precomputation for.
00:33:56.910 --> 00:33:59.290
And if you wanted to test out,
00:33:59.290 --> 00:34:00.590
you would do something like this,
00:34:00.590 --> 00:34:01.810
so this using Sage,
00:34:01.810 --> 00:34:04.910
which is a Python-based open source
mathematics package,
00:34:04.910 --> 00:34:06.760
that does a lot of algebra
and number theory,
00:34:06.760 --> 00:34:08.290
if you like playing with the stuff,
00:34:08.290 --> 00:34:09.429
sage is super cool,
00:34:09.429 --> 00:34:15.500
so, I said, say, my prime m
is this last value in hex there,
00:34:15.500 --> 00:34:16.860
the mod_ssl prime,
00:34:16.860 --> 00:34:23.780
then I take 2 and raise it to
the 0x1337 power mod m,
00:34:23.780 --> 00:34:26.189
and then I print it out in hexadecimal,
00:34:26.189 --> 00:34:35.230
and I get this value, then I can
copy-paste it into a tweet @DLogBot
00:34:35.230 --> 00:34:39.050
then some comp stuff happens
on our back end,
00:34:39.050 --> 00:34:40.889
this is running on one of
the machines in my lab,
00:34:40.889 --> 00:34:43.530
so please don't break it,
00:34:43.530 --> 00:34:46.550
and after a minute or two,
00:34:46.550 --> 00:34:49.019
you should get back an answer.
00:34:49.019 --> 00:34:58.310
applause
00:34:58.310 --> 00:35:01.520
So, there's a queue,
only one thing can run at a time,
00:35:01.520 --> 00:35:02.990
median time is 70 seconds,
00:35:02.990 --> 00:35:06.260
it can vary between
30 seconds and 3 minutes,
00:35:06.260 --> 00:35:08.830
so, you know, if it doesn't respond to you
00:35:08.830 --> 00:35:12.470
within like, you know, an hour
or something,
00:35:12.470 --> 00:35:15.760
then send us a ping and we'll see
if it's still running.
00:35:15.760 --> 00:35:18.300
Okay. So, have fun.
00:35:18.300 --> 00:35:21.480
Please don't actually use this for malice.
00:35:21.480 --> 00:35:27.540
applause
00:35:27.540 --> 00:35:30.230
We already have some satisfied customers.
00:35:30.230 --> 00:35:33.970
laughter
00:35:33.970 --> 00:35:35.790
AH: Alright, so we promised there were
00:35:35.790 --> 00:35:39.400
two exploits that have to do with
weakened Diffie-Hellman,
00:35:39.400 --> 00:35:41.750
and the first, Logjam, right, anyone can
00:35:41.750 --> 00:35:43.410
use backdoors from the 90s
00:35:43.410 --> 00:35:45.480
to pwn modern browsers,
00:35:45.480 --> 00:35:49.200
well, the second one is
a little bit more widespread.
00:35:49.200 --> 00:35:50.810
So, we're going to talk about
00:35:50.810 --> 00:35:53.330
how Diffie-Hellman weaknesses
00:35:53.330 --> 00:35:56.150
can be used for mass surveillance.
00:35:56.150 --> 00:35:58.280
We believe that governments can probably
00:35:58.280 --> 00:36:03.280
already right now, exploit
1024-bit discrete log
00:36:03.280 --> 00:36:08.050
to break Diffie-Hellman for
wide-scale passive decryption
00:36:08.050 --> 00:36:10.850
of Internet communications.
00:36:10.850 --> 00:36:13.970
So, is breaking 1024-bit Diffie-Hellman
00:36:13.970 --> 00:36:15.390
within the reach of governments,
00:36:15.390 --> 00:36:17.970
let's look back at these numbers quickly.
00:36:17.970 --> 00:36:22.300
So we can see that for 512-bit RSA
and Diffie-Hellman,
00:36:22.300 --> 00:36:26.090
they're both really in reach of
basically any effort right now,
00:36:26.090 --> 00:36:27.670
any one of you can probably,
00:36:27.670 --> 00:36:30.210
most of the resources to do this.
00:36:30.210 --> 00:36:34.970
For 768-bit RSA or Diffie-Hellman,
00:36:34.970 --> 00:36:37.460
well, we think this is now in the reach
00:36:37.460 --> 00:36:41.330
of a concerted academic effort.
00:36:41.330 --> 00:36:44.820
For 1024, it's a little bit
more complicated,
00:36:44.820 --> 00:36:46.710
because the number field sieve algorithm
00:36:46.710 --> 00:36:48.090
is complicated enough that even
00:36:48.090 --> 00:36:52.500
making estimates of the runtime
at this size and larger
00:36:52.500 --> 00:36:54.690
is very, very complicated
00:36:54.690 --> 00:36:58.200
and having a high-confidence estimate
is difficult.
00:36:58.200 --> 00:37:01.260
But we've tried to do the math
conservatively,
00:37:01.260 --> 00:37:03.490
and we believe that
a conservative estimate,
00:37:03.490 --> 00:37:05.920
at least for 1024-bit Diffie-Hellman
00:37:05.920 --> 00:37:08.200
is to break, to do those precomputations
00:37:08.200 --> 00:37:10.630
for a single prime p,
00:37:10.630 --> 00:37:13.480
would take about 45 million core-years.
00:37:13.480 --> 00:37:18.190
Now 45 million core-years
sounds like a hell of a lot.
00:37:18.190 --> 00:37:20.520
But, when you start to think about it,
00:37:20.520 --> 00:37:22.640
if you're going to do
an effort that large,
00:37:22.640 --> 00:37:26.050
there are some optimisations
you could start doing,
00:37:26.050 --> 00:37:28.920
and, for instance, maybe instead of
00:37:28.920 --> 00:37:31.690
running this on general-purpose PCs,
00:37:31.690 --> 00:37:33.040
like these estimates show,
00:37:33.040 --> 00:37:35.140
if you're going to do
an effort on this scale,
00:37:35.140 --> 00:37:37.560
maybe you're going to tape out some chips,
00:37:37.560 --> 00:37:39.800
maybe you're going to use custom hardware.
00:37:39.800 --> 00:37:42.520
And if we do the math and look at
what kind of gains
00:37:42.520 --> 00:37:44.380
we can get from custom hardware
00:37:44.380 --> 00:37:47.840
in other applications that
are similar to this,
00:37:47.840 --> 00:37:49.320
we estimate that we can get
00:37:49.320 --> 00:37:51.890
maybe a speedup of 80 times
00:37:51.890 --> 00:37:54.160
just by doing it in custom hardware.
00:37:54.160 --> 00:37:57.450
Okay, and then we ask what's
that's going to cost,
00:37:57.450 --> 00:38:00.670
well, we estimate that for...
00:38:00.670 --> 00:38:02.080
to build a machine that could break
00:38:02.080 --> 00:38:07.610
one 1024-bit p, precompute for
one 1024-bit p every year,
00:38:07.610 --> 00:38:09.070
would cost somewhere in the neighbourhood
00:38:09.070 --> 00:38:11.390
of low hundreds of millions of dollars,
00:38:11.390 --> 00:38:12.810
in a one-time investment.
00:38:12.810 --> 00:38:14.820
As a result of this, you can churn out
00:38:14.820 --> 00:38:16.630
precomputations once a year
00:38:16.630 --> 00:38:19.410
that will let you break efficiently
00:38:19.410 --> 00:38:22.600
every connection that uses that p.
00:38:22.600 --> 00:38:24.630
Now, individual logs then are going to be
00:38:24.630 --> 00:38:26.230
close to real-time, and in fact you can
00:38:26.230 --> 00:38:28.270
re-use much of the same hardware
00:38:28.270 --> 00:38:32.370
to do the computations for
individual logs very quickly.
00:38:32.370 --> 00:38:34.590
So, um, oh shit.
00:38:34.590 --> 00:38:37.550
This is what the estimates look like.
00:38:37.550 --> 00:38:44.050
Now is NSA actually doing this?
00:38:44.050 --> 00:38:45.030
NH: This is where we get into
00:38:45.030 --> 00:38:47.730
the conspiracy theories.
00:38:47.730 --> 00:38:52.720
applause
00:38:52.720 --> 00:38:55.010
So, there have been rumours flying around
00:38:55.010 --> 00:38:56.930
for many years, I mean
for decades, really,
00:38:56.930 --> 00:38:59.720
but sort of credible rumours
for many years,
00:38:59.720 --> 00:39:02.810
of some large cryptanalytic breakthrough
00:39:02.810 --> 00:39:04.130
that the NSA made.
00:39:04.130 --> 00:39:05.890
So here's an article from James Bamford,
00:39:05.890 --> 00:39:09.310
one of the, you know, world experts
in open ???
00:39:09.310 --> 00:39:11.350
of what the NSA's activities are
00:39:11.350 --> 00:39:13.820
and he wrote an article in 2012
00:39:13.820 --> 00:39:15.530
saying very clearly that he had talked
00:39:15.530 --> 00:39:17.290
to multiple government officials
00:39:17.290 --> 00:39:19.980
who said that the NSA made
some enormous breakthrough
00:39:19.980 --> 00:39:21.260
several years ago.
00:39:21.260 --> 00:39:22.770
Everybody's a target,
00:39:22.770 --> 00:39:24.730
everybody with communication is a target,
00:39:24.730 --> 00:39:25.960
and this computing breakthrough
00:39:25.960 --> 00:39:27.320
is going to give them the ability
00:39:27.320 --> 00:39:29.480
to crack current public encryption.
00:39:29.480 --> 00:39:31.960
And it was so secret that no oversight,
00:39:31.960 --> 00:39:35.150
anybody had sort of access
to the details of it.
00:39:35.150 --> 00:39:38.770
But whatever it was,
it was major and massive.
00:39:38.770 --> 00:39:40.250
Of course, you know, after we saw this,
00:39:40.250 --> 00:39:41.530
we said, oh my god, you know,
00:39:41.530 --> 00:39:42.470
what could it possibly be,
00:39:42.470 --> 00:39:44.370
are they breaking RSA?
00:39:44.370 --> 00:39:46.090
Bamford actually goes on in this article
00:39:46.090 --> 00:39:48.960
to speculate that it's
something about AES,
00:39:48.960 --> 00:39:51.170
which at least to my mind
seems less likely
00:39:51.170 --> 00:39:54.510
than some kind of major
public key breakthrough.
00:39:54.510 --> 00:39:56.480
So clearly we have sort of these rumours
00:39:56.480 --> 00:40:02.200
of large breakthroughs by the NSA's
tens of thousands of mathematicians.
00:40:02.200 --> 00:40:04.980
Simultaneously, we can say, you know,
00:40:04.980 --> 00:40:07.910
we know the NSA is clearly
interested in cryptanalysis,
00:40:07.910 --> 00:40:11.390
is cryptanalysis on the scale
of hundreds of millions of dollars
00:40:11.390 --> 00:40:13.630
within their reach?
00:40:13.630 --> 00:40:17.260
The answer, thanks to Snowden, is yes.
00:40:17.260 --> 00:40:18.920
We have some of their budgets
00:40:18.920 --> 00:40:21.700
and they spend billions of dollars a year
00:40:21.700 --> 00:40:23.650
on computer network operations,
00:40:23.650 --> 00:40:25.560
they spend hundred of millions of dollars
00:40:25.560 --> 00:40:28.110
on cryptanalytic IT systems,
00:40:28.110 --> 00:40:31.490
cybercryptanalysis,
exploitation solutions,
00:40:31.490 --> 00:40:33.980
in fact, a couple years ago there was even
00:40:33.980 --> 00:40:41.830
an increase of hundreds of millions of
dollars in their budget for cryptanalysis.
00:40:41.830 --> 00:40:42.950
Interesting.
00:40:42.950 --> 00:40:45.360
So, a hundred million dollars of
special-purpose hardware
00:40:45.360 --> 00:40:51.880
is certainly within range
of a government the size of ours.
00:40:51.880 --> 00:40:53.630
Additionally, we can ask,
00:40:53.630 --> 00:40:55.860
what would the impact of doing one of
00:40:55.860 --> 00:40:57.600
these single precomputations
00:40:57.600 --> 00:41:01.670
for a discrete log
for a single prime would be,
00:41:01.670 --> 00:41:04.590
and the answer is actually
surprisingly large.
00:41:04.590 --> 00:41:06.150
So if you did this precomputation
00:41:06.150 --> 00:41:08.750
for a single 1024-bit prime,
00:41:08.750 --> 00:41:10.619
that would allow passive decryption
00:41:10.619 --> 00:41:13.290
of connections to 66% of VPN servers
00:41:13.290 --> 00:41:16.020
and 26% of SSH servers.
00:41:16.020 --> 00:41:18.180
This is from Internet-wide scanning,
00:41:18.180 --> 00:41:19.520
we connected to all of these
00:41:19.520 --> 00:41:21.380
and we said "we would like to speak
00:41:21.380 --> 00:41:24.120
Diffie-Hellman with you,
what parameters do you prefer?"
00:41:24.120 --> 00:41:26.780
and these are the servers that preferred
00:41:26.780 --> 00:41:32.060
a single 1024-bit prime over
every other parameter in key size.
00:41:32.060 --> 00:41:33.770
A second 1024-bit prime would allow
00:41:33.770 --> 00:41:38.630
passive decryption for 18%
of the top million HTTPS domains.
00:41:38.630 --> 00:41:40.080
These are domains that prefer
00:41:40.080 --> 00:41:45.670
to speak Diffie-Hellman
with this fixed prime.
00:41:45.670 --> 00:41:47.720
And, the final piece of evidence
00:41:47.720 --> 00:41:49.840
for something like this being within range
00:41:49.840 --> 00:41:52.280
and at least being worth worrying about
00:41:52.280 --> 00:41:57.630
is actually some of the slides
that were release last year,
00:41:57.630 --> 00:41:59.050
by der Spiegel,
00:41:59.050 --> 00:42:01.780
and in particular they have
a large amount of detail
00:42:01.780 --> 00:42:06.530
about passive decryptions of VPN traffic.
00:42:06.530 --> 00:42:08.230
So here's an example,
00:42:08.230 --> 00:42:09.510
it is clear from the slides that
00:42:09.510 --> 00:42:10.580
whatever the NSA is doing,
00:42:10.580 --> 00:42:12.420
they have the ability to passively decrypt
00:42:12.420 --> 00:42:15.280
VPN connections on a large scale.
00:42:15.280 --> 00:42:18.900
And they're very happy about it.
00:42:18.900 --> 00:42:21.480
I think this is my favourite
Snowden slide ever.
00:42:21.480 --> 00:42:22.620
laughter
00:42:22.620 --> 00:42:25.010
I feel this way when I decrypt things too.
00:42:25.010 --> 00:42:27.089
laughter
00:42:27.089 --> 00:42:29.580
So, if we take a look at what,
00:42:29.580 --> 00:42:33.540
and these slides are specifically
talking about IPsec VPNs,
00:42:33.540 --> 00:42:39.100
if we take a look at what the
key exchange looks like for IPsec VPNs,
00:42:39.100 --> 00:42:41.260
what happens is, we have two hosts
00:42:41.260 --> 00:42:45.400
who want to make a VPN
connection with each other,
00:42:45.400 --> 00:42:50.950
the key exchange actually uses a
fixed set of parameters
00:42:50.950 --> 00:42:54.080
from a small list of possibilities,
00:42:54.080 --> 00:42:55.619
and so Alice and Bob will negotiate
00:42:55.619 --> 00:42:58.040
which parameters they're going
to use from this list,
00:42:58.040 --> 00:43:00.050
and then they will do a
Diffie-Hellman key exchange,
00:43:00.050 --> 00:43:03.240
from that they will have
a shared secret, g^ab,
00:43:03.240 --> 00:43:05.550
and then they, in the most
commonly used mode,
00:43:05.550 --> 00:43:07.140
they also have some pre-shared key,
00:43:07.140 --> 00:43:09.400
like a password that has been shared
00:43:09.400 --> 00:43:11.250
over some other channel.
00:43:11.250 --> 00:43:14.010
And that Diffie-Hellman secret
00:43:14.010 --> 00:43:16.020
that was negotiated together
with the pre-shared key
00:43:16.020 --> 00:43:19.370
or mixed together to generate
the session key.
00:43:19.370 --> 00:43:22.300
So, if somebody wanted to
00:43:22.300 --> 00:43:24.330
break a connection of this type,
00:43:24.330 --> 00:43:26.080
one option would be to, say,
00:43:26.080 --> 00:43:28.010
steal the pre-shared key
through some other mechanism
00:43:28.010 --> 00:43:29.380
and then break Diffie-Hellman.
00:43:29.380 --> 00:43:32.559
That would be a possibility.
00:43:32.559 --> 00:43:35.500
So, if we look what the
NSA's requirements are
00:43:35.500 --> 00:43:38.920
for their mass-scale decryption efforts,
00:43:38.920 --> 00:43:42.369
they require finding out what
the pre-shared key is,
00:43:42.369 --> 00:43:44.990
getting both sides of the connection,
00:43:44.990 --> 00:43:47.690
getting both the asymmetric key exchange
00:43:47.690 --> 00:43:50.350
and the symmetrically encrypted data,
00:43:50.350 --> 00:43:52.589
and then having some metadata.
00:43:52.589 --> 00:43:56.240
These are the requirements for them
to get decryption.
00:43:56.240 --> 00:43:58.210
And we can also take a closer look
00:43:58.210 --> 00:44:04.260
at what their decryption flow
actually looks like,
00:44:04.260 --> 00:44:06.290
this is somewhat complicated,
00:44:06.290 --> 00:44:07.850
but in this diagram,
00:44:07.850 --> 00:44:10.840
so they're getting the IK exchange,
00:44:10.840 --> 00:44:12.990
and the symmetric data,
00:44:12.990 --> 00:44:17.130
they're sending it into
one system that they have,
00:44:17.130 --> 00:44:19.230
they're sending the IKE messages through
00:44:19.230 --> 00:44:21.880
out to some high-performance
computing resources,
00:44:21.880 --> 00:44:23.619
and then they get sent back with
00:44:23.619 --> 00:44:28.690
some data from stored
databases of information
00:44:28.690 --> 00:44:32.910
that returns the actual decrypted data.
00:44:32.910 --> 00:44:34.840
So that's what the decryption
flow looks like.
00:44:34.840 --> 00:44:37.130
We don't have any details
of the cryptanalysis,
00:44:37.130 --> 00:44:39.480
but we have details from
the sysadmin's perspective
00:44:39.480 --> 00:44:43.190
of how the systems
that do the cryptanalysis
00:44:43.190 --> 00:44:44.670
are hooked together.
00:44:44.670 --> 00:44:46.000
And they're doing something
00:44:46.000 --> 00:44:48.280
that requires high-performance computing,
00:44:48.280 --> 00:44:49.700
that takes in key exchanges
00:44:49.700 --> 00:44:54.040
and hands out decrypted data.
00:44:54.040 --> 00:44:59.740
So, we can line up sort of the NSA's
on-demand IKE decryption
00:44:59.740 --> 00:45:03.710
with what a discrete log decryption
would actually look like,
00:45:03.710 --> 00:45:05.619
and they're very close,
00:45:05.619 --> 00:45:07.640
so they would both require
the pre-shared key,
00:45:07.640 --> 00:45:09.490
both sides of the handshake,
00:45:09.490 --> 00:45:12.440
both the handshake and the symmetric data,
00:45:12.440 --> 00:45:13.450
and they would send off the data
00:45:13.450 --> 00:45:16.090
to high-performance computing.
00:45:16.090 --> 00:45:17.990
So in the same set of slides,
00:45:17.990 --> 00:45:20.770
they also discuss targeted implants
00:45:20.770 --> 00:45:23.040
against particular implementations,
00:45:23.040 --> 00:45:26.890
if you were going to design a
backdoor to make your life easy,
00:45:26.890 --> 00:45:30.360
you would have fewer
requirements than this.
00:45:30.360 --> 00:45:31.320
Potentially.
00:45:31.320 --> 00:45:33.090
There are many kinds of backdoors
that you could design,
00:45:33.090 --> 00:45:35.190
but if you were being clever about it,
00:45:35.190 --> 00:45:38.090
you might try to make it
a little bit easier on yourself
00:45:38.090 --> 00:45:41.100
to decrypt the mess.
00:45:41.100 --> 00:45:43.750
So I will let Alex finish with this.
00:45:43.750 --> 00:45:51.090
applause
00:45:51.090 --> 00:45:53.890
So to wrap up,
00:45:53.890 --> 00:45:55.520
what we've seen today
00:45:55.520 --> 00:46:00.150
through the cryptanalysis
of Diffie-Hellman
00:46:00.150 --> 00:46:05.330
is probably a mass surveillance dream.
00:46:05.330 --> 00:46:08.180
The algorithms that we've talked about
00:46:08.180 --> 00:46:11.400
would let a government with
sufficient resources
00:46:11.400 --> 00:46:15.010
to invest in these precomputation attacks
00:46:15.010 --> 00:46:18.840
break connections on an almost
unheard-of scale,
00:46:18.840 --> 00:46:23.950
across almost every widely-used
crypto protocol on the Internet.
00:46:23.950 --> 00:46:25.530
Here are some numbers again,
00:46:25.530 --> 00:46:28.490
for HTTPS, the top million sites,
00:46:28.490 --> 00:46:29.960
we're looking at a device like
00:46:29.960 --> 00:46:32.480
the ones we hypothesised
00:46:32.480 --> 00:46:38.150
breaking connections to maybe
56% of them passively.
00:46:38.150 --> 00:46:42.900
For IKE, for Internet key
exchange v1 and v2,
00:46:42.900 --> 00:46:46.090
we're looking at in the 60%s of servers
00:46:46.090 --> 00:46:48.240
are potentially compromisable
00:46:48.240 --> 00:46:50.750
using this same hardware.
00:46:50.750 --> 00:47:00.290
For SSH, for IMAP with secure encrypted
connections, for SMTP with STARTTLS,
00:47:00.290 --> 00:47:02.259
the encrypted mail transports,
00:47:02.259 --> 00:47:05.570
all of these protocols are
potentially jeopardised
00:47:05.570 --> 00:47:07.390
by the same kind of attack,
00:47:07.390 --> 00:47:09.490
because everyone fundamentally,
00:47:09.490 --> 00:47:11.110
so many people fundamentally
00:47:11.110 --> 00:47:14.400
rely on the same underlying cryptography,
00:47:14.400 --> 00:47:17.050
often with the very same public parameters
00:47:17.050 --> 00:47:19.560
that are so widely shared.
00:47:19.560 --> 00:47:21.850
So what can we do about this?
00:47:21.850 --> 00:47:24.820
So first, let's go back to the
Logjam attack again,
00:47:24.820 --> 00:47:27.490
using 90s-era backdoored crypto
00:47:27.490 --> 00:47:30.930
that lets any of us break connections
to modern browsers.
00:47:30.930 --> 00:47:32.760
Luckily, browsers have already started
00:47:32.760 --> 00:47:34.490
to mitigate this, as I said,
00:47:34.490 --> 00:47:35.990
by increasing the minimum strength
00:47:35.990 --> 00:47:37.470
of Diffie-Hellman they support,
00:47:37.470 --> 00:47:39.650
although there's still a way to go there,
00:47:39.650 --> 00:47:43.350
since they're all still accepting
1024-bit key exchange.
00:47:43.350 --> 00:47:45.760
Our biggest recommendation
under here though,
00:47:45.760 --> 00:47:49.160
I think the lesson is:
don't backdoor crypto!
00:47:49.160 --> 00:47:50.810
Right, because the backdoored crypto
00:47:50.810 --> 00:47:52.840
of 20 years ago is now coming back
00:47:52.840 --> 00:47:54.510
to bite everyone.
00:47:54.510 --> 00:47:59.440
applause
00:47:59.440 --> 00:48:01.630
And then, we have the second attack,
00:48:01.630 --> 00:48:03.510
the 1024-bit case that enables
00:48:03.510 --> 00:48:05.220
so much mass surveillance.
00:48:05.220 --> 00:48:06.970
Well, to get around this,
00:48:06.970 --> 00:48:09.570
we're going to have to do some upgrades.
00:48:09.570 --> 00:48:11.440
Probably the easiest thing to do,
00:48:11.440 --> 00:48:12.859
and the thing that almost
00:48:12.859 --> 00:48:15.420
every cryptographer that we talked to
00:48:15.420 --> 00:48:16.590
recommends now,
00:48:16.590 --> 00:48:18.690
is to move to elliptic-curve crypto.
00:48:18.690 --> 00:48:19.950
Yes, there's been talk
00:48:19.950 --> 00:48:22.530
about whether the specific NIST curves
00:48:22.530 --> 00:48:25.790
may have been backdoored by NSA,
00:48:25.790 --> 00:48:27.470
but by and large, we think that
00:48:27.470 --> 00:48:29.590
elliptic curve is the most sound choice
00:48:29.590 --> 00:48:31.550
we have for now.
00:48:31.550 --> 00:48:33.119
Now if elliptic curve isn't an option,
00:48:33.119 --> 00:48:35.490
and there's technical reasons
why it might not be,
00:48:35.490 --> 00:48:38.570
at the very least use
a Diffie-Hellman prime
00:48:38.570 --> 00:48:41.410
that's 2048 bits or longer.
00:48:41.410 --> 00:48:43.480
If even that isn't an option,
00:48:43.480 --> 00:48:45.970
you're using legacy systems
for some reason,
00:48:45.970 --> 00:48:49.610
well, or Java yes, thanks,
00:48:49.610 --> 00:48:52.709
if there's anyone there who works for Sun,
00:48:52.709 --> 00:48:58.340
please, please tell them
to fix the crypto in Java!
00:48:58.340 --> 00:49:04.920
applause
00:49:04.920 --> 00:49:06.740
But if that's not an option,
00:49:06.740 --> 00:49:07.660
if that's not an option,
00:49:07.660 --> 00:49:09.359
the fallback is you can generate,
00:49:09.359 --> 00:49:13.890
at least generate your own 1024-bit prime.
00:49:13.890 --> 00:49:17.000
Mind you, there various tricks
that you have to make sure you do
00:49:17.000 --> 00:49:20.310
when generating a prime,
it must be a safe prime,
00:49:20.310 --> 00:49:22.450
but there are implementations
of doing this,
00:49:22.450 --> 00:49:27.100
so it's not exactly free to generate
your own 1024-bit prime,
00:49:27.100 --> 00:49:28.300
but it's inexpensive,
00:49:28.300 --> 00:49:29.810
and if you have no other option,
00:49:29.810 --> 00:49:32.950
at least so that this large
government adversary
00:49:32.950 --> 00:49:35.000
has to spend a lot of precomputation,
00:49:35.000 --> 00:49:37.990
a year perhaps, targeting
you individually,
00:49:37.990 --> 00:49:40.330
and they can't just get this for free.
00:49:40.330 --> 00:49:43.360
Alright, so, that is our talk for tonight,
00:49:43.360 --> 00:49:45.950
we're saving a lot of time for questions,
00:49:45.950 --> 00:49:49.040
thank you all very very much.
00:49:49.040 --> 00:50:00.410
applause
00:50:00.410 --> 00:50:05.300
Herald: Nadia. Nadia and Alex,
thank you very much.
00:50:05.300 --> 00:50:07.350
We installed some microphones
here in the room,
00:50:07.350 --> 00:50:09.290
so please queue up, but first,
00:50:09.290 --> 00:50:11.890
signal angel, do we have
some questions from the net?
00:50:11.890 --> 00:50:14.810
Signal Angel: Yes, we have a lot of questions.
00:50:14.810 --> 00:50:16.160
First question is,
00:50:16.160 --> 00:50:17.780
do you think it's possible that the NSA
00:50:17.780 --> 00:50:19.890
uses quantum Shor factorisation
00:50:19.890 --> 00:50:24.790
for 1024 or bigger keys already?
00:50:24.790 --> 00:50:27.520
NH: I would believe it is much more likely
00:50:27.520 --> 00:50:29.720
that they're using classical cryptanalysis
00:50:29.720 --> 00:50:31.480
for 1024-bit keys than than they have
00:50:31.480 --> 00:50:34.770
a quantum computer that
nobody has heard about.
00:50:34.770 --> 00:50:37.230
Herald: And another one?
00:50:37.230 --> 00:50:38.760
Signal Angel: Another one... Is it thinkable
00:50:38.760 --> 00:50:41.490
that the NSA solved the P=NP problem
00:50:41.490 --> 00:50:43.210
but keeps quiet?
00:50:43.210 --> 00:50:45.780
laughter
00:50:45.780 --> 00:50:47.670
AH: Probably not, but if they have,
00:50:47.670 --> 00:50:50.539
yes, I think they'd want to
keep quiet about it.
00:50:50.539 --> 00:50:52.000
NH: I hope they would tell us!
00:50:52.000 --> 00:50:53.570
AH: I hope they would tell us too,
00:50:53.570 --> 00:50:56.010
but I doubt it.
00:50:56.010 --> 00:50:59.930
Herald: Okay, and over to
number 1, please.
00:50:59.930 --> 00:51:01.540
Q: Two questions.
00:51:01.540 --> 00:51:05.600
First, is it reasonable to think that,
00:51:05.600 --> 00:51:09.200
is it possible they are attacking
individual RSA keys,
00:51:09.200 --> 00:51:11.320
that they can fetch individual RSA keys
00:51:11.320 --> 00:51:13.530
in about a week with custom hardware,
00:51:13.530 --> 00:51:17.580
and two, NSA Suite B came out 2005
00:51:17.580 --> 00:51:19.160
and they don't use Diffie-Hellman,
00:51:19.160 --> 00:51:22.670
so NSA themselves, they told us in 2005,
00:51:22.670 --> 00:51:24.730
"we won't use Diffie-Hellman",
00:51:24.730 --> 00:51:26.570
so is it reasonable that,
00:51:26.570 --> 00:51:28.400
when they changed the requirement
00:51:28.400 --> 00:51:30.730
for top secret, we should follow?
00:51:30.730 --> 00:51:33.470
AH: Well, to the first part
of your question,
00:51:33.470 --> 00:51:35.859
about whether they're factoring RSA,
00:51:35.859 --> 00:51:38.580
I think the answer for 1024,
00:51:38.580 --> 00:51:40.600
is very likely, yes they are,
00:51:40.600 --> 00:51:42.320
for high-value targets.
00:51:42.320 --> 00:51:45.020
So if you're a major website at least
00:51:45.020 --> 00:51:48.090
and you're using a 1024-bit RSA key,
00:51:48.090 --> 00:51:53.000
well, it's long past time to change
to a higher strength.
00:51:53.000 --> 00:51:56.480
NH: If the NSA has not factored
a 1024-bit key,
00:51:56.480 --> 00:51:58.050
I'm going to be very disappointed,
00:51:58.050 --> 00:52:00.930
I'm going to ask where
my tax dollars are going.
00:52:00.930 --> 00:52:07.370
laughter, applause
00:52:07.370 --> 00:52:09.440
And also I think actually,
00:52:09.440 --> 00:52:11.000
the point of sort of watching
00:52:11.000 --> 00:52:12.830
what the defensive side of the NSA
00:52:12.830 --> 00:52:15.200
is advocating in terms of recommendations
00:52:15.200 --> 00:52:17.180
is actually a wise thing to do,
00:52:17.180 --> 00:52:20.160
because as far as we know,
00:52:20.160 --> 00:52:22.140
at least the public recommendations
00:52:22.140 --> 00:52:26.450
defensively should... I mean,
00:52:26.450 --> 00:52:27.580
making recommendations for people
00:52:27.580 --> 00:52:31.000
who are building systems that are
going to be handling classified data,
00:52:31.000 --> 00:52:32.780
so they should be solid recommendations
00:52:32.780 --> 00:52:33.960
as far as we know.
00:52:33.960 --> 00:52:35.280
AH: What the NSA has told me
00:52:35.280 --> 00:52:37.580
about those recommendations, by the way,
00:52:37.580 --> 00:52:40.280
is that as long as you
follow them exactly,
00:52:40.280 --> 00:52:41.609
you're going to be okay,
00:52:41.609 --> 00:52:44.160
but if you deviate in any
small way whatsoever,
00:52:44.160 --> 00:52:46.960
then they make no guarantees whatsoever.
00:52:46.960 --> 00:52:50.040
So, think about what that might mean
00:52:50.040 --> 00:52:52.220
in terms of your implementation
00:52:52.220 --> 00:52:55.630
the next time you read through
those particular recommendations
00:52:55.630 --> 00:52:58.470
that they make.
00:52:58.470 --> 00:53:01.280
Herald: Okay. Then we hop over to
microphone 3, please.
00:53:01.280 --> 00:53:03.549
Q: So, for the moment, is
00:53:03.549 --> 00:53:07.380
elliptic-curve-based
Diffie-Hellman secure?
00:53:07.380 --> 00:53:09.860
NH: I hope so.
00:53:09.860 --> 00:53:13.650
AH: It doesn't suffer from
the same shape of attack
00:53:13.650 --> 00:53:14.900
that we've described here.
00:53:14.900 --> 00:53:16.770
As far as we know, there's not a way
00:53:16.770 --> 00:53:19.020
to do this same kind of precomputation
00:53:19.020 --> 00:53:20.710
for elliptic-curve Diffie-Hellman.
00:53:20.710 --> 00:53:22.530
NH: So what we didn't mention in the talk
00:53:22.530 --> 00:53:24.630
is, so, one of the reasons that
00:53:24.630 --> 00:53:27.300
elliptic curve keys are so much shorter
00:53:27.300 --> 00:53:30.730
than, say, finite-field
Diffie-Hellman or RSA
00:53:30.730 --> 00:53:35.350
is because we have this
superpowerful index calculus
00:53:35.350 --> 00:53:37.410
number field sieve-type algorithms
00:53:37.410 --> 00:53:41.270
for factoring and for discrete log
over finite fields,
00:53:41.270 --> 00:53:43.040
and those don't seem,
00:53:43.040 --> 00:53:44.310
we don't actually have equivalents
00:53:44.310 --> 00:53:47.890
of those algorithms for
properly generated elliptic curves.
00:53:47.890 --> 00:53:50.580
So, that's why those key sizes are shorter
00:53:50.580 --> 00:53:54.020
and that's why we think
they seem to be more secure.
00:53:54.020 --> 00:53:57.109
Herald: Then we take another one
from microphone 3, please.
00:53:57.109 --> 00:54:01.310
Q: Yes, you said that when doing
the precomputations
00:54:01.310 --> 00:54:04.820
for commonly-used primes,
00:54:04.820 --> 00:54:08.330
you can reduce the effort you have to put
00:54:08.330 --> 00:54:11.280
in a single connection
to about 70 seconds.
00:54:11.280 --> 00:54:12.830
How is that usable?
00:54:12.830 --> 00:54:15.850
If my TLS handshake is delayed 70 seconds,
00:54:15.850 --> 00:54:18.420
I already ran away.
00:54:18.420 --> 00:54:20.480
AH: Ah! So we refer you to the paper
00:54:20.480 --> 00:54:22.090
for the full answer to that,
00:54:22.090 --> 00:54:23.680
but it turns out there's a bunch of tricks
00:54:23.680 --> 00:54:28.520
that you can do to keep
a session handshake open
00:54:28.520 --> 00:54:30.210
for at least 70 seconds.
00:54:30.210 --> 00:54:32.240
So, this may not be what you want to do
00:54:32.240 --> 00:54:35.330
to the connection, say, in a web browser
00:54:35.330 --> 00:54:37.770
that's loading index.html,
00:54:37.770 --> 00:54:39.530
but whichever one is loading, say,
00:54:39.530 --> 00:54:44.619
the, I don't know, the 1-pixel
tracking image in the background,
00:54:44.619 --> 00:54:46.349
that nobody sees,
00:54:46.349 --> 00:54:48.710
which is also getting the same
session cookie,
00:54:48.710 --> 00:54:51.060
that one you can hold open
for 70 seconds
00:54:51.060 --> 00:54:52.840
without the user noticing.
00:54:52.840 --> 00:54:54.070
So what we've been able to do
00:54:54.070 --> 00:54:56.369
is show a variety of ways
that we can trick
00:54:56.369 --> 00:54:58.020
browsers and other implementations
00:54:58.020 --> 00:55:00.840
into holding the connection
open long enough.
00:55:00.840 --> 00:55:03.490
Also, 70 seconds is just
what we were able to do
00:55:03.490 --> 00:55:07.040
with a few weeks of hacking
around and optimisation,
00:55:07.040 --> 00:55:10.660
we think that with
not that much more effort
00:55:10.660 --> 00:55:13.239
we could get that number
down quite a bit more.
00:55:13.239 --> 00:55:16.280
But 70 seconds we think
already is not so bad,
00:55:16.280 --> 00:55:18.240
and there's plenty of ways
that we can exploit it.
00:55:18.240 --> 00:55:21.489
NH: Proof of concept.
00:55:21.489 --> 00:55:24.230
Herald: Okay. Do we have
something from the net?
00:55:24.230 --> 00:55:26.780
Signal Angel: How long do you estimate the security
00:55:26.780 --> 00:55:29.490
of RSA-DHE to sustain,
00:55:29.490 --> 00:55:31.030
and do you have any idea if and when
00:55:31.030 --> 00:55:33.680
there's any quantum encryption algorithms
00:55:33.680 --> 00:55:35.320
that will soon be available to be used
00:55:35.320 --> 00:55:36.850
by a broad public?
00:55:36.850 --> 00:55:38.950
AH: Oh, quantum encryption algorithms.
00:55:38.950 --> 00:55:41.150
NH: You should watch Dan
and Tanja's talk from yesterday.
00:55:41.150 --> 00:55:44.070
AH: Yeah, last night was the time
to hear about that.
00:55:44.070 --> 00:55:46.170
NH: The dangers of quantum cryptography.
00:55:46.170 --> 00:55:48.220
I mean, the short answer is
00:55:48.220 --> 00:55:49.750
that people who know
what they're talking about
00:55:49.750 --> 00:55:51.830
have said we should start worrying now
00:55:51.830 --> 00:55:53.930
because we may see quantum computers
00:55:53.930 --> 00:55:56.740
within the next 15 years, maybe.
00:55:56.740 --> 00:55:59.220
But it's really hard to speculate about
00:55:59.220 --> 00:56:05.030
advances in physics that
may be pretty far off.
00:56:05.030 --> 00:56:06.770
Herald: Do we have another one?
00:56:06.770 --> 00:56:09.550
Signal angel: Sure. What's your
opinion on the NIST curves,
00:56:09.550 --> 00:56:10.890
especially with the current rumours
00:56:10.890 --> 00:56:15.530
about the curve parameters
having a backdoor?
00:56:15.530 --> 00:56:18.310
NH: There are no known ways
00:56:18.310 --> 00:56:20.710
that the curves could have been backdoored
00:56:20.710 --> 00:56:23.460
with the given parameters.
00:56:23.460 --> 00:56:25.630
AH: But if you don't trust them,
00:56:25.630 --> 00:56:28.160
you know Dan Bernstein
has a curve you can use too.
00:56:28.160 --> 00:56:30.120
NH: So...
00:56:30.120 --> 00:56:32.230
applause
00:56:32.230 --> 00:56:35.250
NH: Do you trust Dan,
or do you trust the NSA?
00:56:35.250 --> 00:56:37.250
laughter
00:56:37.250 --> 00:56:38.859
Herald: Over to 2, please.
00:56:38.859 --> 00:56:41.800
Q: Some of the little bit
that you recommend,
00:56:41.800 --> 00:56:46.249
you say Diffie-Hellman is worse
than RSA now,
00:56:46.249 --> 00:56:49.930
so, does it mean I should switch back
00:56:49.930 --> 00:56:54.370
to RSA, preferring it instead
of Diffie-Hellman?
00:56:54.370 --> 00:56:57.070
AH: With equivalent key sizes,
00:56:57.070 --> 00:56:59.980
equivalent sizes of your primes,
00:56:59.980 --> 00:57:02.670
or your RSA modulus,
00:57:02.670 --> 00:57:05.020
yes, we are saying that.
00:57:05.020 --> 00:57:06.940
That in the 1024-bit case,
00:57:06.940 --> 00:57:10.109
there's strong reasons that you should
00:57:10.109 --> 00:57:14.160
distrust the very common repeated primes
00:57:14.160 --> 00:57:15.690
for Diffie-Hellman.
00:57:15.690 --> 00:57:17.750
But that's not the whole story.
00:57:17.750 --> 00:57:26.510
Right, so for longer sizes of modulus,
00:57:26.510 --> 00:57:27.790
larger strengths of crypto,
00:57:27.790 --> 00:57:31.680
RSA is probably still okay.
00:57:31.680 --> 00:57:34.369
But I think either way,
00:57:34.369 --> 00:57:37.750
switching to elliptic curve
for key exchange
00:57:37.750 --> 00:57:39.980
is probably the thing to do right now.
00:57:39.980 --> 00:57:42.320
NH: I think the precise statement
that we can make
00:57:42.320 --> 00:57:44.619
is, if you're comparing 1024-bit
Diffie-Hellman
00:57:44.619 --> 00:57:47.430
to a 1024-bit RSA key,
00:57:47.430 --> 00:57:48.730
that if you're using Diffie-Hellman
00:57:48.730 --> 00:57:50.980
with the most commonly used parameters,
00:57:50.980 --> 00:57:52.690
say, the Oakley group 2
00:57:52.690 --> 00:57:55.070
that everybody on the Internet is using,
00:57:55.070 --> 00:57:57.460
and you think it is likely that
a large government agency
00:57:57.460 --> 00:58:00.700
has already done the
precomputation for that prime,
00:58:00.700 --> 00:58:05.359
then breaking an individual
connection using that prime
00:58:05.359 --> 00:58:06.750
with Diffie-Hellman key exchange
00:58:06.750 --> 00:58:08.849
would be much, much, much less effort
00:58:08.849 --> 00:58:14.720
than factoring a freshly generated
1024-bit RSA key that is unique to you.
00:58:14.720 --> 00:58:17.720
Even if that 1024-bit RSA factorisation
00:58:17.720 --> 00:58:20.460
is within range of the NSA,
00:58:20.460 --> 00:58:21.490
it may not be worth their while
00:58:21.490 --> 00:58:23.420
to actually factor your key.
00:58:23.420 --> 00:58:25.810
Whereas breaking a
Diffie-Hellman key exchange,
00:58:25.810 --> 00:58:27.180
they've already done the hard work
00:58:27.180 --> 00:58:28.500
to break everybody on the Internet,
00:58:28.500 --> 00:58:31.250
so, you're just one more fish.
00:58:31.250 --> 00:58:32.000
That's the precise statement
00:58:32.000 --> 00:58:33.590
that we can make about the security.
00:58:33.590 --> 00:58:35.430
The real answer: use elliptic curves,
00:58:35.430 --> 00:58:41.990
or, to use 2048-bit
Diffie-Hellman: probably fine.
00:58:41.990 --> 00:58:43.849
Herald: And, over to number 1, please.
00:58:43.849 --> 00:58:47.230
Q: How realistic is it to use, or to create
00:58:47.230 --> 00:58:50.210
a new prime for every exchange
00:58:50.210 --> 00:58:52.990
or at least every few exchanges?
00:58:52.990 --> 00:58:55.840
NH: So, unfortunately, the properties
00:58:55.840 --> 00:59:01.039
that you need for discrete log to be hard,
00:59:01.039 --> 00:59:02.470
you need to have a safe prime
00:59:02.470 --> 00:59:05.720
and you would hopefully like it
not to be backdoored,
00:59:05.720 --> 00:59:09.430
generating safe primes is
still kind of effortful
00:59:09.430 --> 00:59:10.609
on modern hardware,
00:59:10.609 --> 00:59:12.010
I mean if you try to do it on your laptop
00:59:12.010 --> 00:59:15.170
it will probably take like, I don't know,
a minute or something.
00:59:15.170 --> 00:59:16.940
So, it's actually a lot of effort
00:59:16.940 --> 00:59:20.230
to generate a new safe prime all the time.
00:59:20.230 --> 00:59:24.490
Just use a larger safe prime
and you'll be better.
00:59:24.490 --> 00:59:26.090
Herald: So we're running out of time,
00:59:26.090 --> 00:59:28.730
but let's... with number 2.
00:59:28.730 --> 00:59:32.060
Q: You said that elliptic
curve cryptography
00:59:32.060 --> 00:59:36.930
is not susceptible to
this precomputation attack,
00:59:36.930 --> 00:59:43.750
is that luck, or is it
engineered to be that way?
00:59:43.750 --> 00:59:44.300
AH laughs
00:59:44.300 --> 00:59:45.520
NH: ...luck?
00:59:45.520 --> 00:59:46.940
AH: In part!
00:59:46.940 --> 00:59:48.010
NH: I mean, a combination of both, but
00:59:48.010 --> 00:59:49.160
so as far as we know, I mean, you can't do
00:59:49.160 --> 00:59:50.980
precomputation with elliptic curves,
00:59:50.980 --> 00:59:53.570
so, you know, sort of generically,
00:59:53.570 --> 00:59:54.560
the best thing that you can say
00:59:54.560 --> 00:59:58.500
is you can do a lot of precomputation
00:59:58.500 --> 01:00:00.720
but you still have to do a lot of effort
01:00:00.720 --> 01:00:03.290
for each individual value,
01:00:03.290 --> 01:00:05.849
so you could do, you know, generically
01:00:05.849 --> 01:00:06.920
if you want to break an elliptic curve
01:00:06.920 --> 01:00:08.880
you could do like,
a square-root-of-n attack
01:00:08.880 --> 01:00:10.830
against the key size,
01:00:10.830 --> 01:00:13.599
you could do, say, n^2/3 precomputation
01:00:13.599 --> 01:00:17.540
and then you would have n^1/3 online work
01:00:17.540 --> 01:00:19.369
if that makes sense to you.
01:00:19.369 --> 01:00:22.820
But you get less effort as far as we know.
01:00:22.820 --> 01:00:24.610
Less benefit.
01:00:24.610 --> 01:00:28.490
Herald: Sorry. We're going to finalise
then, with number 4.
01:00:28.490 --> 01:00:31.060
Q: What do you think about blacklisting
these common primes,
01:00:31.060 --> 01:00:32.460
just in the modern browsers?
01:00:32.460 --> 01:00:34.920
Will this get rid of this issue?
01:00:34.920 --> 01:00:36.920
AH: Just blacklisting the common primes,
01:00:36.920 --> 01:00:39.109
well, if you blacklist the common primes,
01:00:39.109 --> 01:00:41.030
if you blacklisted the common primes
01:00:41.030 --> 01:00:43.230
when we first came up with this,
01:00:43.230 --> 01:00:47.480
you'd immediately break
about 10% of websites
01:00:47.480 --> 01:00:49.670
because there's not a good
fallback mechanism
01:00:49.670 --> 01:00:52.420
if you don't like the prime you got
01:00:52.420 --> 01:00:54.730
during key negotiation.
01:00:54.730 --> 01:00:56.730
What the browsers are more likely to do
01:00:56.730 --> 01:01:01.920
is to phase out this kind of
finite-field Diffie-Hellman entirely,
01:01:01.920 --> 01:01:04.550
over the next larger number of years.
01:01:04.550 --> 01:01:06.580
So first they're going to
start rejecting things
01:01:06.580 --> 01:01:09.390
that use unusually weak primes,
01:01:09.390 --> 01:01:11.580
that's what they're doing already today,
01:01:11.580 --> 01:01:13.060
but I think in the long term
01:01:13.060 --> 01:01:16.810
they're going to encourage the use
of elliptic curves as an alternative,
01:01:16.810 --> 01:01:18.410
if you want forward secrecy,
01:01:18.410 --> 01:01:22.020
elliptic curves will be the way to get it.
01:01:22.020 --> 01:01:24.560
Herald: Nadia, Alex, once again,
01:01:24.560 --> 01:01:25.700
thank you so much.
01:01:25.700 --> 01:01:26.790
AH: Thank you.
01:01:26.790 --> 01:01:32.570
applause
01:01:32.570 --> 01:01:36.601
postroll music
01:01:36.601 --> 01:01:44.000
subtitles created by c3subtitles.de
in the year 2016. Join, and help us!