< Return to Video

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

  • 0:00 - 0:10
    preroll music
  • 0:10 - 0:11
    Herald: I did some research,
  • 0:11 - 0:13
    and it was not, not easy
  • 0:13 - 0:16
    that Diffie-Hellman key exchange
  • 0:16 - 0:18
    is so much above my pay grade
  • 0:18 - 0:20
    therefore, I'm going to keep it simple.
  • 0:20 - 0:21
    Please welcome
  • 0:21 - 0:24
    we have Alex Halderman from
    the University of Michigan,
  • 0:24 - 0:29
    and Nadia Heninger from
    the University of Pennsylvania.
  • 0:29 - 0:33
    applause
  • 0:33 - 0:37
    AH: Thank you.
  • 0:37 - 0:39
    Thank you all so much.
  • 0:39 - 0:44
    It's wonderful to be back again in 32C3.
  • 0:44 - 0:46
    I'm Alex Halderman from
    the University of Michigan,
  • 0:46 - 0:49
    here again this year with,
  • 0:49 - 0:51
    with many of my students from my group
  • 0:51 - 0:54
    here in the audience also speaking.
  • 0:54 - 0:57
    We study security in the real world.
  • 0:57 - 1:01
    So tonight, we have
    a very special story to tell you
  • 1:01 - 1:04
    that I'm very proud to be telling
  • 1:04 - 1:06
    along with my colleague Nadia Heninger.
  • 1:06 - 1:08
    We're going to be talking
  • 1:08 - 1:11
    about discrete log, Diffie-Hellman
  • 1:11 - 1:14
    and some of the, um,
  • 1:14 - 1:16
    the research that we've done
  • 1:16 - 1:17
    over the past year,
  • 1:17 - 1:20
    try to understand how the NSA
  • 1:20 - 1:22
    may be breaking so much of the crypto
  • 1:22 - 1:24
    that we know they're breaking.
  • 1:24 - 1:26
    Why do we...? So this work is
  • 1:26 - 1:29
    joint work with a number of co-authors,
  • 1:29 - 1:31
    with 12 other co-authors,
  • 1:31 - 1:34
    3 of them are in this room right now,
  • 1:34 - 1:35
    and I'd ask to stand up
  • 1:35 - 1:36
    but they said they didn't want to
  • 1:36 - 1:38
    so please, a quick round of applause
  • 1:38 - 1:40
    for my co-authors as well.
  • 1:40 - 1:48
    applause
  • 1:48 - 1:50
    So, thank you.
  • 1:50 - 1:51
    So in this very room,
  • 1:51 - 1:54
    a year ago at 31C3,
  • 1:54 - 1:56
    Jacob Appelbaum and Laura Poitras
  • 1:56 - 1:59
    gave a talk, "Reconstructing Narratives",
  • 1:59 - 2:03
    in which they announced some new results
  • 2:03 - 2:05
    from the Snowden archives.
  • 2:05 - 2:09
    They were able to tell us how the NSA,
  • 2:09 - 2:12
    that the NSA was breaking cryptography
  • 2:12 - 2:15
    used in widespread online communication.
  • 2:15 - 2:18
    And, they later published
  • 2:18 - 2:21
    an article in der Spiegel,
  • 2:21 - 2:24
    in which the article included documents
  • 2:24 - 2:28
    that showed indeed the scope of NSA
  • 2:28 - 2:30
    breaking widely used encryption
  • 2:30 - 2:32
    was significant.
  • 2:32 - 2:34
    That NSA is breaking,
  • 2:34 - 2:36
    maybe not all crypto,
  • 2:36 - 2:38
    but they're able to break
    widely used crypto
  • 2:38 - 2:40
    from many of the different kinds
  • 2:40 - 2:45
    of services and protocols we care about.
  • 2:45 - 2:46
    What the leaks didn't answer
  • 2:46 - 2:49
    is how NSA is breaking this cryptography
  • 2:49 - 2:51
    and to a technologist,
  • 2:51 - 2:54
    well, if we don't know
    how they're breaking it,
  • 2:54 - 2:57
    what can we do to stop it?
  • 2:57 - 3:00
    So, Nadia and I and our co-authors set out
  • 3:00 - 3:01
    earlier this year
  • 3:01 - 3:04
    to try to, through our research,
  • 3:04 - 3:06
    start answering those questions.
  • 3:06 - 3:08
    How is NSA likely to be breaking
  • 3:08 - 3:10
    likely used cryptography,
  • 3:10 - 3:13
    and what can we and other researchers do
  • 3:13 - 3:15
    to stop government from being able
  • 3:15 - 3:18
    to attack the crypto
    that all of us depend on?
  • 3:18 - 3:21
    So, so...
    applause
  • 3:21 - 3:24
    Let's tell the story.
  • 3:24 - 3:28
    Wait until you see how it ends!
  • 3:28 - 3:30
    So if I were setting out as the attacker
  • 3:30 - 3:32
    to break widely used crypto,
  • 3:32 - 3:36
    well, there's a few different ways
    that I could do it.
  • 3:36 - 3:38
    One branch of the decision tree here
  • 3:38 - 3:40
    is to attacking the implementations
  • 3:40 - 3:42
    right, either finding vulnerabilities
  • 3:42 - 3:44
    or introducing backdoors,
  • 3:44 - 3:47
    we've all been witnessing over the past
  • 3:47 - 3:51
    week or so with Juniper and their systems
  • 3:51 - 3:54
    being compromised.
  • 3:54 - 3:57
    On the other hand,
    there's another prong you could take.
  • 3:57 - 4:00
    You could try to attack the crypto
    algorithms themselves,
  • 4:00 - 4:02
    the underlying crypto.
  • 4:02 - 4:03
    And the difference is,
  • 4:03 - 4:04
    if you're attacking implementations,
  • 4:04 - 4:06
    you have to make a big investment
  • 4:06 - 4:09
    in every hardware device
    and piece of software
  • 4:09 - 4:11
    that you're trying to compromise.
  • 4:11 - 4:13
    If you're attacking the underlying crypto,
  • 4:13 - 4:17
    you have just one, a one-stop shop
  • 4:17 - 4:21
    to gain access to,
    potentially a very wide swath
  • 4:21 - 4:23
    of all the crypto in use.
  • 4:23 - 4:25
    So a small number of algorithms
  • 4:25 - 4:28
    predominate for both
    symmetric cryptography,
  • 4:28 - 4:31
    things like AES and RC4,
  • 4:31 - 4:33
    but those particular algorithms anyway,
  • 4:33 - 4:35
    most cryptographers seem to think
  • 4:35 - 4:36
    that breaking them,
  • 4:36 - 4:37
    at least in the general case,
  • 4:37 - 4:39
    is pretty hard right now.
  • 4:39 - 4:41
    Instead though, we also have
  • 4:41 - 4:44
    a very small number of
    public key crypto algorithms
  • 4:44 - 4:47
    that are also in use very widely
  • 4:47 - 4:50
    for most or all of the protocols
    and services we care about.
  • 4:50 - 4:53
    Things like RSA and Diffie-Hellman.
  • 4:53 - 4:56
    And here be dragons, as they say,
  • 4:56 - 5:00
    this is the cryptography that we
    and many other cryptographers
  • 5:00 - 5:03
    think is most likely to be targeted.
  • 5:03 - 5:05
    So, I'll hand it off to Nadia
  • 5:05 - 5:08
    to talk about breaking public key.
  • 5:08 - 5:15
    applause
  • 5:15 - 5:17
    NH: So, in order to understand
  • 5:17 - 5:19
    a little bit about
    how cryptanalysis works,
  • 5:19 - 5:21
    I'm going to go all the way back
  • 5:21 - 5:23
    to the very beginning of
    public key cryptography
  • 5:23 - 5:25
    from the 70s,
  • 5:25 - 5:29
    and I'll start by explaining
    a little bit about RSA.
  • 5:29 - 5:32
    This is Rivest, Shamir, and Adleman
    up on the screen here,
  • 5:32 - 5:34
    from the 70s, you can tell.
  • 5:34 - 5:36
    And this is sort of the simple example,
  • 5:36 - 5:37
    and then we'll talk a little bit more
  • 5:37 - 5:41
    about the actual
    Diffie-Hellman-based cryptanalysis
  • 5:41 - 5:43
    that we're actually talking about.
  • 5:43 - 5:47
    So, this the first public-key
    crypto algorithm
  • 5:47 - 5:48
    that was ever published,
  • 5:48 - 5:50
    and it is still the most widely used
  • 5:50 - 5:53
    cryptography, public key cryptography
    algorithm out there.
  • 5:53 - 5:55
    That shows you, I guess something
    about the naturalness of ideas,
  • 5:55 - 5:57
    or maybe the lack of progress
  • 5:57 - 5:59
    that we've had in the past 40 years.
  • 5:59 - 6:04
    So, here's sort of the textbook version
    of RSA encryption,
  • 6:04 - 6:05
    what we really care about is that...
  • 6:05 - 6:07
    So, Alice and Bob, they want
  • 6:07 - 6:09
    to bootstrap communication over
  • 6:09 - 6:10
    an untrusted channel,
  • 6:10 - 6:12
    so there's some eavesdropper
    in between them
  • 6:12 - 6:13
    who's intercepting their messages.
  • 6:13 - 6:16
    And, in order to get around this,
  • 6:16 - 6:18
    they need to somehow figure out
  • 6:18 - 6:21
    how to share a key in order to
  • 6:21 - 6:23
    actually encrypt their communications.
  • 6:23 - 6:25
    And the way that RSA accomplishes this,
  • 6:25 - 6:30
    is, Bob here on the right has a public key
  • 6:30 - 6:33
    which in RSA is e modulus N
  • 6:33 - 6:35
    which is the product of
    two large prime factors,
  • 6:35 - 6:38
    and he sends this over to Alice,
  • 6:38 - 6:39
    and Alice uses Bob's public key
  • 6:39 - 6:42
    to encrypt a message, like a session key,
  • 6:42 - 6:43
    and send it back to Bob,
  • 6:43 - 6:45
    and then Bob can decrypt the message,
  • 6:45 - 6:46
    get the session key,
  • 6:46 - 6:48
    and they can communicate using
  • 6:48 - 6:50
    some other symmetric cipher.
  • 6:50 - 6:54
    So, this is the big picture
    of RSA encryption.
  • 6:54 - 6:55
    The reason that we think
  • 6:55 - 6:58
    that RSA is secure is because
  • 6:58 - 7:03
    the best way that we know how to break
    an RSA public key
  • 7:03 - 7:05
    is to factor the modulus,
  • 7:05 - 7:08
    and as far as we know,
    factoring is not very easy.
  • 7:08 - 7:11
    So, in particular, factoring is
  • 7:11 - 7:12
    what we hope is something like
  • 7:12 - 7:13
    a one-way function,
  • 7:13 - 7:15
    multiplication is easy,
  • 7:15 - 7:17
    factoring the number into
    two pieces again is hard,
  • 7:17 - 7:18
    in some sense.
  • 7:18 - 7:20
    And the best algorithm that we have
  • 7:20 - 7:21
    in the general case, of, say
  • 7:21 - 7:24
    an RSA modulus that's well-generated,
  • 7:24 - 7:27
    is called the number field sieve.
  • 7:27 - 7:29
    So here is the...
  • 7:29 - 7:31
    this is as bad as technical
    as I'm going to get,
  • 7:31 - 7:33
    and I'm waving my hands vigorously here,
  • 7:33 - 7:35
    but here's something along the lines of
  • 7:35 - 7:36
    what the number field sieve algorithm
  • 7:36 - 7:38
    actually looks like,
  • 7:38 - 7:40
    so it's a multi-stage algorithm,
  • 7:40 - 7:41
    it's rather complex,
  • 7:41 - 7:43
    some stages parallelise very well,
  • 7:43 - 7:45
    embarrassingly well,
  • 7:45 - 7:48
    other stages parallelise somewhat
    less well,
  • 7:48 - 7:51
    and so we've got these multiple stages
    that we go through,
  • 7:51 - 7:53
    and at the end of the algorithm,
  • 7:53 - 7:55
    we discover, we hope, a prime factor
  • 7:55 - 8:00
    of the number that we're trying to factor.
  • 8:00 - 8:02
    So, how long does it take to factor?
  • 8:02 - 8:03
    Here's one answer:
  • 8:03 - 8:04
    if you ask a number theorist, this is
  • 8:04 - 8:06
    the answer that they all give you,
  • 8:06 - 8:07
    they all go through the optimisation,
  • 8:07 - 8:10
    and they will tell you the answer is
  • 8:10 - 8:12
    a sub-exponential function in the size
  • 8:12 - 8:13
    of the number that we're trying to factor.
  • 8:13 - 8:15
    That I think is not the answer
  • 8:15 - 8:17
    that you guys are looking for.
  • 8:17 - 8:20
    So, here's a slightly more
    concrete answer.
  • 8:20 - 8:22
    So, how long does it take to factor
  • 8:22 - 8:23
    different sizes of keys?
  • 8:23 - 8:25
    So, for 512-bit RSA,
  • 8:25 - 8:30
    the first 512-bit RSA modulus
    was factored in 1999
  • 8:30 - 8:31
    by a group of academics,
  • 8:31 - 8:34
    that took them 6 months
    and a few supercomputers,
  • 8:34 - 8:37
    now you can rent supercomputers
    by the hour.
  • 8:37 - 8:38
    So what does that do?
  • 8:38 - 8:40
    Well, some students of mine
  • 8:40 - 8:44
    actually were able to factor
    a 512-bit RSA key
  • 8:44 - 8:49
    for 4 hours and 75 dollars on Amazon EC2.
  • 8:49 - 8:51
    If you would like to do this too...
  • 8:51 - 8:54
    applause
  • 8:54 - 8:57
    So, you can also do this too,
  • 8:57 - 9:00
    code is online, right here, download it,
  • 9:00 - 9:03
    send us bug reports, etc.
  • 9:03 - 9:05
    So, as we go up in key sizes,
  • 9:05 - 9:08
    768-bit RSA modulus,
  • 9:08 - 9:10
    estimate, current estimate is
  • 9:10 - 9:12
    less than 1000 core-years,
  • 9:12 - 9:15
    and for sort of reasonable-size
    academic clusters,
  • 9:15 - 9:19
    that should take less than
    a calendar year to finish, now.
  • 9:19 - 9:23
    That was,
    the first 768-bit RSA factorisation
  • 9:23 - 9:25
    was done in public in 2009.
  • 9:25 - 9:28
    So, that gives you some idea
    of sort of the progress.
  • 9:28 - 9:31
    For 1024-bit RSA, nobody has factored
  • 9:31 - 9:33
    a key of that size in public,
  • 9:33 - 9:34
    the estimate is probably,
  • 9:34 - 9:36
    it's about a million core-years,
  • 9:36 - 9:38
    which is certainly within range
  • 9:38 - 9:41
    for a large government,
  • 9:41 - 9:43
    so it is against better recommendations
  • 9:43 - 9:48
    to use a 1024-bit RSA key size,
    at this point.
  • 9:48 - 9:49
    Current recommendation is to use
  • 9:49 - 9:51
    a 2048-bit RSA modulus,
  • 9:51 - 9:53
    with current algorithms,
  • 9:53 - 9:54
    nobody should ever be able to factor
  • 9:54 - 9:55
    something at this size,
  • 9:55 - 9:58
    without some kind of major improvement.
  • 9:58 - 10:02
    So, there's the big picture for you.
  • 10:02 - 10:05
    Now move on to Diffie-Hellman.
  • 10:05 - 10:09
    So, the paper that introduced
    Diffie-Hellman
  • 10:09 - 10:11
    was called "New Directions
    in Cryptography",
  • 10:11 - 10:14
    it's one of the seminal papers
    of the 20th century,
  • 10:14 - 10:16
    how many of you have read this paper?
  • 10:16 - 10:18
    You should all go read it right now,
  • 10:18 - 10:21
    I mean not right now, maybe after I talk.
  • 10:21 - 10:23
    The first sentence of this paper,
  • 10:23 - 10:25
    written in 1976,
  • 10:25 - 10:28
    is "We stand today on the brink
    of a revolution in cryptography".
  • 10:28 - 10:30
    This is one of the best opening sentences
  • 10:30 - 10:32
    of an academic paper I've ever read,
  • 10:32 - 10:36
    and they were 100% right
    about everything they put in the paper.
  • 10:36 - 10:38
    They laid out the entire foundations
  • 10:38 - 10:41
    of cryptographic research
    for a couple decades,
  • 10:41 - 10:43
    and to boot they came up with
  • 10:43 - 10:46
    the first public key exchange,
  • 10:46 - 10:48
    that is still one of the commonly used
  • 10:48 - 10:51
    public key methods we
  • 10:51 - 10:52
    have on the Internet.
  • 10:52 - 10:56
    So, all that in one paper.
  • 10:56 - 10:59
    So, the way that
    textbook Diffie-Hellman works,
  • 10:59 - 11:01
    is, you've got a couple of parameters,
  • 11:01 - 11:04
    you've got a prime p,
  • 11:04 - 11:09
    and some element g less than p,
  • 11:09 - 11:11
    you can think,
    for concreteness, g is 2.
  • 11:11 - 11:13
    It's a good number.
  • 11:13 - 11:16
    And p is some very large prime,
  • 11:16 - 11:19
    say 1024, 2048-bit prime.
  • 11:19 - 11:21
    And so Alice and Bob,
  • 11:21 - 11:22
    same as our previous scenario,
  • 11:22 - 11:23
    they want to bootstrap communication
  • 11:23 - 11:26
    in the presence of
    an untrusted eavesdropper.
  • 11:26 - 11:27
    So what they're going to do,
  • 11:27 - 11:29
    Alice will generate some secret value a,
  • 11:29 - 11:32
    and she will compute g^a mod p,
  • 11:32 - 11:34
    and send it over to Bob,
  • 11:34 - 11:37
    and Bob will compute some secret value b,
  • 11:37 - 11:38
    and compute g^b mod p,
  • 11:38 - 11:40
    and send it over to Alice,
  • 11:40 - 11:44
    the eavesdropper sees the values
    g^a and g^b,
  • 11:44 - 11:46
    can't derive anything useful from those,
  • 11:46 - 11:48
    but Alice and Bob can individually
  • 11:48 - 11:49
    take their secrets
  • 11:49 - 11:52
    and derive the values g^ab mod p,
  • 11:52 - 11:54
    both the same values.
  • 11:54 - 11:56
    And that becomes a shared secret,
  • 11:56 - 11:58
    which they can then use as a session key,
  • 11:58 - 12:00
    and, you know, switch to AES
  • 12:00 - 12:03
    and start symmetrically
    encrypting their data.
  • 12:03 - 12:05
    So, that's Diffie-Hellman key exchange.
  • 12:05 - 12:06
    Used all over the Internet,
  • 12:06 - 12:09
    one of the commonly used things possible.
  • 12:09 - 12:13
    So, one of the reasons that people
  • 12:13 - 12:15
    have been advocating
    Diffie-Hellman key exchange recently
  • 12:15 - 12:17
    over, say, RSA,
  • 12:17 - 12:20
    is because it can be, it can provide
  • 12:20 - 12:22
    the property of perfect forward secrecy.
  • 12:22 - 12:24
    So assuming that Alice and Bob
  • 12:24 - 12:27
    generate fresh random
    secret values a and b
  • 12:27 - 12:29
    for every single connection,
  • 12:29 - 12:33
    then if, say, some large government agency
  • 12:33 - 12:35
    is collecting all of their communications
  • 12:35 - 12:37
    and later tries to hack into Alice or Bob,
  • 12:37 - 12:39
    or break one of their keys,
  • 12:39 - 12:41
    in order to decrypt their communication,
  • 12:41 - 12:44
    they can't hack into Alice or
    Bob's computer later,
  • 12:44 - 12:46
    and then discover the key
  • 12:46 - 12:48
    that Alice and Bob used
  • 12:48 - 12:51
    to generate all the conversations
    that they had,
  • 12:51 - 12:54
    because Alice and Bob have
    already forgotten
  • 12:54 - 12:55
    the keys that they used.
  • 12:55 - 12:57
    So, as long as Alice and Bob
  • 12:57 - 13:00
    are generating fresh random
    values every time,
  • 13:00 - 13:01
    those values should reveal nothing
  • 13:01 - 13:05
    about past or future communications.
  • 13:05 - 13:07
    So, that's perfect forward secrecy.
  • 13:07 - 13:09
    And, a lot of people have,
  • 13:09 - 13:11
    who really know what
    they're talking about,
  • 13:11 - 13:13
    including, unfortunately, me,
  • 13:13 - 13:15
    on this stage a couple years ago,
  • 13:15 - 13:20
    have said, "you guys should always use
    Diffie-Hellman over RSA key exchange
  • 13:20 - 13:23
    because of this property of
    perfect forward secrecy".
  • 13:23 - 13:25
    So here's a selection of quotes
  • 13:25 - 13:26
    that I found on the Internet,
  • 13:26 - 13:28
    just from googling
    "perfect forward secrecy"
  • 13:28 - 13:29
    and "Diffie-Hellman key exchange",
  • 13:29 - 13:31
    and you find people saying that
  • 13:31 - 13:33
    this provides better security,
  • 13:33 - 13:36
    the NSA can decrypt nothing,
  • 13:36 - 13:41
    1024-bit Diffie-Hellman is arguably
    better than 1024-bit RSA,
  • 13:41 - 13:46
    and then 1024-bit Diffie-Hellman
    is better than any key size for RSA.
  • 13:46 - 13:48
    This is a selection of friends
  • 13:48 - 13:49
    and people I respect,
  • 13:49 - 13:52
    and some also, also some
    random people on Stack Overflow,
  • 13:52 - 13:54
    which is where...
  • 13:54 - 13:55
    laughter
  • 13:55 - 13:56
    where we know everybody's actually
  • 13:56 - 13:58
    getting their recommendations from.
  • 13:58 - 14:01
    So, there's been wide-scale advocacy
  • 14:01 - 14:03
    of perfect forward secrecy as
  • 14:03 - 14:06
    like, the reason that you should
    use Diffie-Hellman.
  • 14:06 - 14:09
    It will protect you against the NSA.
  • 14:09 - 14:13
    I'm sorry. We were wrong.
  • 14:13 - 14:14
    And, why were we wrong?
  • 14:14 - 14:15
    I'm going to tell little bit more
  • 14:15 - 14:17
    about what the cryptanalysis looks like
  • 14:17 - 14:18
    for Diffie-Hellman.
  • 14:18 - 14:22
    So, the underlying problem
    that we hope is hard
  • 14:22 - 14:23
    for the security of Diffie-Hellman
  • 14:23 - 14:24
    is called discrete log,
  • 14:24 - 14:27
    it is exactly sort of the problem of
  • 14:27 - 14:30
    given one of the key exchange values g^a mod p
  • 14:30 - 14:33
    compute, say, Alice's secret a.
  • 14:33 - 14:34
    This would allow the attacker
  • 14:34 - 14:36
    to compute the shared secret
  • 14:36 - 14:39
    in the same way that Alice did.
  • 14:39 - 14:43
    And, sort of similar to
    factoring and multiplication,
  • 14:43 - 14:45
    discrete log, we think it's much harder
  • 14:45 - 14:47
    than modular exponentiation,
  • 14:47 - 14:48
    the computation that actually
  • 14:48 - 14:51
    gives you the value g^a mod p.
  • 14:51 - 14:53
    And the best algorithm that we have
  • 14:53 - 14:55
    is called the number field sieve.
  • 14:55 - 14:58
    So, there's a lot of parallels going on here.
  • 14:58 - 14:59
    So what does the number field sieve
  • 14:59 - 15:01
    for discrete log look like?
  • 15:01 - 15:05
    Hopefully this diagram is somewhat
    familiar to you by now,
  • 15:05 - 15:07
    it's a multi-stage algorithm,
  • 15:07 - 15:10
    it has many of the same
    stages as factoring,
  • 15:10 - 15:13
    you can sort of line them up in parallel,
  • 15:13 - 15:15
    the last bit looks a little bit different,
  • 15:15 - 15:17
    but we can sort of ignore that
    for the moment.
  • 15:17 - 15:20
    Okay. So, we have some pictures
  • 15:20 - 15:23
    of what the number field sieve looks like.
  • 15:23 - 15:25
    How long does it take?
  • 15:25 - 15:29
    Answer number 1:
    The same answer as factoring.
  • 15:29 - 15:31
    In case you didn't remember,
    here it is again.
  • 15:31 - 15:33
    This is kind of why everybody
    has been saying
  • 15:33 - 15:35
    "Okay, the security of, you know,
  • 15:35 - 15:37
    1024-bit Diffie-Hellman key exchange
  • 15:37 - 15:39
    is about the same as the security of
  • 15:39 - 15:41
    a 1024-bit RSA key."
  • 15:41 - 15:45
    It's because we have the same
    complicated formula that tells us
  • 15:45 - 15:48
    how hard it is to break.
  • 15:48 - 15:50
    The sort of more subtle answer for...
  • 15:50 - 15:52
    or, not more subtle,
    but the more practical answer
  • 15:52 - 15:53
    for, how secure is it,
  • 15:53 - 15:56
    is, we can say, well, how long do we think
  • 15:56 - 15:57
    it will take to actually compute
  • 15:57 - 16:00
    a discrete log for
    commonly used key sizes,
  • 16:00 - 16:01
    and the answer is,
  • 16:01 - 16:05
    slightly longer than factoring an
    RSA key of equivalent size,
  • 16:05 - 16:09
    but, not so much longer than an RSA key.
  • 16:09 - 16:12
    And, the minimum recommended key size
  • 16:12 - 16:15
    today is 2048 bits.
  • 16:15 - 16:18
    Okay, so, 2048-bit Diffie-Hellman,
  • 16:18 - 16:22
    we're good. Great! We can all go home.
  • 16:22 - 16:24
    Okay. However, okay,
  • 16:24 - 16:26
    what if you want to break many connections
  • 16:26 - 16:29
    that use the same public parameter p?
  • 16:29 - 16:31
    Do you have to go through
  • 16:31 - 16:34
    this whole computation,
  • 16:34 - 16:35
    every single, for every single connection
  • 16:35 - 16:37
    that you want to break?
  • 16:37 - 16:41
    That was kind of the justification
  • 16:41 - 16:43
    for perfect forward secrecy,
  • 16:43 - 16:44
    that every single connection
  • 16:44 - 16:46
    should be as hard as factoring an RSA key
  • 16:46 - 16:48
    of the equivalent size.
  • 16:48 - 16:50
    Except that's not quite the case.
  • 16:50 - 16:52
    Because if you look at where
  • 16:52 - 16:54
    the actual target that
    we're trying to compute
  • 16:54 - 16:57
    appears in this plot,
  • 16:57 - 16:59
    it's only at the very last stage.
  • 16:59 - 17:00
    So all of this only depends
  • 17:00 - 17:02
    on the prime p.
  • 17:02 - 17:06
    So we can actually divide up
    the algorithm in two pieces:
  • 17:06 - 17:10
    A few stages that depend only
    on the prime p that we're using,
  • 17:10 - 17:12
    and then the final computation
  • 17:12 - 17:14
    that takes the output of this
    first precomputation stage,
  • 17:14 - 17:16
    and that's the only stage
  • 17:16 - 17:17
    that actually matters,
  • 17:17 - 17:19
    that actually depends on the target
  • 17:19 - 17:23
    of our discrete log computation.
  • 17:23 - 17:27
    So, we're in trouble.
  • 17:27 - 17:30
    In particular, that means that
  • 17:30 - 17:33
    if many connections are using
    this same prime p,
  • 17:33 - 17:36
    you can do the precomputation once,
  • 17:36 - 17:37
    spend a huge amount of effort,
  • 17:37 - 17:39
    and then the actual effort required
  • 17:39 - 17:43
    to break individual connections
    using those primes
  • 17:43 - 17:46
    is much, much smaller.
  • 17:46 - 17:48
    So here's our current estimates,
  • 17:48 - 17:50
    these are actually somewhat new
    from our paper,
  • 17:50 - 17:54
    of how long the individual log stage
    takes in practice,
  • 17:54 - 17:56
    if you push the primer as far as you can
  • 17:56 - 17:58
    to make this as fast as possible.
  • 17:58 - 17:59
    And the answer is basically,
  • 17:59 - 18:02
    if you're worried about a government,
  • 18:02 - 18:04
    you better start worrying
  • 18:04 - 18:09
    for reasonable key sizes
    that people are using.
  • 18:09 - 18:11
    See, so I'll let Alex continue
  • 18:11 - 18:15
    with the next part of our talk.
  • 18:15 - 18:22
    applause
  • 18:22 - 18:25
    So this fact that Nadia just told us
  • 18:25 - 18:27
    about Diffie-Hellman
  • 18:27 - 18:29
    and the number field sieve,
  • 18:29 - 18:34
    this was something that the
    mathematical crypto people knew about,
  • 18:34 - 18:36
    but most of us who did system security,
  • 18:36 - 18:38
    people like me,
  • 18:38 - 18:40
    didn't ever get the memo.
  • 18:40 - 18:44
    So, it's, I'm here in part to apologise
  • 18:44 - 18:45
    to everyone I've taught
  • 18:45 - 18:48
    about Diffie-Hellman and cryptanalysis
  • 18:48 - 18:50
    who didn't get to hear about this,
  • 18:50 - 18:51
    as we were talking about
  • 18:51 - 18:52
    perfect forward secrecy.
  • 18:52 - 18:55
    Right, this fact about the cryptanalysis
  • 18:55 - 18:57
    and how well it can apply in exactly
  • 18:57 - 18:59
    the scenario that we're worried about,
  • 18:59 - 19:02
    this kind of situation
    involving mass surveillance,
  • 19:02 - 19:05
    was news to many of those.
  • 19:05 - 19:06
    But now that we have that fact,
  • 19:06 - 19:08
    how can we exploit it,
  • 19:08 - 19:10
    to try to break Diffie-Hellman,
  • 19:10 - 19:12
    in scenarios that we all care about?
  • 19:12 - 19:13
    And we're going to talk about
  • 19:13 - 19:16
    two scenarios in the talk today.
  • 19:16 - 19:19
    The first one applies to HTTPS,
  • 19:19 - 19:22
    to encrypted web connections,
  • 19:22 - 19:25
    and it applies not only
    to government agencies,
  • 19:25 - 19:28
    but also just to normal
    everyday attackers,
  • 19:28 - 19:29
    with maybe the same resources
  • 19:29 - 19:31
    that you or I have.
  • 19:31 - 19:35
    Right, this is a down-to-earth
    kind of attack on HTTPS,
  • 19:35 - 19:38
    and we call it Logjam.
  • 19:38 - 19:40
    Logjam allows us to break
  • 19:40 - 19:42
    the HTTPS connections
  • 19:42 - 19:44
    to many, many popular websites
  • 19:44 - 19:46
    in modern browsers,
  • 19:46 - 19:49
    by fooling those browsers into using
  • 19:49 - 19:53
    1990s-era backdoored crypto.
  • 19:53 - 19:56
    So where does this backdoored
    crypto come from?
  • 19:56 - 19:58
    This is from the first crypto wars,
  • 19:58 - 19:59
    back in the 90s,
  • 19:59 - 20:01
    when my country, the US,
  • 20:01 - 20:04
    had restrictions on what kind and strength
  • 20:04 - 20:07
    of cryptography could be exported,
  • 20:07 - 20:09
    and used by people abroad.
  • 20:09 - 20:11
    So US companies were prohibited
  • 20:11 - 20:13
    from exporting products that contained
  • 20:13 - 20:16
    cryptography that had greater
    than a certain strength.
  • 20:16 - 20:18
    For RSA, that was that the key size
  • 20:18 - 20:21
    had to be less than or equal to 512 bits,
  • 20:21 - 20:23
    and for Diffie-Hellman it was that
  • 20:23 - 20:27
    basically the prime had to be
    512 bits or less.
  • 20:27 - 20:29
    So back in the 90s,
  • 20:29 - 20:30
    these were constants,
  • 20:30 - 20:31
    these were strengths of crypto
  • 20:31 - 20:34
    that were chosen presumably because
  • 20:34 - 20:38
    they were easy for NSA to break.
  • 20:38 - 20:40
    So, if you were an American company
  • 20:40 - 20:42
    making products, like let's say
  • 20:42 - 20:45
    Netscape Navigator, the web browser
  • 20:45 - 20:51
    that initiated the first SSL protocol,
  • 20:51 - 20:53
    you needed some way to be able
  • 20:53 - 20:55
    to communicate with,
  • 20:55 - 20:57
    from servers in the US,
  • 20:57 - 20:59
    to clients, including your own browser,
  • 20:59 - 21:01
    that you would ship to people abroad,
  • 21:01 - 21:03
    say, here in Germany.
  • 21:03 - 21:05
    And so they came up with a way
  • 21:05 - 21:11
    to use, to have HTTPS automatically select
  • 21:11 - 21:13
    the appropriate key strength
  • 21:13 - 21:14
    depending on whether the browser
  • 21:14 - 21:17
    was able to support
    the full-strength cryptography,
  • 21:17 - 21:19
    or the weakened version
  • 21:19 - 21:21
    for deployment abroad.
  • 21:21 - 21:22
    And the way that they did that
  • 21:22 - 21:23
    was something called
  • 21:23 - 21:26
    export-grade cipher suites.
  • 21:26 - 21:27
    So when your browser,
  • 21:27 - 21:29
    whenever it starts a TLS connection
  • 21:29 - 21:31
    for an HTTPS URL,
  • 21:31 - 21:33
    one of the first thing that it does
  • 21:33 - 21:36
    is, the browser will send to the server
  • 21:36 - 21:37
    a list of the kinds of cryptography
  • 21:37 - 21:39
    that it can speak,
  • 21:39 - 21:41
    these are called cipher suites,
  • 21:41 - 21:44
    and then the server selects one of those,
  • 21:44 - 21:46
    that is compatible with
    whatever cryptography
  • 21:46 - 21:48
    the server has available,
  • 21:48 - 21:50
    and then that negotiated cipher suite
  • 21:50 - 21:54
    is what's used for the connection.
  • 21:54 - 21:55
    Now the way that they supported
  • 21:55 - 21:58
    the 90s-era backdoor crypto
  • 21:58 - 22:01
    was by having browsers shipped abroad
  • 22:01 - 22:03
    from the United States that could only
  • 22:03 - 22:06
    speak a certain subset
    of crypto algorithms,
  • 22:06 - 22:08
    that were limited in strength
  • 22:08 - 22:10
    to 512 bits or less,
  • 22:10 - 22:12
    those were the export-grade cipher suites
  • 22:12 - 22:14
    with the names you see here.
  • 22:14 - 22:19
    Now, even though no
    browser has been shipped
  • 22:19 - 22:22
    that is limited to only these suites,
  • 22:22 - 22:24
    since probably 2000-sometime,
  • 22:24 - 22:28
    when the US relaxed
    its export regulations,
  • 22:28 - 22:29
    there wasn't just any one day
  • 22:29 - 22:33
    when all of those old browsers
  • 22:33 - 22:35
    from before that era went away.
  • 22:35 - 22:39
    So, servers, even now, many servers
  • 22:39 - 22:43
    will still accept and speak
    these weakened cipher suites,
  • 22:43 - 22:45
    if that's all the browser has available.
  • 22:45 - 22:48
    Like if you're running an e-commerce site,
  • 22:48 - 22:50
    right, I'm sure you still want to be able
  • 22:50 - 22:51
    to speak to any customers
  • 22:51 - 22:55
    who have 1998-era
    Netspace Navigator involved,
  • 22:55 - 22:57
    otherwise you'd lose some sales, right?
  • 22:57 - 22:59
    So there was no reason to turn them off,
  • 22:59 - 23:02
    because no modern browser any more,
  • 23:02 - 23:04
    now that those restrictions are lifted,
  • 23:04 - 23:07
    would choose these weakened suites.
  • 23:07 - 23:09
    Well, that's what we thought, anyway.
  • 23:09 - 23:13
    So, in, over this past year,
  • 23:13 - 23:16
    there were two attacks that exploited
  • 23:16 - 23:17
    these weakened cipher suites,
  • 23:17 - 23:21
    that found ways to convince
    modern browsers
  • 23:21 - 23:24
    to speak them instead of
    full-strength cryptography.
  • 23:24 - 23:26
    The first was the FREAK attack,
  • 23:26 - 23:29
    which was revealed in early 2015
  • 23:29 - 23:32
    by a separate group of authors,
  • 23:32 - 23:35
    and the FREAK attack was
    an implementation flaw
  • 23:35 - 23:39
    in many modern browsers.
  • 23:39 - 23:40
    In order to exploit it,
  • 23:40 - 23:42
    all you need to do is to be able
  • 23:42 - 23:44
    to relatively inexpensively
  • 23:44 - 23:48
    factor a 512-bit RSA key.
  • 23:48 - 23:50
    And, as Nadia has told you,
  • 23:50 - 23:53
    this is now a matter of maybe 4 hours,
  • 23:53 - 23:55
    maybe 75 dollars, something like that,
  • 23:55 - 23:57
    and if you did that, you'd able to break
  • 23:57 - 24:00
    all the connections coming into
  • 24:00 - 24:02
    a weak server for a long period of time,
  • 24:02 - 24:06
    to a server that still spoke
    these cipher suites.
  • 24:06 - 24:08
    So this affected most modern browsers,
  • 24:08 - 24:14
    and just shy of 10% of Alexa
    top million sites that speak HTTPS.
  • 24:14 - 24:17
    Now that left the Diffie-Hellman
  • 24:17 - 24:19
    export-grade cipher suites,
  • 24:19 - 24:21
    which were not affected by FREAK.
  • 24:21 - 24:26
    But we came up with a paper
    in May of this year,
  • 24:26 - 24:28
    that showed a separate attack,
  • 24:28 - 24:29
    the Logjam attack,
  • 24:29 - 24:32
    which is a protocol flaw in TLS,
  • 24:32 - 24:34
    and affects all modern browsers,
  • 24:34 - 24:38
    and, similarly, allows you
    to downgrade connections
  • 24:38 - 24:41
    to export-grade Diffie-Hellman,
  • 24:41 - 24:43
    and then intercept or modify the contents,
  • 24:43 - 24:47
    if the server speaks and still supports
  • 24:47 - 24:51
    these export-grade Diffie-Hellman
    cipher suites.
  • 24:51 - 24:52
    So now let me give you
  • 24:52 - 24:55
    the hopefully brief technical overview
  • 24:55 - 24:57
    of how the Logjam attack works.
  • 24:57 - 24:59
    If you've been curious about this,
  • 24:59 - 25:03
    this is the chance to see it.
  • 25:03 - 25:05
    So, Logjam is a problem that happens
  • 25:05 - 25:08
    during the TLS connection handshake.
  • 25:08 - 25:10
    And the first thing that happens
    in the handshake,
  • 25:10 - 25:12
    at the top of this diagram,
  • 25:12 - 25:13
    so this is just your browser connecting
  • 25:13 - 25:17
    to some website, some server
    there on the right,
  • 25:17 - 25:20
    maybe Alice connecting to
    her favourite website here.
  • 25:20 - 25:22
    So the first stage is this client hello,
  • 25:22 - 25:25
    where, you know, a normal client
    is going to say,
  • 25:25 - 25:27
    I speak various kinds of cryptography,
  • 25:27 - 25:30
    including full-strength Diffie-Hellman.
  • 25:30 - 25:31
    The server at that point is going to
  • 25:31 - 25:36
    respond by picking some cipher suite,
  • 25:36 - 25:38
    let's say Diffie-Hellman,
  • 25:38 - 25:41
    and then sending over
    its certificate chain,
  • 25:41 - 25:45
    as well as its Diffie-Hellman
    public parameters,
  • 25:45 - 25:48
    p and g, the server gets to choose them,
  • 25:48 - 25:49
    as well as g^a.
  • 25:49 - 25:51
    And then it's going to use
  • 25:51 - 25:55
    its long-term RSA key that is the thing
  • 25:55 - 25:57
    that is signed in its certificate,
  • 25:57 - 26:00
    in order to make a signature on
    those Diffie-Hellman parameters.
  • 26:00 - 26:02
    Okay, then it's going to do...
  • 26:02 - 26:05
    complete the negotiation, and so on.
  • 26:05 - 26:07
    In the Logjam attack,
  • 26:07 - 26:09
    we have a man-in-the-middle attacker,
  • 26:09 - 26:11
    who's able to modify some
    of these messages
  • 26:11 - 26:13
    as they're going by.
  • 26:13 - 26:15
    So the first thing the attacker does,
  • 26:15 - 26:17
    he modifies the client hello message,
  • 26:17 - 26:20
    to replace all of the different
    kinds of cryptography
  • 26:20 - 26:22
    the client says it supports,
  • 26:22 - 26:25
    and just put in export-grade
    Diffie-Hellman.
  • 26:25 - 26:27
    Ah, the 90s are here again.
  • 26:27 - 26:30
    Alright, so then, you know, the server
  • 26:30 - 26:33
    will get that, and if the server supports
  • 26:33 - 26:35
    export-grade Diffie-Hellman,
  • 26:35 - 26:39
    as about 10% or so of servers
  • 26:39 - 26:41
    still support export grade Diffie-Hellman,
  • 26:41 - 26:44
    it's going to respond and say,
  • 26:44 - 26:46
    okay, that's what you asked for,
    I'll take it,
  • 26:46 - 26:49
    and it's going to send over its side
  • 26:49 - 26:51
    of the Diffie-Hellman key exchange,
  • 26:51 - 26:54
    but using a 512-bit prime,
  • 26:54 - 26:57
    because that's what is required under
  • 26:57 - 27:00
    these export-grade suites.
  • 27:00 - 27:02
    Now, at that point, the browser would
  • 27:02 - 27:05
    normally reject this message,
  • 27:05 - 27:07
    because it didn't ask for export-grade,
  • 27:07 - 27:10
    it really asked for full-strength,
  • 27:10 - 27:12
    so instead, the man in the middle has to
  • 27:12 - 27:16
    modify the server's hello message,
  • 27:16 - 27:18
    and say that this is full-strength
    Diffie-Hellman,
  • 27:18 - 27:20
    well, if it's full-strength,
  • 27:20 - 27:23
    why is it only a 512-bit prime
    that's being used?
  • 27:23 - 27:26
    Well, there's actually no limitation,
  • 27:26 - 27:28
    and no distinction between the messages
  • 27:28 - 27:34
    that the server would send
    in that space with p and g,
  • 27:34 - 27:36
    that says normal-grade Diffie-Hellman
  • 27:36 - 27:38
    has to be more than 512 bits.
  • 27:38 - 27:41
    In fact we found a handful of real sites
  • 27:41 - 27:43
    that even for normal-strength
    Diffie-Hellman
  • 27:43 - 27:49
    just happened to use 512-bit
    or even weaker cryptography.
  • 27:49 - 27:51
    So, as long as we modify
    this earlier message,
  • 27:51 - 27:53
    the server's hello message,
  • 27:53 - 27:55
    and make it say, "normal-strength
    Diffie-Hellman",
  • 27:55 - 27:57
    there's no way for the client to tell
  • 27:57 - 27:59
    from just the structure of the protocol,
  • 27:59 - 28:01
    that anything is amiss.
  • 28:01 - 28:05
    So, at this point, there is one last place
  • 28:05 - 28:06
    that we could catch the problem,
  • 28:06 - 28:08
    that the client or the server could see
  • 28:08 - 28:10
    that something's wrong,
  • 28:10 - 28:13
    which is that each side sends
    the other a finished message,
  • 28:13 - 28:15
    here at the end,
  • 28:15 - 28:22
    that says, basically, has, uses
    the session secrets
  • 28:22 - 28:25
    to add an authentication code
  • 28:25 - 28:28
    to a dialogue of all of the
    protocol messages
  • 28:28 - 28:30
    that match the handshake dialogue,
  • 28:30 - 28:34
    all the messages going back
    in each direction so far
  • 28:34 - 28:37
    have to be the same from each side of you.
  • 28:37 - 28:40
    However, in our case, in Logjam,
  • 28:40 - 28:43
    the attacker is able to spoof
    these messages,
  • 28:43 - 28:46
    to make them look correct to each side.
  • 28:46 - 28:48
    He's able to modify that dialogue why?
  • 28:48 - 28:53
    Well, because we're using this
    512-bit Diffie-Hellman
  • 28:53 - 28:58
    that we know from using
    the number field sieve,
  • 28:58 - 29:00
    we are able to efficiently break.
  • 29:00 - 29:03
    So, if the attacker is able to quickly
  • 29:03 - 29:04
    perform the discrete log
  • 29:04 - 29:09
    on the Diffie-Hellman key exchange
  • 29:09 - 29:11
    that's going by at 512-bit strength,
  • 29:11 - 29:15
    then he can fix up the client
    and server hello messages,
  • 29:15 - 29:17
    and neither side will notice
    that anything went wrong.
  • 29:17 - 29:19
    So that's Logjam in a nutshell.
  • 29:19 - 29:22
    I'm sorry, it's a little bit complicated.
  • 29:22 - 29:25
    So, how widely shared are
  • 29:25 - 29:28
    these Diffie-Hellman public parameters?
  • 29:28 - 29:31
    Well, we used Internet-wide
    scanning to find out.
  • 29:31 - 29:34
    So, my group, we also made
    something called zmap,
  • 29:34 - 29:36
    that I talked about here
    a couple of years ago,
  • 29:36 - 29:39
    which lets us quickly probe
    everything on the Internet,
  • 29:39 - 29:42
    and so we did this and tried to make
  • 29:42 - 29:44
    connections to each HTTPS server
  • 29:44 - 29:47
    in the public IPv4 address space,
  • 29:47 - 29:50
    and found out what key exchange methods
  • 29:50 - 29:52
    were supported and with what primes.
  • 29:52 - 29:56
    And what we find is that 97% of hosts
  • 29:56 - 29:58
    that support export-grade Diffie-Hellman
  • 29:58 - 30:01
    use one of only 3 512-bit primes.
  • 30:01 - 30:03
    They're that widely-shared.
  • 30:03 - 30:05
    Why is this? Because those parameters
  • 30:05 - 30:07
    are very often either hard-coded
  • 30:07 - 30:08
    or encoded in standards
  • 30:08 - 30:10
    that different people implement.
  • 30:10 - 30:12
    The most common of these,
  • 30:12 - 30:15
    used by 80% of hosts that support
    export-grade Diffie-Hellman,
  • 30:15 - 30:21
    is a public parameter that's
    hardcoded into Apache 2.2.
  • 30:21 - 30:23
    So, it's actually there,
    embedded in the source,
  • 30:23 - 30:26
    you have to recompile Apache to change it.
  • 30:26 - 30:28
    13% of hosts supported something,
  • 30:28 - 30:32
    a second prime that has also 512 bits,
  • 30:32 - 30:35
    that's hardcoded in mod_ssl,
  • 30:35 - 30:37
    and the next most popular, 4%,
  • 30:37 - 30:40
    was in the Sun JDK.
  • 30:40 - 30:43
    Only 10 primes accounted for 99%
  • 30:43 - 30:45
    of all the hosts we found in
    the public address space
  • 30:45 - 30:49
    that supported export-grade
    Diffie-Hellman.
  • 30:49 - 30:54
    So, if we would like to compromise these,
  • 30:54 - 30:57
    well, Nadia just told you about
  • 30:57 - 31:02
    how long it takes to use
    the number field sieve
  • 31:02 - 31:05
    to break 512-bit discrete log,
  • 31:05 - 31:08
    well, we actually went and did
    the precomputation
  • 31:08 - 31:13
    for all 3 of these most widely used
    Diffie-Hellman primes,
  • 31:13 - 31:19
    and our colleagues who make a tool
    called CADO-NFS
  • 31:19 - 31:22
    where able to implement the code
  • 31:22 - 31:28
    for that piece of the discrete log version
    of the number field sieve
  • 31:28 - 31:31
    and they ran the algorithm on these primes
  • 31:31 - 31:34
    on a cluster they just happened
    to have lying around,
  • 31:34 - 31:38
    it took about a week of time
    on the cluster
  • 31:38 - 31:40
    for each of these primes.
  • 31:40 - 31:42
    After which, using an optimised version
  • 31:42 - 31:45
    of the last portion of
    the number field sieve,
  • 31:45 - 31:48
    it takes about 70 seconds for us to break
  • 31:48 - 31:49
    any individual connection
  • 31:49 - 31:54
    that uses any one of these
    3 most popular primes.
  • 31:54 - 31:57
    So, Logjam and our precomputations
  • 31:57 - 31:59
    now allow us to break any connection
  • 31:59 - 32:05
    to about 8% of the top million
    HTTPS sites from Alexa
  • 32:05 - 32:08
    and when we came up with this attack,
  • 32:08 - 32:11
    it worked in all modern browsers.
  • 32:11 - 32:13
    So, mitigation!
  • 32:13 - 32:19
    applause
  • 32:19 - 32:22
    This is bad, everyone, this is the crypto
  • 32:22 - 32:25
    all of us are using.
  • 32:25 - 32:27
    So we do have some mitigations.
  • 32:27 - 32:28
    This is the actual positive part,
  • 32:28 - 32:30
    is that the browser makers have now
  • 32:30 - 32:33
    started to increase the minimum strength
  • 32:33 - 32:35
    of Diffie-Hellman they will accept.
  • 32:35 - 32:37
    So IE, Chrome, and Firefox will reject
  • 32:37 - 32:39
    primes less than 1024 bits
  • 32:39 - 32:41
    and Safari less than 768.
  • 32:41 - 32:44
    And the new draft of TLS 1.3 is including
  • 32:44 - 32:45
    an anti-downgrade flag
  • 32:45 - 32:47
    that will make it even harder
  • 32:47 - 32:50
    for such attacks to take place
    in the future.
  • 32:50 - 32:52
    Now back to Nadia.
  • 32:52 - 32:54
    NH: So we promised in our abstract...
  • 32:54 - 33:00
    applause
  • 33:00 - 33:02
    ...that there would be a hands-on
    portion of this talk.
  • 33:02 - 33:04
    So, you have a couple options,
  • 33:04 - 33:06
    number 1 is, if you're really into this,
  • 33:06 - 33:08
    you can do and download
    CADO-NFS yourselves,
  • 33:08 - 33:12
    cado-nfs.gforge.inria.fr
  • 33:12 - 33:16
    and, you know, run
    discrete log algorithms yourselves
  • 33:16 - 33:18
    for any prime you wish
  • 33:18 - 33:20
    and then you can compute
    arbitrary discrete logs.
  • 33:20 - 33:22
    However, since we have already done
  • 33:22 - 33:23
    some of the computations,
  • 33:23 - 33:25
    we figured that we would make
    them available for you guys
  • 33:25 - 33:27
    if you wanted to play with them.
  • 33:27 - 33:33
    So...
    applause
  • 33:33 - 33:36
    We have done so through the Twitter API,
  • 33:36 - 33:39
    so we have a bot running on Twitter
  • 33:39 - 33:41
    and if you would like to compute
  • 33:41 - 33:45
    discrete logs for any of these
    widely-used parameters,
  • 33:45 - 33:48
    this bot will do so for you.
  • 33:48 - 33:53
    So here is the group generator
    and the primes in hexadecimal,
  • 33:53 - 33:57
    for the 3 groups that we
    did the precomputation for.
  • 33:57 - 33:59
    And if you wanted to test out,
  • 33:59 - 34:01
    you would do something like this,
  • 34:01 - 34:02
    so this using Sage,
  • 34:02 - 34:05
    which is a Python-based open source
    mathematics package,
  • 34:05 - 34:07
    that does a lot of algebra
    and number theory,
  • 34:07 - 34:08
    if you like playing with the stuff,
  • 34:08 - 34:09
    sage is super cool,
  • 34:09 - 34:16
    so, I said, say, my prime m
    is this last value in hex there,
  • 34:16 - 34:17
    the mod_ssl prime,
  • 34:17 - 34:24
    then I take 2 and raise it to
    the 0x1337 power mod m,
  • 34:24 - 34:26
    and then I print it out in hexadecimal,
  • 34:26 - 34:35
    and I get this value, then I can
    copy-paste it into a tweet @DLogBot
  • 34:35 - 34:39
    then some comp stuff happens
    on our back end,
  • 34:39 - 34:41
    this is running on one of
    the machines in my lab,
  • 34:41 - 34:44
    so please don't break it,
  • 34:44 - 34:47
    and after a minute or two,
  • 34:47 - 34:49
    you should get back an answer.
  • 34:49 - 34:58
    applause
  • 34:58 - 35:02
    So, there's a queue,
    only one thing can run at a time,
  • 35:02 - 35:03
    median time is 70 seconds,
  • 35:03 - 35:06
    it can vary between
    30 seconds and 3 minutes,
  • 35:06 - 35:09
    so, you know, if it doesn't respond to you
  • 35:09 - 35:12
    within like, you know, an hour
    or something,
  • 35:12 - 35:16
    then send us a ping and we'll see
    if it's still running.
  • 35:16 - 35:18
    Okay. So, have fun.
  • 35:18 - 35:21
    Please don't actually use this for malice.
  • 35:21 - 35:28
    applause
  • 35:28 - 35:30
    We already have some satisfied customers.
  • 35:30 - 35:34
    laughter
  • 35:34 - 35:36
    AH: Alright, so we promised there were
  • 35:36 - 35:39
    two exploits that have to do with
    weakened Diffie-Hellman,
  • 35:39 - 35:42
    and the first, Logjam, right, anyone can
  • 35:42 - 35:43
    use backdoors from the 90s
  • 35:43 - 35:45
    to pwn modern browsers,
  • 35:45 - 35:49
    well, the second one is
    a little bit more widespread.
  • 35:49 - 35:51
    So, we're going to talk about
  • 35:51 - 35:53
    how Diffie-Hellman weaknesses
  • 35:53 - 35:56
    can be used for mass surveillance.
  • 35:56 - 35:58
    We believe that governments can probably
  • 35:58 - 36:03
    already right now, exploit
    1024-bit discrete log
  • 36:03 - 36:08
    to break Diffie-Hellman for
    wide-scale passive decryption
  • 36:08 - 36:11
    of Internet communications.
  • 36:11 - 36:14
    So, is breaking 1024-bit Diffie-Hellman
  • 36:14 - 36:15
    within the reach of governments,
  • 36:15 - 36:18
    let's look back at these numbers quickly.
  • 36:18 - 36:22
    So we can see that for 512-bit RSA
    and Diffie-Hellman,
  • 36:22 - 36:26
    they're both really in reach of
    basically any effort right now,
  • 36:26 - 36:28
    any one of you can probably,
  • 36:28 - 36:30
    most of the resources to do this.
  • 36:30 - 36:35
    For 768-bit RSA or Diffie-Hellman,
  • 36:35 - 36:37
    well, we think this is now in the reach
  • 36:37 - 36:41
    of a concerted academic effort.
  • 36:41 - 36:45
    For 1024, it's a little bit
    more complicated,
  • 36:45 - 36:47
    because the number field sieve algorithm
  • 36:47 - 36:48
    is complicated enough that even
  • 36:48 - 36:52
    making estimates of the runtime
    at this size and larger
  • 36:52 - 36:55
    is very, very complicated
  • 36:55 - 36:58
    and having a high-confidence estimate
    is difficult.
  • 36:58 - 37:01
    But we've tried to do the math
    conservatively,
  • 37:01 - 37:03
    and we believe that
    a conservative estimate,
  • 37:03 - 37:06
    at least for 1024-bit Diffie-Hellman
  • 37:06 - 37:08
    is to break, to do those precomputations
  • 37:08 - 37:11
    for a single prime p,
  • 37:11 - 37:13
    would take about 45 million core-years.
  • 37:13 - 37:18
    Now 45 million core-years
    sounds like a hell of a lot.
  • 37:18 - 37:21
    But, when you start to think about it,
  • 37:21 - 37:23
    if you're going to do
    an effort that large,
  • 37:23 - 37:26
    there are some optimisations
    you could start doing,
  • 37:26 - 37:29
    and, for instance, maybe instead of
  • 37:29 - 37:32
    running this on general-purpose PCs,
  • 37:32 - 37:33
    like these estimates show,
  • 37:33 - 37:35
    if you're going to do
    an effort on this scale,
  • 37:35 - 37:38
    maybe you're going to tape out some chips,
  • 37:38 - 37:40
    maybe you're going to use custom hardware.
  • 37:40 - 37:43
    And if we do the math and look at
    what kind of gains
  • 37:43 - 37:44
    we can get from custom hardware
  • 37:44 - 37:48
    in other applications that
    are similar to this,
  • 37:48 - 37:49
    we estimate that we can get
  • 37:49 - 37:52
    maybe a speedup of 80 times
  • 37:52 - 37:54
    just by doing it in custom hardware.
  • 37:54 - 37:57
    Okay, and then we ask what's
    that's going to cost,
  • 37:57 - 38:01
    well, we estimate that for...
  • 38:01 - 38:02
    to build a machine that could break
  • 38:02 - 38:08
    one 1024-bit p, precompute for
    one 1024-bit p every year,
  • 38:08 - 38:09
    would cost somewhere in the neighbourhood
  • 38:09 - 38:11
    of low hundreds of millions of dollars,
  • 38:11 - 38:13
    in a one-time investment.
  • 38:13 - 38:15
    As a result of this, you can churn out
  • 38:15 - 38:17
    precomputations once a year
  • 38:17 - 38:19
    that will let you break efficiently
  • 38:19 - 38:23
    every connection that uses that p.
  • 38:23 - 38:25
    Now, individual logs then are going to be
  • 38:25 - 38:26
    close to real-time, and in fact you can
  • 38:26 - 38:28
    re-use much of the same hardware
  • 38:28 - 38:32
    to do the computations for
    individual logs very quickly.
  • 38:32 - 38:35
    So, um, oh shit.
  • 38:35 - 38:38
    This is what the estimates look like.
  • 38:38 - 38:44
    Now is NSA actually doing this?
  • 38:44 - 38:45
    NH: This is where we get into
  • 38:45 - 38:48
    the conspiracy theories.
  • 38:48 - 38:53
    applause
  • 38:53 - 38:55
    So, there have been rumours flying around
  • 38:55 - 38:57
    for many years, I mean
    for decades, really,
  • 38:57 - 39:00
    but sort of credible rumours
    for many years,
  • 39:00 - 39:03
    of some large cryptanalytic breakthrough
  • 39:03 - 39:04
    that the NSA made.
  • 39:04 - 39:06
    So here's an article from James Bamford,
  • 39:06 - 39:09
    one of the, you know, world experts
    in open ???
  • 39:09 - 39:11
    of what the NSA's activities are
  • 39:11 - 39:14
    and he wrote an article in 2012
  • 39:14 - 39:16
    saying very clearly that he had talked
  • 39:16 - 39:17
    to multiple government officials
  • 39:17 - 39:20
    who said that the NSA made
    some enormous breakthrough
  • 39:20 - 39:21
    several years ago.
  • 39:21 - 39:23
    Everybody's a target,
  • 39:23 - 39:25
    everybody with communication is a target,
  • 39:25 - 39:26
    and this computing breakthrough
  • 39:26 - 39:27
    is going to give them the ability
  • 39:27 - 39:29
    to crack current public encryption.
  • 39:29 - 39:32
    And it was so secret that no oversight,
  • 39:32 - 39:35
    anybody had sort of access
    to the details of it.
  • 39:35 - 39:39
    But whatever it was,
    it was major and massive.
  • 39:39 - 39:40
    Of course, you know, after we saw this,
  • 39:40 - 39:42
    we said, oh my god, you know,
  • 39:42 - 39:42
    what could it possibly be,
  • 39:42 - 39:44
    are they breaking RSA?
  • 39:44 - 39:46
    Bamford actually goes on in this article
  • 39:46 - 39:49
    to speculate that it's
    something about AES,
  • 39:49 - 39:51
    which at least to my mind
    seems less likely
  • 39:51 - 39:55
    than some kind of major
    public key breakthrough.
  • 39:55 - 39:56
    So clearly we have sort of these rumours
  • 39:56 - 40:02
    of large breakthroughs by the NSA's
    tens of thousands of mathematicians.
  • 40:02 - 40:05
    Simultaneously, we can say, you know,
  • 40:05 - 40:08
    we know the NSA is clearly
    interested in cryptanalysis,
  • 40:08 - 40:11
    is cryptanalysis on the scale
    of hundreds of millions of dollars
  • 40:11 - 40:14
    within their reach?
  • 40:14 - 40:17
    The answer, thanks to Snowden, is yes.
  • 40:17 - 40:19
    We have some of their budgets
  • 40:19 - 40:22
    and they spend billions of dollars a year
  • 40:22 - 40:24
    on computer network operations,
  • 40:24 - 40:26
    they spend hundred of millions of dollars
  • 40:26 - 40:28
    on cryptanalytic IT systems,
  • 40:28 - 40:31
    cybercryptanalysis,
    exploitation solutions,
  • 40:31 - 40:34
    in fact, a couple years ago there was even
  • 40:34 - 40:42
    an increase of hundreds of millions of
    dollars in their budget for cryptanalysis.
  • 40:42 - 40:43
    Interesting.
  • 40:43 - 40:45
    So, a hundred million dollars of
    special-purpose hardware
  • 40:45 - 40:52
    is certainly within range
    of a government the size of ours.
  • 40:52 - 40:54
    Additionally, we can ask,
  • 40:54 - 40:56
    what would the impact of doing one of
  • 40:56 - 40:58
    these single precomputations
  • 40:58 - 41:02
    for a discrete log
    for a single prime would be,
  • 41:02 - 41:05
    and the answer is actually
    surprisingly large.
  • 41:05 - 41:06
    So if you did this precomputation
  • 41:06 - 41:09
    for a single 1024-bit prime,
  • 41:09 - 41:11
    that would allow passive decryption
  • 41:11 - 41:13
    of connections to 66% of VPN servers
  • 41:13 - 41:16
    and 26% of SSH servers.
  • 41:16 - 41:18
    This is from Internet-wide scanning,
  • 41:18 - 41:20
    we connected to all of these
  • 41:20 - 41:21
    and we said "we would like to speak
  • 41:21 - 41:24
    Diffie-Hellman with you,
    what parameters do you prefer?"
  • 41:24 - 41:27
    and these are the servers that preferred
  • 41:27 - 41:32
    a single 1024-bit prime over
    every other parameter in key size.
  • 41:32 - 41:34
    A second 1024-bit prime would allow
  • 41:34 - 41:39
    passive decryption for 18%
    of the top million HTTPS domains.
  • 41:39 - 41:40
    These are domains that prefer
  • 41:40 - 41:46
    to speak Diffie-Hellman
    with this fixed prime.
  • 41:46 - 41:48
    And, the final piece of evidence
  • 41:48 - 41:50
    for something like this being within range
  • 41:50 - 41:52
    and at least being worth worrying about
  • 41:52 - 41:58
    is actually some of the slides
    that were release last year,
  • 41:58 - 41:59
    by der Spiegel,
  • 41:59 - 42:02
    and in particular they have
    a large amount of detail
  • 42:02 - 42:07
    about passive decryptions of VPN traffic.
  • 42:07 - 42:08
    So here's an example,
  • 42:08 - 42:10
    it is clear from the slides that
  • 42:10 - 42:11
    whatever the NSA is doing,
  • 42:11 - 42:12
    they have the ability to passively decrypt
  • 42:12 - 42:15
    VPN connections on a large scale.
  • 42:15 - 42:19
    And they're very happy about it.
  • 42:19 - 42:21
    I think this is my favourite
    Snowden slide ever.
  • 42:21 - 42:23
    laughter
  • 42:23 - 42:25
    I feel this way when I decrypt things too.
  • 42:25 - 42:27
    laughter
  • 42:27 - 42:30
    So, if we take a look at what,
  • 42:30 - 42:34
    and these slides are specifically
    talking about IPsec VPNs,
  • 42:34 - 42:39
    if we take a look at what the
    key exchange looks like for IPsec VPNs,
  • 42:39 - 42:41
    what happens is, we have two hosts
  • 42:41 - 42:45
    who want to make a VPN
    connection with each other,
  • 42:45 - 42:51
    the key exchange actually uses a
    fixed set of parameters
  • 42:51 - 42:54
    from a small list of possibilities,
  • 42:54 - 42:56
    and so Alice and Bob will negotiate
  • 42:56 - 42:58
    which parameters they're going
    to use from this list,
  • 42:58 - 43:00
    and then they will do a
    Diffie-Hellman key exchange,
  • 43:00 - 43:03
    from that they will have
    a shared secret, g^ab,
  • 43:03 - 43:06
    and then they, in the most
    commonly used mode,
  • 43:06 - 43:07
    they also have some pre-shared key,
  • 43:07 - 43:09
    like a password that has been shared
  • 43:09 - 43:11
    over some other channel.
  • 43:11 - 43:14
    And that Diffie-Hellman secret
  • 43:14 - 43:16
    that was negotiated together
    with the pre-shared key
  • 43:16 - 43:19
    or mixed together to generate
    the session key.
  • 43:19 - 43:22
    So, if somebody wanted to
  • 43:22 - 43:24
    break a connection of this type,
  • 43:24 - 43:26
    one option would be to, say,
  • 43:26 - 43:28
    steal the pre-shared key
    through some other mechanism
  • 43:28 - 43:29
    and then break Diffie-Hellman.
  • 43:29 - 43:33
    That would be a possibility.
  • 43:33 - 43:36
    So, if we look what the
    NSA's requirements are
  • 43:36 - 43:39
    for their mass-scale decryption efforts,
  • 43:39 - 43:42
    they require finding out what
    the pre-shared key is,
  • 43:42 - 43:45
    getting both sides of the connection,
  • 43:45 - 43:48
    getting both the asymmetric key exchange
  • 43:48 - 43:50
    and the symmetrically encrypted data,
  • 43:50 - 43:53
    and then having some metadata.
  • 43:53 - 43:56
    These are the requirements for them
    to get decryption.
  • 43:56 - 43:58
    And we can also take a closer look
  • 43:58 - 44:04
    at what their decryption flow
    actually looks like,
  • 44:04 - 44:06
    this is somewhat complicated,
  • 44:06 - 44:08
    but in this diagram,
  • 44:08 - 44:11
    so they're getting the IK exchange,
  • 44:11 - 44:13
    and the symmetric data,
  • 44:13 - 44:17
    they're sending it into
    one system that they have,
  • 44:17 - 44:19
    they're sending the IKE messages through
  • 44:19 - 44:22
    out to some high-performance
    computing resources,
  • 44:22 - 44:24
    and then they get sent back with
  • 44:24 - 44:29
    some data from stored
    databases of information
  • 44:29 - 44:33
    that returns the actual decrypted data.
  • 44:33 - 44:35
    So that's what the decryption
    flow looks like.
  • 44:35 - 44:37
    We don't have any details
    of the cryptanalysis,
  • 44:37 - 44:39
    but we have details from
    the sysadmin's perspective
  • 44:39 - 44:43
    of how the systems
    that do the cryptanalysis
  • 44:43 - 44:45
    are hooked together.
  • 44:45 - 44:46
    And they're doing something
  • 44:46 - 44:48
    that requires high-performance computing,
  • 44:48 - 44:50
    that takes in key exchanges
  • 44:50 - 44:54
    and hands out decrypted data.
  • 44:54 - 45:00
    So, we can line up sort of the NSA's
    on-demand IKE decryption
  • 45:00 - 45:04
    with what a discrete log decryption
    would actually look like,
  • 45:04 - 45:06
    and they're very close,
  • 45:06 - 45:08
    so they would both require
    the pre-shared key,
  • 45:08 - 45:09
    both sides of the handshake,
  • 45:09 - 45:12
    both the handshake and the symmetric data,
  • 45:12 - 45:13
    and they would send off the data
  • 45:13 - 45:16
    to high-performance computing.
  • 45:16 - 45:18
    So in the same set of slides,
  • 45:18 - 45:21
    they also discuss targeted implants
  • 45:21 - 45:23
    against particular implementations,
  • 45:23 - 45:27
    if you were going to design a
    backdoor to make your life easy,
  • 45:27 - 45:30
    you would have fewer
    requirements than this.
  • 45:30 - 45:31
    Potentially.
  • 45:31 - 45:33
    There are many kinds of backdoors
    that you could design,
  • 45:33 - 45:35
    but if you were being clever about it,
  • 45:35 - 45:38
    you might try to make it
    a little bit easier on yourself
  • 45:38 - 45:41
    to decrypt the mess.
  • 45:41 - 45:44
    So I will let Alex finish with this.
  • 45:44 - 45:51
    applause
  • 45:51 - 45:54
    So to wrap up,
  • 45:54 - 45:56
    what we've seen today
  • 45:56 - 46:00
    through the cryptanalysis
    of Diffie-Hellman
  • 46:00 - 46:05
    is probably a mass surveillance dream.
  • 46:05 - 46:08
    The algorithms that we've talked about
  • 46:08 - 46:11
    would let a government with
    sufficient resources
  • 46:11 - 46:15
    to invest in these precomputation attacks
  • 46:15 - 46:19
    break connections on an almost
    unheard-of scale,
  • 46:19 - 46:24
    across almost every widely-used
    crypto protocol on the Internet.
  • 46:24 - 46:26
    Here are some numbers again,
  • 46:26 - 46:28
    for HTTPS, the top million sites,
  • 46:28 - 46:30
    we're looking at a device like
  • 46:30 - 46:32
    the ones we hypothesised
  • 46:32 - 46:38
    breaking connections to maybe
    56% of them passively.
  • 46:38 - 46:43
    For IKE, for Internet key
    exchange v1 and v2,
  • 46:43 - 46:46
    we're looking at in the 60%s of servers
  • 46:46 - 46:48
    are potentially compromisable
  • 46:48 - 46:51
    using this same hardware.
  • 46:51 - 47:00
    For SSH, for IMAP with secure encrypted
    connections, for SMTP with STARTTLS,
  • 47:00 - 47:02
    the encrypted mail transports,
  • 47:02 - 47:06
    all of these protocols are
    potentially jeopardised
  • 47:06 - 47:07
    by the same kind of attack,
  • 47:07 - 47:09
    because everyone fundamentally,
  • 47:09 - 47:11
    so many people fundamentally
  • 47:11 - 47:14
    rely on the same underlying cryptography,
  • 47:14 - 47:17
    often with the very same public parameters
  • 47:17 - 47:20
    that are so widely shared.
  • 47:20 - 47:22
    So what can we do about this?
  • 47:22 - 47:25
    So first, let's go back to the
    Logjam attack again,
  • 47:25 - 47:27
    using 90s-era backdoored crypto
  • 47:27 - 47:31
    that lets any of us break connections
    to modern browsers.
  • 47:31 - 47:33
    Luckily, browsers have already started
  • 47:33 - 47:34
    to mitigate this, as I said,
  • 47:34 - 47:36
    by increasing the minimum strength
  • 47:36 - 47:37
    of Diffie-Hellman they support,
  • 47:37 - 47:40
    although there's still a way to go there,
  • 47:40 - 47:43
    since they're all still accepting
    1024-bit key exchange.
  • 47:43 - 47:46
    Our biggest recommendation
    under here though,
  • 47:46 - 47:49
    I think the lesson is:
    don't backdoor crypto!
  • 47:49 - 47:51
    Right, because the backdoored crypto
  • 47:51 - 47:53
    of 20 years ago is now coming back
  • 47:53 - 47:55
    to bite everyone.
  • 47:55 - 47:59
    applause
  • 47:59 - 48:02
    And then, we have the second attack,
  • 48:02 - 48:04
    the 1024-bit case that enables
  • 48:04 - 48:05
    so much mass surveillance.
  • 48:05 - 48:07
    Well, to get around this,
  • 48:07 - 48:10
    we're going to have to do some upgrades.
  • 48:10 - 48:11
    Probably the easiest thing to do,
  • 48:11 - 48:13
    and the thing that almost
  • 48:13 - 48:15
    every cryptographer that we talked to
  • 48:15 - 48:17
    recommends now,
  • 48:17 - 48:19
    is to move to elliptic-curve crypto.
  • 48:19 - 48:20
    Yes, there's been talk
  • 48:20 - 48:23
    about whether the specific NIST curves
  • 48:23 - 48:26
    may have been backdoored by NSA,
  • 48:26 - 48:27
    but by and large, we think that
  • 48:27 - 48:30
    elliptic curve is the most sound choice
  • 48:30 - 48:32
    we have for now.
  • 48:32 - 48:33
    Now if elliptic curve isn't an option,
  • 48:33 - 48:35
    and there's technical reasons
    why it might not be,
  • 48:35 - 48:39
    at the very least use
    a Diffie-Hellman prime
  • 48:39 - 48:41
    that's 2048 bits or longer.
  • 48:41 - 48:43
    If even that isn't an option,
  • 48:43 - 48:46
    you're using legacy systems
    for some reason,
  • 48:46 - 48:50
    well, or Java yes, thanks,
  • 48:50 - 48:53
    if there's anyone there who works for Sun,
  • 48:53 - 48:58
    please, please tell them
    to fix the crypto in Java!
  • 48:58 - 49:05
    applause
  • 49:05 - 49:07
    But if that's not an option,
  • 49:07 - 49:08
    if that's not an option,
  • 49:08 - 49:09
    the fallback is you can generate,
  • 49:09 - 49:14
    at least generate your own 1024-bit prime.
  • 49:14 - 49:17
    Mind you, there various tricks
    that you have to make sure you do
  • 49:17 - 49:20
    when generating a prime,
    it must be a safe prime,
  • 49:20 - 49:22
    but there are implementations
    of doing this,
  • 49:22 - 49:27
    so it's not exactly free to generate
    your own 1024-bit prime,
  • 49:27 - 49:28
    but it's inexpensive,
  • 49:28 - 49:30
    and if you have no other option,
  • 49:30 - 49:33
    at least so that this large
    government adversary
  • 49:33 - 49:35
    has to spend a lot of precomputation,
  • 49:35 - 49:38
    a year perhaps, targeting
    you individually,
  • 49:38 - 49:40
    and they can't just get this for free.
  • 49:40 - 49:43
    Alright, so, that is our talk for tonight,
  • 49:43 - 49:46
    we're saving a lot of time for questions,
  • 49:46 - 49:49
    thank you all very very much.
  • 49:49 - 50:00
    applause
  • 50:00 - 50:05
    Herald: Nadia. Nadia and Alex,
    thank you very much.
  • 50:05 - 50:07
    We installed some microphones
    here in the room,
  • 50:07 - 50:09
    so please queue up, but first,
  • 50:09 - 50:12
    signal angel, do we have
    some questions from the net?
  • 50:12 - 50:15
    Signal Angel: Yes, we have a lot of questions.
  • 50:15 - 50:16
    First question is,
  • 50:16 - 50:18
    do you think it's possible that the NSA
  • 50:18 - 50:20
    uses quantum Shor factorisation
  • 50:20 - 50:25
    for 1024 or bigger keys already?
  • 50:25 - 50:28
    NH: I would believe it is much more likely
  • 50:28 - 50:30
    that they're using classical cryptanalysis
  • 50:30 - 50:31
    for 1024-bit keys than than they have
  • 50:31 - 50:35
    a quantum computer that
    nobody has heard about.
  • 50:35 - 50:37
    Herald: And another one?
  • 50:37 - 50:39
    Signal Angel: Another one... Is it thinkable
  • 50:39 - 50:41
    that the NSA solved the P=NP problem
  • 50:41 - 50:43
    but keeps quiet?
  • 50:43 - 50:46
    laughter
  • 50:46 - 50:48
    AH: Probably not, but if they have,
  • 50:48 - 50:51
    yes, I think they'd want to
    keep quiet about it.
  • 50:51 - 50:52
    NH: I hope they would tell us!
  • 50:52 - 50:54
    AH: I hope they would tell us too,
  • 50:54 - 50:56
    but I doubt it.
  • 50:56 - 51:00
    Herald: Okay, and over to
    number 1, please.
  • 51:00 - 51:02
    Q: Two questions.
  • 51:02 - 51:06
    First, is it reasonable to think that,
  • 51:06 - 51:09
    is it possible they are attacking
    individual RSA keys,
  • 51:09 - 51:11
    that they can fetch individual RSA keys
  • 51:11 - 51:14
    in about a week with custom hardware,
  • 51:14 - 51:18
    and two, NSA Suite B came out 2005
  • 51:18 - 51:19
    and they don't use Diffie-Hellman,
  • 51:19 - 51:23
    so NSA themselves, they told us in 2005,
  • 51:23 - 51:25
    "we won't use Diffie-Hellman",
  • 51:25 - 51:27
    so is it reasonable that,
  • 51:27 - 51:28
    when they changed the requirement
  • 51:28 - 51:31
    for top secret, we should follow?
  • 51:31 - 51:33
    AH: Well, to the first part
    of your question,
  • 51:33 - 51:36
    about whether they're factoring RSA,
  • 51:36 - 51:39
    I think the answer for 1024,
  • 51:39 - 51:41
    is very likely, yes they are,
  • 51:41 - 51:42
    for high-value targets.
  • 51:42 - 51:45
    So if you're a major website at least
  • 51:45 - 51:48
    and you're using a 1024-bit RSA key,
  • 51:48 - 51:53
    well, it's long past time to change
    to a higher strength.
  • 51:53 - 51:56
    NH: If the NSA has not factored
    a 1024-bit key,
  • 51:56 - 51:58
    I'm going to be very disappointed,
  • 51:58 - 52:01
    I'm going to ask where
    my tax dollars are going.
  • 52:01 - 52:07
    laughter, applause
  • 52:07 - 52:09
    And also I think actually,
  • 52:09 - 52:11
    the point of sort of watching
  • 52:11 - 52:13
    what the defensive side of the NSA
  • 52:13 - 52:15
    is advocating in terms of recommendations
  • 52:15 - 52:17
    is actually a wise thing to do,
  • 52:17 - 52:20
    because as far as we know,
  • 52:20 - 52:22
    at least the public recommendations
  • 52:22 - 52:26
    defensively should... I mean,
  • 52:26 - 52:28
    making recommendations for people
  • 52:28 - 52:31
    who are building systems that are
    going to be handling classified data,
  • 52:31 - 52:33
    so they should be solid recommendations
  • 52:33 - 52:34
    as far as we know.
  • 52:34 - 52:35
    AH: What the NSA has told me
  • 52:35 - 52:38
    about those recommendations, by the way,
  • 52:38 - 52:40
    is that as long as you
    follow them exactly,
  • 52:40 - 52:42
    you're going to be okay,
  • 52:42 - 52:44
    but if you deviate in any
    small way whatsoever,
  • 52:44 - 52:47
    then they make no guarantees whatsoever.
  • 52:47 - 52:50
    So, think about what that might mean
  • 52:50 - 52:52
    in terms of your implementation
  • 52:52 - 52:56
    the next time you read through
    those particular recommendations
  • 52:56 - 52:58
    that they make.
  • 52:58 - 53:01
    Herald: Okay. Then we hop over to
    microphone 3, please.
  • 53:01 - 53:04
    Q: So, for the moment, is
  • 53:04 - 53:07
    elliptic-curve-based
    Diffie-Hellman secure?
  • 53:07 - 53:10
    NH: I hope so.
  • 53:10 - 53:14
    AH: It doesn't suffer from
    the same shape of attack
  • 53:14 - 53:15
    that we've described here.
  • 53:15 - 53:17
    As far as we know, there's not a way
  • 53:17 - 53:19
    to do this same kind of precomputation
  • 53:19 - 53:21
    for elliptic-curve Diffie-Hellman.
  • 53:21 - 53:23
    NH: So what we didn't mention in the talk
  • 53:23 - 53:25
    is, so, one of the reasons that
  • 53:25 - 53:27
    elliptic curve keys are so much shorter
  • 53:27 - 53:31
    than, say, finite-field
    Diffie-Hellman or RSA
  • 53:31 - 53:35
    is because we have this
    superpowerful index calculus
  • 53:35 - 53:37
    number field sieve-type algorithms
  • 53:37 - 53:41
    for factoring and for discrete log
    over finite fields,
  • 53:41 - 53:43
    and those don't seem,
  • 53:43 - 53:44
    we don't actually have equivalents
  • 53:44 - 53:48
    of those algorithms for
    properly generated elliptic curves.
  • 53:48 - 53:51
    So, that's why those key sizes are shorter
  • 53:51 - 53:54
    and that's why we think
    they seem to be more secure.
  • 53:54 - 53:57
    Herald: Then we take another one
    from microphone 3, please.
  • 53:57 - 54:01
    Q: Yes, you said that when doing
    the precomputations
  • 54:01 - 54:05
    for commonly-used primes,
  • 54:05 - 54:08
    you can reduce the effort you have to put
  • 54:08 - 54:11
    in a single connection
    to about 70 seconds.
  • 54:11 - 54:13
    How is that usable?
  • 54:13 - 54:16
    If my TLS handshake is delayed 70 seconds,
  • 54:16 - 54:18
    I already ran away.
  • 54:18 - 54:20
    AH: Ah! So we refer you to the paper
  • 54:20 - 54:22
    for the full answer to that,
  • 54:22 - 54:24
    but it turns out there's a bunch of tricks
  • 54:24 - 54:29
    that you can do to keep
    a session handshake open
  • 54:29 - 54:30
    for at least 70 seconds.
  • 54:30 - 54:32
    So, this may not be what you want to do
  • 54:32 - 54:35
    to the connection, say, in a web browser
  • 54:35 - 54:38
    that's loading index.html,
  • 54:38 - 54:40
    but whichever one is loading, say,
  • 54:40 - 54:45
    the, I don't know, the 1-pixel
    tracking image in the background,
  • 54:45 - 54:46
    that nobody sees,
  • 54:46 - 54:49
    which is also getting the same
    session cookie,
  • 54:49 - 54:51
    that one you can hold open
    for 70 seconds
  • 54:51 - 54:53
    without the user noticing.
  • 54:53 - 54:54
    So what we've been able to do
  • 54:54 - 54:56
    is show a variety of ways
    that we can trick
  • 54:56 - 54:58
    browsers and other implementations
  • 54:58 - 55:01
    into holding the connection
    open long enough.
  • 55:01 - 55:03
    Also, 70 seconds is just
    what we were able to do
  • 55:03 - 55:07
    with a few weeks of hacking
    around and optimisation,
  • 55:07 - 55:11
    we think that with
    not that much more effort
  • 55:11 - 55:13
    we could get that number
    down quite a bit more.
  • 55:13 - 55:16
    But 70 seconds we think
    already is not so bad,
  • 55:16 - 55:18
    and there's plenty of ways
    that we can exploit it.
  • 55:18 - 55:21
    NH: Proof of concept.
  • 55:21 - 55:24
    Herald: Okay. Do we have
    something from the net?
  • 55:24 - 55:27
    Signal Angel: How long do you estimate the security
  • 55:27 - 55:29
    of RSA-DHE to sustain,
  • 55:29 - 55:31
    and do you have any idea if and when
  • 55:31 - 55:34
    there's any quantum encryption algorithms
  • 55:34 - 55:35
    that will soon be available to be used
  • 55:35 - 55:37
    by a broad public?
  • 55:37 - 55:39
    AH: Oh, quantum encryption algorithms.
  • 55:39 - 55:41
    NH: You should watch Dan
    and Tanja's talk from yesterday.
  • 55:41 - 55:44
    AH: Yeah, last night was the time
    to hear about that.
  • 55:44 - 55:46
    NH: The dangers of quantum cryptography.
  • 55:46 - 55:48
    I mean, the short answer is
  • 55:48 - 55:50
    that people who know
    what they're talking about
  • 55:50 - 55:52
    have said we should start worrying now
  • 55:52 - 55:54
    because we may see quantum computers
  • 55:54 - 55:57
    within the next 15 years, maybe.
  • 55:57 - 55:59
    But it's really hard to speculate about
  • 55:59 - 56:05
    advances in physics that
    may be pretty far off.
  • 56:05 - 56:07
    Herald: Do we have another one?
  • 56:07 - 56:10
    Signal angel: Sure. What's your
    opinion on the NIST curves,
  • 56:10 - 56:11
    especially with the current rumours
  • 56:11 - 56:16
    about the curve parameters
    having a backdoor?
  • 56:16 - 56:18
    NH: There are no known ways
  • 56:18 - 56:21
    that the curves could have been backdoored
  • 56:21 - 56:23
    with the given parameters.
  • 56:23 - 56:26
    AH: But if you don't trust them,
  • 56:26 - 56:28
    you know Dan Bernstein
    has a curve you can use too.
  • 56:28 - 56:30
    NH: So...
  • 56:30 - 56:32
    applause
  • 56:32 - 56:35
    NH: Do you trust Dan,
    or do you trust the NSA?
  • 56:35 - 56:37
    laughter
  • 56:37 - 56:39
    Herald: Over to 2, please.
  • 56:39 - 56:42
    Q: Some of the little bit
    that you recommend,
  • 56:42 - 56:46
    you say Diffie-Hellman is worse
    than RSA now,
  • 56:46 - 56:50
    so, does it mean I should switch back
  • 56:50 - 56:54
    to RSA, preferring it instead
    of Diffie-Hellman?
  • 56:54 - 56:57
    AH: With equivalent key sizes,
  • 56:57 - 57:00
    equivalent sizes of your primes,
  • 57:00 - 57:03
    or your RSA modulus,
  • 57:03 - 57:05
    yes, we are saying that.
  • 57:05 - 57:07
    That in the 1024-bit case,
  • 57:07 - 57:10
    there's strong reasons that you should
  • 57:10 - 57:14
    distrust the very common repeated primes
  • 57:14 - 57:16
    for Diffie-Hellman.
  • 57:16 - 57:18
    But that's not the whole story.
  • 57:18 - 57:27
    Right, so for longer sizes of modulus,
  • 57:27 - 57:28
    larger strengths of crypto,
  • 57:28 - 57:32
    RSA is probably still okay.
  • 57:32 - 57:34
    But I think either way,
  • 57:34 - 57:38
    switching to elliptic curve
    for key exchange
  • 57:38 - 57:40
    is probably the thing to do right now.
  • 57:40 - 57:42
    NH: I think the precise statement
    that we can make
  • 57:42 - 57:45
    is, if you're comparing 1024-bit
    Diffie-Hellman
  • 57:45 - 57:47
    to a 1024-bit RSA key,
  • 57:47 - 57:49
    that if you're using Diffie-Hellman
  • 57:49 - 57:51
    with the most commonly used parameters,
  • 57:51 - 57:53
    say, the Oakley group 2
  • 57:53 - 57:55
    that everybody on the Internet is using,
  • 57:55 - 57:57
    and you think it is likely that
    a large government agency
  • 57:57 - 58:01
    has already done the
    precomputation for that prime,
  • 58:01 - 58:05
    then breaking an individual
    connection using that prime
  • 58:05 - 58:07
    with Diffie-Hellman key exchange
  • 58:07 - 58:09
    would be much, much, much less effort
  • 58:09 - 58:15
    than factoring a freshly generated
    1024-bit RSA key that is unique to you.
  • 58:15 - 58:18
    Even if that 1024-bit RSA factorisation
  • 58:18 - 58:20
    is within range of the NSA,
  • 58:20 - 58:21
    it may not be worth their while
  • 58:21 - 58:23
    to actually factor your key.
  • 58:23 - 58:26
    Whereas breaking a
    Diffie-Hellman key exchange,
  • 58:26 - 58:27
    they've already done the hard work
  • 58:27 - 58:28
    to break everybody on the Internet,
  • 58:28 - 58:31
    so, you're just one more fish.
  • 58:31 - 58:32
    That's the precise statement
  • 58:32 - 58:34
    that we can make about the security.
  • 58:34 - 58:35
    The real answer: use elliptic curves,
  • 58:35 - 58:42
    or, to use 2048-bit
    Diffie-Hellman: probably fine.
  • 58:42 - 58:44
    Herald: And, over to number 1, please.
  • 58:44 - 58:47
    Q: How realistic is it to use, or to create
  • 58:47 - 58:50
    a new prime for every exchange
  • 58:50 - 58:53
    or at least every few exchanges?
  • 58:53 - 58:56
    NH: So, unfortunately, the properties
  • 58:56 - 59:01
    that you need for discrete log to be hard,
  • 59:01 - 59:02
    you need to have a safe prime
  • 59:02 - 59:06
    and you would hopefully like it
    not to be backdoored,
  • 59:06 - 59:09
    generating safe primes is
    still kind of effortful
  • 59:09 - 59:11
    on modern hardware,
  • 59:11 - 59:12
    I mean if you try to do it on your laptop
  • 59:12 - 59:15
    it will probably take like, I don't know,
    a minute or something.
  • 59:15 - 59:17
    So, it's actually a lot of effort
  • 59:17 - 59:20
    to generate a new safe prime all the time.
  • 59:20 - 59:24
    Just use a larger safe prime
    and you'll be better.
  • 59:24 - 59:26
    Herald: So we're running out of time,
  • 59:26 - 59:29
    but let's... with number 2.
  • 59:29 - 59:32
    Q: You said that elliptic
    curve cryptography
  • 59:32 - 59:37
    is not susceptible to
    this precomputation attack,
  • 59:37 - 59:44
    is that luck, or is it
    engineered to be that way?
  • 59:44 - 59:44
    AH laughs
  • 59:44 - 59:46
    NH: ...luck?
  • 59:46 - 59:47
    AH: In part!
  • 59:47 - 59:48
    NH: I mean, a combination of both, but
  • 59:48 - 59:49
    so as far as we know, I mean, you can't do
  • 59:49 - 59:51
    precomputation with elliptic curves,
  • 59:51 - 59:54
    so, you know, sort of generically,
  • 59:54 - 59:55
    the best thing that you can say
  • 59:55 - 59:58
    is you can do a lot of precomputation
  • 59:58 - 60:01
    but you still have to do a lot of effort
  • 60:01 - 60:03
    for each individual value,
  • 60:03 - 60:06
    so you could do, you know, generically
  • 60:06 - 60:07
    if you want to break an elliptic curve
  • 60:07 - 60:09
    you could do like,
    a square-root-of-n attack
  • 60:09 - 60:11
    against the key size,
  • 60:11 - 60:14
    you could do, say, n^2/3 precomputation
  • 60:14 - 60:18
    and then you would have n^1/3 online work
  • 60:18 - 60:19
    if that makes sense to you.
  • 60:19 - 60:23
    But you get less effort as far as we know.
  • 60:23 - 60:25
    Less benefit.
  • 60:25 - 60:28
    Herald: Sorry. We're going to finalise
    then, with number 4.
  • 60:28 - 60:31
    Q: What do you think about blacklisting
    these common primes,
  • 60:31 - 60:32
    just in the modern browsers?
  • 60:32 - 60:35
    Will this get rid of this issue?
  • 60:35 - 60:37
    AH: Just blacklisting the common primes,
  • 60:37 - 60:39
    well, if you blacklist the common primes,
  • 60:39 - 60:41
    if you blacklisted the common primes
  • 60:41 - 60:43
    when we first came up with this,
  • 60:43 - 60:47
    you'd immediately break
    about 10% of websites
  • 60:47 - 60:50
    because there's not a good
    fallback mechanism
  • 60:50 - 60:52
    if you don't like the prime you got
  • 60:52 - 60:55
    during key negotiation.
  • 60:55 - 60:57
    What the browsers are more likely to do
  • 60:57 - 61:02
    is to phase out this kind of
    finite-field Diffie-Hellman entirely,
  • 61:02 - 61:05
    over the next larger number of years.
  • 61:05 - 61:07
    So first they're going to
    start rejecting things
  • 61:07 - 61:09
    that use unusually weak primes,
  • 61:09 - 61:12
    that's what they're doing already today,
  • 61:12 - 61:13
    but I think in the long term
  • 61:13 - 61:17
    they're going to encourage the use
    of elliptic curves as an alternative,
  • 61:17 - 61:18
    if you want forward secrecy,
  • 61:18 - 61:22
    elliptic curves will be the way to get it.
  • 61:22 - 61:25
    Herald: Nadia, Alex, once again,
  • 61:25 - 61:26
    thank you so much.
  • 61:26 - 61:27
    AH: Thank you.
  • 61:27 - 61:33
    applause
  • 61:33 - 61:37
    postroll music
  • 61:37 - 61:44
    subtitles created by c3subtitles.de
    in the year 2016. Join, and help us!
Title:
J. Alex Halderman, Nadia Heninger: Logjam: Diffie-Hellman, discrete logs, the NSA, and you
Description:

more » « less
Video Language:
English
Duration:
01:01:44

English subtitles

Revisions