J. Alex Halderman, Nadia Heninger: Logjam: DiffieHellman, discrete logs, the NSA, and you

0:00  0:10preroll music

0:10  0:11Herald: I did some research,

0:11  0:13and it was not, not easy

0:13  0:16that DiffieHellman key exchange

0:16  0:18is so much above my pay grade

0:18  0:20therefore, I'm going to keep it simple.

0:20  0:21Please welcome

0:21  0:24we have Alex Halderman from
the University of Michigan, 
0:24  0:29and Nadia Heninger from
the University of Pennsylvania. 
0:29  0:33applause

0:33  0:37AH: Thank you.

0:37  0:39Thank you all so much.

0:39  0:44It's wonderful to be back again in 32C3.

0:44  0:46I'm Alex Halderman from
the University of Michigan, 
0:46  0:49here again this year with,

0:49  0:51with many of my students from my group

0:51  0:54here in the audience also speaking.

0:54  0:57We study security in the real world.

0:57  1:01So tonight, we have
a very special story to tell you 
1:01  1:04that I'm very proud to be telling

1:04  1:06along with my colleague Nadia Heninger.

1:06  1:08We're going to be talking

1:08  1:11about discrete log, DiffieHellman

1:11  1:14and some of the, um,

1:14  1:16the research that we've done

1:16  1:17over the past year,

1:17  1:20try to understand how the NSA

1:20  1:22may be breaking so much of the crypto

1:22  1:24that we know they're breaking.

1:24  1:26Why do we...? So this work is

1:26  1:29joint work with a number of coauthors,

1:29  1:31with 12 other coauthors,

1:31  1:343 of them are in this room right now,

1:34  1:35and I'd ask to stand up

1:35  1:36but they said they didn't want to

1:36  1:38so please, a quick round of applause

1:38  1:40for my coauthors as well.

1:40  1:48applause

1:48  1:50So, thank you.

1:50  1:51So in this very room,

1:51  1:54a year ago at 31C3,

1:54  1:56Jacob Appelbaum and Laura Poitras

1:56  1:59gave a talk, "Reconstructing Narratives",

1:59  2:03in which they announced some new results

2:03  2:05from the Snowden archives.

2:05  2:09They were able to tell us how the NSA,

2:09  2:12that the NSA was breaking cryptography

2:12  2:15used in widespread online communication.

2:15  2:18And, they later published

2:18  2:21an article in der Spiegel,

2:21  2:24in which the article included documents

2:24  2:28that showed indeed the scope of NSA

2:28  2:30breaking widely used encryption

2:30  2:32was significant.

2:32  2:34That NSA is breaking,

2:34  2:36maybe not all crypto,

2:36  2:38but they're able to break
widely used crypto 
2:38  2:40from many of the different kinds

2:40  2:45of services and protocols we care about.

2:45  2:46What the leaks didn't answer

2:46  2:49is how NSA is breaking this cryptography

2:49  2:51and to a technologist,

2:51  2:54well, if we don't know
how they're breaking it, 
2:54  2:57what can we do to stop it?

2:57  3:00So, Nadia and I and our coauthors set out

3:00  3:01earlier this year

3:01  3:04to try to, through our research,

3:04  3:06start answering those questions.

3:06  3:08How is NSA likely to be breaking

3:08  3:10likely used cryptography,

3:10  3:13and what can we and other researchers do

3:13  3:15to stop government from being able

3:15  3:18to attack the crypto
that all of us depend on? 
3:18  3:21So, so...
applause 
3:21  3:24Let's tell the story.

3:24  3:28Wait until you see how it ends!

3:28  3:30So if I were setting out as the attacker

3:30  3:32to break widely used crypto,

3:32  3:36well, there's a few different ways
that I could do it. 
3:36  3:38One branch of the decision tree here

3:38  3:40is to attacking the implementations

3:40  3:42right, either finding vulnerabilities

3:42  3:44or introducing backdoors,

3:44  3:47we've all been witnessing over the past

3:47  3:51week or so with Juniper and their systems

3:51  3:54being compromised.

3:54  3:57On the other hand,
there's another prong you could take. 
3:57  4:00You could try to attack the crypto
algorithms themselves, 
4:00  4:02the underlying crypto.

4:02  4:03And the difference is,

4:03  4:04if you're attacking implementations,

4:04  4:06you have to make a big investment

4:06  4:09in every hardware device
and piece of software 
4:09  4:11that you're trying to compromise.

4:11  4:13If you're attacking the underlying crypto,

4:13  4:17you have just one, a onestop shop

4:17  4:21to gain access to,
potentially a very wide swath 
4:21  4:23of all the crypto in use.

4:23  4:25So a small number of algorithms

4:25  4:28predominate for both
symmetric cryptography, 
4:28  4:31things like AES and RC4,

4:31  4:33but those particular algorithms anyway,

4:33  4:35most cryptographers seem to think

4:35  4:36that breaking them,

4:36  4:37at least in the general case,

4:37  4:39is pretty hard right now.

4:39  4:41Instead though, we also have

4:41  4:44a very small number of
public key crypto algorithms 
4:44  4:47that are also in use very widely

4:47  4:50for most or all of the protocols
and services we care about. 
4:50  4:53Things like RSA and DiffieHellman.

4:53  4:56And here be dragons, as they say,

4:56  5:00this is the cryptography that we
and many other cryptographers 
5:00  5:03think is most likely to be targeted.

5:03  5:05So, I'll hand it off to Nadia

5:05  5:08to talk about breaking public key.

5:08  5:15applause

5:15  5:17NH: So, in order to understand

5:17  5:19a little bit about
how cryptanalysis works, 
5:19  5:21I'm going to go all the way back

5:21  5:23to the very beginning of
public key cryptography 
5:23  5:25from the 70s,

5:25  5:29and I'll start by explaining
a little bit about RSA. 
5:29  5:32This is Rivest, Shamir, and Adleman
up on the screen here, 
5:32  5:34from the 70s, you can tell.

5:34  5:36And this is sort of the simple example,

5:36  5:37and then we'll talk a little bit more

5:37  5:41about the actual
DiffieHellmanbased cryptanalysis 
5:41  5:43that we're actually talking about.

5:43  5:47So, this the first publickey
crypto algorithm 
5:47  5:48that was ever published,

5:48  5:50and it is still the most widely used

5:50  5:53cryptography, public key cryptography
algorithm out there. 
5:53  5:55That shows you, I guess something
about the naturalness of ideas, 
5:55  5:57or maybe the lack of progress

5:57  5:59that we've had in the past 40 years.

5:59  6:04So, here's sort of the textbook version
of RSA encryption, 
6:04  6:05what we really care about is that...

6:05  6:07So, Alice and Bob, they want

6:07  6:09to bootstrap communication over

6:09  6:10an untrusted channel,

6:10  6:12so there's some eavesdropper
in between them 
6:12  6:13who's intercepting their messages.

6:13  6:16And, in order to get around this,

6:16  6:18they need to somehow figure out

6:18  6:21how to share a key in order to

6:21  6:23actually encrypt their communications.

6:23  6:25And the way that RSA accomplishes this,

6:25  6:30is, Bob here on the right has a public key

6:30  6:33which in RSA is e modulus N

6:33  6:35which is the product of
two large prime factors, 
6:35  6:38and he sends this over to Alice,

6:38  6:39and Alice uses Bob's public key

6:39  6:42to encrypt a message, like a session key,

6:42  6:43and send it back to Bob,

6:43  6:45and then Bob can decrypt the message,

6:45  6:46get the session key,

6:46  6:48and they can communicate using

6:48  6:50some other symmetric cipher.

6:50  6:54So, this is the big picture
of RSA encryption. 
6:54  6:55The reason that we think

6:55  6:58that RSA is secure is because

6:58  7:03the best way that we know how to break
an RSA public key 
7:03  7:05is to factor the modulus,

7:05  7:08and as far as we know,
factoring is not very easy. 
7:08  7:11So, in particular, factoring is

7:11  7:12what we hope is something like

7:12  7:13a oneway function,

7:13  7:15multiplication is easy,

7:15  7:17factoring the number into
two pieces again is hard, 
7:17  7:18in some sense.

7:18  7:20And the best algorithm that we have

7:20  7:21in the general case, of, say

7:21  7:24an RSA modulus that's wellgenerated,

7:24  7:27is called the number field sieve.

7:27  7:29So here is the...

7:29  7:31this is as bad as technical
as I'm going to get, 
7:31  7:33and I'm waving my hands vigorously here,

7:33  7:35but here's something along the lines of

7:35  7:36what the number field sieve algorithm

7:36  7:38actually looks like,

7:38  7:40so it's a multistage algorithm,

7:40  7:41it's rather complex,

7:41  7:43some stages parallelise very well,

7:43  7:45embarrassingly well,

7:45  7:48other stages parallelise somewhat
less well, 
7:48  7:51and so we've got these multiple stages
that we go through, 
7:51  7:53and at the end of the algorithm,

7:53  7:55we discover, we hope, a prime factor

7:55  8:00of the number that we're trying to factor.

8:00  8:02So, how long does it take to factor?

8:02  8:03Here's one answer:

8:03  8:04if you ask a number theorist, this is

8:04  8:06the answer that they all give you,

8:06  8:07they all go through the optimisation,

8:07  8:10and they will tell you the answer is

8:10  8:12a subexponential function in the size

8:12  8:13of the number that we're trying to factor.

8:13  8:15That I think is not the answer

8:15  8:17that you guys are looking for.

8:17  8:20So, here's a slightly more
concrete answer. 
8:20  8:22So, how long does it take to factor

8:22  8:23different sizes of keys?

8:23  8:25So, for 512bit RSA,

8:25  8:30the first 512bit RSA modulus
was factored in 1999 
8:30  8:31by a group of academics,

8:31  8:34that took them 6 months
and a few supercomputers, 
8:34  8:37now you can rent supercomputers
by the hour. 
8:37  8:38So what does that do?

8:38  8:40Well, some students of mine

8:40  8:44actually were able to factor
a 512bit RSA key 
8:44  8:49for 4 hours and 75 dollars on Amazon EC2.

8:49  8:51If you would like to do this too...

8:51  8:54applause

8:54  8:57So, you can also do this too,

8:57  9:00code is online, right here, download it,

9:00  9:03send us bug reports, etc.

9:03  9:05So, as we go up in key sizes,

9:05  9:08768bit RSA modulus,

9:08  9:10estimate, current estimate is

9:10  9:12less than 1000 coreyears,

9:12  9:15and for sort of reasonablesize
academic clusters, 
9:15  9:19that should take less than
a calendar year to finish, now. 
9:19  9:23That was,
the first 768bit RSA factorisation 
9:23  9:25was done in public in 2009.

9:25  9:28So, that gives you some idea
of sort of the progress. 
9:28  9:31For 1024bit RSA, nobody has factored

9:31  9:33a key of that size in public,

9:33  9:34the estimate is probably,

9:34  9:36it's about a million coreyears,

9:36  9:38which is certainly within range

9:38  9:41for a large government,

9:41  9:43so it is against better recommendations

9:43  9:48to use a 1024bit RSA key size,
at this point. 
9:48  9:49Current recommendation is to use

9:49  9:51a 2048bit RSA modulus,

9:51  9:53with current algorithms,

9:53  9:54nobody should ever be able to factor

9:54  9:55something at this size,

9:55  9:58without some kind of major improvement.

9:58  10:02So, there's the big picture for you.

10:02  10:05Now move on to DiffieHellman.

10:05  10:09So, the paper that introduced
DiffieHellman 
10:09  10:11was called "New Directions
in Cryptography", 
10:11  10:14it's one of the seminal papers
of the 20th century, 
10:14  10:16how many of you have read this paper?

10:16  10:18You should all go read it right now,

10:18  10:21I mean not right now, maybe after I talk.

10:21  10:23The first sentence of this paper,

10:23  10:25written in 1976,

10:25  10:28is "We stand today on the brink
of a revolution in cryptography". 
10:28  10:30This is one of the best opening sentences

10:30  10:32of an academic paper I've ever read,

10:32  10:36and they were 100% right
about everything they put in the paper. 
10:36  10:38They laid out the entire foundations

10:38  10:41of cryptographic research
for a couple decades, 
10:41  10:43and to boot they came up with

10:43  10:46the first public key exchange,

10:46  10:48that is still one of the commonly used

10:48  10:51public key methods we

10:51  10:52have on the Internet.

10:52  10:56So, all that in one paper.

10:56  10:59So, the way that
textbook DiffieHellman works, 
10:59  11:01is, you've got a couple of parameters,

11:01  11:04you've got a prime p,

11:04  11:09and some element g less than p,

11:09  11:11you can think,
for concreteness, g is 2. 
11:11  11:13It's a good number.

11:13  11:16And p is some very large prime,

11:16  11:19say 1024, 2048bit prime.

11:19  11:21And so Alice and Bob,

11:21  11:22same as our previous scenario,

11:22  11:23they want to bootstrap communication

11:23  11:26in the presence of
an untrusted eavesdropper. 
11:26  11:27So what they're going to do,

11:27  11:29Alice will generate some secret value a,

11:29  11:32and she will compute g^a mod p,

11:32  11:34and send it over to Bob,

11:34  11:37and Bob will compute some secret value b,

11:37  11:38and compute g^b mod p,

11:38  11:40and send it over to Alice,

11:40  11:44the eavesdropper sees the values
g^a and g^b, 
11:44  11:46can't derive anything useful from those,

11:46  11:48but Alice and Bob can individually

11:48  11:49take their secrets

11:49  11:52and derive the values g^ab mod p,

11:52  11:54both the same values.

11:54  11:56And that becomes a shared secret,

11:56  11:58which they can then use as a session key,

11:58  12:00and, you know, switch to AES

12:00  12:03and start symmetrically
encrypting their data. 
12:03  12:05So, that's DiffieHellman key exchange.

12:05  12:06Used all over the Internet,

12:06  12:09one of the commonly used things possible.

12:09  12:13So, one of the reasons that people

12:13  12:15have been advocating
DiffieHellman key exchange recently 
12:15  12:17over, say, RSA,

12:17  12:20is because it can be, it can provide

12:20  12:22the property of perfect forward secrecy.

12:22  12:24So assuming that Alice and Bob

12:24  12:27generate fresh random
secret values a and b 
12:27  12:29for every single connection,

12:29  12:33then if, say, some large government agency

12:33  12:35is collecting all of their communications

12:35  12:37and later tries to hack into Alice or Bob,

12:37  12:39or break one of their keys,

12:39  12:41in order to decrypt their communication,

12:41  12:44they can't hack into Alice or
Bob's computer later, 
12:44  12:46and then discover the key

12:46  12:48that Alice and Bob used

12:48  12:51to generate all the conversations
that they had, 
12:51  12:54because Alice and Bob have
already forgotten 
12:54  12:55the keys that they used.

12:55  12:57So, as long as Alice and Bob

12:57  13:00are generating fresh random
values every time, 
13:00  13:01those values should reveal nothing

13:01  13:05about past or future communications.

13:05  13:07So, that's perfect forward secrecy.

13:07  13:09And, a lot of people have,

13:09  13:11who really know what
they're talking about, 
13:11  13:13including, unfortunately, me,

13:13  13:15on this stage a couple years ago,

13:15  13:20have said, "you guys should always use
DiffieHellman over RSA key exchange 
13:20  13:23because of this property of
perfect forward secrecy". 
13:23  13:25So here's a selection of quotes

13:25  13:26that I found on the Internet,

13:26  13:28just from googling
"perfect forward secrecy" 
13:28  13:29and "DiffieHellman key exchange",

13:29  13:31and you find people saying that

13:31  13:33this provides better security,

13:33  13:36the NSA can decrypt nothing,

13:36  13:411024bit DiffieHellman is arguably
better than 1024bit RSA, 
13:41  13:46and then 1024bit DiffieHellman
is better than any key size for RSA. 
13:46  13:48This is a selection of friends

13:48  13:49and people I respect,

13:49  13:52and some also, also some
random people on Stack Overflow, 
13:52  13:54which is where...

13:54  13:55laughter

13:55  13:56where we know everybody's actually

13:56  13:58getting their recommendations from.

13:58  14:01So, there's been widescale advocacy

14:01  14:03of perfect forward secrecy as

14:03  14:06like, the reason that you should
use DiffieHellman. 
14:06  14:09It will protect you against the NSA.

14:09  14:13I'm sorry. We were wrong.

14:13  14:14And, why were we wrong?

14:14  14:15I'm going to tell little bit more

14:15  14:17about what the cryptanalysis looks like

14:17  14:18for DiffieHellman.

14:18  14:22So, the underlying problem
that we hope is hard 
14:22  14:23for the security of DiffieHellman

14:23  14:24is called discrete log,

14:24  14:27it is exactly sort of the problem of

14:27  14:30given one of the key exchange values g^a mod p

14:30  14:33compute, say, Alice's secret a.

14:33  14:34This would allow the attacker

14:34  14:36to compute the shared secret

14:36  14:39in the same way that Alice did.

14:39  14:43And, sort of similar to
factoring and multiplication, 
14:43  14:45discrete log, we think it's much harder

14:45  14:47than modular exponentiation,

14:47  14:48the computation that actually

14:48  14:51gives you the value g^a mod p.

14:51  14:53And the best algorithm that we have

14:53  14:55is called the number field sieve.

14:55  14:58So, there's a lot of parallels going on here.

14:58  14:59So what does the number field sieve

14:59  15:01for discrete log look like?

15:01  15:05Hopefully this diagram is somewhat
familiar to you by now, 
15:05  15:07it's a multistage algorithm,

15:07  15:10it has many of the same
stages as factoring, 
15:10  15:13you can sort of line them up in parallel,

15:13  15:15the last bit looks a little bit different,

15:15  15:17but we can sort of ignore that
for the moment. 
15:17  15:20Okay. So, we have some pictures

15:20  15:23of what the number field sieve looks like.

15:23  15:25How long does it take?

15:25  15:29Answer number 1:
The same answer as factoring. 
15:29  15:31In case you didn't remember,
here it is again. 
15:31  15:33This is kind of why everybody
has been saying 
15:33  15:35"Okay, the security of, you know,

15:35  15:371024bit DiffieHellman key exchange

15:37  15:39is about the same as the security of

15:39  15:41a 1024bit RSA key."

15:41  15:45It's because we have the same
complicated formula that tells us 
15:45  15:48how hard it is to break.

15:48  15:50The sort of more subtle answer for...

15:50  15:52or, not more subtle,
but the more practical answer 
15:52  15:53for, how secure is it,

15:53  15:56is, we can say, well, how long do we think

15:56  15:57it will take to actually compute

15:57  16:00a discrete log for
commonly used key sizes, 
16:00  16:01and the answer is,

16:01  16:05slightly longer than factoring an
RSA key of equivalent size, 
16:05  16:09but, not so much longer than an RSA key.

16:09  16:12And, the minimum recommended key size

16:12  16:15today is 2048 bits.

16:15  16:18Okay, so, 2048bit DiffieHellman,

16:18  16:22we're good. Great! We can all go home.

16:22  16:24Okay. However, okay,

16:24  16:26what if you want to break many connections

16:26  16:29that use the same public parameter p?

16:29  16:31Do you have to go through

16:31  16:34this whole computation,

16:34  16:35every single, for every single connection

16:35  16:37that you want to break?

16:37  16:41That was kind of the justification

16:41  16:43for perfect forward secrecy,

16:43  16:44that every single connection

16:44  16:46should be as hard as factoring an RSA key

16:46  16:48of the equivalent size.

16:48  16:50Except that's not quite the case.

16:50  16:52Because if you look at where

16:52  16:54the actual target that
we're trying to compute 
16:54  16:57appears in this plot,

16:57  16:59it's only at the very last stage.

16:59  17:00So all of this only depends

17:00  17:02on the prime p.

17:02  17:06So we can actually divide up
the algorithm in two pieces: 
17:06  17:10A few stages that depend only
on the prime p that we're using, 
17:10  17:12and then the final computation

17:12  17:14that takes the output of this
first precomputation stage, 
17:14  17:16and that's the only stage

17:16  17:17that actually matters,

17:17  17:19that actually depends on the target

17:19  17:23of our discrete log computation.

17:23  17:27So, we're in trouble.

17:27  17:30In particular, that means that

17:30  17:33if many connections are using
this same prime p, 
17:33  17:36you can do the precomputation once,

17:36  17:37spend a huge amount of effort,

17:37  17:39and then the actual effort required

17:39  17:43to break individual connections
using those primes 
17:43  17:46is much, much smaller.

17:46  17:48So here's our current estimates,

17:48  17:50these are actually somewhat new
from our paper, 
17:50  17:54of how long the individual log stage
takes in practice, 
17:54  17:56if you push the primer as far as you can

17:56  17:58to make this as fast as possible.

17:58  17:59And the answer is basically,

17:59  18:02if you're worried about a government,

18:02  18:04you better start worrying

18:04  18:09for reasonable key sizes
that people are using. 
18:09  18:11See, so I'll let Alex continue

18:11  18:15with the next part of our talk.

18:15  18:22applause

18:22  18:25So this fact that Nadia just told us

18:25  18:27about DiffieHellman

18:27  18:29and the number field sieve,

18:29  18:34this was something that the
mathematical crypto people knew about, 
18:34  18:36but most of us who did system security,

18:36  18:38people like me,

18:38  18:40didn't ever get the memo.

18:40  18:44So, it's, I'm here in part to apologise

18:44  18:45to everyone I've taught

18:45  18:48about DiffieHellman and cryptanalysis

18:48  18:50who didn't get to hear about this,

18:50  18:51as we were talking about

18:51  18:52perfect forward secrecy.

18:52  18:55Right, this fact about the cryptanalysis

18:55  18:57and how well it can apply in exactly

18:57  18:59the scenario that we're worried about,

18:59  19:02this kind of situation
involving mass surveillance, 
19:02  19:05was news to many of those.

19:05  19:06But now that we have that fact,

19:06  19:08how can we exploit it,

19:08  19:10to try to break DiffieHellman,

19:10  19:12in scenarios that we all care about?

19:12  19:13And we're going to talk about

19:13  19:16two scenarios in the talk today.

19:16  19:19The first one applies to HTTPS,

19:19  19:22to encrypted web connections,

19:22  19:25and it applies not only
to government agencies, 
19:25  19:28but also just to normal
everyday attackers, 
19:28  19:29with maybe the same resources

19:29  19:31that you or I have.

19:31  19:35Right, this is a downtoearth
kind of attack on HTTPS, 
19:35  19:38and we call it Logjam.

19:38  19:40Logjam allows us to break

19:40  19:42the HTTPS connections

19:42  19:44to many, many popular websites

19:44  19:46in modern browsers,

19:46  19:49by fooling those browsers into using

19:49  19:531990sera backdoored crypto.

19:53  19:56So where does this backdoored
crypto come from? 
19:56  19:58This is from the first crypto wars,

19:58  19:59back in the 90s,

19:59  20:01when my country, the US,

20:01  20:04had restrictions on what kind and strength

20:04  20:07of cryptography could be exported,

20:07  20:09and used by people abroad.

20:09  20:11So US companies were prohibited

20:11  20:13from exporting products that contained

20:13  20:16cryptography that had greater
than a certain strength. 
20:16  20:18For RSA, that was that the key size

20:18  20:21had to be less than or equal to 512 bits,

20:21  20:23and for DiffieHellman it was that

20:23  20:27basically the prime had to be
512 bits or less. 
20:27  20:29So back in the 90s,

20:29  20:30these were constants,

20:30  20:31these were strengths of crypto

20:31  20:34that were chosen presumably because

20:34  20:38they were easy for NSA to break.

20:38  20:40So, if you were an American company

20:40  20:42making products, like let's say

20:42  20:45Netscape Navigator, the web browser

20:45  20:51that initiated the first SSL protocol,

20:51  20:53you needed some way to be able

20:53  20:55to communicate with,

20:55  20:57from servers in the US,

20:57  20:59to clients, including your own browser,

20:59  21:01that you would ship to people abroad,

21:01  21:03say, here in Germany.

21:03  21:05And so they came up with a way

21:05  21:11to use, to have HTTPS automatically select

21:11  21:13the appropriate key strength

21:13  21:14depending on whether the browser

21:14  21:17was able to support
the fullstrength cryptography, 
21:17  21:19or the weakened version

21:19  21:21for deployment abroad.

21:21  21:22And the way that they did that

21:22  21:23was something called

21:23  21:26exportgrade cipher suites.

21:26  21:27So when your browser,

21:27  21:29whenever it starts a TLS connection

21:29  21:31for an HTTPS URL,

21:31  21:33one of the first thing that it does

21:33  21:36is, the browser will send to the server

21:36  21:37a list of the kinds of cryptography

21:37  21:39that it can speak,

21:39  21:41these are called cipher suites,

21:41  21:44and then the server selects one of those,

21:44  21:46that is compatible with
whatever cryptography 
21:46  21:48the server has available,

21:48  21:50and then that negotiated cipher suite

21:50  21:54is what's used for the connection.

21:54  21:55Now the way that they supported

21:55  21:58the 90sera backdoor crypto

21:58  22:01was by having browsers shipped abroad

22:01  22:03from the United States that could only

22:03  22:06speak a certain subset
of crypto algorithms, 
22:06  22:08that were limited in strength

22:08  22:10to 512 bits or less,

22:10  22:12those were the exportgrade cipher suites

22:12  22:14with the names you see here.

22:14  22:19Now, even though no
browser has been shipped 
22:19  22:22that is limited to only these suites,

22:22  22:24since probably 2000sometime,

22:24  22:28when the US relaxed
its export regulations, 
22:28  22:29there wasn't just any one day

22:29  22:33when all of those old browsers

22:33  22:35from before that era went away.

22:35  22:39So, servers, even now, many servers

22:39  22:43will still accept and speak
these weakened cipher suites, 
22:43  22:45if that's all the browser has available.

22:45  22:48Like if you're running an ecommerce site,

22:48  22:50right, I'm sure you still want to be able

22:50  22:51to speak to any customers

22:51  22:55who have 1998era
Netspace Navigator involved, 
22:55  22:57otherwise you'd lose some sales, right?

22:57  22:59So there was no reason to turn them off,

22:59  23:02because no modern browser any more,

23:02  23:04now that those restrictions are lifted,

23:04  23:07would choose these weakened suites.

23:07  23:09Well, that's what we thought, anyway.

23:09  23:13So, in, over this past year,

23:13  23:16there were two attacks that exploited

23:16  23:17these weakened cipher suites,

23:17  23:21that found ways to convince
modern browsers 
23:21  23:24to speak them instead of
fullstrength cryptography. 
23:24  23:26The first was the FREAK attack,

23:26  23:29which was revealed in early 2015

23:29  23:32by a separate group of authors,

23:32  23:35and the FREAK attack was
an implementation flaw 
23:35  23:39in many modern browsers.

23:39  23:40In order to exploit it,

23:40  23:42all you need to do is to be able

23:42  23:44to relatively inexpensively

23:44  23:48factor a 512bit RSA key.

23:48  23:50And, as Nadia has told you,

23:50  23:53this is now a matter of maybe 4 hours,

23:53  23:55maybe 75 dollars, something like that,

23:55  23:57and if you did that, you'd able to break

23:57  24:00all the connections coming into

24:00  24:02a weak server for a long period of time,

24:02  24:06to a server that still spoke
these cipher suites. 
24:06  24:08So this affected most modern browsers,

24:08  24:14and just shy of 10% of Alexa
top million sites that speak HTTPS. 
24:14  24:17Now that left the DiffieHellman

24:17  24:19exportgrade cipher suites,

24:19  24:21which were not affected by FREAK.

24:21  24:26But we came up with a paper
in May of this year, 
24:26  24:28that showed a separate attack,

24:28  24:29the Logjam attack,

24:29  24:32which is a protocol flaw in TLS,

24:32  24:34and affects all modern browsers,

24:34  24:38and, similarly, allows you
to downgrade connections 
24:38  24:41to exportgrade DiffieHellman,

24:41  24:43and then intercept or modify the contents,

24:43  24:47if the server speaks and still supports

24:47  24:51these exportgrade DiffieHellman
cipher suites. 
24:51  24:52So now let me give you

24:52  24:55the hopefully brief technical overview

24:55  24:57of how the Logjam attack works.

24:57  24:59If you've been curious about this,

24:59  25:03this is the chance to see it.

25:03  25:05So, Logjam is a problem that happens

25:05  25:08during the TLS connection handshake.

25:08  25:10And the first thing that happens
in the handshake, 
25:10  25:12at the top of this diagram,

25:12  25:13so this is just your browser connecting

25:13  25:17to some website, some server
there on the right, 
25:17  25:20maybe Alice connecting to
her favourite website here. 
25:20  25:22So the first stage is this client hello,

25:22  25:25where, you know, a normal client
is going to say, 
25:25  25:27I speak various kinds of cryptography,

25:27  25:30including fullstrength DiffieHellman.

25:30  25:31The server at that point is going to

25:31  25:36respond by picking some cipher suite,

25:36  25:38let's say DiffieHellman,

25:38  25:41and then sending over
its certificate chain, 
25:41  25:45as well as its DiffieHellman
public parameters, 
25:45  25:48p and g, the server gets to choose them,

25:48  25:49as well as g^a.

25:49  25:51And then it's going to use

25:51  25:55its longterm RSA key that is the thing

25:55  25:57that is signed in its certificate,

25:57  26:00in order to make a signature on
those DiffieHellman parameters. 
26:00  26:02Okay, then it's going to do...

26:02  26:05complete the negotiation, and so on.

26:05  26:07In the Logjam attack,

26:07  26:09we have a maninthemiddle attacker,

26:09  26:11who's able to modify some
of these messages 
26:11  26:13as they're going by.

26:13  26:15So the first thing the attacker does,

26:15  26:17he modifies the client hello message,

26:17  26:20to replace all of the different
kinds of cryptography 
26:20  26:22the client says it supports,

26:22  26:25and just put in exportgrade
DiffieHellman. 
26:25  26:27Ah, the 90s are here again.

26:27  26:30Alright, so then, you know, the server

26:30  26:33will get that, and if the server supports

26:33  26:35exportgrade DiffieHellman,

26:35  26:39as about 10% or so of servers

26:39  26:41still support export grade DiffieHellman,

26:41  26:44it's going to respond and say,

26:44  26:46okay, that's what you asked for,
I'll take it, 
26:46  26:49and it's going to send over its side

26:49  26:51of the DiffieHellman key exchange,

26:51  26:54but using a 512bit prime,

26:54  26:57because that's what is required under

26:57  27:00these exportgrade suites.

27:00  27:02Now, at that point, the browser would

27:02  27:05normally reject this message,

27:05  27:07because it didn't ask for exportgrade,

27:07  27:10it really asked for fullstrength,

27:10  27:12so instead, the man in the middle has to

27:12  27:16modify the server's hello message,

27:16  27:18and say that this is fullstrength
DiffieHellman, 
27:18  27:20well, if it's fullstrength,

27:20  27:23why is it only a 512bit prime
that's being used? 
27:23  27:26Well, there's actually no limitation,

27:26  27:28and no distinction between the messages

27:28  27:34that the server would send
in that space with p and g, 
27:34  27:36that says normalgrade DiffieHellman

27:36  27:38has to be more than 512 bits.

27:38  27:41In fact we found a handful of real sites

27:41  27:43that even for normalstrength
DiffieHellman 
27:43  27:49just happened to use 512bit
or even weaker cryptography. 
27:49  27:51So, as long as we modify
this earlier message, 
27:51  27:53the server's hello message,

27:53  27:55and make it say, "normalstrength
DiffieHellman", 
27:55  27:57there's no way for the client to tell

27:57  27:59from just the structure of the protocol,

27:59  28:01that anything is amiss.

28:01  28:05So, at this point, there is one last place

28:05  28:06that we could catch the problem,

28:06  28:08that the client or the server could see

28:08  28:10that something's wrong,

28:10  28:13which is that each side sends
the other a finished message, 
28:13  28:15here at the end,

28:15  28:22that says, basically, has, uses
the session secrets 
28:22  28:25to add an authentication code

28:25  28:28to a dialogue of all of the
protocol messages 
28:28  28:30that match the handshake dialogue,

28:30  28:34all the messages going back
in each direction so far 
28:34  28:37have to be the same from each side of you.

28:37  28:40However, in our case, in Logjam,

28:40  28:43the attacker is able to spoof
these messages, 
28:43  28:46to make them look correct to each side.

28:46  28:48He's able to modify that dialogue why?

28:48  28:53Well, because we're using this
512bit DiffieHellman 
28:53  28:58that we know from using
the number field sieve, 
28:58  29:00we are able to efficiently break.

29:00  29:03So, if the attacker is able to quickly

29:03  29:04perform the discrete log

29:04  29:09on the DiffieHellman key exchange

29:09  29:11that's going by at 512bit strength,

29:11  29:15then he can fix up the client
and server hello messages, 
29:15  29:17and neither side will notice
that anything went wrong. 
29:17  29:19So that's Logjam in a nutshell.

29:19  29:22I'm sorry, it's a little bit complicated.

29:22  29:25So, how widely shared are

29:25  29:28these DiffieHellman public parameters?

29:28  29:31Well, we used Internetwide
scanning to find out. 
29:31  29:34So, my group, we also made
something called zmap, 
29:34  29:36that I talked about here
a couple of years ago, 
29:36  29:39which lets us quickly probe
everything on the Internet, 
29:39  29:42and so we did this and tried to make

29:42  29:44connections to each HTTPS server

29:44  29:47in the public IPv4 address space,

29:47  29:50and found out what key exchange methods

29:50  29:52were supported and with what primes.

29:52  29:56And what we find is that 97% of hosts

29:56  29:58that support exportgrade DiffieHellman

29:58  30:01use one of only 3 512bit primes.

30:01  30:03They're that widelyshared.

30:03  30:05Why is this? Because those parameters

30:05  30:07are very often either hardcoded

30:07  30:08or encoded in standards

30:08  30:10that different people implement.

30:10  30:12The most common of these,

30:12  30:15used by 80% of hosts that support
exportgrade DiffieHellman, 
30:15  30:21is a public parameter that's
hardcoded into Apache 2.2. 
30:21  30:23So, it's actually there,
embedded in the source, 
30:23  30:26you have to recompile Apache to change it.

30:26  30:2813% of hosts supported something,

30:28  30:32a second prime that has also 512 bits,

30:32  30:35that's hardcoded in mod_ssl,

30:35  30:37and the next most popular, 4%,

30:37  30:40was in the Sun JDK.

30:40  30:43Only 10 primes accounted for 99%

30:43  30:45of all the hosts we found in
the public address space 
30:45  30:49that supported exportgrade
DiffieHellman. 
30:49  30:54So, if we would like to compromise these,

30:54  30:57well, Nadia just told you about

30:57  31:02how long it takes to use
the number field sieve 
31:02  31:05to break 512bit discrete log,

31:05  31:08well, we actually went and did
the precomputation 
31:08  31:13for all 3 of these most widely used
DiffieHellman primes, 
31:13  31:19and our colleagues who make a tool
called CADONFS 
31:19  31:22where able to implement the code

31:22  31:28for that piece of the discrete log version
of the number field sieve 
31:28  31:31and they ran the algorithm on these primes

31:31  31:34on a cluster they just happened
to have lying around, 
31:34  31:38it took about a week of time
on the cluster 
31:38  31:40for each of these primes.

31:40  31:42After which, using an optimised version

31:42  31:45of the last portion of
the number field sieve, 
31:45  31:48it takes about 70 seconds for us to break

31:48  31:49any individual connection

31:49  31:54that uses any one of these
3 most popular primes. 
31:54  31:57So, Logjam and our precomputations

31:57  31:59now allow us to break any connection

31:59  32:05to about 8% of the top million
HTTPS sites from Alexa 
32:05  32:08and when we came up with this attack,

32:08  32:11it worked in all modern browsers.

32:11  32:13So, mitigation!

32:13  32:19applause

32:19  32:22This is bad, everyone, this is the crypto

32:22  32:25all of us are using.

32:25  32:27So we do have some mitigations.

32:27  32:28This is the actual positive part,

32:28  32:30is that the browser makers have now

32:30  32:33started to increase the minimum strength

32:33  32:35of DiffieHellman they will accept.

32:35  32:37So IE, Chrome, and Firefox will reject

32:37  32:39primes less than 1024 bits

32:39  32:41and Safari less than 768.

32:41  32:44And the new draft of TLS 1.3 is including

32:44  32:45an antidowngrade flag

32:45  32:47that will make it even harder

32:47  32:50for such attacks to take place
in the future. 
32:50  32:52Now back to Nadia.

32:52  32:54NH: So we promised in our abstract...

32:54  33:00applause

33:00  33:02...that there would be a handson
portion of this talk. 
33:02  33:04So, you have a couple options,

33:04  33:06number 1 is, if you're really into this,

33:06  33:08you can do and download
CADONFS yourselves, 
33:08  33:12cadonfs.gforge.inria.fr

33:12  33:16and, you know, run
discrete log algorithms yourselves 
33:16  33:18for any prime you wish

33:18  33:20and then you can compute
arbitrary discrete logs. 
33:20  33:22However, since we have already done

33:22  33:23some of the computations,

33:23  33:25we figured that we would make
them available for you guys 
33:25  33:27if you wanted to play with them.

33:27  33:33So...
applause 
33:33  33:36We have done so through the Twitter API,

33:36  33:39so we have a bot running on Twitter

33:39  33:41and if you would like to compute

33:41  33:45discrete logs for any of these
widelyused parameters, 
33:45  33:48this bot will do so for you.

33:48  33:53So here is the group generator
and the primes in hexadecimal, 
33:53  33:57for the 3 groups that we
did the precomputation for. 
33:57  33:59And if you wanted to test out,

33:59  34:01you would do something like this,

34:01  34:02so this using Sage,

34:02  34:05which is a Pythonbased open source
mathematics package, 
34:05  34:07that does a lot of algebra
and number theory, 
34:07  34:08if you like playing with the stuff,

34:08  34:09sage is super cool,

34:09  34:16so, I said, say, my prime m
is this last value in hex there, 
34:16  34:17the mod_ssl prime,

34:17  34:24then I take 2 and raise it to
the 0x1337 power mod m, 
34:24  34:26and then I print it out in hexadecimal,

34:26  34:35and I get this value, then I can
copypaste it into a tweet @DLogBot 
34:35  34:39then some comp stuff happens
on our back end, 
34:39  34:41this is running on one of
the machines in my lab, 
34:41  34:44so please don't break it,

34:44  34:47and after a minute or two,

34:47  34:49you should get back an answer.

34:49  34:58applause

34:58  35:02So, there's a queue,
only one thing can run at a time, 
35:02  35:03median time is 70 seconds,

35:03  35:06it can vary between
30 seconds and 3 minutes, 
35:06  35:09so, you know, if it doesn't respond to you

35:09  35:12within like, you know, an hour
or something, 
35:12  35:16then send us a ping and we'll see
if it's still running. 
35:16  35:18Okay. So, have fun.

35:18  35:21Please don't actually use this for malice.

35:21  35:28applause

35:28  35:30We already have some satisfied customers.

35:30  35:34laughter

35:34  35:36AH: Alright, so we promised there were

35:36  35:39two exploits that have to do with
weakened DiffieHellman, 
35:39  35:42and the first, Logjam, right, anyone can

35:42  35:43use backdoors from the 90s

35:43  35:45to pwn modern browsers,

35:45  35:49well, the second one is
a little bit more widespread. 
35:49  35:51So, we're going to talk about

35:51  35:53how DiffieHellman weaknesses

35:53  35:56can be used for mass surveillance.

35:56  35:58We believe that governments can probably

35:58  36:03already right now, exploit
1024bit discrete log 
36:03  36:08to break DiffieHellman for
widescale passive decryption 
36:08  36:11of Internet communications.

36:11  36:14So, is breaking 1024bit DiffieHellman

36:14  36:15within the reach of governments,

36:15  36:18let's look back at these numbers quickly.

36:18  36:22So we can see that for 512bit RSA
and DiffieHellman, 
36:22  36:26they're both really in reach of
basically any effort right now, 
36:26  36:28any one of you can probably,

36:28  36:30most of the resources to do this.

36:30  36:35For 768bit RSA or DiffieHellman,

36:35  36:37well, we think this is now in the reach

36:37  36:41of a concerted academic effort.

36:41  36:45For 1024, it's a little bit
more complicated, 
36:45  36:47because the number field sieve algorithm

36:47  36:48is complicated enough that even

36:48  36:52making estimates of the runtime
at this size and larger 
36:52  36:55is very, very complicated

36:55  36:58and having a highconfidence estimate
is difficult. 
36:58  37:01But we've tried to do the math
conservatively, 
37:01  37:03and we believe that
a conservative estimate, 
37:03  37:06at least for 1024bit DiffieHellman

37:06  37:08is to break, to do those precomputations

37:08  37:11for a single prime p,

37:11  37:13would take about 45 million coreyears.

37:13  37:18Now 45 million coreyears
sounds like a hell of a lot. 
37:18  37:21But, when you start to think about it,

37:21  37:23if you're going to do
an effort that large, 
37:23  37:26there are some optimisations
you could start doing, 
37:26  37:29and, for instance, maybe instead of

37:29  37:32running this on generalpurpose PCs,

37:32  37:33like these estimates show,

37:33  37:35if you're going to do
an effort on this scale, 
37:35  37:38maybe you're going to tape out some chips,

37:38  37:40maybe you're going to use custom hardware.

37:40  37:43And if we do the math and look at
what kind of gains 
37:43  37:44we can get from custom hardware

37:44  37:48in other applications that
are similar to this, 
37:48  37:49we estimate that we can get

37:49  37:52maybe a speedup of 80 times

37:52  37:54just by doing it in custom hardware.

37:54  37:57Okay, and then we ask what's
that's going to cost, 
37:57  38:01well, we estimate that for...

38:01  38:02to build a machine that could break

38:02  38:08one 1024bit p, precompute for
one 1024bit p every year, 
38:08  38:09would cost somewhere in the neighbourhood

38:09  38:11of low hundreds of millions of dollars,

38:11  38:13in a onetime investment.

38:13  38:15As a result of this, you can churn out

38:15  38:17precomputations once a year

38:17  38:19that will let you break efficiently

38:19  38:23every connection that uses that p.

38:23  38:25Now, individual logs then are going to be

38:25  38:26close to realtime, and in fact you can

38:26  38:28reuse much of the same hardware

38:28  38:32to do the computations for
individual logs very quickly. 
38:32  38:35So, um, oh shit.

38:35  38:38This is what the estimates look like.

38:38  38:44Now is NSA actually doing this?

38:44  38:45NH: This is where we get into

38:45  38:48the conspiracy theories.

38:48  38:53applause

38:53  38:55So, there have been rumours flying around

38:55  38:57for many years, I mean
for decades, really, 
38:57  39:00but sort of credible rumours
for many years, 
39:00  39:03of some large cryptanalytic breakthrough

39:03  39:04that the NSA made.

39:04  39:06So here's an article from James Bamford,

39:06  39:09one of the, you know, world experts
in open ??? 
39:09  39:11of what the NSA's activities are

39:11  39:14and he wrote an article in 2012

39:14  39:16saying very clearly that he had talked

39:16  39:17to multiple government officials

39:17  39:20who said that the NSA made
some enormous breakthrough 
39:20  39:21several years ago.

39:21  39:23Everybody's a target,

39:23  39:25everybody with communication is a target,

39:25  39:26and this computing breakthrough

39:26  39:27is going to give them the ability

39:27  39:29to crack current public encryption.

39:29  39:32And it was so secret that no oversight,

39:32  39:35anybody had sort of access
to the details of it. 
39:35  39:39But whatever it was,
it was major and massive. 
39:39  39:40Of course, you know, after we saw this,

39:40  39:42we said, oh my god, you know,

39:42  39:42what could it possibly be,

39:42  39:44are they breaking RSA?

39:44  39:46Bamford actually goes on in this article

39:46  39:49to speculate that it's
something about AES, 
39:49  39:51which at least to my mind
seems less likely 
39:51  39:55than some kind of major
public key breakthrough. 
39:55  39:56So clearly we have sort of these rumours

39:56  40:02of large breakthroughs by the NSA's
tens of thousands of mathematicians. 
40:02  40:05Simultaneously, we can say, you know,

40:05  40:08we know the NSA is clearly
interested in cryptanalysis, 
40:08  40:11is cryptanalysis on the scale
of hundreds of millions of dollars 
40:11  40:14within their reach?

40:14  40:17The answer, thanks to Snowden, is yes.

40:17  40:19We have some of their budgets

40:19  40:22and they spend billions of dollars a year

40:22  40:24on computer network operations,

40:24  40:26they spend hundred of millions of dollars

40:26  40:28on cryptanalytic IT systems,

40:28  40:31cybercryptanalysis,
exploitation solutions, 
40:31  40:34in fact, a couple years ago there was even

40:34  40:42an increase of hundreds of millions of
dollars in their budget for cryptanalysis. 
40:42  40:43Interesting.

40:43  40:45So, a hundred million dollars of
specialpurpose hardware 
40:45  40:52is certainly within range
of a government the size of ours. 
40:52  40:54Additionally, we can ask,

40:54  40:56what would the impact of doing one of

40:56  40:58these single precomputations

40:58  41:02for a discrete log
for a single prime would be, 
41:02  41:05and the answer is actually
surprisingly large. 
41:05  41:06So if you did this precomputation

41:06  41:09for a single 1024bit prime,

41:09  41:11that would allow passive decryption

41:11  41:13of connections to 66% of VPN servers

41:13  41:16and 26% of SSH servers.

41:16  41:18This is from Internetwide scanning,

41:18  41:20we connected to all of these

41:20  41:21and we said "we would like to speak

41:21  41:24DiffieHellman with you,
what parameters do you prefer?" 
41:24  41:27and these are the servers that preferred

41:27  41:32a single 1024bit prime over
every other parameter in key size. 
41:32  41:34A second 1024bit prime would allow

41:34  41:39passive decryption for 18%
of the top million HTTPS domains. 
41:39  41:40These are domains that prefer

41:40  41:46to speak DiffieHellman
with this fixed prime. 
41:46  41:48And, the final piece of evidence

41:48  41:50for something like this being within range

41:50  41:52and at least being worth worrying about

41:52  41:58is actually some of the slides
that were release last year, 
41:58  41:59by der Spiegel,

41:59  42:02and in particular they have
a large amount of detail 
42:02  42:07about passive decryptions of VPN traffic.

42:07  42:08So here's an example,

42:08  42:10it is clear from the slides that

42:10  42:11whatever the NSA is doing,

42:11  42:12they have the ability to passively decrypt

42:12  42:15VPN connections on a large scale.

42:15  42:19And they're very happy about it.

42:19  42:21I think this is my favourite
Snowden slide ever. 
42:21  42:23laughter

42:23  42:25I feel this way when I decrypt things too.

42:25  42:27laughter

42:27  42:30So, if we take a look at what,

42:30  42:34and these slides are specifically
talking about IPsec VPNs, 
42:34  42:39if we take a look at what the
key exchange looks like for IPsec VPNs, 
42:39  42:41what happens is, we have two hosts

42:41  42:45who want to make a VPN
connection with each other, 
42:45  42:51the key exchange actually uses a
fixed set of parameters 
42:51  42:54from a small list of possibilities,

42:54  42:56and so Alice and Bob will negotiate

42:56  42:58which parameters they're going
to use from this list, 
42:58  43:00and then they will do a
DiffieHellman key exchange, 
43:00  43:03from that they will have
a shared secret, g^ab, 
43:03  43:06and then they, in the most
commonly used mode, 
43:06  43:07they also have some preshared key,

43:07  43:09like a password that has been shared

43:09  43:11over some other channel.

43:11  43:14And that DiffieHellman secret

43:14  43:16that was negotiated together
with the preshared key 
43:16  43:19or mixed together to generate
the session key. 
43:19  43:22So, if somebody wanted to

43:22  43:24break a connection of this type,

43:24  43:26one option would be to, say,

43:26  43:28steal the preshared key
through some other mechanism 
43:28  43:29and then break DiffieHellman.

43:29  43:33That would be a possibility.

43:33  43:36So, if we look what the
NSA's requirements are 
43:36  43:39for their massscale decryption efforts,

43:39  43:42they require finding out what
the preshared key is, 
43:42  43:45getting both sides of the connection,

43:45  43:48getting both the asymmetric key exchange

43:48  43:50and the symmetrically encrypted data,

43:50  43:53and then having some metadata.

43:53  43:56These are the requirements for them
to get decryption. 
43:56  43:58And we can also take a closer look

43:58  44:04at what their decryption flow
actually looks like, 
44:04  44:06this is somewhat complicated,

44:06  44:08but in this diagram,

44:08  44:11so they're getting the IK exchange,

44:11  44:13and the symmetric data,

44:13  44:17they're sending it into
one system that they have, 
44:17  44:19they're sending the IKE messages through

44:19  44:22out to some highperformance
computing resources, 
44:22  44:24and then they get sent back with

44:24  44:29some data from stored
databases of information 
44:29  44:33that returns the actual decrypted data.

44:33  44:35So that's what the decryption
flow looks like. 
44:35  44:37We don't have any details
of the cryptanalysis, 
44:37  44:39but we have details from
the sysadmin's perspective 
44:39  44:43of how the systems
that do the cryptanalysis 
44:43  44:45are hooked together.

44:45  44:46And they're doing something

44:46  44:48that requires highperformance computing,

44:48  44:50that takes in key exchanges

44:50  44:54and hands out decrypted data.

44:54  45:00So, we can line up sort of the NSA's
ondemand IKE decryption 
45:00  45:04with what a discrete log decryption
would actually look like, 
45:04  45:06and they're very close,

45:06  45:08so they would both require
the preshared key, 
45:08  45:09both sides of the handshake,

45:09  45:12both the handshake and the symmetric data,

45:12  45:13and they would send off the data

45:13  45:16to highperformance computing.

45:16  45:18So in the same set of slides,

45:18  45:21they also discuss targeted implants

45:21  45:23against particular implementations,

45:23  45:27if you were going to design a
backdoor to make your life easy, 
45:27  45:30you would have fewer
requirements than this. 
45:30  45:31Potentially.

45:31  45:33There are many kinds of backdoors
that you could design, 
45:33  45:35but if you were being clever about it,

45:35  45:38you might try to make it
a little bit easier on yourself 
45:38  45:41to decrypt the mess.

45:41  45:44So I will let Alex finish with this.

45:44  45:51applause

45:51  45:54So to wrap up,

45:54  45:56what we've seen today

45:56  46:00through the cryptanalysis
of DiffieHellman 
46:00  46:05is probably a mass surveillance dream.

46:05  46:08The algorithms that we've talked about

46:08  46:11would let a government with
sufficient resources 
46:11  46:15to invest in these precomputation attacks

46:15  46:19break connections on an almost
unheardof scale, 
46:19  46:24across almost every widelyused
crypto protocol on the Internet. 
46:24  46:26Here are some numbers again,

46:26  46:28for HTTPS, the top million sites,

46:28  46:30we're looking at a device like

46:30  46:32the ones we hypothesised

46:32  46:38breaking connections to maybe
56% of them passively. 
46:38  46:43For IKE, for Internet key
exchange v1 and v2, 
46:43  46:46we're looking at in the 60%s of servers

46:46  46:48are potentially compromisable

46:48  46:51using this same hardware.

46:51  47:00For SSH, for IMAP with secure encrypted
connections, for SMTP with STARTTLS, 
47:00  47:02the encrypted mail transports,

47:02  47:06all of these protocols are
potentially jeopardised 
47:06  47:07by the same kind of attack,

47:07  47:09because everyone fundamentally,

47:09  47:11so many people fundamentally

47:11  47:14rely on the same underlying cryptography,

47:14  47:17often with the very same public parameters

47:17  47:20that are so widely shared.

47:20  47:22So what can we do about this?

47:22  47:25So first, let's go back to the
Logjam attack again, 
47:25  47:27using 90sera backdoored crypto

47:27  47:31that lets any of us break connections
to modern browsers. 
47:31  47:33Luckily, browsers have already started

47:33  47:34to mitigate this, as I said,

47:34  47:36by increasing the minimum strength

47:36  47:37of DiffieHellman they support,

47:37  47:40although there's still a way to go there,

47:40  47:43since they're all still accepting
1024bit key exchange. 
47:43  47:46Our biggest recommendation
under here though, 
47:46  47:49I think the lesson is:
don't backdoor crypto! 
47:49  47:51Right, because the backdoored crypto

47:51  47:53of 20 years ago is now coming back

47:53  47:55to bite everyone.

47:55  47:59applause

47:59  48:02And then, we have the second attack,

48:02  48:04the 1024bit case that enables

48:04  48:05so much mass surveillance.

48:05  48:07Well, to get around this,

48:07  48:10we're going to have to do some upgrades.

48:10  48:11Probably the easiest thing to do,

48:11  48:13and the thing that almost

48:13  48:15every cryptographer that we talked to

48:15  48:17recommends now,

48:17  48:19is to move to ellipticcurve crypto.

48:19  48:20Yes, there's been talk

48:20  48:23about whether the specific NIST curves

48:23  48:26may have been backdoored by NSA,

48:26  48:27but by and large, we think that

48:27  48:30elliptic curve is the most sound choice

48:30  48:32we have for now.

48:32  48:33Now if elliptic curve isn't an option,

48:33  48:35and there's technical reasons
why it might not be, 
48:35  48:39at the very least use
a DiffieHellman prime 
48:39  48:41that's 2048 bits or longer.

48:41  48:43If even that isn't an option,

48:43  48:46you're using legacy systems
for some reason, 
48:46  48:50well, or Java yes, thanks,

48:50  48:53if there's anyone there who works for Sun,

48:53  48:58please, please tell them
to fix the crypto in Java! 
48:58  49:05applause

49:05  49:07But if that's not an option,

49:07  49:08if that's not an option,

49:08  49:09the fallback is you can generate,

49:09  49:14at least generate your own 1024bit prime.

49:14  49:17Mind you, there various tricks
that you have to make sure you do 
49:17  49:20when generating a prime,
it must be a safe prime, 
49:20  49:22but there are implementations
of doing this, 
49:22  49:27so it's not exactly free to generate
your own 1024bit prime, 
49:27  49:28but it's inexpensive,

49:28  49:30and if you have no other option,

49:30  49:33at least so that this large
government adversary 
49:33  49:35has to spend a lot of precomputation,

49:35  49:38a year perhaps, targeting
you individually, 
49:38  49:40and they can't just get this for free.

49:40  49:43Alright, so, that is our talk for tonight,

49:43  49:46we're saving a lot of time for questions,

49:46  49:49thank you all very very much.

49:49  50:00applause

50:00  50:05Herald: Nadia. Nadia and Alex,
thank you very much. 
50:05  50:07We installed some microphones
here in the room, 
50:07  50:09so please queue up, but first,

50:09  50:12signal angel, do we have
some questions from the net? 
50:12  50:15Signal Angel: Yes, we have a lot of questions.

50:15  50:16First question is,

50:16  50:18do you think it's possible that the NSA

50:18  50:20uses quantum Shor factorisation

50:20  50:25for 1024 or bigger keys already?

50:25  50:28NH: I would believe it is much more likely

50:28  50:30that they're using classical cryptanalysis

50:30  50:31for 1024bit keys than than they have

50:31  50:35a quantum computer that
nobody has heard about. 
50:35  50:37Herald: And another one?

50:37  50:39Signal Angel: Another one... Is it thinkable

50:39  50:41that the NSA solved the P=NP problem

50:41  50:43but keeps quiet?

50:43  50:46laughter

50:46  50:48AH: Probably not, but if they have,

50:48  50:51yes, I think they'd want to
keep quiet about it. 
50:51  50:52NH: I hope they would tell us!

50:52  50:54AH: I hope they would tell us too,

50:54  50:56but I doubt it.

50:56  51:00Herald: Okay, and over to
number 1, please. 
51:00  51:02Q: Two questions.

51:02  51:06First, is it reasonable to think that,

51:06  51:09is it possible they are attacking
individual RSA keys, 
51:09  51:11that they can fetch individual RSA keys

51:11  51:14in about a week with custom hardware,

51:14  51:18and two, NSA Suite B came out 2005

51:18  51:19and they don't use DiffieHellman,

51:19  51:23so NSA themselves, they told us in 2005,

51:23  51:25"we won't use DiffieHellman",

51:25  51:27so is it reasonable that,

51:27  51:28when they changed the requirement

51:28  51:31for top secret, we should follow?

51:31  51:33AH: Well, to the first part
of your question, 
51:33  51:36about whether they're factoring RSA,

51:36  51:39I think the answer for 1024,

51:39  51:41is very likely, yes they are,

51:41  51:42for highvalue targets.

51:42  51:45So if you're a major website at least

51:45  51:48and you're using a 1024bit RSA key,

51:48  51:53well, it's long past time to change
to a higher strength. 
51:53  51:56NH: If the NSA has not factored
a 1024bit key, 
51:56  51:58I'm going to be very disappointed,

51:58  52:01I'm going to ask where
my tax dollars are going. 
52:01  52:07laughter, applause

52:07  52:09And also I think actually,

52:09  52:11the point of sort of watching

52:11  52:13what the defensive side of the NSA

52:13  52:15is advocating in terms of recommendations

52:15  52:17is actually a wise thing to do,

52:17  52:20because as far as we know,

52:20  52:22at least the public recommendations

52:22  52:26defensively should... I mean,

52:26  52:28making recommendations for people

52:28  52:31who are building systems that are
going to be handling classified data, 
52:31  52:33so they should be solid recommendations

52:33  52:34as far as we know.

52:34  52:35AH: What the NSA has told me

52:35  52:38about those recommendations, by the way,

52:38  52:40is that as long as you
follow them exactly, 
52:40  52:42you're going to be okay,

52:42  52:44but if you deviate in any
small way whatsoever, 
52:44  52:47then they make no guarantees whatsoever.

52:47  52:50So, think about what that might mean

52:50  52:52in terms of your implementation

52:52  52:56the next time you read through
those particular recommendations 
52:56  52:58that they make.

52:58  53:01Herald: Okay. Then we hop over to
microphone 3, please. 
53:01  53:04Q: So, for the moment, is

53:04  53:07ellipticcurvebased
DiffieHellman secure? 
53:07  53:10NH: I hope so.

53:10  53:14AH: It doesn't suffer from
the same shape of attack 
53:14  53:15that we've described here.

53:15  53:17As far as we know, there's not a way

53:17  53:19to do this same kind of precomputation

53:19  53:21for ellipticcurve DiffieHellman.

53:21  53:23NH: So what we didn't mention in the talk

53:23  53:25is, so, one of the reasons that

53:25  53:27elliptic curve keys are so much shorter

53:27  53:31than, say, finitefield
DiffieHellman or RSA 
53:31  53:35is because we have this
superpowerful index calculus 
53:35  53:37number field sievetype algorithms

53:37  53:41for factoring and for discrete log
over finite fields, 
53:41  53:43and those don't seem,

53:43  53:44we don't actually have equivalents

53:44  53:48of those algorithms for
properly generated elliptic curves. 
53:48  53:51So, that's why those key sizes are shorter

53:51  53:54and that's why we think
they seem to be more secure. 
53:54  53:57Herald: Then we take another one
from microphone 3, please. 
53:57  54:01Q: Yes, you said that when doing
the precomputations 
54:01  54:05for commonlyused primes,

54:05  54:08you can reduce the effort you have to put

54:08  54:11in a single connection
to about 70 seconds. 
54:11  54:13How is that usable?

54:13  54:16If my TLS handshake is delayed 70 seconds,

54:16  54:18I already ran away.

54:18  54:20AH: Ah! So we refer you to the paper

54:20  54:22for the full answer to that,

54:22  54:24but it turns out there's a bunch of tricks

54:24  54:29that you can do to keep
a session handshake open 
54:29  54:30for at least 70 seconds.

54:30  54:32So, this may not be what you want to do

54:32  54:35to the connection, say, in a web browser

54:35  54:38that's loading index.html,

54:38  54:40but whichever one is loading, say,

54:40  54:45the, I don't know, the 1pixel
tracking image in the background, 
54:45  54:46that nobody sees,

54:46  54:49which is also getting the same
session cookie, 
54:49  54:51that one you can hold open
for 70 seconds 
54:51  54:53without the user noticing.

54:53  54:54So what we've been able to do

54:54  54:56is show a variety of ways
that we can trick 
54:56  54:58browsers and other implementations

54:58  55:01into holding the connection
open long enough. 
55:01  55:03Also, 70 seconds is just
what we were able to do 
55:03  55:07with a few weeks of hacking
around and optimisation, 
55:07  55:11we think that with
not that much more effort 
55:11  55:13we could get that number
down quite a bit more. 
55:13  55:16But 70 seconds we think
already is not so bad, 
55:16  55:18and there's plenty of ways
that we can exploit it. 
55:18  55:21NH: Proof of concept.

55:21  55:24Herald: Okay. Do we have
something from the net? 
55:24  55:27Signal Angel: How long do you estimate the security

55:27  55:29of RSADHE to sustain,

55:29  55:31and do you have any idea if and when

55:31  55:34there's any quantum encryption algorithms

55:34  55:35that will soon be available to be used

55:35  55:37by a broad public?

55:37  55:39AH: Oh, quantum encryption algorithms.

55:39  55:41NH: You should watch Dan
and Tanja's talk from yesterday. 
55:41  55:44AH: Yeah, last night was the time
to hear about that. 
55:44  55:46NH: The dangers of quantum cryptography.

55:46  55:48I mean, the short answer is

55:48  55:50that people who know
what they're talking about 
55:50  55:52have said we should start worrying now

55:52  55:54because we may see quantum computers

55:54  55:57within the next 15 years, maybe.

55:57  55:59But it's really hard to speculate about

55:59  56:05advances in physics that
may be pretty far off. 
56:05  56:07Herald: Do we have another one?

56:07  56:10Signal angel: Sure. What's your
opinion on the NIST curves, 
56:10  56:11especially with the current rumours

56:11  56:16about the curve parameters
having a backdoor? 
56:16  56:18NH: There are no known ways

56:18  56:21that the curves could have been backdoored

56:21  56:23with the given parameters.

56:23  56:26AH: But if you don't trust them,

56:26  56:28you know Dan Bernstein
has a curve you can use too. 
56:28  56:30NH: So...

56:30  56:32applause

56:32  56:35NH: Do you trust Dan,
or do you trust the NSA? 
56:35  56:37laughter

56:37  56:39Herald: Over to 2, please.

56:39  56:42Q: Some of the little bit
that you recommend, 
56:42  56:46you say DiffieHellman is worse
than RSA now, 
56:46  56:50so, does it mean I should switch back

56:50  56:54to RSA, preferring it instead
of DiffieHellman? 
56:54  56:57AH: With equivalent key sizes,

56:57  57:00equivalent sizes of your primes,

57:00  57:03or your RSA modulus,

57:03  57:05yes, we are saying that.

57:05  57:07That in the 1024bit case,

57:07  57:10there's strong reasons that you should

57:10  57:14distrust the very common repeated primes

57:14  57:16for DiffieHellman.

57:16  57:18But that's not the whole story.

57:18  57:27Right, so for longer sizes of modulus,

57:27  57:28larger strengths of crypto,

57:28  57:32RSA is probably still okay.

57:32  57:34But I think either way,

57:34  57:38switching to elliptic curve
for key exchange 
57:38  57:40is probably the thing to do right now.

57:40  57:42NH: I think the precise statement
that we can make 
57:42  57:45is, if you're comparing 1024bit
DiffieHellman 
57:45  57:47to a 1024bit RSA key,

57:47  57:49that if you're using DiffieHellman

57:49  57:51with the most commonly used parameters,

57:51  57:53say, the Oakley group 2

57:53  57:55that everybody on the Internet is using,

57:55  57:57and you think it is likely that
a large government agency 
57:57  58:01has already done the
precomputation for that prime, 
58:01  58:05then breaking an individual
connection using that prime 
58:05  58:07with DiffieHellman key exchange

58:07  58:09would be much, much, much less effort

58:09  58:15than factoring a freshly generated
1024bit RSA key that is unique to you. 
58:15  58:18Even if that 1024bit RSA factorisation

58:18  58:20is within range of the NSA,

58:20  58:21it may not be worth their while

58:21  58:23to actually factor your key.

58:23  58:26Whereas breaking a
DiffieHellman key exchange, 
58:26  58:27they've already done the hard work

58:27  58:28to break everybody on the Internet,

58:28  58:31so, you're just one more fish.

58:31  58:32That's the precise statement

58:32  58:34that we can make about the security.

58:34  58:35The real answer: use elliptic curves,

58:35  58:42or, to use 2048bit
DiffieHellman: probably fine. 
58:42  58:44Herald: And, over to number 1, please.

58:44  58:47Q: How realistic is it to use, or to create

58:47  58:50a new prime for every exchange

58:50  58:53or at least every few exchanges?

58:53  58:56NH: So, unfortunately, the properties

58:56  59:01that you need for discrete log to be hard,

59:01  59:02you need to have a safe prime

59:02  59:06and you would hopefully like it
not to be backdoored, 
59:06  59:09generating safe primes is
still kind of effortful 
59:09  59:11on modern hardware,

59:11  59:12I mean if you try to do it on your laptop

59:12  59:15it will probably take like, I don't know,
a minute or something. 
59:15  59:17So, it's actually a lot of effort

59:17  59:20to generate a new safe prime all the time.

59:20  59:24Just use a larger safe prime
and you'll be better. 
59:24  59:26Herald: So we're running out of time,

59:26  59:29but let's... with number 2.

59:29  59:32Q: You said that elliptic
curve cryptography 
59:32  59:37is not susceptible to
this precomputation attack, 
59:37  59:44is that luck, or is it
engineered to be that way? 
59:44  59:44AH laughs

59:44  59:46NH: ...luck?

59:46  59:47AH: In part!

59:47  59:48NH: I mean, a combination of both, but

59:48  59:49so as far as we know, I mean, you can't do

59:49  59:51precomputation with elliptic curves,

59:51  59:54so, you know, sort of generically,

59:54  59:55the best thing that you can say

59:55  59:58is you can do a lot of precomputation

59:58  60:01but you still have to do a lot of effort

60:01  60:03for each individual value,

60:03  60:06so you could do, you know, generically

60:06  60:07if you want to break an elliptic curve

60:07  60:09you could do like,
a squarerootofn attack 
60:09  60:11against the key size,

60:11  60:14you could do, say, n^2/3 precomputation

60:14  60:18and then you would have n^1/3 online work

60:18  60:19if that makes sense to you.

60:19  60:23But you get less effort as far as we know.

60:23  60:25Less benefit.

60:25  60:28Herald: Sorry. We're going to finalise
then, with number 4. 
60:28  60:31Q: What do you think about blacklisting
these common primes, 
60:31  60:32just in the modern browsers?

60:32  60:35Will this get rid of this issue?

60:35  60:37AH: Just blacklisting the common primes,

60:37  60:39well, if you blacklist the common primes,

60:39  60:41if you blacklisted the common primes

60:41  60:43when we first came up with this,

60:43  60:47you'd immediately break
about 10% of websites 
60:47  60:50because there's not a good
fallback mechanism 
60:50  60:52if you don't like the prime you got

60:52  60:55during key negotiation.

60:55  60:57What the browsers are more likely to do

60:57  61:02is to phase out this kind of
finitefield DiffieHellman entirely, 
61:02  61:05over the next larger number of years.

61:05  61:07So first they're going to
start rejecting things 
61:07  61:09that use unusually weak primes,

61:09  61:12that's what they're doing already today,

61:12  61:13but I think in the long term

61:13  61:17they're going to encourage the use
of elliptic curves as an alternative, 
61:17  61:18if you want forward secrecy,

61:18  61:22elliptic curves will be the way to get it.

61:22  61:25Herald: Nadia, Alex, once again,

61:25  61:26thank you so much.

61:26  61:27AH: Thank you.

61:27  61:33applause

61:33  61:37postroll music

61:37  61:44subtitles created by c3subtitles.de
in the year 2016. Join, and help us!
Show all