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