J. Alex Halderman, Nadia Heninger: Logjam: Diffie-Hellman, discrete logs, the NSA, and you

preroll music

Herald: I did some research,

and it was not, not easy

that Diffie-Hellman key exchange

is so much above my pay grade

therefore, I'm going to keep it simple.

Please welcome

we have Alex Halderman from
the University of Michigan,

and Nadia Heninger from
the University of Pennsylvania.

applause

AH: Thank you.

Thank you all so much.

It's wonderful to be back again in 32C3.

I'm Alex Halderman from
the University of Michigan,

here again this year with,

with many of my students from my group

here in the audience also speaking.

We study security in the real world.

So tonight, we have
a very special story to tell you

that I'm very proud to be telling

along with my colleague Nadia Heninger.

We're going to be talking

about discrete log, Diffie-Hellman

and some of the, um,

the research that we've done

over the past year,

try to understand how the NSA

may be breaking so much of the crypto

that we know they're breaking.

Why do we...? So this work is

joint work with a number of co-authors,

with 12 other co-authors,

3 of them are in this room right now,

and I'd ask to stand up

but they said they didn't want to

so please, a quick round of applause

for my co-authors as well.

applause

So, thank you.

So in this very room,

a year ago at 31C3,

Jacob Appelbaum and Laura Poitras

gave a talk, "Reconstructing Narratives",

in which they announced some new results

from the Snowden archives.

They were able to tell us how the NSA,

that the NSA was breaking cryptography

used in widespread online communication.

And, they later published

an article in der Spiegel,

in which the article included documents

that showed indeed the scope of NSA

breaking widely used encryption

was significant.

That NSA is breaking,

maybe not all crypto,

but they're able to break
widely used crypto

from many of the different kinds

of services and protocols we care about.

What the leaks didn't answer

is how NSA is breaking this cryptography

and to a technologist,

well, if we don't know
how they're breaking it,

what can we do to stop it?

So, Nadia and I and our co-authors set out

earlier this year

to try to, through our research,

start answering those questions.

How is NSA likely to be breaking

likely used cryptography,

and what can we and other researchers do

to stop government from being able

to attack the crypto
that all of us depend on?

So, so...
applause

Let's tell the story.

Wait until you see how it ends!

So if I were setting out as the attacker

to break widely used crypto,

well, there's a few different ways
that I could do it.

One branch of the decision tree here

is to attacking the implementations

right, either finding vulnerabilities

or introducing backdoors,

we've all been witnessing over the past

week or so with Juniper and their systems

being compromised.

On the other hand,
there's another prong you could take.

You could try to attack the crypto
algorithms themselves,

the underlying crypto.

And the difference is,

if you're attacking implementations,

you have to make a big investment

in every hardware device
and piece of software

that you're trying to compromise.

If you're attacking the underlying crypto,

you have just one, a one-stop shop

to gain access to,
potentially a very wide swath

of all the crypto in use.

So a small number of algorithms

predominate for both
symmetric cryptography,

things like AES and RC4,

but those particular algorithms anyway,

most cryptographers seem to think

that breaking them,

at least in the general case,

is pretty hard right now.

Instead though, we also have

a very small number of
public key crypto algorithms

that are also in use very widely

for most or all of the protocols
and services we care about.

Things like RSA and Diffie-Hellman.

And here be dragons, as they say,

this is the cryptography that we
and many other cryptographers

think is most likely to be targeted.

So, I'll hand it off to Nadia

to talk about breaking public key.

applause

NH: So, in order to understand

a little bit about
how cryptanalysis works,

I'm going to go all the way back

to the very beginning of
public key cryptography

from the 70s,

and I'll start by explaining
a little bit about RSA.

This is Rivest, Shamir, and Adleman
up on the screen here,

from the 70s, you can tell.

And this is sort of the simple example,

and then we'll talk a little bit more

about the actual
Diffie-Hellman-based cryptanalysis

that we're actually talking about.

So, this the first public-key
crypto algorithm

that was ever published,

and it is still the most widely used

cryptography, public key cryptography
algorithm out there.

That shows you, I guess something
about the naturalness of ideas,

or maybe the lack of progress

that we've had in the past 40 years.

So, here's sort of the textbook version
of RSA encryption,

what we really care about is that...

So, Alice and Bob, they want

to bootstrap communication over

an untrusted channel,

so there's some eavesdropper
in between them

who's intercepting their messages.

And, in order to get around this,

they need to somehow figure out

how to share a key in order to

actually encrypt their communications.

And the way that RSA accomplishes this,

is, Bob here on the right has a public key

which in RSA is e modulus N

which is the product of
two large prime factors,

and he sends this over to Alice,

and Alice uses Bob's public key

to encrypt a message, like a session key,

and send it back to Bob,

and then Bob can decrypt the message,

get the session key,

and they can communicate using

some other symmetric cipher.

So, this is the big picture
of RSA encryption.

The reason that we think

that RSA is secure is because

the best way that we know how to break
an RSA public key

is to factor the modulus,

and as far as we know,
factoring is not very easy.

So, in particular, factoring is

what we hope is something like

a one-way function,

multiplication is easy,

factoring the number into
two pieces again is hard,

in some sense.

And the best algorithm that we have

in the general case, of, say

an RSA modulus that's well-generated,

is called the number field sieve.

So here is the...

this is as bad as technical
as I'm going to get,

and I'm waving my hands vigorously here,

but here's something along the lines of

what the number field sieve algorithm

actually looks like,

so it's a multi-stage algorithm,

it's rather complex,

some stages parallelise very well,

embarrassingly well,

other stages parallelise somewhat
less well,

and so we've got these multiple stages
that we go through,

and at the end of the algorithm,

we discover, we hope, a prime factor

of the number that we're trying to factor.

So, how long does it take to factor?

Here's one answer:

if you ask a number theorist, this is

the answer that they all give you,

they all go through the optimisation,

and they will tell you the answer is

a sub-exponential function in the size

of the number that we're trying to factor.

That I think is not the answer

that you guys are looking for.

So, here's a slightly more
concrete answer.

So, how long does it take to factor

different sizes of keys?

So, for 512-bit RSA,

the first 512-bit RSA modulus
was factored in 1999

by a group of academics,

that took them 6 months
and a few supercomputers,

now you can rent supercomputers
by the hour.

So what does that do?

Well, some students of mine

actually were able to factor
a 512-bit RSA key

for 4 hours and 75 dollars on Amazon EC2.

If you would like to do this too...

applause

So, you can also do this too,

code is online, right here, download it,

send us bug reports, etc.

So, as we go up in key sizes,

768-bit RSA modulus,

estimate, current estimate is

less than 1000 core-years,

and for sort of reasonable-size
academic clusters,

that should take less than
a calendar year to finish, now.

That was,
the first 768-bit RSA factorisation

was done in public in 2009.

So, that gives you some idea
of sort of the progress.

For 1024-bit RSA, nobody has factored

a key of that size in public,

the estimate is probably,

it's about a million core-years,

which is certainly within range

for a large government,

so it is against better recommendations

to use a 1024-bit RSA key size,
at this point.

Current recommendation is to use

a 2048-bit RSA modulus,

with current algorithms,

nobody should ever be able to factor

something at this size,

without some kind of major improvement.

So, there's the big picture for you.

Now move on to Diffie-Hellman.

So, the paper that introduced
Diffie-Hellman

was called "New Directions
in Cryptography",

it's one of the seminal papers
of the 20th century,

how many of you have read this paper?

You should all go read it right now,

I mean not right now, maybe after I talk.

The first sentence of this paper,

written in 1976,

is "We stand today on the brink
of a revolution in cryptography".

This is one of the best opening sentences

of an academic paper I've ever read,

and they were 100% right
about everything they put in the paper.

They laid out the entire foundations

of cryptographic research
for a couple decades,

and to boot they came up with

the first public key exchange,

that is still one of the commonly used

public key methods we

have on the Internet.

So, all that in one paper.

So, the way that
textbook Diffie-Hellman works,

is, you've got a couple of parameters,

you've got a prime p,

and some element g less than p,

you can think,
for concreteness, g is 2.

It's a good number.

And p is some very large prime,

say 1024, 2048-bit prime.

And so Alice and Bob,

same as our previous scenario,

they want to bootstrap communication

in the presence of
an untrusted eavesdropper.

So what they're going to do,

Alice will generate some secret value a,

and she will compute g^a mod p,

and send it over to Bob,

and Bob will compute some secret value b,

and compute g^b mod p,

and send it over to Alice,

the eavesdropper sees the values
g^a and g^b,

can't derive anything useful from those,

but Alice and Bob can individually

take their secrets

and derive the values g^ab mod p,

both the same values.

And that becomes a shared secret,

which they can then use as a session key,

and, you know, switch to AES

and start symmetrically
encrypting their data.

So, that's Diffie-Hellman key exchange.

Used all over the Internet,

one of the commonly used things possible.

So, one of the reasons that people

have been advocating
Diffie-Hellman key exchange recently

over, say, RSA,

is because it can be, it can provide

the property of perfect forward secrecy.

So assuming that Alice and Bob

generate fresh random
secret values a and b

for every single connection,

then if, say, some large government agency

is collecting all of their communications

and later tries to hack into Alice or Bob,

or break one of their keys,

in order to decrypt their communication,

they can't hack into Alice or
Bob's computer later,

and then discover the key

that Alice and Bob used

to generate all the conversations
that they had,

because Alice and Bob have
already forgotten

the keys that they used.

So, as long as Alice and Bob

are generating fresh random
values every time,

those values should reveal nothing

about past or future communications.

So, that's perfect forward secrecy.

And, a lot of people have,

who really know what
they're talking about,

including, unfortunately, me,

on this stage a couple years ago,

have said, "you guys should always use
Diffie-Hellman over RSA key exchange

because of this property of
perfect forward secrecy".

So here's a selection of quotes

that I found on the Internet,

just from googling
"perfect forward secrecy"

and "Diffie-Hellman key exchange",

and you find people saying that

this provides better security,

the NSA can decrypt nothing,

1024-bit Diffie-Hellman is arguably
better than 1024-bit RSA,

and then 1024-bit Diffie-Hellman
is better than any key size for RSA.

This is a selection of friends

and people I respect,

and some also, also some
random people on Stack Overflow,

which is where...

laughter

where we know everybody's actually

getting their recommendations from.

So, there's been wide-scale advocacy

of perfect forward secrecy as

like, the reason that you should
use Diffie-Hellman.

It will protect you against the NSA.

I'm sorry. We were wrong.

And, why were we wrong?

I'm going to tell little bit more

about what the cryptanalysis looks like

for Diffie-Hellman.

So, the underlying problem
that we hope is hard

for the security of Diffie-Hellman

is called discrete log,

it is exactly sort of the problem of

given one of the key exchange values g^a mod p

compute, say, Alice's secret a.

This would allow the attacker

to compute the shared secret

in the same way that Alice did.

And, sort of similar to
factoring and multiplication,

discrete log, we think it's much harder

than modular exponentiation,

the computation that actually

gives you the value g^a mod p.

And the best algorithm that we have

is called the number field sieve.

So, there's a lot of parallels going on here.

So what does the number field sieve

for discrete log look like?

Hopefully this diagram is somewhat
familiar to you by now,

it's a multi-stage algorithm,

it has many of the same
stages as factoring,

you can sort of line them up in parallel,

the last bit looks a little bit different,

but we can sort of ignore that
for the moment.

Okay. So, we have some pictures

of what the number field sieve looks like.

How long does it take?

Answer number 1:
The same answer as factoring.

In case you didn't remember,
here it is again.

This is kind of why everybody
has been saying

"Okay, the security of, you know,

1024-bit Diffie-Hellman key exchange

is about the same as the security of

a 1024-bit RSA key."

It's because we have the same
complicated formula that tells us

how hard it is to break.

The sort of more subtle answer for...

or, not more subtle,
but the more practical answer

for, how secure is it,

is, we can say, well, how long do we think

it will take to actually compute

a discrete log for
commonly used key sizes,

and the answer is,

slightly longer than factoring an
RSA key of equivalent size,

but, not so much longer than an RSA key.

And, the minimum recommended key size

today is 2048 bits.

Okay, so, 2048-bit Diffie-Hellman,

we're good. Great! We can all go home.

Okay. However, okay,

what if you want to break many connections

that use the same public parameter p?

Do you have to go through

this whole computation,

every single, for every single connection

that you want to break?

That was kind of the justification

for perfect forward secrecy,

that every single connection

should be as hard as factoring an RSA key

of the equivalent size.

Except that's not quite the case.

Because if you look at where

the actual target that
we're trying to compute

appears in this plot,

it's only at the very last stage.

So all of this only depends

on the prime p.

So we can actually divide up
the algorithm in two pieces:

A few stages that depend only
on the prime p that we're using,

and then the final computation

that takes the output of this
first precomputation stage,

and that's the only stage

that actually matters,

that actually depends on the target

of our discrete log computation.

So, we're in trouble.

In particular, that means that

if many connections are using
this same prime p,

you can do the precomputation once,

spend a huge amount of effort,

and then the actual effort required

to break individual connections
using those primes

is much, much smaller.

So here's our current estimates,

these are actually somewhat new
from our paper,

of how long the individual log stage
takes in practice,

if you push the primer as far as you can

to make this as fast as possible.

And the answer is basically,

if you're worried about a government,

you better start worrying

for reasonable key sizes
that people are using.

See, so I'll let Alex continue

with the next part of our talk.

applause

So this fact that Nadia just told us

about Diffie-Hellman

and the number field sieve,

this was something that the
mathematical crypto people knew about,

but most of us who did system security,

people like me,

didn't ever get the memo.

So, it's, I'm here in part to apologise

to everyone I've taught

about Diffie-Hellman and cryptanalysis

who didn't get to hear about this,

as we were talking about

perfect forward secrecy.

Right, this fact about the cryptanalysis

and how well it can apply in exactly

the scenario that we're worried about,

this kind of situation
involving mass surveillance,

was news to many of those.

But now that we have that fact,

how can we exploit it,

to try to break Diffie-Hellman,

in scenarios that we all care about?

And we're going to talk about

two scenarios in the talk today.

The first one applies to HTTPS,

to encrypted web connections,

and it applies not only
to government agencies,

but also just to normal
everyday attackers,

with maybe the same resources

that you or I have.

Right, this is a down-to-earth
kind of attack on HTTPS,

and we call it Logjam.

Logjam allows us to break

the HTTPS connections

to many, many popular websites

in modern browsers,

by fooling those browsers into using

1990s-era backdoored crypto.

So where does this backdoored
crypto come from?

This is from the first crypto wars,

back in the 90s,

when my country, the US,

had restrictions on what kind and strength

of cryptography could be exported,

and used by people abroad.

So US companies were prohibited

from exporting products that contained

cryptography that had greater
than a certain strength.

For RSA, that was that the key size

had to be less than or equal to 512 bits,

and for Diffie-Hellman it was that

basically the prime had to be
512 bits or less.

So back in the 90s,

these were constants,

these were strengths of crypto

that were chosen presumably because

they were easy for NSA to break.

So, if you were an American company

making products, like let's say

Netscape Navigator, the web browser

that initiated the first SSL protocol,

you needed some way to be able

to communicate with,

from servers in the US,

to clients, including your own browser,

that you would ship to people abroad,

say, here in Germany.

And so they came up with a way

to use, to have HTTPS automatically select

the appropriate key strength

depending on whether the browser

was able to support
the full-strength cryptography,

or the weakened version

for deployment abroad.

And the way that they did that

was something called

export-grade cipher suites.

So when your browser,

whenever it starts a TLS connection

for an HTTPS URL,

one of the first thing that it does

is, the browser will send to the server

a list of the kinds of cryptography

that it can speak,

these are called cipher suites,

and then the server selects one of those,

that is compatible with
whatever cryptography

the server has available,

and then that negotiated cipher suite

is what's used for the connection.

Now the way that they supported

the 90s-era backdoor crypto

was by having browsers shipped abroad

from the United States that could only

speak a certain subset
of crypto algorithms,

that were limited in strength

to 512 bits or less,

those were the export-grade cipher suites

with the names you see here.

Now, even though no
browser has been shipped

that is limited to only these suites,

since probably 2000-sometime,

when the US relaxed
its export regulations,

there wasn't just any one day

when all of those old browsers

from before that era went away.

So, servers, even now, many servers

will still accept and speak
these weakened cipher suites,

if that's all the browser has available.

Like if you're running an e-commerce site,

right, I'm sure you still want to be able

to speak to any customers

who have 1998-era
Netspace Navigator involved,

otherwise you'd lose some sales, right?

So there was no reason to turn them off,

because no modern browser any more,

now that those restrictions are lifted,

would choose these weakened suites.

Well, that's what we thought, anyway.

So, in, over this past year,

there were two attacks that exploited

these weakened cipher suites,

that found ways to convince
modern browsers

to speak them instead of
full-strength cryptography.

The first was the FREAK attack,

which was revealed in early 2015

by a separate group of authors,

and the FREAK attack was
an implementation flaw

in many modern browsers.

In order to exploit it,

all you need to do is to be able

to relatively inexpensively

factor a 512-bit RSA key.

And, as Nadia has told you,

this is now a matter of maybe 4 hours,

maybe 75 dollars, something like that,

and if you did that, you'd able to break

all the connections coming into

a weak server for a long period of time,

to a server that still spoke
these cipher suites.

So this affected most modern browsers,

and just shy of 10% of Alexa
top million sites that speak HTTPS.

Now that left the Diffie-Hellman

export-grade cipher suites,

which were not affected by FREAK.

But we came up with a paper
in May of this year,

that showed a separate attack,

the Logjam attack,

which is a protocol flaw in TLS,

and affects all modern browsers,

and, similarly, allows you
to downgrade connections

to export-grade Diffie-Hellman,

and then intercept or modify the contents,

if the server speaks and still supports

these export-grade Diffie-Hellman
cipher suites.

So now let me give you

the hopefully brief technical overview

of how the Logjam attack works.

If you've been curious about this,

this is the chance to see it.

So, Logjam is a problem that happens

during the TLS connection handshake.

And the first thing that happens
in the handshake,

at the top of this diagram,

so this is just your browser connecting

to some website, some server
there on the right,

maybe Alice connecting to
her favourite website here.

So the first stage is this client hello,

where, you know, a normal client
is going to say,

I speak various kinds of cryptography,

including full-strength Diffie-Hellman.

The server at that point is going to

respond by picking some cipher suite,

let's say Diffie-Hellman,

and then sending over
its certificate chain,

as well as its Diffie-Hellman
public parameters,

p and g, the server gets to choose them,

as well as g^a.

And then it's going to use

its long-term RSA key that is the thing

that is signed in its certificate,

in order to make a signature on
those Diffie-Hellman parameters.

Okay, then it's going to do...

complete the negotiation, and so on.

In the Logjam attack,

we have a man-in-the-middle attacker,

who's able to modify some
of these messages

as they're going by.

So the first thing the attacker does,

he modifies the client hello message,

to replace all of the different
kinds of cryptography

the client says it supports,

and just put in export-grade
Diffie-Hellman.

Ah, the 90s are here again.

Alright, so then, you know, the server

will get that, and if the server supports

export-grade Diffie-Hellman,

as about 10% or so of servers

still support export grade Diffie-Hellman,

it's going to respond and say,

okay, that's what you asked for,
I'll take it,

and it's going to send over its side

of the Diffie-Hellman key exchange,

but using a 512-bit prime,

because that's what is required under

these export-grade suites.

Now, at that point, the browser would

normally reject this message,

because it didn't ask for export-grade,

it really asked for full-strength,

so instead, the man in the middle has to

modify the server's hello message,

and say that this is full-strength
Diffie-Hellman,

well, if it's full-strength,

why is it only a 512-bit prime
that's being used?

Well, there's actually no limitation,

and no distinction between the messages

that the server would send
in that space with p and g,

that says normal-grade Diffie-Hellman

has to be more than 512 bits.

In fact we found a handful of real sites

that even for normal-strength
Diffie-Hellman

just happened to use 512-bit
or even weaker cryptography.

So, as long as we modify
this earlier message,

the server's hello message,

and make it say, "normal-strength
Diffie-Hellman",

there's no way for the client to tell

from just the structure of the protocol,

that anything is amiss.

So, at this point, there is one last place

that we could catch the problem,

that the client or the server could see

that something's wrong,

which is that each side sends
the other a finished message,

here at the end,

that says, basically, has, uses
the session secrets

to add an authentication code

to a dialogue of all of the
protocol messages

that match the handshake dialogue,

all the messages going back
in each direction so far

have to be the same from each side of you.

However, in our case, in Logjam,

the attacker is able to spoof
these messages,

to make them look correct to each side.

He's able to modify that dialogue why?

Well, because we're using this
512-bit Diffie-Hellman

that we know from using
the number field sieve,

we are able to efficiently break.

So, if the attacker is able to quickly

perform the discrete log

on the Diffie-Hellman key exchange

that's going by at 512-bit strength,

then he can fix up the client
and server hello messages,

and neither side will notice
that anything went wrong.

So that's Logjam in a nutshell.

I'm sorry, it's a little bit complicated.

So, how widely shared are

these Diffie-Hellman public parameters?

Well, we used Internet-wide
scanning to find out.

So, my group, we also made
something called zmap,

that I talked about here
a couple of years ago,

which lets us quickly probe
everything on the Internet,

and so we did this and tried to make

connections to each HTTPS server

in the public IPv4 address space,

and found out what key exchange methods

were supported and with what primes.

And what we find is that 97% of hosts

that support export-grade Diffie-Hellman

use one of only 3 512-bit primes.

They're that widely-shared.

Why is this? Because those parameters

are very often either hard-coded

or encoded in standards

that different people implement.

The most common of these,

used by 80% of hosts that support
export-grade Diffie-Hellman,

is a public parameter that's
hardcoded into Apache 2.2.

So, it's actually there,
embedded in the source,

you have to recompile Apache to change it.

13% of hosts supported something,

a second prime that has also 512 bits,

that's hardcoded in mod_ssl,

and the next most popular, 4%,

was in the Sun JDK.

Only 10 primes accounted for 99%

of all the hosts we found in
the public address space

that supported export-grade
Diffie-Hellman.

So, if we would like to compromise these,

well, Nadia just told you about

how long it takes to use
the number field sieve

to break 512-bit discrete log,

well, we actually went and did
the precomputation

for all 3 of these most widely used
Diffie-Hellman primes,

and our colleagues who make a tool
called CADO-NFS

where able to implement the code

for that piece of the discrete log version
of the number field sieve

and they ran the algorithm on these primes

on a cluster they just happened
to have lying around,

it took about a week of time
on the cluster

for each of these primes.

After which, using an optimised version

of the last portion of
the number field sieve,

it takes about 70 seconds for us to break

any individual connection

that uses any one of these
3 most popular primes.

So, Logjam and our precomputations

now allow us to break any connection

to about 8% of the top million
HTTPS sites from Alexa

and when we came up with this attack,

it worked in all modern browsers.

So, mitigation!

applause

This is bad, everyone, this is the crypto

all of us are using.

So we do have some mitigations.

This is the actual positive part,

is that the browser makers have now

started to increase the minimum strength

of Diffie-Hellman they will accept.

So IE, Chrome, and Firefox will reject

primes less than 1024 bits

and Safari less than 768.

And the new draft of TLS 1.3 is including

an anti-downgrade flag

that will make it even harder

for such attacks to take place
in the future.

Now back to Nadia.

NH: So we promised in our abstract...

applause

...that there would be a hands-on
portion of this talk.

So, you have a couple options,

number 1 is, if you're really into this,

you can do and download
CADO-NFS yourselves,

cado-nfs.gforge.inria.fr

and, you know, run
discrete log algorithms yourselves

for any prime you wish

and then you can compute
arbitrary discrete logs.

However, since we have already done

some of the computations,

we figured that we would make
them available for you guys

if you wanted to play with them.

So...
applause

We have done so through the Twitter API,

so we have a bot running on Twitter

and if you would like to compute

discrete logs for any of these
widely-used parameters,

this bot will do so for you.

So here is the group generator
and the primes in hexadecimal,

for the 3 groups that we
did the precomputation for.

And if you wanted to test out,

you would do something like this,

so this using Sage,

which is a Python-based open source
mathematics package,

that does a lot of algebra
and number theory,

if you like playing with the stuff,

sage is super cool,

so, I said, say, my prime m
is this last value in hex there,

the mod_ssl prime,

then I take 2 and raise it to
the 0x1337 power mod m,

and then I print it out in hexadecimal,

and I get this value, then I can
copy-paste it into a tweet @DLogBot

then some comp stuff happens
on our back end,

this is running on one of
the machines in my lab,

so please don't break it,

and after a minute or two,

you should get back an answer.

applause

So, there's a queue,
only one thing can run at a time,

median time is 70 seconds,

it can vary between
30 seconds and 3 minutes,

so, you know, if it doesn't respond to you

within like, you know, an hour
or something,

then send us a ping and we'll see
if it's still running.

Okay. So, have fun.

Please don't actually use this for malice.

applause

We already have some satisfied customers.

laughter

AH: Alright, so we promised there were

two exploits that have to do with
weakened Diffie-Hellman,

and the first, Logjam, right, anyone can

use backdoors from the 90s

to pwn modern browsers,

well, the second one is
a little bit more widespread.

So, we're going to talk about

how Diffie-Hellman weaknesses

can be used for mass surveillance.

We believe that governments can probably

already right now, exploit
1024-bit discrete log

to break Diffie-Hellman for
wide-scale passive decryption

of Internet communications.

So, is breaking 1024-bit Diffie-Hellman

within the reach of governments,

let's look back at these numbers quickly.

So we can see that for 512-bit RSA
and Diffie-Hellman,

they're both really in reach of
basically any effort right now,

any one of you can probably,

most of the resources to do this.

For 768-bit RSA or Diffie-Hellman,

well, we think this is now in the reach

of a concerted academic effort.

For 1024, it's a little bit
more complicated,

because the number field sieve algorithm

is complicated enough that even

making estimates of the runtime
at this size and larger

is very, very complicated

and having a high-confidence estimate
is difficult.

But we've tried to do the math
conservatively,

and we believe that
a conservative estimate,

at least for 1024-bit Diffie-Hellman

is to break, to do those precomputations

for a single prime p,

would take about 45 million core-years.

Now 45 million core-years
sounds like a hell of a lot.

But, when you start to think about it,

if you're going to do
an effort that large,

there are some optimisations
you could start doing,

and, for instance, maybe instead of

running this on general-purpose PCs,

like these estimates show,

if you're going to do
an effort on this scale,

maybe you're going to tape out some chips,

maybe you're going to use custom hardware.

And if we do the math and look at
what kind of gains

we can get from custom hardware

in other applications that
are similar to this,

we estimate that we can get

maybe a speedup of 80 times

just by doing it in custom hardware.

Okay, and then we ask what's
that's going to cost,

well, we estimate that for...

to build a machine that could break

one 1024-bit p, precompute for
one 1024-bit p every year,

would cost somewhere in the neighbourhood

of low hundreds of millions of dollars,

in a one-time investment.

As a result of this, you can churn out

precomputations once a year

that will let you break efficiently

every connection that uses that p.

Now, individual logs then are going to be

close to real-time, and in fact you can

re-use much of the same hardware

to do the computations for
individual logs very quickly.

So, um, oh shit.

This is what the estimates look like.

Now is NSA actually doing this?

NH: This is where we get into

the conspiracy theories.

applause

So, there have been rumours flying around

for many years, I mean
for decades, really,

but sort of credible rumours
for many years,

of some large cryptanalytic breakthrough

that the NSA made.

So here's an article from James Bamford,

one of the, you know, world experts
in open ???

of what the NSA's activities are

and he wrote an article in 2012

saying very clearly that he had talked

to multiple government officials

who said that the NSA made
some enormous breakthrough

several years ago.

Everybody's a target,

everybody with communication is a target,

and this computing breakthrough

is going to give them the ability

to crack current public encryption.

And it was so secret that no oversight,

anybody had sort of access
to the details of it.

But whatever it was,
it was major and massive.

Of course, you know, after we saw this,

we said, oh my god, you know,

what could it possibly be,

are they breaking RSA?

Bamford actually goes on in this article

to speculate that it's
something about AES,

which at least to my mind
seems less likely

than some kind of major
public key breakthrough.

So clearly we have sort of these rumours

of large breakthroughs by the NSA's
tens of thousands of mathematicians.

Simultaneously, we can say, you know,

we know the NSA is clearly
interested in cryptanalysis,

is cryptanalysis on the scale
of hundreds of millions of dollars

within their reach?

The answer, thanks to Snowden, is yes.

We have some of their budgets

and they spend billions of dollars a year

on computer network operations,

they spend hundred of millions of dollars

on cryptanalytic IT systems,

cybercryptanalysis,
exploitation solutions,

in fact, a couple years ago there was even

an increase of hundreds of millions of
dollars in their budget for cryptanalysis.

Interesting.

So, a hundred million dollars of
special-purpose hardware

is certainly within range
of a government the size of ours.

Additionally, we can ask,

what would the impact of doing one of

these single precomputations

for a discrete log
for a single prime would be,

and the answer is actually
surprisingly large.

So if you did this precomputation

for a single 1024-bit prime,

that would allow passive decryption

of connections to 66% of VPN servers

and 26% of SSH servers.

This is from Internet-wide scanning,

we connected to all of these

and we said "we would like to speak

Diffie-Hellman with you,
what parameters do you prefer?"

and these are the servers that preferred

a single 1024-bit prime over
every other parameter in key size.

A second 1024-bit prime would allow

passive decryption for 18%
of the top million HTTPS domains.

These are domains that prefer

to speak Diffie-Hellman
with this fixed prime.

And, the final piece of evidence

for something like this being within range

and at least being worth worrying about

is actually some of the slides
that were release last year,

by der Spiegel,

and in particular they have
a large amount of detail

about passive decryptions of VPN traffic.

So here's an example,

it is clear from the slides that

whatever the NSA is doing,

they have the ability to passively decrypt

VPN connections on a large scale.

And they're very happy about it.

I think this is my favourite
Snowden slide ever.

laughter

I feel this way when I decrypt things too.

laughter

So, if we take a look at what,

and these slides are specifically
talking about IPsec VPNs,

if we take a look at what the
key exchange looks like for IPsec VPNs,

what happens is, we have two hosts

who want to make a VPN
connection with each other,

the key exchange actually uses a
fixed set of parameters

from a small list of possibilities,

and so Alice and Bob will negotiate

which parameters they're going
to use from this list,

and then they will do a
Diffie-Hellman key exchange,

from that they will have
a shared secret, g^ab,

and then they, in the most
commonly used mode,

they also have some pre-shared key,

like a password that has been shared

over some other channel.

And that Diffie-Hellman secret

that was negotiated together
with the pre-shared key

or mixed together to generate
the session key.

So, if somebody wanted to

break a connection of this type,

one option would be to, say,

steal the pre-shared key
through some other mechanism

and then break Diffie-Hellman.

That would be a possibility.

So, if we look what the
NSA's requirements are

for their mass-scale decryption efforts,

they require finding out what
the pre-shared key is,

getting both sides of the connection,

getting both the asymmetric key exchange

and the symmetrically encrypted data,

and then having some metadata.

These are the requirements for them
to get decryption.

And we can also take a closer look

at what their decryption flow
actually looks like,

this is somewhat complicated,

but in this diagram,

so they're getting the IK exchange,

and the symmetric data,

they're sending it into
one system that they have,

they're sending the IKE messages through

out to some high-performance
computing resources,

and then they get sent back with

some data from stored
databases of information

that returns the actual decrypted data.

So that's what the decryption
flow looks like.

We don't have any details
of the cryptanalysis,

but we have details from
the sysadmin's perspective

of how the systems
that do the cryptanalysis

are hooked together.

And they're doing something

that requires high-performance computing,

that takes in key exchanges

and hands out decrypted data.

So, we can line up sort of the NSA's
on-demand IKE decryption

with what a discrete log decryption
would actually look like,

and they're very close,

so they would both require
the pre-shared key,

both sides of the handshake,

both the handshake and the symmetric data,

and they would send off the data

to high-performance computing.

So in the same set of slides,

they also discuss targeted implants

against particular implementations,

if you were going to design a
backdoor to make your life easy,

you would have fewer
requirements than this.

Potentially.

There are many kinds of backdoors
that you could design,

but if you were being clever about it,

you might try to make it
a little bit easier on yourself

to decrypt the mess.

So I will let Alex finish with this.

applause

So to wrap up,

what we've seen today

through the cryptanalysis
of Diffie-Hellman

is probably a mass surveillance dream.

The algorithms that we've talked about

would let a government with
sufficient resources

to invest in these precomputation attacks

break connections on an almost
unheard-of scale,

across almost every widely-used
crypto protocol on the Internet.

Here are some numbers again,

for HTTPS, the top million sites,

we're looking at a device like

the ones we hypothesised

breaking connections to maybe
56% of them passively.

For IKE, for Internet key
exchange v1 and v2,

we're looking at in the 60%s of servers

are potentially compromisable

using this same hardware.

For SSH, for IMAP with secure encrypted
connections, for SMTP with STARTTLS,

the encrypted mail transports,

all of these protocols are
potentially jeopardised

by the same kind of attack,

because everyone fundamentally,

so many people fundamentally

rely on the same underlying cryptography,

often with the very same public parameters

that are so widely shared.

So what can we do about this?

So first, let's go back to the
Logjam attack again,

using 90s-era backdoored crypto

that lets any of us break connections
to modern browsers.

Luckily, browsers have already started

to mitigate this, as I said,

by increasing the minimum strength

of Diffie-Hellman they support,

although there's still a way to go there,

since they're all still accepting
1024-bit key exchange.

Our biggest recommendation
under here though,

I think the lesson is:
don't backdoor crypto!

Right, because the backdoored crypto

of 20 years ago is now coming back

to bite everyone.

applause

And then, we have the second attack,

the 1024-bit case that enables

so much mass surveillance.

Well, to get around this,

we're going to have to do some upgrades.

Probably the easiest thing to do,

and the thing that almost

every cryptographer that we talked to

recommends now,

is to move to elliptic-curve crypto.

Yes, there's been talk

about whether the specific NIST curves

may have been backdoored by NSA,

but by and large, we think that

elliptic curve is the most sound choice

we have for now.

Now if elliptic curve isn't an option,

and there's technical reasons
why it might not be,

at the very least use
a Diffie-Hellman prime

that's 2048 bits or longer.

If even that isn't an option,

you're using legacy systems
for some reason,

well, or Java yes, thanks,

if there's anyone there who works for Sun,

please, please tell them
to fix the crypto in Java!

applause

But if that's not an option,

if that's not an option,

the fallback is you can generate,

at least generate your own 1024-bit prime.

Mind you, there various tricks
that you have to make sure you do

when generating a prime,
it must be a safe prime,

but there are implementations
of doing this,

so it's not exactly free to generate
your own 1024-bit prime,

but it's inexpensive,

and if you have no other option,

at least so that this large
government adversary

has to spend a lot of precomputation,

a year perhaps, targeting
you individually,

and they can't just get this for free.

Alright, so, that is our talk for tonight,

we're saving a lot of time for questions,

thank you all very very much.

applause

Herald: Nadia. Nadia and Alex,
thank you very much.

We installed some microphones
here in the room,

so please queue up, but first,

signal angel, do we have
some questions from the net?

Signal Angel: Yes, we have a lot of questions.

First question is,

do you think it's possible that the NSA

uses quantum Shor factorisation

for 1024 or bigger keys already?

NH: I would believe it is much more likely

that they're using classical cryptanalysis

for 1024-bit keys than than they have

a quantum computer that
nobody has heard about.

Herald: And another one?

Signal Angel: Another one... Is it thinkable

that the NSA solved the P=NP problem

but keeps quiet?

laughter

AH: Probably not, but if they have,

yes, I think they'd want to
keep quiet about it.

NH: I hope they would tell us!

AH: I hope they would tell us too,

but I doubt it.

Herald: Okay, and over to
number 1, please.

Q: Two questions.

First, is it reasonable to think that,

is it possible they are attacking
individual RSA keys,

that they can fetch individual RSA keys

in about a week with custom hardware,

and two, NSA Suite B came out 2005

and they don't use Diffie-Hellman,

so NSA themselves, they told us in 2005,

"we won't use Diffie-Hellman",

so is it reasonable that,

when they changed the requirement

for top secret, we should follow?

AH: Well, to the first part
of your question,

about whether they're factoring RSA,

I think the answer for 1024,

is very likely, yes they are,

for high-value targets.

So if you're a major website at least

and you're using a 1024-bit RSA key,

well, it's long past time to change
to a higher strength.

NH: If the NSA has not factored
a 1024-bit key,

I'm going to be very disappointed,

I'm going to ask where
my tax dollars are going.

laughter, applause

And also I think actually,

the point of sort of watching

what the defensive side of the NSA

is advocating in terms of recommendations

is actually a wise thing to do,

because as far as we know,

at least the public recommendations

defensively should... I mean,

making recommendations for people

who are building systems that are
going to be handling classified data,

so they should be solid recommendations

as far as we know.

AH: What the NSA has told me

about those recommendations, by the way,

is that as long as you
follow them exactly,

you're going to be okay,

but if you deviate in any
small way whatsoever,

then they make no guarantees whatsoever.

So, think about what that might mean

in terms of your implementation

the next time you read through
those particular recommendations

that they make.

Herald: Okay. Then we hop over to
microphone 3, please.

Q: So, for the moment, is

elliptic-curve-based
Diffie-Hellman secure?

NH: I hope so.

AH: It doesn't suffer from
the same shape of attack

that we've described here.

As far as we know, there's not a way

to do this same kind of precomputation

for elliptic-curve Diffie-Hellman.

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

is, so, one of the reasons that

elliptic curve keys are so much shorter

than, say, finite-field
Diffie-Hellman or RSA

is because we have this
superpowerful index calculus

number field sieve-type algorithms

for factoring and for discrete log
over finite fields,

and those don't seem,

we don't actually have equivalents

of those algorithms for
properly generated elliptic curves.

So, that's why those key sizes are shorter

and that's why we think
they seem to be more secure.

Herald: Then we take another one
from microphone 3, please.

Q: Yes, you said that when doing
the precomputations

for commonly-used primes,

you can reduce the effort you have to put

in a single connection
to about 70 seconds.

How is that usable?

If my TLS handshake is delayed 70 seconds,

I already ran away.

AH: Ah! So we refer you to the paper

for the full answer to that,

but it turns out there's a bunch of tricks

that you can do to keep
a session handshake open

for at least 70 seconds.

So, this may not be what you want to do

to the connection, say, in a web browser

that's loading index.html,

but whichever one is loading, say,

the, I don't know, the 1-pixel
tracking image in the background,

that nobody sees,

which is also getting the same
session cookie,

that one you can hold open
for 70 seconds

without the user noticing.

So what we've been able to do

is show a variety of ways
that we can trick

browsers and other implementations

into holding the connection
open long enough.

Also, 70 seconds is just
what we were able to do

with a few weeks of hacking
around and optimisation,

we think that with
not that much more effort

we could get that number
down quite a bit more.

But 70 seconds we think
already is not so bad,

and there's plenty of ways
that we can exploit it.

NH: Proof of concept.

Herald: Okay. Do we have
something from the net?

Signal Angel: How long do you estimate the security

of RSA-DHE to sustain,

and do you have any idea if and when

there's any quantum encryption algorithms

that will soon be available to be used

by a broad public?

AH: Oh, quantum encryption algorithms.

NH: You should watch Dan
and Tanja's talk from yesterday.

AH: Yeah, last night was the time
to hear about that.

NH: The dangers of quantum cryptography.

I mean, the short answer is

that people who know
what they're talking about

have said we should start worrying now

because we may see quantum computers

within the next 15 years, maybe.

But it's really hard to speculate about

advances in physics that
may be pretty far off.

Herald: Do we have another one?

Signal angel: Sure. What's your
opinion on the NIST curves,

especially with the current rumours

about the curve parameters
having a backdoor?

NH: There are no known ways

that the curves could have been backdoored

with the given parameters.

AH: But if you don't trust them,

you know Dan Bernstein
has a curve you can use too.

NH: So...

applause

NH: Do you trust Dan,
or do you trust the NSA?

laughter

Herald: Over to 2, please.

Q: Some of the little bit
that you recommend,

you say Diffie-Hellman is worse
than RSA now,

so, does it mean I should switch back

to RSA, preferring it instead
of Diffie-Hellman?

AH: With equivalent key sizes,

equivalent sizes of your primes,

or your RSA modulus,

yes, we are saying that.

That in the 1024-bit case,

there's strong reasons that you should

distrust the very common repeated primes

for Diffie-Hellman.

But that's not the whole story.

Right, so for longer sizes of modulus,

larger strengths of crypto,

RSA is probably still okay.

But I think either way,

switching to elliptic curve
for key exchange

is probably the thing to do right now.

NH: I think the precise statement
that we can make

is, if you're comparing 1024-bit
Diffie-Hellman

to a 1024-bit RSA key,

that if you're using Diffie-Hellman

with the most commonly used parameters,

say, the Oakley group 2

that everybody on the Internet is using,

and you think it is likely that
a large government agency

has already done the
precomputation for that prime,

then breaking an individual
connection using that prime

with Diffie-Hellman key exchange

would be much, much, much less effort

than factoring a freshly generated
1024-bit RSA key that is unique to you.

Even if that 1024-bit RSA factorisation

is within range of the NSA,

it may not be worth their while

to actually factor your key.

Whereas breaking a
Diffie-Hellman key exchange,

they've already done the hard work

to break everybody on the Internet,

so, you're just one more fish.

That's the precise statement

that we can make about the security.

The real answer: use elliptic curves,

or, to use 2048-bit
Diffie-Hellman: probably fine.

Herald: And, over to number 1, please.

Q: How realistic is it to use, or to create

a new prime for every exchange

or at least every few exchanges?

NH: So, unfortunately, the properties

that you need for discrete log to be hard,

you need to have a safe prime

and you would hopefully like it
not to be backdoored,

generating safe primes is
still kind of effortful

on modern hardware,

I mean if you try to do it on your laptop

it will probably take like, I don't know,
a minute or something.

So, it's actually a lot of effort

to generate a new safe prime all the time.

Just use a larger safe prime
and you'll be better.

Herald: So we're running out of time,

but let's... with number 2.

Q: You said that elliptic
curve cryptography

is not susceptible to
this precomputation attack,

is that luck, or is it
engineered to be that way?

AH laughs

NH: ...luck?

AH: In part!

NH: I mean, a combination of both, but

so as far as we know, I mean, you can't do

precomputation with elliptic curves,

so, you know, sort of generically,

the best thing that you can say

is you can do a lot of precomputation

but you still have to do a lot of effort

for each individual value,

so you could do, you know, generically

if you want to break an elliptic curve

you could do like,
a square-root-of-n attack

against the key size,

you could do, say, n^2/3 precomputation

and then you would have n^1/3 online work

if that makes sense to you.

But you get less effort as far as we know.

Less benefit.

Herald: Sorry. We're going to finalise
then, with number 4.

Q: What do you think about blacklisting
these common primes,

just in the modern browsers?

Will this get rid of this issue?

AH: Just blacklisting the common primes,

well, if you blacklist the common primes,

if you blacklisted the common primes

when we first came up with this,

you'd immediately break
about 10% of websites

because there's not a good
fallback mechanism

if you don't like the prime you got

during key negotiation.

What the browsers are more likely to do

is to phase out this kind of
finite-field Diffie-Hellman entirely,

over the next larger number of years.

So first they're going to
start rejecting things

that use unusually weak primes,

that's what they're doing already today,

but I think in the long term

they're going to encourage the use
of elliptic curves as an alternative,

if you want forward secrecy,

elliptic curves will be the way to get it.

Herald: Nadia, Alex, once again,

thank you so much.

AH: Thank you.

applause

postroll music

subtitles created by c3subtitles.de
in the year 2016. Join, and help us!