Return to Video

djb, Tanja Lange: PQCHacks

  • 0:00 - 0:10
    preroll music
  • 0:10 - 0:12
    Herald: Tanja Lange and djb,
  • 0:12 - 0:16
    or, Daniel Bernstein,
  • 0:16 - 0:20
    came from the elliptic curve
  • 0:20 - 0:22
    are gonna talk today also about
  • 0:22 - 0:24
    the McEliece crypto where they took us.
  • 0:24 - 0:26
    They're both in the steering committee
  • 0:26 - 0:28
    for the PQCrypt
  • 0:28 - 0:30
    and I've talked to other people
    in the community
  • 0:30 - 0:31
    and they said,
  • 0:31 - 0:32
    especially about Tanja,
  • 0:32 - 0:38
    she is the one that brings practice
    and reality into all this theoretical mess
  • 0:38 - 0:44
    so let's please have a hand for
    Tanja Lange and Daniel Bernstein.
  • 0:44 - 0:55
    applause
  • 0:55 - 0:59
    djb: Okay. Am I on? I apparently am.
  • 0:59 - 1:02
    Welcome to a late night show,
    with Dan and Tanja.
  • 1:02 - 1:06
    laughter
    There's a lot of crypto talks out there
  • 1:06 - 1:10
    where you'll get the idea that
    crypto has problems.
  • 1:10 - 1:12
    Crypto has massive usability problems,
  • 1:12 - 1:14
    has performance problems,
  • 1:14 - 1:15
    has pitfalls for implementors,
  • 1:15 - 1:18
    has crazy complexity in implementation,
  • 1:18 - 1:20
    stupid standards,
  • 1:20 - 1:22
    millions of lines of unauditable code,
  • 1:22 - 1:23
    and then all of these problems
  • 1:23 - 1:27
    are combined into a
    grand unified clusterfuck
  • 1:27 - 1:30
    called transport layer security.
  • 1:30 - 1:38
    laughter, applause
  • 1:38 - 1:41
    But, actually, the situation is worse.
  • 1:41 - 1:44
    laughter
  • 1:44 - 1:46
    Because of what's coming, namely,
  • 1:46 - 1:49
    quantum computers.
  • 1:49 - 1:52
    These typical talks will give you the idea
  • 1:52 - 1:55
    that the core of crypto,
    the basic cryptographic primitives
  • 1:55 - 1:57
    like elliptic curve crypto, ECC,
  • 1:57 - 1:59
    that those are just fine,
    and all the problems
  • 1:59 - 2:01
    are integration into applications,
  • 2:01 - 2:03
    that's where the security problems happen.
  • 2:03 - 2:07
    But quantum computers will break ECC.
  • 2:07 - 2:09
    This has been know since the 1990s.
  • 2:09 - 2:12
    For people who don't recognise
    the picture here,
  • 2:12 - 2:17
    this is a mathematician named Peter Shor,
    20 years ago.
  • 2:17 - 2:26
    laughter, applause
  • 2:26 - 2:28
    20 years ago he wrote a paper saying
  • 2:28 - 2:29
    that a big quantum computer would be
  • 2:29 - 2:33
    able to factor big integers
    in polynomial time.
  • 2:33 - 2:35
    Now, if you like doing attacks,
  • 2:35 - 2:36
    and you hear about something like this,
  • 2:36 - 2:37
    then your first thought is
  • 2:37 - 2:39
    "Ooh, I wanna quantum computer!"
  • 2:39 - 2:41
    "I want a big quantum computer
    so I can run this attack!"
  • 2:41 - 2:43
    "And, where is it? Does anybody have one?"
  • 2:43 - 2:45
    "Can anybody gimme one?"
  • 2:45 - 2:47
    "Oh, it isn't there yet?
    Well, what's the progress?"
  • 2:47 - 2:49
    "Are we there yet?
    Can I have one, please?"
  • 2:49 - 2:50
    And, well, in the news, you now hear
  • 2:50 - 2:54
    about this D-wave quantum computer,
  • 2:54 - 2:57
    which, okay, there's some very good
    quantum engineering
  • 2:57 - 2:58
    that goes into this machine.
  • 2:58 - 2:59
    It's pretty clear that it's quantum,
  • 2:59 - 3:02
    I mean, it's actually doing the quantum
    stuff they say it does.
  • 3:02 - 3:05
    And there's some fantastic
    marketing in this machine.
  • 3:05 - 3:06
    But, unfortunately,
  • 3:06 - 3:08
    it's not actually useful.
  • 3:08 - 3:10
    So the D-wave quantum computer
  • 3:10 - 3:12
    doesn't do the basic things
  • 3:12 - 3:15
    that we expect a universal
    quantum computer to do.
  • 3:15 - 3:18
    It can only do very limited
    kinds of quantum computation.
  • 3:18 - 3:20
    It cannot maintain qubits,
  • 3:20 - 3:23
    do error correction on qubits for a while,
  • 3:23 - 3:24
    hold on to them to be able to do
  • 3:24 - 3:26
    basic qubit computations.
  • 3:26 - 3:28
    It can't even do those computations,
  • 3:28 - 3:30
    even if it could hold on to the qubits.
  • 3:30 - 3:31
    It can't do Shor's algorithm.
  • 3:31 - 3:33
    Can't factor big numbers.
  • 3:33 - 3:35
    Can't do other quantum algorithms
    that we care about.
  • 3:35 - 3:38
    Now, the D-wave company says that's
    not the point,
  • 3:38 - 3:40
    there's some other computations
  • 3:40 - 3:42
    that we designed this machine to do.
  • 3:42 - 3:44
    But they cherry-picked the computations
  • 3:44 - 3:45
    for this machine, saying basically
  • 3:45 - 3:49
    Here is the problem of
    simulating this machine
  • 3:49 - 3:51
    simulating the quantum
    thing that it's doing,
  • 3:51 - 3:53
    and of course the machine is very good
    at simulating itself,
  • 3:53 - 3:55
    by just running,
  • 3:55 - 3:58
    whereas a normal laptop, they compared to
  • 3:58 - 4:00
    sort of standard programs
    on a normal laptop,
  • 4:00 - 4:02
    and latest results, 10^8 times faster
  • 4:02 - 4:06
    except, well, there's a much
    more optimised program
  • 4:06 - 4:08
    that somebody put out last year,
  • 4:08 - 4:10
    which basically is the same speed
    as the D-wave machine
  • 4:10 - 4:12
    and like ten thousand times cheaper.
  • 4:12 - 4:16
    So, the D-wave machine is not,
    for the moment, something useful.
  • 4:16 - 4:18
    Lange: Well, if this makes you
    kind of comfortable,
  • 4:18 - 4:22
    so, no Shor monster coming,
  • 4:22 - 4:24
    there is progress.
  • 4:24 - 4:26
    There will be a universal
    quantum computer,
  • 4:26 - 4:28
    so, something that can run
    Shor's algorithm,
  • 4:28 - 4:30
    and there's a lot of research effort
    going into this,
  • 4:30 - 4:32
    so if you track, like, spending on crypto
  • 4:32 - 4:33
    and you can spend...
  • 4:33 - 4:36
    and track spending on quantum computers,
  • 4:36 - 4:38
    that is a lot of money.
  • 4:38 - 4:40
    And there's a lot of institutions
    and companies
  • 4:40 - 4:42
    and of course governments
    all over the world
  • 4:42 - 4:43
    building stuff.
  • 4:43 - 4:44
    And we do see progress, so
  • 4:44 - 4:46
    we're keeping track on this,
  • 4:46 - 4:48
    and, go to the Wikipedia page here
  • 4:48 - 4:50
    so we see over the last few years
  • 4:50 - 4:54
    a huge progress in stability of qubits,
  • 4:54 - 4:56
    so these things usually
    forget what they had,
  • 4:56 - 4:58
    they decay,
  • 4:58 - 5:00
    but they get more stable,
  • 5:00 - 5:02
    there's better error correction,
  • 5:02 - 5:03
    and there's better communication.
  • 5:03 - 5:07
    So the latest was that
    even silicon-based qubits can communicate.
  • 5:07 - 5:09
    So something is happening.
  • 5:09 - 5:13
    Um, IBM has
    on the record of Mark Ketchen
  • 5:13 - 5:15
    who's their CEO saying
  • 5:15 - 5:20
    "We actually do things that make us think
    like, hey, this isn't 50 years off"
  • 5:20 - 5:23
    "This is maybe just 10 or 15 years off.
    It's within reach."
  • 5:23 - 5:25
    So IBM is leaning out the window
  • 5:25 - 5:28
    and saying, yup, we're gonna be there
    pretty damn soon.
  • 5:28 - 5:32
    They said that in 2012, so
    let's fast-forward by 10 to 15 years
  • 5:32 - 5:35
    so it's now 2022 or 2027
  • 5:35 - 5:38
    and so there is a universal
    quantum computer.
  • 5:38 - 5:42
    The effect this has on the Internet crypto
  • 5:42 - 5:45
    is that RSA, which is still the majority
  • 5:45 - 5:47
    of all the connections today,
  • 5:47 - 5:50
    RSA is broken. RSA is dead.
  • 5:50 - 5:52
    Discrete logs in finite fields.
  • 5:52 - 5:53
    You might have thought a lot about it
  • 5:53 - 5:55
    earlier this year about Logjam.
  • 5:55 - 5:58
    But Logjam just breaks the very small one.
  • 5:58 - 6:00
    This is breaking any big one.
  • 6:00 - 6:03
    So, discrete logs in finite fields
    is totally dead as well.
  • 6:03 - 6:06
    Elliptic curves, that I already mentioned,
    ECC is dead.
  • 6:06 - 6:11
    So this breaks all public-key crypto
    on the Internet.
  • 6:11 - 6:13
    There's another algorithm due to Grover,
  • 6:13 - 6:16
    which is somewhat better under control,
  • 6:16 - 6:18
    somewhat less scary for crypto,
  • 6:18 - 6:20
    but it still has quite an effect,
  • 6:20 - 6:22
    so if you believe in the security of AES
  • 6:22 - 6:26
    and go like, well, AES-128 seems just fine,
  • 6:26 - 6:27
    has been not getting any
  • 6:27 - 6:30
    big progress in cryptanalysis,
  • 6:30 - 6:34
    but it halves the security,
    so AES 128-bit keys
  • 6:34 - 6:37
    are only 64-bit secure.
  • 6:37 - 6:40
    However, you can go to 256 bits.
  • 6:40 - 6:43
    djb: Okay, so, the AES situation:
    not so bad,
  • 6:43 - 6:46
    but all this public key stuff is broken.
  • 6:46 - 6:46
    So what do we do?
  • 6:46 - 6:48
    Well, you could bury
    your head in the sand,
  • 6:48 - 6:51
    you could hope that quantum computers
    don't come along,
  • 6:51 - 6:56
    you could deploy
    a physically secure crypto.
  • 6:56 - 6:59
    You could take a locked briefcase
    and chain it to your wrist,
  • 6:59 - 7:01
    or you could do quantum key distribution.
  • 7:01 - 7:04
    Now these things, obviously,
    are very very expensive.
  • 7:04 - 7:08
    This is crypto, information protection
    for rich people.
  • 7:08 - 7:12
    Or, quantum key distribution is crypto
    for even richer people.
  • 7:12 - 7:15
    You, obviously, aren't going to be able
    to democratically give this
  • 7:15 - 7:17
    to everybody who has a laptop.
  • 7:17 - 7:19
    But, well, okay, imagine that
    you have enough money,
  • 7:19 - 7:20
    that you don't mind this.
  • 7:20 - 7:24
    There's a bigger problem
    with physical cryptography,
  • 7:24 - 7:25
    which is the security.
  • 7:25 - 7:27
    Now these things are always advertised
  • 7:27 - 7:30
    as provably secure, guaranteed secure.
  • 7:30 - 7:32
    Nobody can get into this briefcase!
  • 7:32 - 7:34
    Nobody can get into this
    quantum key distribution system!
  • 7:34 - 7:36
    Assuming, of course, blah blah blah.
  • 7:36 - 7:38
    And then you look at the assumptions
  • 7:38 - 7:38
    and you start saying
  • 7:38 - 7:41
    "Wait a minute, is that actually true?"
  • 7:41 - 7:43
    And then it turns out that when people try
    attacking these systems,
  • 7:43 - 7:45
    the assumptions are not true.
  • 7:45 - 7:48
    And the systems get broken
    again and again and again
  • 7:48 - 7:50
    for a very reasonable attack cost.
  • 7:50 - 7:54
    Okay. Even if you have a system
    where you think it's secure,
  • 7:54 - 7:56
    which nobody's managed to build yet,
  • 7:56 - 7:59
    even if you had that, the design of
    this physical security system
  • 7:59 - 8:02
    is incredibly difficult to audit.
  • 8:02 - 8:04
    It's something where, if somebody wants
    to slip in a backdoor,
  • 8:04 - 8:05
    it's really easy.
  • 8:05 - 8:06
    But there's an even worse problem
  • 8:06 - 8:08
    with physical cryptography,
  • 8:08 - 8:10
    which is that it doesn't
    do very much crypto.
  • 8:10 - 8:15
    Typically these systems do about
    the same thing that AES does.
  • 8:15 - 8:17
    You start with a shared secret,
  • 8:17 - 8:18
    and then from that shared secret
  • 8:18 - 8:21
    you can authenticate more secrets
  • 8:21 - 8:25
    that you transmit through this
    physically secure communication mechanism.
  • 8:25 - 8:26
    For instance, quantum key distribution
  • 8:26 - 8:29
    starts with some way,
    some pre-existing way
  • 8:29 - 8:30
    of authenticating.
  • 8:30 - 8:33
    But that's just like AES starts with
    a, a secret key
  • 8:33 - 8:34
    which is then used to generate
  • 8:34 - 8:37
    more and more secret data.
  • 8:37 - 8:38
    And quantum key distribution says
  • 8:38 - 8:41
    well, it's provably secure under
    certain assumptions,
  • 8:41 - 8:43
    instead of AES which, well,
  • 8:43 - 8:45
    we just heard AES may be a little affected
  • 8:45 - 8:46
    by quantum computers, but
  • 8:46 - 8:48
    AES-256 is not broken.
  • 8:48 - 8:50
    Nobody has any idea how to break it.
  • 8:50 - 8:52
    So this physical cryptography
  • 8:52 - 8:55
    isn't actually serving
    the needs that we want.
  • 8:55 - 8:58
    Imagine trying to distribute
    operating system updates
  • 8:58 - 9:01
    through locked briefcases.
  • 9:01 - 9:02
    It's just not going to happen.
  • 9:02 - 9:04
    Microsoft sending out billions
    of locked briefcases
  • 9:04 - 9:06
    to all of its customers.
  • 9:06 - 9:07
    If you think that's realistic,
  • 9:07 - 9:11
    or if you think that,
    just, lasers are cool,
  • 9:11 - 9:13
    then there's a talk about quantum crypto
  • 9:13 - 9:15
    tomorrow, I believe.
  • 9:15 - 9:20
    Back in the real world, we obviously
    need to do something better with crypto.
  • 9:20 - 9:23
    Lange: Alright, so,
    let me take, momentarily,
  • 9:23 - 9:25
    a slightly more optimistic perspective.
  • 9:25 - 9:26
    Is there any hope? Yes.
  • 9:26 - 9:29
    So, the title of this talk, PQCHacks,
  • 9:29 - 9:31
    comes from post-quantum crypto,
  • 9:31 - 9:33
    and that's the term Dan coined
  • 9:33 - 9:35
    back in 2003
  • 9:35 - 9:36
    for crypto that remains secure
  • 9:36 - 9:39
    even if the adversary has
    a quantum computer.
  • 9:39 - 9:42
    So you, the normal people,
    me, him, the normal people,
  • 9:42 - 9:44
    the Internet, all the connections,
  • 9:44 - 9:47
    we have normal computers.
  • 9:47 - 9:49
    The adversary has a quantum computer.
  • 9:49 - 9:51
    We, today, encrypt something.
  • 9:51 - 9:52
    Adversary has all the time in the world
  • 9:52 - 9:53
    to build the quantum computer,
  • 9:53 - 9:56
    break us now or break us in the future.
  • 9:56 - 9:57
    And so this took off,
  • 9:57 - 9:59
    and there's been the first workshop
  • 9:59 - 10:02
    on post-quantum crypto,
    called PQCrypto2006
  • 10:02 - 10:04
    and then there's been
    a series of workshops
  • 10:04 - 10:05
    you can see here.
  • 10:05 - 10:07
    These are the attendees
    of the last edition
  • 10:07 - 10:10
    which was in Waterloo.
    It's more than a hundred people,
  • 10:10 - 10:11
    going like, yes,
    this is an important topic,
  • 10:11 - 10:13
    let's do some research on it.
  • 10:13 - 10:16
    So something is happening.
  • 10:16 - 10:18
    If you're curious what's happening,
  • 10:18 - 10:21
    next there's a workshop in Japan
    in February
  • 10:21 - 10:23
    and then in the Netherlands
    in 2017,
  • 10:23 - 10:27
    and we also got a project through
    from the EU
  • 10:27 - 10:29
    to support research on post-quantum.
  • 10:29 - 10:30
    So something is happening.
  • 10:30 - 10:34
    Actually, um, did I forget somebody?
    Yes.
  • 10:34 - 10:38
    Um, the NSA is also saying,
    let's do something.
  • 10:38 - 10:44
    So, on August 11 the NSA posted
    on their Suite B... page
  • 10:44 - 10:48
    saying, "The Information Assurance
    Director (so, IAD)
  • 10:48 - 10:52
    recognizes that there will be a move, in
    the not distant future, to a
  • 10:52 - 10:53
    quantum resistant algorithm suite."
  • 10:53 - 10:56
    Oh my god! Somebody is doing something!
  • 10:56 - 10:58
    The public has realised
    we have to do something!
  • 10:58 - 11:01
    Quick, quick,
    let's put out a press release!
  • 11:01 - 11:03
    Um.
  • 11:03 - 11:06
    Looks like they kind of realised
    it was embarrassing.
  • 11:06 - 11:10
    So, eight days later they pushed
    a new release, saying
  • 11:10 - 11:15
    "IAD will initiate a transition to quantum
    resistant algorithms in the not distant future."
  • 11:15 - 11:20
    So, NSA will lead us to a bright and
    glorious future.
  • 11:20 - 11:23
    djb: America, fuck yeah.
  • 11:23 - 11:31
    laughter, applause
  • 11:31 - 11:35
    Lange: But if you thought that,
    so far, this was bad,
  • 11:35 - 11:38
    it actually takes a lot of time
    to build crypto.
  • 11:38 - 11:42
    With let's say, NSA
    all ask the researchers
  • 11:42 - 11:44
    If you have some idea of
    what could be secure
  • 11:44 - 11:46
    against a quantum computer,
  • 11:46 - 11:47
    say AES-256,
  • 11:47 - 11:49
    the reason that you have confidence in it
  • 11:49 - 11:51
    is we had more than ten years of people
  • 11:51 - 11:53
    trying to break it,
  • 11:53 - 11:55
    trying all kinds of approaches
  • 11:55 - 11:56
    and not getting anywhere.
  • 11:56 - 12:00
    It takes a lot of time to explore
    the space of cryptosystems.
  • 12:00 - 12:02
    Once you have figured out
  • 12:02 - 12:03
    what could be actually doable,
  • 12:03 - 12:05
    you want to figure
    what the best attacks are,
  • 12:05 - 12:07
    you want to focus on the security system,
  • 12:07 - 12:09
    you want to figure out
    how to implement them,
  • 12:09 - 12:10
    how to implement them securely,
  • 12:10 - 12:14
    that is a whole lot of work
    that needs to be done
  • 12:14 - 12:16
    before you can say, well,
    this is actually practical.
  • 12:16 - 12:18
    We can actually use this.
  • 12:18 - 12:23
    Or sometimes, this is as practical
    as we can get it.
  • 12:23 - 12:27
    And then, you have this tiny little
    crypto primitive,
  • 12:27 - 12:28
    and then you have to build the hooks
  • 12:28 - 12:31
    and connections to get it into TLS.
  • 12:31 - 12:33
    Then we said at the beginning
  • 12:33 - 12:34
    that maybe you believe
  • 12:34 - 12:37
    that the cute little crypto cores
    are all secure
  • 12:37 - 12:38
    and it's just the connections
  • 12:38 - 12:40
    with the AES, sorry, with the TLS
  • 12:40 - 12:42
    in other world that is the problem.
  • 12:42 - 12:45
    That still needs to be done
    for post-quantum as well.
  • 12:45 - 12:46
    And, the side-channel attacks,
  • 12:46 - 12:48
    there's, uh, as an example,
  • 12:48 - 12:52
    ECC was introduced back in 85,
  • 12:52 - 12:54
    and now 30 years later,
  • 12:54 - 12:57
    we're seeing that ECC is actually
    getting deployed on the Internet,
  • 12:57 - 13:02
    that now the IETF, having called
    for having elliptic curve crypto,
  • 13:02 - 13:06
    because people start saying, yes,
    we would like to use this.
  • 13:06 - 13:08
    So we cannot wait until
    there's a quantum computer
  • 13:08 - 13:11
    in order to start research on it.
  • 13:11 - 13:15
    If you remember what 85 looked like
  • 13:15 - 13:19
    That's a while ago.
  • 13:19 - 13:22
    Now, if that sounded bad,
  • 13:22 - 13:23
    it's actually worse.
  • 13:23 - 13:26
    It's not just that, in 15 years from now,
  • 13:26 - 13:29
    whatever you send then will be broken.
  • 13:29 - 13:33
    There's some indication that some entities
  • 13:33 - 13:41
    might be recording your traffic.
  • 13:41 - 13:43
    We've given a talk like this in 2012
  • 13:43 - 13:44
    which was "Crypto for the Paranoid",
  • 13:44 - 13:45
    everybody thought it was, like,
  • 13:45 - 13:47
    pfft, you're crazy,
  • 13:47 - 13:49
    now it goes like
    "well, there might be an entity"
  • 13:49 - 13:53
    and everybody goes like, yeah, hmm, yeah.
  • 13:53 - 13:55
    So, let's assume that this entity
  • 13:55 - 13:57
    has the records of all the connections,
  • 13:57 - 14:01
    and, that in ten years, you're going
    to be an interesting person.
  • 14:01 - 14:05
    Maybe you're a politician,
    maybe you've become rich,
  • 14:05 - 14:08
    maybe you associate with the wrong people,
    or so they think,
  • 14:08 - 14:13
    and so somehow they go back to
    the 27th of December 2015,
  • 14:13 - 14:16
    and figure out what you
    were emailing during the talks,
  • 14:16 - 14:18
    because they have all the connections here
  • 14:18 - 14:20
    so they can go back in time
  • 14:20 - 14:26
    just by the metadata,
    and of course the real data.
  • 14:26 - 14:29
    From the metadata, they can decrypt it,
  • 14:29 - 14:32
    because this metadata is using RSA or ECC
  • 14:32 - 14:33
    which are broken.
  • 14:33 - 14:35
    And then they get the same key
  • 14:35 - 14:38
    than you're currently using with your
    other side to communicate.
  • 14:38 - 14:43
    And so they can go and decrypt this.
  • 14:43 - 14:46
    So it's not only that we can't wait for
    quantum computers to come,
  • 14:46 - 14:51
    we might already be too late.
  • 14:51 - 14:53
    Well, on the next slide,
  • 14:53 - 14:56
    here's a bunch of people who are getting
    together in this EU project,
  • 14:56 - 15:00
    and we have come up with
    what we're currently thinking
  • 15:00 - 15:02
    are good recommendations.
  • 15:02 - 15:04
    We think it's necessary for people
  • 15:04 - 15:07
    who really care about the security
    of their connections,
  • 15:07 - 15:08
    and when I say people I include myself,
  • 15:08 - 15:11
    I care about the security of
    my connections,
  • 15:11 - 15:12
    we would like to have something
  • 15:12 - 15:15
    that we believe is secure
    for the next hundred years.
  • 15:15 - 15:17
    And so we put out
    a list of recommendations.
  • 15:17 - 15:20
    So, for symmetric, it's relatively easy.
  • 15:20 - 15:22
    You want something which is at least
    a 256-bit key
  • 15:22 - 15:25
    and is sufficiently well understood
  • 15:25 - 15:29
    so there we have Salsa20,
    and we have AES-256.
  • 15:29 - 15:33
    Then, for authentication in symmetric,
  • 15:33 - 15:35
    there, we don't actually have any decrease
  • 15:35 - 15:37
    from a quantum computer, because
  • 15:37 - 15:39
    these are already
    information-theoretically secure.
  • 15:39 - 15:41
    So these are the nice part.
  • 15:41 - 15:44
    These two talk items is where we go like
  • 15:44 - 15:48
    "Pff. We might be okay on those."
  • 15:48 - 15:50
    We can do better,
    we can have nice research
  • 15:50 - 15:52
    and get something which is even
    better protected,
  • 15:52 - 15:54
    even faster under the new scenario,
  • 15:54 - 15:56
    but it's not so dire.
  • 15:56 - 15:59
    The bottom two, these are
    the public key systems.
  • 15:59 - 16:03
    That's public key encryption
    and public key signatures.
  • 16:03 - 16:05
    That's what we're going to
    focus on in this talk.
  • 16:05 - 16:08
    So, for public key encryption,
    we're recommending
  • 16:08 - 16:11
    the McEliece cryptosystem
    with Goppa codes
  • 16:11 - 16:13
    for a certain parameter size,
  • 16:13 - 16:15
    and then for signatures,
  • 16:15 - 16:18
    the recommendation is to use hash-based.
  • 16:18 - 16:19
    djb: Okay, so...
  • 16:19 - 16:23
    Let me dive into
    the hash-based part of this.
  • 16:23 - 16:26
    This is something which goes back
    even further than the 80s.
  • 16:26 - 16:29
    It goes back to the 1970s. Lamport.
  • 16:29 - 16:33
    So here's a way to use hashes
    to do one-time signatures.
  • 16:33 - 16:34
    Which are, we'll see in a few minutes,
  • 16:34 - 16:36
    signatures that you can use
  • 16:36 - 16:38
    to sign one message under a given key.
  • 16:38 - 16:41
    And then, well, that's a little bit
    inconvenient
  • 16:41 - 16:42
    that you can't sign more messages
  • 16:42 - 16:43
    so then Merkle came along
  • 16:43 - 16:45
    and said, you can sign more messages
  • 16:45 - 16:46
    by modifying the system,
  • 16:46 - 16:48
    and we'll also take a look at that.
  • 16:48 - 16:51
    The only thing you need
    for these public-key signature systems
  • 16:51 - 16:52
    is a good hash function.
  • 16:52 - 16:55
    And, okay, that's something where
    historically,
  • 16:55 - 16:58
    some hash functions designed in like, 1991
  • 16:58 - 16:59
    had trouble.
  • 16:59 - 17:01
    But, now, we have some good hash functions
  • 17:01 - 17:04
    so, for instance, SHA-3 has
    some great hash functions,
  • 17:04 - 17:06
    even SHA-2, there's no sign of trouble,
  • 17:06 - 17:07
    of those things being broken.
  • 17:07 - 17:10
    And then after these original systems
    from Lamport and Merkle,
  • 17:10 - 17:12
    there's lots and lots of improvements,
  • 17:12 - 17:14
    but all of these hash-based systems,
  • 17:14 - 17:17
    it's really easy to
    understand the security.
  • 17:17 - 17:18
    It's something where the basic idea
  • 17:18 - 17:20
    is really, really simple,
  • 17:20 - 17:21
    and the security analysis also ends up
  • 17:21 - 17:23
    being very straightforward.
  • 17:23 - 17:25
    You have to be careful about some things,
  • 17:25 - 17:27
    but, when you're careful about those,
  • 17:27 - 17:29
    and there's nothing subtle
    about it, nothing tricky,
  • 17:29 - 17:32
    then we understand exactly
    what security we get from these.
  • 17:32 - 17:35
    So let's dive into a signature scheme
  • 17:35 - 17:38
    that can only sign empty messages.
  • 17:38 - 17:41
    Now, this sounds kind of, like,
    wait a minute,
  • 17:41 - 17:43
    what do you mean,
    "can only sign empty messages?"
  • 17:43 - 17:45
    There's only one empty string,
  • 17:45 - 17:46
    and that's the only thing you can sign.
  • 17:46 - 17:50
    But imagine that you want
    to have a panic button,
  • 17:50 - 17:51
    like, your revocation key,
  • 17:51 - 17:52
    you want to be able to say,
  • 17:52 - 17:56
    "Here's a message that says,
    my house, my computer's been compromised,
  • 17:56 - 17:58
    don't trust anything from this anymore".
  • 17:58 - 18:01
    It's this one message
    that you want to sign,
  • 18:01 - 18:02
    under a certain key,
  • 18:02 - 18:04
    and if anybody has that public key,
  • 18:04 - 18:07
    then they should be able to verify
    that you sent that message,
  • 18:07 - 18:08
    and nobody should be able to forge that,
  • 18:08 - 18:10
    because it's really bad
    if somebody can forge
  • 18:10 - 18:11
    your panic message.
  • 18:11 - 18:13
    So, being able to sign just one message
  • 18:13 - 18:16
    is not actually such a useless thing,
  • 18:16 - 18:17
    and we'll also see that it builds up
  • 18:17 - 18:20
    to the rest of hash-based crypto.
  • 18:20 - 18:23
    Okay. Let's look at
    some Python stuff here,
  • 18:23 - 18:26
    simple SHA-3 you can get online
  • 18:26 - 18:30
    under Ubuntu or Debian
    do install python-pip and python-dev
  • 18:30 - 18:31
    because it's a C library actually,
  • 18:31 - 18:34
    and then, pip install simplesha3,
  • 18:34 - 18:36
    that will give you SHA3-256,
  • 18:36 - 18:38
    and then to generate a keypair
  • 18:38 - 18:41
    in this empty-message signature system,
  • 18:41 - 18:44
    all you do is you make 32 bytes
    of random data
  • 18:44 - 18:45
    and just hash it again,
  • 18:45 - 18:50
    just in in case... urandom is not
    too well-reviewed...
  • 18:50 - 18:52
    I mean, we should trust urandom,
  • 18:52 - 18:54
    but it's really cheap
    to put an extra hash on it.
  • 18:54 - 18:57
    So that's your secret key,
    it's a 32-byte hash.
  • 18:57 - 18:59
    And then the public key is,
  • 18:59 - 19:00
    hash that secret again.
  • 19:00 - 19:03
    So the public key is simply
    a hash of the secret key.
  • 19:03 - 19:05
    And then return the public key
    and the secret key,
  • 19:05 - 19:07
    of course the public key
    will get published,
  • 19:07 - 19:09
    and the secret key you keep for yourself.
  • 19:09 - 19:11
    As an example of doing this, well, um,
  • 19:11 - 19:13
    you just get random-looking data
  • 19:13 - 19:15
    coming out from your public key
    at the bottom
  • 19:15 - 19:18
    your secret key right at the bottom
    and public key above that.
  • 19:18 - 19:20
    And you can check that one
    of them's a hash of the other
  • 19:20 - 19:21
    if you know the secret key,
  • 19:21 - 19:23
    you can hash it to get the public.
  • 19:23 - 19:25
    Okay, now, how do you sign a message?
  • 19:25 - 19:27
    Well, this maybe sort of spelled out
  • 19:27 - 19:29
    in more steps than it has to be.
  • 19:29 - 19:32
    The API here, this is, I would say,
  • 19:32 - 19:34
    getting to be a pretty popular API
  • 19:34 - 19:37
    for signatures and for verification,
  • 19:37 - 19:40
    where you include the signature
    and the message together,
  • 19:40 - 19:41
    as a signed message.
  • 19:41 - 19:45
    And to emphasise that, here's a returned
    signed message from the sign function.
  • 19:45 - 19:49
    Now, the signed message
    will be later on verified,
  • 19:49 - 19:50
    and you get a message out of it,
  • 19:50 - 19:52
    where the only possible message
  • 19:52 - 19:54
    to be signed is the empty string,
  • 19:54 - 19:56
    and you can see that the top there
  • 19:56 - 19:58
    of the signature is checking
  • 19:58 - 20:00
    if the message is anything
    other than the empty string
  • 20:00 - 20:02
    then you're not allowed to sign it.
  • 20:02 - 20:05
    Um, if you have the empty string coming in
  • 20:05 - 20:10
    then the signature is simply
    your secret key.
  • 20:10 - 20:12
    So you reveal your secret key
  • 20:12 - 20:14
    and the whole idea of hash-based crypto
  • 20:14 - 20:16
    is that somebody can publicly check
  • 20:16 - 20:19
    the hashes of something that you reveal
  • 20:19 - 20:22
    to sign, in this case, the empty message.
  • 20:22 - 20:24
    And we'll see later how
    you can use the same idea
  • 20:24 - 20:25
    to sign lots more.
  • 20:25 - 20:27
    And then, okay, verification,
  • 20:27 - 20:29
    you simply checked that signedmessage,
  • 20:29 - 20:31
    which is supposed to be the secret key,
  • 20:31 - 20:32
    check its hash
  • 20:32 - 20:34
    and see if that matches the public key.
  • 20:34 - 20:36
    What would somebody have to do
    to attack this?
  • 20:36 - 20:37
    He would have to,
  • 20:37 - 20:40
    if you haven't actually signed a message,
  • 20:40 - 20:41
    the one message,
  • 20:41 - 20:42
    then he would have to figure out
  • 20:42 - 20:45
    some string that, when you hash it,
  • 20:45 - 20:47
    gives this public key.
  • 20:47 - 20:48
    And, well, that public key,
  • 20:48 - 20:50
    this is a preimage problem,
  • 20:50 - 20:52
    inverting the hash function.
  • 20:52 - 20:54
    The hash is supposed to be one-way,
  • 20:54 - 20:55
    if the input were low-entropy,
  • 20:55 - 20:57
    then this would be doable,
  • 20:57 - 20:59
    but the input was a 32-byte random string,
  • 20:59 - 21:01
    so nobody will be able to guess that,
  • 21:01 - 21:04
    or find any other string that passes this.
  • 21:04 - 21:05
    And then you return the message
  • 21:05 - 21:07
    and you can try this out
  • 21:07 - 21:08
    and see that it works.
  • 21:08 - 21:10
    Alright, let's move on.
  • 21:10 - 21:11
    We've managed to sign empty messages.
  • 21:11 - 21:14
    How about signing 0 or 1?
  • 21:14 - 21:16
    So now we'll make a signature system
  • 21:16 - 21:18
    where your key can sign 0
  • 21:18 - 21:20
    and your key can sign 1.
  • 21:20 - 21:22
    And, well, this is going
    to be kind of stupid,
  • 21:22 - 21:25
    what you do is, you make two keys,
  • 21:25 - 21:26
    one of them is signing 0,
  • 21:26 - 21:28
    and the other one is signing 1.
  • 21:28 - 21:32
    You can see how complicated
    this hash-based signature stuff is,
  • 21:32 - 21:34
    it's, okay, you put two keys together,
  • 21:34 - 21:36
    you make one key that will sign 0,
  • 21:36 - 21:37
    one key that will sign 1,
  • 21:37 - 21:39
    concatenate the public keys,
  • 21:39 - 21:40
    concatenate the secret keys,
  • 21:40 - 21:43
    the p0+p1, s0+s1,
  • 21:43 - 21:44
    and then if you want to sign, then,
  • 21:44 - 21:46
    well, if you're signing 0,
  • 21:46 - 21:48
    now the messages being signed
    are integers now
  • 21:48 - 21:49
    instead the empty string,
  • 21:49 - 21:51
    if you want to sign 0,
  • 21:51 - 21:52
    then the signed message will be
  • 21:52 - 21:56
    the string "0", followed by the 32 bytes,
  • 21:56 - 21:59
    well, this is again more complicated
    than it has to be,
  • 21:59 - 22:01
    but think of this as
    signing the empty message
  • 22:01 - 22:03
    with the empty signature system,
  • 22:03 - 22:07
    which is just copying the 32 bytes
    of the secret key.
  • 22:07 - 22:08
    And then if you want to sign message 1,
  • 22:08 - 22:12
    then you do that with the other 32 bytes
    of the secret key.
  • 22:12 - 22:14
    And then, to verify it,
  • 22:14 - 22:16
    well, just whether the
    signed message is 0 or 1,
  • 22:16 - 22:18
    just do the obvious thing.
  • 22:18 - 22:20
    Maybe I should emphasise this code
  • 22:20 - 22:22
    was written just for this talk,
  • 22:22 - 22:24
    it has not been reviewed,
  • 22:24 - 22:26
    and you should audit everything.
  • 22:26 - 22:27
    You know, you might feel like
  • 22:27 - 22:29
    six lines of code,
    you can't possibly screw it up,
  • 22:29 - 22:33
    but, don't ever
    use code like that in crypto.
  • 22:33 - 22:35
    So, this is just meant for
    you to understand
  • 22:35 - 22:36
    what this is supposed to be doing,
  • 22:36 - 22:37
    this has not passed review.
  • 22:37 - 22:40
    But, I like to think it would pass review.
  • 22:40 - 22:42
    Um, okay, if you try
  • 22:42 - 22:45
    signing the 1 message, for example,
  • 22:45 - 22:48
    and take the signed 1 message
    and open that signed message,
  • 22:48 - 22:49
    you do get the integer 1 back.
  • 22:49 - 22:50
    And if you try forging it,
  • 22:50 - 22:52
    you're again faced with this problem
  • 22:52 - 22:54
    of coming up with some 32-byte string
  • 22:54 - 22:57
    that hashes to a particular result.
  • 22:57 - 23:00
    Alright, let's move on to 4-bit messages!
  • 23:00 - 23:02
    So, I promise I won't do
    every possible length.
  • 23:02 - 23:05
    But, 4 bits, this will make
    an important point
  • 23:05 - 23:07
    that you don't see from 1 bit.
  • 23:07 - 23:09
    Let's try to sign a 4-bit message
  • 23:09 - 23:11
    by signing each of the four bits.
  • 23:11 - 23:14
    This all scales up to signing 1000 bits
    if you want.
  • 23:14 - 23:18
    Um, so, okay, let's make
    4 sign-bit keypairs
  • 23:18 - 23:21
    where each of those was
    two 32-byte hashes,
  • 23:21 - 23:26
    I mean, each secret key is
    two 32-byte random strings
  • 23:26 - 23:29
    and each of the public keys is the hash
    of those 32-byte random strings.
  • 23:29 - 23:32
    Make 4 of those pairs
    and concatenate them
  • 23:32 - 23:35
    to make some new public keys
    and secret keys.
  • 23:35 - 23:38
    Alright, and now to sign a message, well,
    you look at the message
  • 23:38 - 23:41
    and check,
    is it an integer between 0 and 15,
  • 23:41 - 23:43
    and reject otherwise,
  • 23:43 - 23:45
    and then sign each bit of the message.
  • 23:45 - 23:48
    You can see m shifted right by 0, 1, 2, 3,
  • 23:48 - 23:50
    extract the bottom bit of each of those,
  • 23:50 - 23:52
    and then sign each of those bits,
  • 23:52 - 23:54
    and then concatenate the signatures
  • 23:54 - 23:57
    to get, well, signatures of the four bits
    of the message.
  • 23:57 - 24:00
    And then verification works the way
    you expect
  • 24:00 - 24:03
    and I'll just skip that.
  • 24:03 - 24:04
    Alright, this has a problem.
  • 24:04 - 24:07
    That if you use this signature system
  • 24:07 - 24:10
    to sign two different messages,
  • 24:10 - 24:13
    then you might actually allow forgeries.
  • 24:13 - 24:15
    So let's look, for example,
  • 24:15 - 24:18
    suppose you sign 11 and you sign 7.
  • 24:18 - 24:20
    Now what is that signature of 11,
  • 24:20 - 24:23
    11, uh-oh, I have to do 11 in binary now,
  • 24:23 - 24:27
    so 11 sounds like 8+2+1.
  • 24:27 - 24:31
    And you sign 7, which is 4+2+1.
  • 24:31 - 24:33
    So what if you revealed now?
  • 24:33 - 24:36
    You reveal the signature on that 8,
  • 24:36 - 24:38
    so the 3rd bit you revealed
  • 24:38 - 24:41
    a signature saying, "the 3rd bit is 1"
  • 24:41 - 24:43
    as part of the signature of 11.
  • 24:43 - 24:45
    But as part of the signature of 7,
  • 24:45 - 24:47
    you revealed, you signed a message
  • 24:47 - 24:50
    saying "the 3rd bit is 0".
  • 24:50 - 24:53
    And now you can just mix and match
    those messages,
  • 24:53 - 24:54
    wherever the bits were different.
  • 24:54 - 24:56
    So for instance if you take the top bit
    from the 11
  • 24:56 - 24:59
    and the bottom 3 bits from the 7
  • 24:59 - 25:01
    then you end up signing 15.
  • 25:01 - 25:03
    So this signature system,
  • 25:03 - 25:06
    it's totally safe
    if you're signing one message.
  • 25:06 - 25:07
    But if you think about the data flow,
  • 25:07 - 25:10
    what does it mean
    to sign the individual bits
  • 25:10 - 25:11
    of two different messages,
  • 25:11 - 25:13
    then you can get in big trouble.
  • 25:13 - 25:16
    So this is a one-time signature system.
  • 25:16 - 25:19
    Alright. Here's how Lamport's
    signature system
  • 25:19 - 25:21
    works for one-time signatures
  • 25:21 - 25:23
    of any length of message.
  • 25:23 - 25:27
    First of all, you scale that 4 bits
    up to 256 bits.
  • 25:27 - 25:29
    And then, if you want to sign
    whatever length of message,
  • 25:29 - 25:32
    you just hash the message to 256 bits.
  • 25:32 - 25:35
    And the code for it is very simple.
  • 25:35 - 25:36
    This is not quite the state of the art
  • 25:36 - 25:38
    for one-time signatures,
  • 25:38 - 25:39
    there's fancier things you can do,
  • 25:39 - 25:41
    you can sign with Winternitz signatures
  • 25:41 - 25:46
    and get instead of something
    like 256 or 512 hash values
  • 25:46 - 25:48
    you can compress that down to like
  • 25:48 - 25:50
    50 or even fewer hash values.
  • 25:50 - 25:52
    There's all sorts of tricks to
    trade space for time
  • 25:52 - 25:53
    in these systems
  • 25:53 - 25:56
    but it's totally feasible to deploy
    Lamport signatures
  • 25:56 - 26:00
    and, well, Winternitz makes it
    even more practical.
  • 26:00 - 26:03
    Alright. What about this
    one-time restriction?
  • 26:03 - 26:04
    So these last, the 4-bit,
  • 26:04 - 26:06
    and the Lamport bigger message system,
  • 26:06 - 26:07
    these are only usable for,
  • 26:07 - 26:09
    you can only use your key
  • 26:09 - 26:11
    to sign one message.
  • 26:11 - 26:13
    And this was fixed by Merkle.
  • 26:13 - 26:15
    What Merkle said was,
  • 26:15 - 26:19
    you take 8 Lamport, for example 8,
    it can be any number,
  • 26:19 - 26:20
    here's how we'll make a public key
  • 26:20 - 26:23
    that can sign 8 different messages.
  • 26:23 - 26:25
    You make, well, 8 different Lamport keys
  • 26:25 - 26:27
    and you concatenate them together
  • 26:27 - 26:28
    and you use each one just once.
  • 26:28 - 26:31
    But it's actually more space-efficient
    than that sounds.
  • 26:31 - 26:33
    So here's what you send along.
  • 26:33 - 26:39
    You make 8 Ss there, those are the secret
    Lamport keys,
  • 26:39 - 26:41
    that are able to each sign one message,
  • 26:41 - 26:43
    and then you have 8
    corresponding public keys,
  • 26:43 - 26:45
    P1 through P8,
  • 26:45 - 26:48
    and then you hash together in a tree,
  • 26:48 - 26:52
    you hash together P1 and P2,
    and P3 and P4
  • 26:52 - 26:53
    to form P9 and P10,
  • 26:53 - 26:55
    and hash those together to get P13,
  • 26:55 - 26:59
    and same over here to get
    a final public key P15.
  • 26:59 - 27:01
    So just one hash value, that's your whole
    public key.
  • 27:01 - 27:04
    And then you have to remember
    lots of secrets,
  • 27:04 - 27:06
    but, okay, nobody has to see
    those secrets,
  • 27:06 - 27:08
    you just keep them on your computer.
  • 27:08 - 27:09
    And now what does it look like to,
  • 27:09 - 27:13
    to hash, sorry, to sign one message?
  • 27:13 - 27:17
    Well, here's what it looks like signing
    the first message.
  • 27:17 - 27:19
    That's when you use S1.
  • 27:19 - 27:21
    Once you use S1, you cross it out,
  • 27:21 - 27:22
    you never use it again,
  • 27:22 - 27:23
    you kill the secret.
  • 27:23 - 27:26
    You sign your message with S1,
  • 27:26 - 27:27
    and somebody can verify,
  • 27:27 - 27:31
    if they see the public key P1
    for Lamport signatures.
  • 27:31 - 27:32
    Or whatever one-time signature system
  • 27:32 - 27:34
    you put at the top.
  • 27:34 - 27:37
    But, well, your public key
    in Merkle systems is P15.
  • 27:37 - 27:40
    And how does somebody verify that
    P1 and P15 are related?
  • 27:40 - 27:45
    Well, you show them the P2 and the P10
    and the P14
  • 27:45 - 27:47
    that they need to hash together with P1
  • 27:47 - 27:50
    to get your public key, P15.
  • 27:50 - 27:52
    Alright, and that's as complicated
  • 27:52 - 27:54
    as the Merkle signature system gets,
  • 27:54 - 27:56
    if you want to be able to sign
    a million messages,
  • 27:56 - 27:57
    you have to have a million secrets,
  • 27:57 - 27:59
    but, again, just put it on
    your local hard drive,
  • 27:59 - 28:01
    you're not worried about the space.
  • 28:01 - 28:04
    It takes a few moments to generate the key,
  • 28:04 - 28:06
    but that's also not a problem.
  • 28:06 - 28:08
    Okay.
  • 28:08 - 28:09
    Good things about hash-based signatures,
  • 28:09 - 28:10
    and a few bad things.
  • 28:10 - 28:12
    Good things: It's post-quantum secure,
  • 28:12 - 28:16
    we totally understand what hash function
    security looks like,
  • 28:16 - 28:19
    after quantum computers
    and before quantum computers,
  • 28:19 - 28:21
    all you need is a good hash function,
  • 28:21 - 28:22
    and there's lots of hash functions
  • 28:22 - 28:23
    which have been thoroughly studied,
  • 28:23 - 28:25
    so, we're confident they're secure,
  • 28:25 - 28:27
    SHA-3 was the result of a long competition
  • 28:27 - 28:29
    with lots of people bashing on it,
  • 28:29 - 28:31
    and really has no problems.
  • 28:31 - 28:32
    The public key is very small,
  • 28:32 - 28:34
    just one hash value.
  • 28:34 - 28:37
    The security, as I said,
    is well-understood.
  • 28:37 - 28:40
    All the computations are very fast,
  • 28:40 - 28:42
    and you can already find
    standard proposals
  • 28:42 - 28:43
    for this system.
  • 28:43 - 28:46
    This is going to be the first standardised
  • 28:46 - 28:50
    and the first deployed
    post-quantum public key system.
  • 28:50 - 28:54
    On the other hand,
    if you look at the signature size,
  • 28:54 - 28:55
    it's kind of big,
  • 28:55 - 28:57
    and then the more scary thing
  • 28:57 - 28:59
    is the statefulness.
  • 28:59 - 29:01
    That you can only use S1 once,
  • 29:01 - 29:03
    and then you have to cross it out.
  • 29:03 - 29:05
    You can only use S2 once, and you have to
    cross it out.
  • 29:05 - 29:06
    What if you clone your VM?
  • 29:06 - 29:08
    What if you have a backup and restore?
  • 29:08 - 29:11
    Then, you've forgotten that you've
    used S2.
  • 29:11 - 29:12
    And then you use it again,
  • 29:12 - 29:14
    and then somebody can forge messages,
  • 29:14 - 29:17
    just like I was saying before.
  • 29:17 - 29:19
    Alright, so state is a problem,
  • 29:19 - 29:20
    actually some of you I'm sure were
  • 29:20 - 29:22
    in Rutkowska's talk earlier today
  • 29:22 - 29:25
    you also heard that
    state is harmful there.
  • 29:25 - 29:27
    And the solution:
  • 29:27 - 29:30
    Eliminate the state!
  • 29:30 - 29:36
    applause
  • 29:36 - 29:38
    I think I only have
    about three minutes left
  • 29:38 - 29:41
    for this, this section, well,
    this slide,
  • 29:41 - 29:45
    but, let me try to briefly say, the idea
    for getting rid of the state
  • 29:45 - 29:48
    is, you have, instead of signatures,
  • 29:48 - 29:50
    you have certificate chains.
  • 29:50 - 29:53
    So you have whole chain of CAs,
  • 29:53 - 29:56
    like, as a signer, you build
    a whole bunch of CAs,
  • 29:56 - 29:59
    you build, say, 2^256
    certificate authorities.
  • 29:59 - 30:01
    Now, that's too much computation to do,
  • 30:01 - 30:03
    but you do it on the fly,
    as you need them.
  • 30:03 - 30:05
    So you say, I'm going to sign
  • 30:05 - 30:08
    using one of these bottom-level
    certificate authorities,
  • 30:08 - 30:11
    that will sign my actual message.
  • 30:11 - 30:13
    And now, you don't have to know
    anything about any of the others,
  • 30:13 - 30:17
    you just pick one and use that to
    sign your message.
  • 30:17 - 30:20
    And then it has to be signed
    by the parent CA,
  • 30:20 - 30:21
    and that's signed by the next parent,
  • 30:21 - 30:23
    and so on, up the tree, to the top level,
  • 30:23 - 30:24
    only 256 levels.
  • 30:24 - 30:28
    And then, okay, you have your
    certificate chain,
  • 30:28 - 30:31
    how do you manufacture these
    certificate authorities?
  • 30:31 - 30:36
    Well, a certificate authority is just
    some bytes of code on disk,
  • 30:36 - 30:37
    that's what real CAs are like,
  • 30:37 - 30:39
    and you do the same thing signing,
  • 30:39 - 30:41
    and, those bytes of code, you can,
  • 30:41 - 30:46
    instead of storing the CA as a program
    in a configuration file on disk,
  • 30:46 - 30:49
    you just generate it on the fly
    when you need it,
  • 30:49 - 30:52
    by taking the position of the CA
    within this huge tree
  • 30:52 - 30:56
    and then hashing that together with
    some long-term secret.
  • 30:56 - 30:59
    That one long-term secret
    is the only thing you remember.
  • 30:59 - 31:02
    So you can manufacture CAs on demand
  • 31:02 - 31:03
    in some huge tree
  • 31:03 - 31:06
    and have them sign
    certificates for each other
  • 31:06 - 31:08
    only looking at a few CAs that you need
  • 31:08 - 31:11
    for the particular signature
    that you want.
  • 31:11 - 31:12
    The reason for having this big tree
  • 31:12 - 31:14
    is that then you're never going
  • 31:14 - 31:18
    to randomly use the same CA
    at the bottom twice.
  • 31:18 - 31:20
    So the problem of having
    one-time signatures
  • 31:20 - 31:22
    is no longer a problem.
  • 31:22 - 31:25
    Each CA will only sign one message.
  • 31:25 - 31:26
    Okay, and this is something where
  • 31:26 - 31:30
    the original proposal
    from Goldreich in 87,
  • 31:30 - 31:32
    if you use good one-time signatures,
  • 31:32 - 31:34
    Winternitz and all that stuff,
  • 31:34 - 31:38
    you get something like 0.6 megs
    for a signature.
  • 31:38 - 31:41
    Now that's a little bit inconvenient,
  • 31:41 - 31:43
    for comparison, if you do an OS update,
  • 31:43 - 31:46
    you look at the average
    Debian packet size,
  • 31:46 - 31:48
    then it's 1.2 megs.
  • 31:48 - 31:50
    And then, there is some
    number of signatures
  • 31:50 - 31:53
    with each update, and some
    of them are in packages,
  • 31:53 - 31:55
    and well, it's not inconceivable
  • 31:55 - 31:57
    to send 0.6 megs for each signature,
  • 31:57 - 31:59
    but it's kind of big.
  • 31:59 - 32:01
    And then if you look at, well,
  • 32:01 - 32:03
    web pages, say the Alexa top
    million web pages,
  • 32:03 - 32:07
    that average is 1.8 megs.
  • 32:07 - 32:09
    And again there's several
    signatures on the web page,
  • 32:09 - 32:13
    depending how many sites are providing
    graphics for it and so on.
  • 32:13 - 32:15
    So, 0.6 megs is maybe a problem.
  • 32:15 - 32:18
    But, okay, we took a look at this and
  • 32:18 - 32:22
    a bunch of people
    made the signature a lot smaller,
  • 32:22 - 32:24
    0.041 megabytes.
  • 32:24 - 32:27
    You know how to make a 41-kilobyte
    signature sound small:
  • 32:27 - 32:34
    only 0.041 megabytes for a sphincs 2^128
    post-quantum secure signature system.
  • 32:34 - 32:36
    If you're interested in more about
    what sphincs does,
  • 32:36 - 32:40
    go to sphincs.cr.yp.to
  • 32:40 - 32:42
    Lange: Alright, so.
  • 32:42 - 32:45
    Now we have some idea of
    how we can do signatures.
  • 32:45 - 32:47
    And signature's just the thing
  • 32:47 - 32:49
    that quantum crypto really
    really can't do,
  • 32:49 - 32:52
    I mean, also, locked briefcases,
  • 32:52 - 32:56
    how do you trust that this is
    actually your locked briefcase?
  • 32:56 - 32:59
    But also, public key crypto is a problem.
  • 32:59 - 33:02
    So, the one that we recommend
  • 33:02 - 33:03
    is code-based cryptography,
  • 33:03 - 33:05
    and code, in this context, is not like
  • 33:05 - 33:07
    code as in writing a program
  • 33:07 - 33:10
    but it comes from error-correcting codes.
  • 33:10 - 33:12
    So when you think about,
    say, your computer,
  • 33:12 - 33:14
    you have RAM in there
  • 33:14 - 33:18
    and this RAM might get cosmic radiation
  • 33:18 - 33:20
    or just a bump somewhere,
  • 33:20 - 33:21
    might forget something.
  • 33:21 - 33:22
    Or, a more trivial example,
  • 33:22 - 33:25
    if you order a book, or, nowadays,
  • 33:25 - 33:27
    order any media,
  • 33:27 - 33:29
    it has an ISBN number.
  • 33:29 - 33:33
    This last digit is dependent on
    the previous digits.
  • 33:33 - 33:35
    So they can figure out whether any
    of the digits before
  • 33:35 - 33:38
    was mistransmitted
  • 33:38 - 33:39
    then then go like, hmm,
  • 33:39 - 33:41
    that number doesn't exist, try again.
  • 33:41 - 33:45
    With your ECC RAM it's actually
    a little more sophisticated.
  • 33:45 - 33:47
    So you have your RAM sitting there,
  • 33:47 - 33:50
    and it stores 64 bits.
  • 33:50 - 33:54
    But it stores these 64 bits
    with some redundancy.
  • 33:54 - 33:57
    Internally, it has some extra check bits.
  • 33:57 - 34:01
    It stores 8 extra bits
  • 34:01 - 34:02
    and those 8 extra bits allow you
  • 34:02 - 34:06
    to recover the 64
    that you're interested in
  • 34:06 - 34:08
    in case there was some error.
  • 34:08 - 34:09
    Not in case of a massive error,
  • 34:09 - 34:13
    not in case somebody
    took a screwdriver and hit it,
  • 34:13 - 34:15
    but if there was just one random bit flip,
  • 34:15 - 34:16
    you can recover it.
  • 34:16 - 34:18
    Also, if two bits flip,
  • 34:18 - 34:20
    you can at least figure out
    that there was something
  • 34:20 - 34:22
    and raise a flag.
  • 34:22 - 34:24
    So the common scenario in error correction
  • 34:24 - 34:30
    is that we have a certain number, say, k
    bits that we care about
  • 34:30 - 34:34
    and then in order to be able
    to recover those,
  • 34:34 - 34:35
    to correct those,
  • 34:35 - 34:37
    we add some redundancy.
  • 34:37 - 34:40
    So we encapsulate, we encode those k bits
  • 34:40 - 34:42
    into n bits.
  • 34:42 - 34:45
    Now, we would like to have those n bits
  • 34:45 - 34:48
    be not too much larger than k.
  • 34:48 - 34:50
    We call those the parity check,
  • 34:50 - 34:52
    so this is like from the old days
    where you check
  • 34:52 - 34:56
    "those two add up to zero,
    zero zero zero...
  • 34:56 - 34:59
    oops! there's one, aha, there must
    have been one bit flip."
  • 34:59 - 35:04
    So parity as in, it has to be
    an even number at the end.
  • 35:04 - 35:05
    If you're talking about more positions
  • 35:05 - 35:07
    then it's obviously more
    than just the parity
  • 35:07 - 35:10
    but it's parity of some
    more complicated equations.
  • 35:10 - 35:17
    So, if no error occurred, if those 64 bits
    in your ECC RAM are just fine,
  • 35:17 - 35:22
    then all those extra n-k
    checks will be okay.
  • 35:22 - 35:26
    If there was an error,
    then something will fail,
  • 35:26 - 35:26
    raise a flag,
  • 35:26 - 35:29
    1, 2, 3 of those will not be satisfied,
  • 35:29 - 35:32
    and depending on this error pattern,
  • 35:32 - 35:37
    you will be able to recover what
    was going wrong in those bits.
  • 35:37 - 35:39
    It might actually be that
    it was your parity check bits.
  • 35:39 - 35:42
    It might be that one of
    those 8 extra bits flipped.
  • 35:42 - 35:46
    In which case, your 64 bits were just fine
  • 35:46 - 35:50
    but you don't know this when
    you get the error message.
  • 35:50 - 35:52
    And, if you have a good code,
  • 35:52 - 35:54
    so the kind of code
    that coding theorists study,
  • 35:54 - 35:55
    then you would like to have
  • 35:55 - 36:00
    your k pretty large, and the n
    not too much larger.
  • 36:00 - 36:03
    Because that's the amount of storage
  • 36:03 - 36:04
    you actually have to afford
  • 36:04 - 36:07
    for just getting this much data out of it.
  • 36:07 - 36:11
    Now, we get some guarantees
    when we design these,
  • 36:11 - 36:14
    there's a guarantee of getting t errors,
  • 36:14 - 36:16
    but for most of the codes that we know,
  • 36:16 - 36:17
    the guarantees are actually worse
  • 36:17 - 36:19
    than we get in practice,
  • 36:19 - 36:22
    so if something guarantees you 100 errors,
  • 36:22 - 36:26
    most of the time,
    you can actually correct 203.
  • 36:26 - 36:27
    Um, to get a little bit further
  • 36:27 - 36:33
    we actually did to, um, represent
    those equations with matrix,
  • 36:33 - 36:37
    um, not quite this one, sorry.
  • 36:37 - 36:41
    So, here's our equations.
  • 36:41 - 36:45
    So, small example,
    we would like to encode 4 bits,
  • 36:45 - 36:47
    k is 4,
  • 36:47 - 36:49
    and we're adding 3 extra bits.
  • 36:49 - 36:51
    That's not very efficient,
  • 36:51 - 36:55
    but it's a very nice example
    that one can see.
  • 36:55 - 37:01
    So, those rows there are
    our parity equations.
  • 37:01 - 37:03
    So let's assume we have those 7 bits,
  • 37:03 - 37:06
    which add redundancy to it,
  • 37:06 - 37:07
    then let's translate this first row,
  • 37:07 - 37:10
    which is 1 0 0 1 1 0 1,
  • 37:10 - 37:13
    that means we take the first bit,
  • 37:13 - 37:15
    skip the second and third,
  • 37:15 - 37:17
    so, have be 0,
  • 37:17 - 37:19
    and then, bit 3, then the next bit is set
  • 37:19 - 37:23
    so bit 4, and then bit 6.
  • 37:23 - 37:25
    Second row, similarly,
    we skip the first one,
  • 37:25 - 37:27
    so there's no bit 0, there's a bit 1,
  • 37:27 - 37:28
    no bit 2, there's a bit 3,
  • 37:28 - 37:31
    it was a 1 1 0 column,
  • 37:31 - 37:33
    and then bit 5 and bit 6,
  • 37:33 - 37:34
    and similarly.
  • 37:34 - 37:38
    So we have a nice diagonal
    on the left-hand side,
  • 37:38 - 37:42
    and then the rest is determined
    by these equations.
  • 37:42 - 37:44
    Now let's assume that
    something went wrong.
  • 37:44 - 37:46
    So we have our 7 bits here,
  • 37:46 - 37:49
    and a few hours later we come back
  • 37:49 - 37:51
    and want to look at those 7 bits,
  • 37:51 - 37:52
    we check whether anything went wrong,
  • 37:52 - 37:56
    we run through this parity check program,
  • 37:56 - 37:59
    and we actually get a failure pattern.
  • 37:59 - 38:02
    If everything was fine,
    we would have gotten 0 0 0,
  • 38:02 - 38:06
    but we're getting 1 0 1.
  • 38:06 - 38:08
    So the first equation doesn't hold,
  • 38:08 - 38:10
    the second one does hold,
  • 38:10 - 38:13
    and the third one does not hold.
  • 38:13 - 38:17
    Okay. Where could this come from?
  • 38:17 - 38:19
    We're pretty sure that b1 is okay
  • 38:19 - 38:22
    because otherwise the second
    equation would be wrong
  • 38:22 - 38:25
    because b1 only appears there,
  • 38:25 - 38:26
    and we're also making the promise
  • 38:26 - 38:28
    that it would be only one error.
  • 38:28 - 38:29
    If you have two errors, three errors,
  • 38:29 - 38:31
    then lots of other combinations
    could occur.
  • 38:31 - 38:33
    But it's much more likely that
    one bit flipped
  • 38:33 - 38:36
    than that a whole bunch
    of bits flipped at once.
  • 38:36 - 38:40
    Okay, so, tracing this
    a little bit further,
  • 38:40 - 38:43
    yes, so the b3 would get
    the two first equations,
  • 38:43 - 38:45
    b4, yes! b4 actually would get
  • 38:45 - 38:48
    that the first and the third
    equations are false.
  • 38:48 - 38:51
    So by seeing the error pattern 1 0 1,
  • 38:51 - 38:53
    we know it was b4.
  • 38:53 - 38:56
    Now this is a very nice and small example,
  • 38:56 - 38:58
    which doesn't even cover like the ECC RAM,
  • 38:58 - 39:01
    but it gives you an idea of how to try it.
  • 39:01 - 39:02
    On the other hand, it also gives you
  • 39:02 - 39:05
    the idea that you need to do kind of
  • 39:05 - 39:07
    brute force search it.
  • 39:07 - 39:11
    So for just n=7, you have to
    try up to 7 times.
  • 39:11 - 39:12
    If you now have two errors,
  • 39:12 - 39:16
    I would need to try every combination of 2
  • 39:16 - 39:18
    out of those n.
  • 39:18 - 39:24
    If I have a n which is like 2000 bits,
    really long,
  • 39:24 - 39:27
    and I tell you there's 100 errors,
  • 39:27 - 39:29
    so you would need to try every combination
  • 39:29 - 39:31
    of 100 positions in there.
  • 39:31 - 39:34
    So that would be a huge number.
  • 39:34 - 39:37
    That's obviously not a good way
    of error correction,
  • 39:37 - 39:38
    and that's certainly not how
  • 39:38 - 39:40
    DVDs and whatever else works.
  • 39:40 - 39:42
    Oh yeah, one bit of maths notation,
  • 39:42 - 39:46
    so, we call these things,
    the parentheses up there, matrix,
  • 39:46 - 39:48
    and in order to have a shorthand,
  • 39:48 - 39:55
    because I can't quite put my 2000 bits
    times 1000 bits matrix on the page,
  • 39:55 - 39:57
    I call this thing H,
  • 39:57 - 40:01
    and boldface b is such a bit vector.
  • 40:01 - 40:05
    So boldface b is that
    bits that I'm storing,
  • 40:05 - 40:09
    and the combination of
    applying this matrix,
  • 40:09 - 40:11
    wherever is 1, I take the variable,
  • 40:11 - 40:13
    where there's a 0, I don't write it,
  • 40:13 - 40:15
    that I write as H times b.
  • 40:15 - 40:16
    So in maths, if you have seen this,
  • 40:16 - 40:20
    this is just a matrix times
    vector multiplication,
  • 40:20 - 40:24
    otherwise, just take this as
    the instruction of evaluating
  • 40:24 - 40:29
    this, each row, as a set of equations.
  • 40:29 - 40:31
    Alright, so, to give this some names,
  • 40:31 - 40:34
    in coding theory we call c the code word,
  • 40:34 - 40:37
    so that's an element
    which is not compromised,
  • 40:37 - 40:38
    which will give you 0,
  • 40:38 - 40:40
    then there might be an error vector,
  • 40:40 - 40:42
    that's the bits that flip,
  • 40:42 - 40:44
    and so, when you retrieve the memory
  • 40:44 - 40:46
    or when you have a transmission,
  • 40:46 - 40:47
    we call this the received word,
  • 40:47 - 40:50
    and that's my b from the previous slide.
  • 40:50 - 40:52
    We do like to save on space,
  • 40:52 - 40:53
    so when there's this diagonal
  • 40:53 - 40:56
    which has all 0s down there
  • 40:56 - 40:58
    we just skip it.
  • 40:58 - 41:06
    So instead of writing a 7-by-3,
    we just write 4 columns and 3 rows.
  • 41:06 - 41:08
    Now there's lots of stuff
    happening in coding theory,
  • 41:08 - 41:11
    it's a, well, 65 years old topic,
  • 41:11 - 41:13
    and we can go up to very large matrices,
  • 41:13 - 41:16
    and for some special codes,
  • 41:16 - 41:18
    these are the ones that coding theorists
    come up with,
  • 41:18 - 41:20
    we actually have efficient methods.
  • 41:20 - 41:23
    Much much nicer than taking
    every combination of 100 positions
  • 41:23 - 41:27
    out of 2000 positions.
  • 41:27 - 41:29
    Of course, if you get too many errors,
  • 41:29 - 41:30
    you can't correct.
  • 41:30 - 41:33
    You can only correct up to
    whatever the promise is,
  • 41:33 - 41:35
    plus maybe a little bit later.
  • 41:35 - 41:37
    But if you don't know
    any of the structure,
  • 41:37 - 41:39
    if you don't know what
    the coding theorists put into it,
  • 41:39 - 41:43
    or if this H matrix got somewhat perturbed
  • 41:43 - 41:47
    by me giving a slightly
    different representation,
  • 41:47 - 41:51
    I don't call this b1 anymore,
    I call it now b17,
  • 41:51 - 41:52
    and let's flip those and so on,
  • 41:52 - 41:55
    suddenly it doesn't look like
    the code that you're used to.
  • 41:55 - 41:58
    If it's a random matrix,
  • 41:58 - 42:00
    the best attacks are not quite as bad
  • 42:00 - 42:03
    as picking 100 out of 2000,
  • 42:03 - 42:05
    but they are close to that,
  • 42:05 - 42:06
    they're pretty slow attacks,
  • 42:06 - 42:09
    it's an exponential-time algorithm,
  • 42:09 - 42:11
    if you have a random matrix.
  • 42:11 - 42:13
    And so what we're doing
    in code-based crypto
  • 42:13 - 42:16
    is to use this difference for encryption.
  • 42:16 - 42:18
    Now going back again to the 70s,
  • 42:18 - 42:21
    so, basically, yes, the stuff that we're
    really confident in
  • 42:21 - 42:23
    that it will last another 100 years,
  • 42:23 - 42:25
    is the stuff from the 70s that lots of
    people have looked at,
  • 42:25 - 42:27
    so, McEliece in 1978,
  • 42:27 - 42:30
    so just the year after RSA,
  • 42:30 - 42:36
    came up with a system
    which is using encoding as encryption.
  • 42:36 - 42:38
    So your method is,
  • 42:38 - 42:41
    you just encode a vector, your message,
  • 42:41 - 42:43
    and then you add some errors to it.
  • 42:43 - 42:45
    And, if the other side doesn't have
  • 42:45 - 42:47
    an efficient algorithm to decode,
  • 42:47 - 42:49
    they actually can't break it.
  • 42:49 - 42:52
    They're using a special code in there,
  • 42:52 - 42:53
    so there's a code from Goppa
  • 42:53 - 42:56
    from a few years earlier than that,
  • 42:56 - 42:58
    and that code, so far, nobody has found
  • 42:58 - 43:01
    any way to take the perturbed,
  • 43:01 - 43:03
    this complicated way of representing it,
  • 43:03 - 43:07
    and coming up with
    efficient decoding algorithm.
  • 43:07 - 43:11
    1986, Niederreither came up with
    a version of McEliece
  • 43:11 - 43:13
    which is smaller,
    the code size is smaller,
  • 43:13 - 43:16
    the public key size is smaller,
  • 43:16 - 43:19
    and we have similar things to
  • 43:19 - 43:21
    what you've seen before,
    so we have those H matrix,
  • 43:21 - 43:23
    we skip the diagonal,
  • 43:23 - 43:28
    we just represent this H as our public key
    as the remaining part of the matrix,
  • 43:28 - 43:33
    the secret key, that's the algorithm
    that only I know.
  • 43:33 - 43:35
    It's a Goppa code,
  • 43:35 - 43:36
    but it's a Goppa code
  • 43:36 - 43:39
    and there's many many Goppa codes
    for the same size.
  • 43:39 - 43:41
    So that's something that Goppa says,
  • 43:41 - 43:42
    well, if you want to have Goppa codes
  • 43:42 - 43:47
    with 2000 bits
    that can correct 200 errors,
  • 43:47 - 43:48
    here's how you set it up,
  • 43:48 - 43:51
    but there's lots and lots and lots
    of choices in there.
  • 43:51 - 43:52
    And your encryption is just,
  • 43:52 - 43:55
    take an error vector,
  • 43:55 - 43:57
    with a fixed number of bits,
  • 43:57 - 43:59
    and send me the error pattern of it.
  • 43:59 - 44:04
    So the outcome of multiplying H by this e.
  • 44:04 - 44:06
    And then we want to use this in crypto,
  • 44:06 - 44:08
    so we use the hash of this to encrypt it.
  • 44:08 - 44:12
    Um, then Peter Schwabe and
    Tung Chou, our PhD student,
  • 44:12 - 44:14
    wrote a very efficient
    implementation of this
  • 44:14 - 44:16
    called mcbits,
  • 44:16 - 44:17
    so if you want to have more detail
  • 44:17 - 44:20
    on how you could really
    use this in practice,
  • 44:20 - 44:21
    then go to that url.
  • 44:21 - 44:23
    Um, but let me talk a little bit
  • 44:23 - 44:26
    about why we are confident in this.
  • 44:26 - 44:28
    Code-based crypto is less obvious
    than hash-based,
  • 44:28 - 44:30
    I mean with hash-based it's like,
  • 44:30 - 44:32
    the, all we're doing is, hash.
  • 44:32 - 44:36
    A hash function by definition is
    something which is one-way.
  • 44:36 - 44:40
    For this code-based crypto,
    you need to think a little more,
  • 44:40 - 44:41
    to have people studying it
  • 44:41 - 44:45
    to figure out why this
    actually can be secure.
  • 44:45 - 44:48
    Now, the attacks, if I may say so,
  • 44:48 - 44:49
    started before the cryptosystem
    was proposed,
  • 44:49 - 44:51
    so it was another hard problem
  • 44:51 - 44:53
    that coding theorists were
    studying naturally,
  • 44:53 - 44:56
    and then McEliece said, hey, we have
    this hard problem here,
  • 44:56 - 44:59
    decoding a random code is not easy,
  • 44:59 - 45:02
    well, actually, afterwards, figuring out,
  • 45:02 - 45:05
    well, if you have a really random code,
  • 45:05 - 45:08
    even finding out whether there is
    a smaller code word is NP-hard.
  • 45:08 - 45:12
    And then, once it was a cryptosystem,
  • 45:12 - 45:15
    so, Omura, Lee-Brickell, all of those,
  • 45:15 - 45:18
    those come after
    it was proposed for crypto.
  • 45:18 - 45:21
    There's some which have an extra
    parenthetic comment,
  • 45:21 - 45:24
    those are papers which study
    the security of McEliece
  • 45:24 - 45:25
    if the attacker has a quantum computer,
  • 45:25 - 45:27
    so there's been lots and lots of work
  • 45:27 - 45:30
    for studying it
    against a classical computer,
  • 45:30 - 45:32
    and there's been some work
  • 45:32 - 45:34
    studying it against quantum computers.
  • 45:34 - 45:36
    It's pretty clear that we can't use Shor,
  • 45:36 - 45:37
    but we can use Grover,
  • 45:37 - 45:42
    and it's not so easily obvious
    how much Grover can give us.
  • 45:42 - 45:44
    However, the best that Grover can do
  • 45:44 - 45:47
    is basically halve the bit size.
  • 45:47 - 45:49
    So we had this AES-128,
    leading to 64-bit security,
  • 45:49 - 45:51
    so if you're conservative,
  • 45:51 - 45:54
    if you want to be like really really
    on the secure size,
  • 45:54 - 45:59
    then let's assume that we want to go for
    pre-quantum security at least 256
  • 45:59 - 46:02
    in order to get post-quantum security 128.
  • 46:02 - 46:04
    So here are some key sizes,
  • 46:04 - 46:08
    so if you're okay with 1000 kilobytes,
  • 46:08 - 46:15
    then you're getting something
    which is at least 131 post-quantum secure,
  • 46:15 - 46:17
    and that's actually very conservative,
  • 46:17 - 46:20
    most likely we can go much down
    on the key size.
  • 46:20 - 46:22
    But that's where more research is needed.
  • 46:22 - 46:26
    If you need something where you can get
    a guarantee of 100 years security,
  • 46:26 - 46:27
    take this one,
  • 46:27 - 46:29
    it's not small,
  • 46:29 - 46:32
    it's fast, but it's not small,
  • 46:32 - 46:34
    and hopefully in 5 years,
    less than 5 years,
  • 46:34 - 46:37
    they can give you something
    which is smaller
  • 46:37 - 46:40
    and still as secure.
  • 46:40 - 46:40
    djb: Okay.
  • 46:40 - 46:45
    There are lots of possibilities for
    what the smaller things might be,
  • 46:45 - 46:48
    for instance, there's something
    called QC-MDPC,
  • 46:48 - 46:49
    there's actually lots and lots
  • 46:49 - 46:51
    of variations of McEliece
  • 46:51 - 46:52
    that people have proposed,
  • 46:52 - 46:54
    and some of those variations have held up,
  • 46:54 - 46:55
    some of them haven't.
  • 46:55 - 46:58
    QC-MDPC is something that has
    held up so far,
  • 46:58 - 47:00
    but how many people've looked at it,
  • 47:00 - 47:04
    and what's going to happen when
    more attacks get optimised?
  • 47:04 - 47:06
    You can't be trusting something which
  • 47:06 - 47:09
    is new or hasn't been studied enough,
  • 47:09 - 47:11
    or hasn't been studied
    in the right directions,
  • 47:11 - 47:13
    you also have to be sceptical
    about crypto.
  • 47:13 - 47:15
    There's, well, lots of proposals,
  • 47:15 - 47:18
    QC-MDPC looks like one of the most
    interesting ones,
  • 47:18 - 47:21
    that nobody's been able to damage
    its security,
  • 47:21 - 47:24
    for 2^80 pre-quantum security,
  • 47:24 - 47:25
    which is not very good,
  • 47:25 - 47:26
    but, just as an example,
  • 47:26 - 47:30
    they have 0.6 kilobytes, or 600 bytes,
  • 47:30 - 47:32
    for the public key,
  • 47:32 - 47:34
    and that's a very reasonable size
    for a public key,
  • 47:34 - 47:35
    not as small as ECC
  • 47:35 - 47:37
    but it's quite tolerable.
  • 47:37 - 47:39
    Um, lattice-based crypto,
  • 47:39 - 47:40
    there's NTRU, for example,
  • 47:40 - 47:42
    that's been around since the 1990s,
  • 47:42 - 47:45
    and maybe that's enough time to start
    getting confident,
  • 47:45 - 47:47
    but, well, again, there's
    lattice-based systems
  • 47:47 - 47:48
    that get proposed and broken,
  • 47:48 - 47:52
    for instance, there's a system from
    Smart-Vercauteren in 2009,
  • 47:52 - 47:55
    that was, it's not broken pre-quantum,
  • 47:55 - 47:59
    but it was shown in 2014-2015,
    some follow-up papers,
  • 47:59 - 48:02
    to be broken in polynomial time
    by a quantum computer.
  • 48:02 - 48:05
    So, it's a lattice-based system which
    sounded good at the beginning,
  • 48:05 - 48:08
    but is definitely not going to be part of
    post-quantum cryptography.
  • 48:08 - 48:10
    There's multivariate-quadratic,
  • 48:10 - 48:12
    now those have
    the interesting feature that
  • 48:12 - 48:15
    the signatures they provide
    can be very very small,
  • 48:15 - 48:17
    like, you can have 100-bit signatures
  • 48:17 - 48:19
    and still get some reasonable security
  • 48:19 - 48:21
    that nobody knows how to break these,
  • 48:21 - 48:23
    well, there's lots and lots
    of these proposals
  • 48:23 - 48:25
    and some of them are broken,
    some of them...
  • 48:25 - 48:28
    HFEv-, that's a multivariate
    quadratic system
  • 48:28 - 48:31
    that's been unbroken for 20 years.
  • 48:31 - 48:32
    Maybe it will continue holding up,
  • 48:32 - 48:34
    but, well, how many people have looked?
  • 48:34 - 48:37
    You have to make sure enough people
    look at these things.
  • 48:37 - 48:39
    The reason we like these
    simple systems from the 70s is
  • 48:39 - 48:40
    enough people have looked
  • 48:40 - 48:43
    but maybe if you've got more serious
    performance constraints
  • 48:43 - 48:44
    you should look at these other things,
  • 48:44 - 48:46
    and of course we are looking at
    these other things,
  • 48:46 - 48:48
    trying to figure out what's secure,
  • 48:48 - 48:52
    and how well we can actually, er,
  • 48:52 - 48:54
    choose among all these
    different possibilities.
  • 48:54 - 48:56
    Something else, just last mention here,
  • 48:56 - 48:57
    is isogeny-based,
  • 48:57 - 48:59
    this is for people who like
    elliptic curves,
  • 48:59 - 49:03
    that there is maybe a way to use
    elliptic curves post-quantum,
  • 49:03 - 49:04
    and this has the interesting feature
  • 49:04 - 49:08
    that it does exactly the same data flows
    as Diffie-Hellman.
  • 49:08 - 49:10
    So everything you're used to doing
    with Diffie-Hellman,
  • 49:10 - 49:12
    and having, like, a secret key over here
  • 49:12 - 49:13
    and a public key over there,
  • 49:13 - 49:16
    agree on a shared secret,
  • 49:16 - 49:18
    that you can also do with
    isogeny-based systems,
  • 49:18 - 49:21
    but only a few people
    have studied the security
  • 49:21 - 49:22
    and maybe this'll also get broken.
  • 49:22 - 49:25
    So, a lots more work,
    lots more possibilities.
  • 49:25 - 49:28
    Last slide, if you're interested
    in more information
  • 49:28 - 49:30
    here are a few places to look,
  • 49:30 - 49:32
    first of all you can go to pqcrypto.org,
  • 49:32 - 49:37
    so this is our first survey site
    for post-quantum cryptography,
  • 49:37 - 49:38
    and the biggest chunk of information there
  • 49:38 - 49:42
    is bibliography, and if anybody has
    newer papers,
  • 49:42 - 49:46
    if you happen to write papers on
    post-quantum crypto,
  • 49:46 - 49:47
    and you'd like us to add those,
  • 49:47 - 49:48
    then just let us know,
  • 49:48 - 49:51
    um, and then, well,
    we also have on the front page
  • 49:51 - 49:54
    things like pointers to all
    the PQCrypto conferences,
  • 49:54 - 49:55
    that's the main place to look,
  • 49:55 - 49:57
    go to pqcrypto.org and follow links to,
  • 49:57 - 50:00
    for instance, the February
    Japan conference.
  • 50:00 - 50:02
    Then pqcrypto.eu.org, that's the main page
  • 50:02 - 50:05
    for the EU project that Tanja mentioned,
  • 50:05 - 50:08
    which is putting out as it progresses,
  • 50:08 - 50:10
    well, it just started this year, but
  • 50:10 - 50:13
    it's putting out, soon, free libraries!
  • 50:13 - 50:16
    Software libraries, for actually doing
    post-quantum cryptography.
  • 50:16 - 50:18
    And benchmarking results,
  • 50:18 - 50:19
    so you can actually say
  • 50:19 - 50:21
    "Yeah, I've got the following performance
    constraints here,
  • 50:21 - 50:23
    that's what I'm able to use."
  • 50:23 - 50:25
    And then in 2017, there's going to be
  • 50:25 - 50:29
    a workshop, and a summer school, maybe
    it'll be a spring school, we'll see,
  • 50:29 - 50:34
    if you're interested in the Twitter feed
    for that, then twitter.com/pqc_eu
  • 50:34 - 50:37
    and final resource on the slide is you.
  • 50:37 - 50:40
    You have the responsibility
    if you care about crypto,
  • 50:40 - 50:42
    then you have to get used to this stuff.
  • 50:42 - 50:44
    You have to learn about hash-based,
  • 50:44 - 50:47
    code-based, maybe lattice-based,
    multivariate quadratics,
  • 50:47 - 50:50
    these are the things which will be
    the future of crypto.
  • 50:50 - 50:54
    In the future, all of crypto will be
    post-quantum crypto,
  • 50:54 - 50:57
    because eventually the attackers
    will have quantum computers.
  • 50:57 - 50:58
    If you want to adapt to that future,
  • 50:58 - 51:00
    then, well, take a look at these sytems
  • 51:00 - 51:02
    and see, maybe find improvements,
  • 51:02 - 51:04
    then, cool, then let us know,
  • 51:04 - 51:06
    and, you know, publish papers,
  • 51:06 - 51:08
    integrate them into real applications,
    networking applications,
  • 51:08 - 51:10
    implement the things
    that aren't implemented,
  • 51:10 - 51:11
    speed them up,
  • 51:11 - 51:13
    there's lots of work that
    still has to be done.
  • 51:13 - 51:15
    That's it, thank you for your attention.
  • 51:15 - 51:29
    applause
  • 51:29 - 51:34
    Herald: Wow. Now we'll have some
    short questions please.
  • 51:34 - 51:36
    Because we're a bit late on time.
  • 51:36 - 51:40
    Questioners, go around ahead,
    there's a mike there,
  • 51:40 - 51:42
    talk into it please.
  • 51:42 - 51:43
    Can we have mike 1?
  • 51:43 - 51:46
    Q: Oh, okay. Uh, quick question.
  • 51:46 - 51:50
    So there was this result of
    Laszlo Babai that there's a,
  • 51:50 - 51:56
    that graph isomorphism has a
    quasipolynomial time algorithm,
  • 51:56 - 52:00
    um, not really knowing the subject at all,
  • 52:00 - 52:04
    there's some very, very
    superficial similarities,
  • 52:04 - 52:09
    like, that is a hidden subgroup
    problem, basically.
  • 52:09 - 52:12
    Um, is there going to be any, like,
  • 52:12 - 52:14
    is there any indication that the methods
    he used in that proof
  • 52:14 - 52:17
    are relevant to breaking, like,
  • 52:17 - 52:20
    to weakening NTRU or things like this?
  • 52:20 - 52:26
    djb: That's a good question. So, the, um,
    the graph isomorphism advance now,
  • 52:26 - 52:27
    is basically saying,
  • 52:27 - 52:30
    so, graph isomorphism is a problem
    which was famous as being
  • 52:30 - 52:33
    not know to be solvable in polynomial
  • 52:33 - 52:35
    or even, like you said,
    quasipolynomial time.
  • 52:35 - 52:38
    Um, except there were some really good
    software algorithms
  • 52:38 - 52:41
    which would solve most cases of it,
    really quickly.
  • 52:41 - 52:43
    There were just some really weird,
  • 52:43 - 52:44
    highly symmetric cases,
  • 52:44 - 52:45
    that were hard to solve
  • 52:45 - 52:47
    and that's what Babai managed
    to completely kill now,
  • 52:47 - 52:49
    so he's handled all the cases.
  • 52:49 - 52:52
    But we try to stay away from
    problems like that in crypto,
  • 52:52 - 52:55
    so, an example that's very closely
    analogous to that is
  • 52:55 - 52:57
    what's called support splitting,
  • 52:57 - 52:59
    which is a certain type of attack strategy
  • 52:59 - 53:01
    against code-based crypto
  • 53:01 - 53:03
    if somebody gives away lots of information
  • 53:03 - 53:05
    from the legitimate user.
  • 53:05 - 53:07
    And that's something where the
    support-splitting algorithm
  • 53:07 - 53:09
    works in most cases,
  • 53:09 - 53:13
    but it kind of fails in some corner cases,
  • 53:13 - 53:16
    and, well, we try to stay away from
    thinking about this anyway,
  • 53:16 - 53:19
    because you just don't want to give
    somebody that extra information,
  • 53:19 - 53:23
    but if you did, then maybe Babai's
    technique could be useful there.
  • 53:23 - 53:26
    Herald: Thank you. This talk is not over.
  • 53:26 - 53:30
    If you're leaving, which is okay,
    please be silent.
  • 53:30 - 53:34
    Next question, number 3, no, number 1.
  • 53:34 - 53:36
    Q: Uh, hello, thank you for the talk.
  • 53:36 - 53:40
    Um, how are the chances to have something
    like forward secrecy with that?
  • 53:40 - 53:44
    I recognise the last algorithm
    has a chance
  • 53:44 - 53:45
    to reuse Diffie-Hellman,
  • 53:45 - 53:48
    that's possibly the only one?
  • 53:48 - 53:52
    Lange: So, if you think that
    forward secrecy means Diffie-Hellman,
  • 53:52 - 53:56
    you can have forward secrecy
    from normal encryption algorithms,
  • 53:56 - 53:58
    at the expense of generating
    a new key each time.
  • 53:58 - 54:01
    You can have forward secrecy with RSA,
  • 54:01 - 54:03
    if Alice talking to Bob starts by saying
  • 54:03 - 54:06
    "Okay, this is my one-time RSA key,
  • 54:06 - 54:08
    and I send this to Bob,
  • 54:08 - 54:13
    with a request to encrypt to this key."
  • 54:13 - 54:16
    If Alice never reuses this key,
  • 54:16 - 54:18
    then this method is forward-secure.
  • 54:18 - 54:21
    And similar to how you can
    do this with RSA keys,
  • 54:21 - 54:23
    you can also do this with McEliece keys.
  • 54:23 - 54:25
    At the moment, there is a difficulty
  • 54:25 - 54:29
    that the keys are very large.
  • 54:29 - 54:33
    It is inconvenient when you want
    to start talking,
  • 54:33 - 54:36
    "Hey, I'm a client, hello server,
    please talk to me",
  • 54:36 - 54:37
    and the first thing you have to do
  • 54:37 - 54:42
    is transmit a megabyte of key.
  • 54:42 - 54:44
    On the other hand, you can do it.
  • 54:44 - 54:48
    It just requires you to engineer
    your protocol to expect,
  • 54:48 - 54:51
    yes, you have to send a few packages.
  • 54:51 - 54:54
    And then it has all the
    forward secrecy that you want.
  • 54:54 - 54:58
    Q: But, uh, a way without
    transferring the key,
  • 54:58 - 54:59
    like Diffie-Hellman?
  • 54:59 - 55:03
    Lange: But, Diffie-Hellman
    is transferring a key.
  • 55:03 - 55:03
    Q: Okay.
  • 55:03 - 55:05
    Lange: I mean, you're basically
    transferring
  • 55:05 - 55:07
    the first part of a discrete log pair.
  • 55:07 - 55:10
    If Alice sends a*p, and there is
    some one-time key,
  • 55:10 - 55:12
    she's sending a public key.
  • 55:12 - 55:16
    It's just that the method of how
    those two public keys interact
  • 55:16 - 55:19
    is slightly different from how
    RSA encryption works.
  • 55:19 - 55:21
    Q: Okay, thank you.
  • 55:21 - 55:25
    Herald: Thank you. Do we have
    an Internet message? Question?
  • 55:25 - 55:30
    Signal Angel: Actually, we do. There are
    two questions that are somehow related.
  • 55:30 - 55:31
    The first one is:
  • 55:31 - 55:37
    Given that there is no actual working
    quantum computer,
  • 55:37 - 55:41
    how do you start developing
    a crypto algorithm?
  • 55:41 - 55:42
    Where do you start, how do you design it,
  • 55:42 - 55:46
    how do you test it? Is there a way
    to prove that it's secure?
  • 55:46 - 55:49
    And the second question is related:
  • 55:49 - 55:55
    The whole thing is based on the property
    of the hash functions being one-way,
  • 55:55 - 55:58
    how does one know that there is no
    quantum algorithm
  • 55:58 - 56:00
    that breaks this property?
  • 56:00 - 56:02
    Can you prove this?
  • 56:02 - 56:04
    djb: Okay. For both of these questions,
  • 56:04 - 56:06
    the technique that the community
    goes through,
  • 56:06 - 56:08
    that we all go through,
    is cryptanalysis.
  • 56:08 - 56:11
    So we have as many smart people as
    we can find
  • 56:11 - 56:13
    focusing on these problems and saying
  • 56:13 - 56:17
    "Can you find an algorithm which is
    breaking these problems
  • 56:17 - 56:19
    better than any previous algorithms can?"
  • 56:19 - 56:21
    and we put as many incentives as we can
  • 56:21 - 56:23
    so that we try to get as many smart people
  • 56:23 - 56:25
    to stay ahead of the bad guys,
  • 56:25 - 56:27
    and hopefully find the best algorithms.
  • 56:27 - 56:29
    But there's no guarantees in this.
  • 56:29 - 56:30
    And you do always have to be sceptical
  • 56:30 - 56:33
    about whether people have
    actually looked at, for instance
  • 56:33 - 56:35
    quantum algorithms to attack systems.
  • 56:35 - 56:37
    And there is that extra difficulty
  • 56:37 - 56:40
    that the first part of the question,
    at the beginning, was saying,
  • 56:40 - 56:42
    that we don't have a quantum computer.
  • 56:42 - 56:45
    So if we're trying to verify quantum
    algorithms that we're developing,
  • 56:45 - 56:48
    we don't get to experiment with them.
  • 56:48 - 56:51
    That's the usual procedure for
    making sure your algorithms work.
  • 56:51 - 56:53
    In state-of-the-art cryptanalysis,
  • 56:53 - 56:55
    like the number field sieve for factoring,
  • 56:55 - 56:58
    that does not have a proof that
    it works in any particular,
  • 56:58 - 57:00
    well, at the speed that we think,
  • 57:00 - 57:01
    it works out from experiment.
  • 57:01 - 57:03
    So experiments are really important,
  • 57:03 - 57:06
    because we don't have proofs
    for state-of-the-art cryptanalysis,
  • 57:06 - 57:10
    and that's something where it's actually
    really tough for quantum computers.
  • 57:10 - 57:12
    Of course eventually we'll all have
    quantum computers,
  • 57:12 - 57:15
    and there's ideas for simulating
    quantum algorithms
  • 57:15 - 57:18
    which have had some success
    at verifying that algorithms work
  • 57:18 - 57:21
    even though we can't actually
    run them yet.
  • 57:21 - 57:25
    That we're actually able to verify
    a simulation of those algorithms.
  • 57:25 - 57:28
    Lange: Let me do a second part of this.
  • 57:28 - 57:31
    Um, when we use quantum cryptanalysis,
  • 57:31 - 57:33
    for estimates, we usually go
    for the worst-case estimate.
  • 57:33 - 57:39
    So we say, well, McEliece, at worst,
    gets broken to half the security level.
  • 57:39 - 57:41
    Most likely it won't be that fast,
  • 57:41 - 57:46
    but we're staying on the side
    where we're very confident.
  • 57:46 - 57:48
    Um, if I understood correctly
    there was also the part of the question,
  • 57:48 - 57:50
    how can we test the algorithms?
  • 57:50 - 57:53
    If this is for
    the constructive algorithms,
  • 57:53 - 57:54
    then all the algorithms we analyse,
  • 57:54 - 57:57
    all the algorithms we propose
    for post-quantum crypto,
  • 57:57 - 58:00
    are algorithms that you can run on
    your normal computer.
  • 58:00 - 58:02
    So, you can test those, you can run those,
  • 58:02 - 58:04
    we have benchmarking numbers from those,
  • 58:04 - 58:07
    on our current hardware.
  • 58:07 - 58:12
    Herald: We'll do two more questions,
    please. Number 1.
  • 58:12 - 58:16
    Q: Yeah, I got a question on
    the practicality of the attacks.
  • 58:16 - 58:19
    So, um, if we assume there is
    a quantum computer,
  • 58:19 - 58:22
    how much time will it take in practice,
  • 58:22 - 58:23
    order of magnitude,
  • 58:23 - 58:26
    to break, let's say, RSA 2048-bit key?
  • 58:26 - 58:29
    Is it on the order of hours,
    weeks, months, years?
  • 58:29 - 58:31
    Lange: snaps fingers Done.
  • 58:31 - 58:32
    Q: Okay, thanks.
  • 58:32 - 58:33
    laughter
  • 58:33 - 58:36
    djb: That was easy!
    Herald: Number 3.
  • 58:36 - 58:37
    Q: Okay.
  • 58:37 - 58:39
    Herald: Talk into the mike, please.
  • 58:39 - 58:41
    Q: Thank you. So, it's very,
    very nice to have
  • 58:41 - 58:46
    both quantum encryption and signing,
  • 58:46 - 58:49
    but do you know anything about
    some other cryptographic primitives,
  • 58:49 - 58:52
    such as zero-knowledge proofs?
  • 58:52 - 58:53
    Lange: Well, I mean, zero-knowledge proofs
  • 58:53 - 58:57
    are basically signatures
    which are not interactive.
  • 58:57 - 59:00
    So if you have something which is, um,
  • 59:00 - 59:02
    a primitive for a signature is usually
    very closely related
  • 59:02 - 59:04
    to zero-knowledge proofs.
  • 59:04 - 59:06
    So, there is work going on,
  • 59:06 - 59:08
    we are focusing on
    the most important things
  • 59:08 - 59:10
    that we see on the Internet,
  • 59:10 - 59:13
    but, that shouldn't mean that people
    shouldn't do research on it.
  • 59:13 - 59:17
    Please do research on
    zero-knowledge proofs!
  • 59:17 - 59:22
    Herald: Okay. Last question. Number 1.
  • 59:22 - 59:25
    Q: So, why do you put so much emphasis
  • 59:25 - 59:29
    on smaller key sizes and
    on performance in encryption,
  • 59:29 - 59:35
    um, especially in a delicate topic like
    post-quantum computing?
  • 59:35 - 59:37
    Why can't we just use 1-megabyte keys
  • 59:37 - 59:42
    and why can't we just use a few seconds
    instead of miliseconds
  • 59:42 - 59:44
    to compute those?
    Lange: So...
  • 59:44 - 59:45
    Q: What's the the problem here?
  • 59:45 - 59:48
    Lange: We are suggesting
    to use a key of 1 megabyte.
  • 59:48 - 59:52
    So, our recommendation that we have on
    the Internet on the pqcrypto.org page
  • 59:52 - 59:56
    are precisely using this system
    which has a 1-megabyte key.
  • 59:56 - 59:58
    The nice thing is, that actually
  • 59:58 - 60:02
    encryption and decryption
    are very efficient.
  • 60:02 - 60:04
    But that was not our main goal,
  • 60:04 - 60:06
    our main goal was to get something
    which is very secure,
  • 60:06 - 60:11
    and where we have a high confidence
    that we actually understand the attack.
  • 60:11 - 60:14
    And then, well, once we have this system,
  • 60:14 - 60:18
    then you try to optimise
    how to implement it,
  • 60:18 - 60:19
    and the implementation,
    when we looked at the numbers
  • 60:19 - 60:22
    is actually faster than
    elliptic curve implementations
  • 60:22 - 60:24
    except for the size.
  • 60:24 - 60:26
    So, you get a very nice speed,
  • 60:26 - 60:32
    even though it was not our
    target for optimisation.
  • 60:32 - 60:33
    Herald: Okay, this is it.
  • 60:33 - 60:35
    Thank you very much,
    let's have a final hand
  • 60:35 - 60:38
    for Tanja Lange and djb Bernstein!
  • 60:38 - 60:46
    applause
  • 60:46 - 60:51
    postroll music
  • 60:51 - 60:58
    Untertitel erstellt von c3subtitles.de
    im Jahr 2016. Mach mit und hilf uns!
Title:
djb, Tanja Lange: PQCHacks
Description:

more » « less
Video Language:
English
Duration:
01:00:58

English subtitles

Revisions Compare revisions