speaking of looking back I remember
maybe 15 years ago Microsoft was still
relatively inward focused I guess in the
security arena and it took a little bit
of time before they basically sacrificed
a young engineer by the name of Rob
Henson by sending him to a first
conference and the first time a
Microsoft security guy showed up at a
first conference he was easily the most
popular person in both good and bad ways
at the conference but Rob was amazing he
took all of it and was happy to work
with everybody in bringing Microsoft
into part of this community and as a
result the nsrc has been a huge
proponent and and and sponsor and
supporter and in any possible way of
first conferences it's interesting
because our keynote speaker Brian
LaMacchia
works in a different part of Microsoft a
crypto part and obviously he knows the
nsrc folks but it when first reached out
to him and asked it he'd be interested
in doing a keynote he didn't know al
awful lot about first being on the Crypt
both side so he reached out to the nsrc
and said you know anything about these
guys and obviously the endorsement was
good because we are very fortunate they
have Brian here to talk to us as I said
he is the director of security of the
security and cryptography group within
the Microsoft Research arm he's had
various roles at Microsoft for about 20
years
security architect he's part in industry
he's part of the crypto review board
involved of another things there he's an
adjunct professor at the at Indiana
University and I promise I did not know
that when I chose to warm my Purdue
University shirt today and he is also
the treasurer of the International
Association of Cryptologic research and
I am very proud and happy to have him
here today so Brian LaMacchia thank you
[Applause]
thank you all
ok the laptop decided to rotate yeah can
you guys see that this is going to be
really interesting here hold on a sec it
went into portrait mode so I got a this
is not my laptop so hi I'm Brian
while the laptop is coming back up here
for a minute
hopefully ok
tech support may want to come up and
like rotate this back because of course
Windows 10 has decided that I'm looking
at this the wrong way so let me start by
saying thank you very much it's a
pleasure to be here as they said yeah I
run the security and crypto group at
Microsoft Research where we focus on
trying to both do long term research for
the needs of the company out 10-15 years
as well as near-term sorts of things
I've been asked here in continuing the
theme of keynotes of the morning
keynotes I'm here to talk to you about
how we're going to make sticks and taxi
quantum resistant and we'll spend the
next hour doing that actually assuming
that my slides come up we'll actually
talk about more general issues in
quantum resistant cryptography
how can you throw it in the landscape
mode
okay so let me let me try to I don't
have my slider so um it went into
portrait mode yeah yeah take the take
the landscape but yeah you got them what
what do you want me to ctrl alt down
there
well now it's upside down okay I think
we got it back thank you you can tell
I'm in research at MSR okay but I will
send that over to the office team there
we go have I and I got a clicker here so
this works
can I Drive off of that okay
you're going to drive I'll Drive it
manually that's fine there we go yay
okay what's a Microsoft keynote without
a little bit of problem with office in
Windows right okay so let me let's get
back on track here um why am I here to
talk about quantum resistant crypto and
to give you some motivation for this
let's start by looking back at how
computing has changed over really the
last 2,000 years we don't normally think
about computing as having a 2,000 year
history but if you actually go back to
the Antikythera mechanisms and other
sorts of very early mechanical devices
that were used for doing astronomical
calculations there is a long history of
us actually using physics in one way or
another to build computing devices
whether mechanical whether something
like Babbage's Difference Engine when we
move to electrical computer starting
with the e niak more recently the de
Haan hey - which until very recently was
the number one computer on the top 500
supercomputers it's now been superseded
by another Chinese supercomputer and the
reason I'm here today is because we are
we believe we are on
cusp of another change in fundamental
physics for computing just like the move
from mechanical to electrical we believe
that we are now going to be able to
build computers built on top of quantum
physical properties that have a
different computing model and they admit
or will admit if we can build them big
enough and coherent long enough to solve
different classes of problems quickly
and Microsoft happens to have a group
that sits right above me in Microsoft
Research is working on topological
quantum computing and there are other
research groups around the world working
on different types of quantum computing
and the good news about this is that if
you could actually build a quantum
computer it's going to let you solve a
whole bunch of problems quickly that we
can't solve today bad news from my
perspective which I'll get to for a
moment is I'll let you solve a whole
bunch of problems that you can't solve
quickly today like all the ones we use
for cryptography so we have to have it
two defenses against that um we
celebrated recently the 50th anniversary
of Moore's law right this is a chart I
pulled just recently again off top 500
of basically the top number of flops per
second of the the triangles here in the
middle is the number one machine on the
list that's the number 500 machine on
the list that's the sum of the top 500
machines and you can see on a log scale
on the left it's that very nice growth
line that we expect from Moore's Law
that seems to be continuing pretty much
on and on and it is natural for us to
ask the question is there anything we
can't solve on digital computers because
frankly we got plenty of compute power
and if there's a problem that we can't
seem to solve today with what we've got
we can either put more compute power out
there or we can wait a little bit and
wait for everything to get faster and
all of a sudden we can solve more things
and that's how that approach is kind of
taken on the way there are a class of
problems though that don't fit that
model and we depend upon them for
securing all of our electronic commerce
and a lot of online businesses such
today and that's the problems that
cryptography are based on and these
problems are just intractable with
classical computing factoring is the one
that's most common it's the fundamental
problem underneath the RSA encryption
and digital signature algorithm every
day this gets used and
time you connect to an HTTP website
you're probably using RSA or using a
related problem on elliptic curves and
this is the 2048 bit RSA challenge
problem that is the product that is a
2048-bit number that is the product of
two 1024 bit primes if I give you the
two 1024 bit Prime's and I say would you
please go multiply them that's easy we
can do that quickly if I give you the
product and I say find the two numbers
that multiply to that that's really hard
we don't have a polynomial time
algorithm to do that that is outside of
our bounds in fact if you were to go get
a bunch of CPUs you need a billion CPU
years with current technology and what
we know about the fastest known hours to
do that but if I can build a quantum
computer that's big enough and big
enough is really important here I don't
just need like two little quantum bits I
need about twice the number of quantum
bits as that number I need four to five
thousand quantum bits logical quantum
bits that are coherent I can solve that
in a hundred seconds that's the type of
breakthrough that is the potential of
quantum computing if we're actually able
to build it now that's great unless
you're a cryptographer trying to protect
information because we have been
dependent on the exponential work factor
of adding a couple more bits to the
encryption keys or to the size of RSA
numbers to making the amount of work
that it takes to break it that's how
we've been staying at a Moore's Law as
computers have gotten faster and faster
we've upped our key sizes but we've only
had to up our key sizes a little bit to
account for great growth in the amount
of compute power that's available okay
we believe that a how can I put this a
well-funded nation state agency or
similar sized organization could
probably gather enough compute power
together in secret to factor a 1024 bit
RSA number we don't think anybody's
actually got enough compute power to do
a 2048 but number because that's so far
out of reach of what we think is
physically possible but quantum
computing changes that and we have
actually known that fact since 1994 when
Peter shor at 18 T Bell Labs came up
with a quantum based factoring algorithm
and what Pete what Peter showed was that
if you had a quantum computer you could
actually solve a subproblem of the
factoring for all
in polynomial time and that reduced the
entire problem so this is why we are all
theoretically worried about this and
since 1994 it's been a theoretical
concern and nobody was really a
practical concern we didn't see any way
to build a quantum computer and now you
know we're starting to get some sense
that that might be true and it's not
just factoring okay if you look at
everything that we use in contemporary
cryptography today and for example take
the most common TLS cipher suite that's
out there so if you're running HTTP
you're running TLS you end up using
elliptic curve diffie-hellman ephemeral
for a key exchange and you use RSA for
validating those certificates for server
and maybe client and then you do some
symmetric cryptography with AES and shot
256 on the inside all of those
algorithms to a greater extent or a
lesser extent can be solved more quickly
if quantum computers are available that
is if your attacker has access to one
they can do something for the
fundamental math the number theory
problems underlying RSA factoring and
elliptic curve diffie-hellman they all
fall and there's no way to resolve that
because you can just build you double
the key length for the RSA you just
double them or quantum bits and the same
happens on the elliptic curve side you
actually need about six times the number
of quantum bits for elliptic curve but
the curves are smaller for AES and shot
to the quantum attacks aren't quite as
big what they do is they reduce the
number of bits the effective length the
effective length of bits in half so in a
AES 128-bit key that's a very commonly
saw you sized a two to the 128 bit work
to brute-force it quantum makes at two
to the 64 so the answer there should
double the key length and you go to to
256 that's what we do with hash
functions so we're not really as worried
about the far side of the screen as we
are about the number theory now where
are we aquatic computing
well they look something like this this
is the photo from Charlie Marcus's lab
in Copenhagen Denmark there well he's
one of the groups that collaborates with
Microsoft Research on building quantum
machines I love putting these pictures
in because cryptographers have no fancy
pictures we have nothing to show you
okay but these guys they have all the
cool equipment right this is the
dilution refrigerator logical
wanna bits and experiment with it and
it's really really cold and we don't
even know how we're gonna get data in
and out of there yet
but that's kind of what they're building
and they're demonstrating this problem
and there's other groups iBM has done
some stuff with I think ion traps and
there's a couple other physics this is
not something we're going to deploy in
every Windows PC okay but well-funded
organizations if you can build and make
enough wonnum bits out of this could
start to actually do something
interesting with it and there's a lot of
interesting problems that you can kind
of solve so where are we on this journey
right is this a cold fusion situation
when we don't think so but we're still
just somewhere along the stack of
solving the engineering problems that we
have to solve okay we are not in
imminent danger of having a 9000 quantum
bit computer tomorrow okay this is
actually a graph from a debragoff
science article from 2013 where we are
basically you know three or four steps
along the way but we are making progress
or I should say the groups that are
doing that are trying to build the
computers that got to break by stuff
they are making progress and we're
making progress in trying to defend
against that so this is kind of what's
happening in the world and you know the
question now is why should we care about
this now I'm up here telling you that
there's a threat that's going to come
sometime in the far future this
organizations worried about threats that
are happening right now and we all are
right we're trying to defend the
internet today against a bunch of things
so why do we care and what you know why
should you be thinking about this well
it's real simple we don't have a
large-scale quantum computer now but
there might be one and let's say 15
years okay could be 10 years it could be
20 years there's a few people to say
optimistically 5 years in which case
we're really in trouble but let's say
that roughly speaking just to put your
finger in the wind 15 years from now one
or more organizations will have access
to quantum computers big enough to break
these types of algorithms a well funded
organization have it a little bit sooner
but let's just say that
how long does it take to migrate the
internet to a new public key encryption
algorithm
it take took us at least a decade just
to switch hash functions we're still
trying to get rid of sha-1 you may have
seen the ongoing wars between the
browser organizations and some of the
other certificate authorities trying to
get sha-1 out of places before that it
was md5 we are not very good at
migrating the entire internet and all of
the embedded devices to new algorithms
and migrating a new public key algorithm
is going to be even worse
we haven't even standardized on anything
yet okay so that's a problem the second
one has to do with recording of
encrypted data we have to assume that in
communications that are encrypted today
may have lifetimes beyond the working
lifetime of the algorithms right if your
data is got a 20 year or 30 year
confidentiality lifetime that data could
be recorded by an adversary and could be
broken down the road and so even today
we have customers who are concerned
about the long term confidentiality of
the data that they sent and we need
answers for them so how long is it going
to take to even re-encrypt storage data
things like that and then to throw into
this mix we had this little announcement
from the US National Security Agency in
August 2015
now NSA doesn't say a lot very often
they don't really say a lot period in
2005 NSA came to the cryptographic
community they made an announcement at
the RSA security conference and they
announced something called suite B which
was their set of algorithms that they
were going to back and that they wanted
a the commercial industry to implement
for use in up - what up - top secret
which in NSA terminology isn't actually
that secret but it's top secret okay um
and this was a set of algorithms using
an elliptic curve and some curves they
specified an AES and shot - and we all
went and implemented that was one of my
jobs for vishton for this device none of
you probably ever heard of called a
Windows Phone that we that I did the
crypto for that
and the most interesting was that's been
what we've kind of been following the
guidance for 10 years and in an August
without any announcement NSA made an
update to their website it was a stealth
update that folks just kind of noticed
that talked about the transition of
quantum resistant crypto including this
line for those partners in vendor
have not yet made the transition to
sweet be elliptic curve algorithms we
recommend not making a significant
expenditure to do so at this point but
instead to prepare for the upcoming
quantum resistant algorithm translation
now you show that to developers that
you've just tasked with moving to
elliptic curve and they're going to say
why should I bother I'm going to move on
to something else and in fact there was
a lot of pushback to NSA saying well how
much should I invest to keep going you
know how much of my sunk cost is worth
going to elliptic curve and they did a
fact that said well if you like if
you're seventy percent of the way you
should kind of finish but if maybe if
you're not that far you should kind of
hold off because something might come
down the road it was very vague but this
caused um really everyone to take notice
that a transition was going to be coming
soon possibly by specification from the
NSA possibly by other folks so we needed
to really start paying attention so to
be clear what I'm talking about here are
cryptographic schemes that we believe
will be secure against both classical
attacks that we know today as well as if
your adversary has access to a big
enough quantum computer we come close
call this quantum safe for quantum
resistant this is not quantum
cryptography or quantum key distribution
some of you may have seen an article
that was in science I think yesterday
the day before about the Chinese
government demonstrated that they could
do spooky action at a distance over 1200
kilometers so they've got a satellite
now that actually creates entangled
photons and beams them down to two
different ground stations in China and
you know you change one photon here and
it changes 1,200 kilometers away that's
not what we're talking about we're not
going to be building you know photonic
equipment into every laptop that's
sitting out there but what I want to do
is come up with classical algorithms
that could resist the types of quantum
attacks as well as classical attacks so
that's the problem because I've got
things that aren't going to sell that
problem and the reason that we're really
concerned about this now is because of
the potential 15 year time horizon for
the work we have to go do so back in
2015 when I actually started this
project in my group I went upstairs to
the quantum guys and I said how long is
it going to take for us to get a
reasonable sized quantum computer and
they gave me the 15-year
number so I said okay it's January 2015
let's think about having a quantum
computer in 2030 what's that mean in
terms of doing the research on
algorithms trying to test them out
trying to standardize them trying to
even roll it out a big company like
Microsoft trying to get it into software
stacks and deploy I'm out of time that
was the conclusion in January 2015 was
we were right on the edge of being out
of time when you actually look at how
long it takes to do all of the work to
come up with a new set of cryptographic
algorithms and evaluate them and decide
whether or not they're actually usable
and deploy and now to give you an update
we're here at that point the double
question mark is five years from now if
we get a quantum computer by then that's
big enough we're not going to have stuff
deployed we're going to be in as they
say a world of hurt at ten years we're
likely to have more stuff ready to go
and through the standardization process
and deployment and the testing and that
sort of thing but that is why that the
cryptographic community is actively
working on this and it's also why the US
government is now launching a
competition to neh to develop and choose
new quantum resistant algorithms for
Standardization and that's what the NIST
PQ start is that's going to happen later
this year and that's a process that's
going to run for six years and this is
what that looks like so the Nationals
use of standard technology in the in the
US government standardized it chooses
and standardizes algorithms for US
government use these become FIPS federal
information processing standards AES was
developed through a public competition
that NIST ran sha-3 was developed
through a public competition and mr. and
Miss is now announced they're not
calling in a competition they're calling
it a selection process for certain
technical reasons on because they may
pick multiple algorithms but they've put
out a call for proposals there's a
deadline at the end of November for
schemes to be submitted by teams around
the world and then there's going to be a
six year bake-off and NIST will run this
process like they've run past things
where they sort of weigh the pros and
cons of particular schemes they asked
everybody to attack everybody else's
algorithms and at the end of this and
they hold a series
workshops and at the end of this the
goal is for nist to pick one or more
algorithms for key exchange of digital
signature that are resistant to
classical attacks and are resistant to
known quantum attacks and would be
suitable for deployment either alone or
what's more likely and we'll talk about
this in a little bit in combination with
existing schemes that we already have
deployed today to sort of do built-in
suspenders approach so the nist
competition right now is what's driving
work in this field in cryptography
across the world so there's a lot of
different groups i'm going to talk about
three efforts that my group at
microsoft's involved in in trying to
come up with algorithms that are based
on different hard problems that are as
resistant to classical attacks as RSA
note the curve but not subject to
quantum attacks and we're all that a
submitted earnest and then everybody's
going to kind of shoot at everybody else
and we're going to see who wins because
that's what cryptographers like to do so
i'm going to now give you a little bit
of math don't get scared arm i want to
talk a little bit and just give you a
flavor for the types of problems that we
and the other folks in the community are
looking at for new post quantum schemes
and my reason for doing that is mostly
to give you a feel for the fact that
none of these schemes have the same
complete engineering characteristics is
what we're all using today and what that
means is that when we transition to post
quantum schemes some of the assumptions
that are in our software stacks may
break like how long it takes to do a
signature or do a key exchange or how
small the data elements are that go by
the schemes that we are playing with
right now some of them are fast some of
them are slow some of them are small in
size some of them are larger size and
you need to understand what the
trade-offs are to think through what the
protocols look like what's best um to
give you a rough feel for the space
right now there are five main families
of hard problems or problems that we
think are hard that we are that we as a
community are looking at basing one or
more quantum resistant schemes on this
is just a list of some of the possible
the ones that are out there the five
families of problems are roughly coding
theory lattice based schemes the scheme
signatures use based off cryptographic
hashes
schemes based off like sahjhan EES which
are maps between elliptic curves and
multivariate based systems
none of these get used widely today and
anything that's currently being used Bom
they you know basically RS an elliptic
curve are all faster than all of these
schemes or have more knowledge about
them but this is the space where we
think that you can build on these
problems and we're not aware of any
quantum resistant attacks now my team at
Microsoft is involved in efforts in two
of these spaces in both the lattice
based scheme and the ISO geneva-based
scheme and those are things we'll talk
about in a little bit in terms of just
to give you a feel for what the
properties look like for them and we
also have just started developing a
signature scheme that builds off hashes
but doesn't really fit in that hash base
bucket the lwe stands for learning with
errors the r - LW e stands for ring
based where there's an algebraic ring
which adds some structure to it there's
pros and cons to doing that and then
super singular isogen we'll talk about
that in a little bit now when you go to
develop a new crypto system there's lots
of questions that you have to answer you
want to design better schemes you start
with a hard problem and you try to
figure out well how can I build a key
exchange scheme out of this hard problem
right you start with factoring and you
try to figure out how do I build a
digital signature algorithm or a key
exchange algorithm out of factoring it's
not as easy as just doing the raw RSA
operation there's a lot of engineering
steps that happen there because there's
a lot of ways that even if you do if you
have built on top of factoring the
system can fail and we have seen a
series of attacks against say the use of
RSA with with inappropriate padding
modes for example or or you know in
signature schemes and things like that
over the years so there's a lot of steps
to what you have to do when you pick a
problem and try to build a scheme on it
you try to improve the best known
classic and quantum attacks for all the
schemes and I'm going to talk about
we're not aware of a quantum attack
that's efficient that doesn't mean there
isn't one right we have no proofs in
this space that any of these problems
are the equivalent of np-hard ok there
is no proof that we're guaranteed so we
are this is an area of
to study and the classical attacks on
all these problems have not been studied
as much as factoring has which is one of
the reasons why we're not comfortable
necessarily using just any of these as a
replacement we do the
belt-and-suspenders approach because we
think that we would need we have more
confidence in the older problems in
cryptography old is really good I keep
telling my younger developers that old
is good we want problems to be studied
for a long time and we want folks to be
able to have caught and we build
confidence and problems by actually
trying to break them and failing okay so
we're going to try and improve our
classical attacks we have to pick
parameter sizes and there's a lot of
engineering trade-offs if you choose
your problem too big you end up spending
sending too much data and you slow down
too much for the amount of security that
you want to be competitive if you don't
choose your parameters big enough to try
to speed things up you might get broken
quickly and there's a lot of tension in
that and this is something that NIST
deals with did in their process in the
AES competition there was the the
algorithm Rhine ball which became AES
actually got submitted with more
encryption rounds in it than what NIST
ended up standardizing on because NIST
was worried about the overall time now
at the end of the day instructions got
put into CPUs for doing that and it was
less of a concern because your Intel
processor for example has an AES
instruction but it's one of the things
you have to weigh in trade-off you want
to develop fast and secure
implementations that's not necessarily
the easiest thing to do and then you
want to try to integrate them and test
them out in things like TLS and see how
well it runs and figure out where your
software stacks are going to break
because your certificates may be larger
or it may take a lot longer to do a
setup when you're trying to negotiate an
IPSec connection or things like that all
right so let me briefly talk about ah
three schemes and just give you a taste
for what's going on here and they're
called frodo cid h and picnic because we
have to have cute names for things let's
start with frodo which is our learning
with errors key exchange now why is it
call Frodo
it's called Frodo because a four of the
folks on this list originally did a ring
based learning with error scheme that
they integrated an OpenSSL as a proof of
concept that got improved by
another group into something called New
Hope which is sort of the leading ring
based scheme but the ring adds algebraic
structure so of course we want to
attempt to get rid of the ring okay
thus Frodo thus humor among
cryptographers okay so this is a this is
a collaborate clean researchers in my
own organization at Microsoft Google nxp
CWI in the Netherlands McMaster in
Canada and Stanford University and this
will be sort of one of the schemes that
we submit to the to the nist competition
the nice thing about these lattice
schemes are that they're fast and that
they're very competitive when in terms
of speed when you compare them to what
you're using today for RSA and elliptic
curves and i'll show you some numbers in
a bit the downside is that the keys are
relatively large and the assumptions
that we have made in software stacks
today about the size of our signature
keys or our encryption keys don't
necessarily hold when we're looking at
this problem so fast but large um okay
this is the this is the most math I'll
put on a slide at least for this scheme
arm the basic idea in a lattice scheme
and I'm going to walk you through a toy
example in a minute is we are choosing
samples and we're doing basically linear
algebra but adding a little bit of error
to it and I'm asking you to distinguish
between whether or not I actually did
linear algebra and added a little bit of
error or whether I picked some values at
random and that's a hard problem to
actually distinguish and we can use that
as the basis to build a scheme the best
known attack against this class of
problem are the set of algorithms like
lll that try to find the shortest vector
in a lattice and we can build post
quantum security of at least 130 bits of
security that's comparable to AES 128 in
the classical realm and we get 144 bits
of classical security what's this thing
looked like now let me show you the toy
example this is equivalent to doing RSA
with like 21 is 3 times 7 arm the
fundamental problem here is I'm going to
ask you to solve a system of linear
equations you choose a public matrix in
blue I have a secret little element in
red
and I multiply and I tell you what the
answer is now if I give you the blue
boxes and I ask you to find the red
boxes you'd all have to go back and
think through your basic linear algebra
that we've all forgotten for many years
ago but that's actually doable that
that's Gaussian elimination that is an
easy problem to solve and even though I
am doing that mod thirteen that's an
easy problem to solve okay okay trust me
it's it's relatively easy as these
things go okay okay it's as these things
go it's easy armed now I'm going to make
it harder and I'm going to add a very
small vector of error terms a little bit
of noise not a lot of noise just a
little bit of noise sampled from a
Gaussian distribution and I'm going to
say okay I'm going to take my matrix
that's public I have my secret value I
sample some error that gets mixed in and
I give you the answer back on the right
hand side and now there's two problems
there's a computational problem and a
different and a decision problem the
computational problem is if I give you
the blue elements and I tell you that
there is a secret red and some noise can
you find the red and that's equivalent
to basically I can cast this in lattice
terms I can cast it in matrix terms here
can you figure out what the red is where
the where the yellow is restricted to
being sampled off a particular small
error distribution that's hard the
equivalent decision problem is if I give
you the green and I give you the blue
can you tell me whether the green was
actually computed this way or did I just
make the green up and choose random
values okay that's actually hard that
decision problem is hard the
computations problem is hard and we can
use that difficulty to cast to make up
to make a public key scheme now I'm not
going to actually do it with seven by
four matrices over mod thirteen that's a
toy example okay what I'm going to do it
over is something in the real world
where I'm doing 752 by 8 over 16-bit
values and I'm sending about 11
kilobytes of data across the matrix and
that blue is basically the public key so
now I'm talking about instead of an RS
a 2048-bit value or a 4096 bit value I'm
talking about 11 kilobytes of data and
that's fast
that's fast but that's kind of one of
the problems we'll work on now let me
give you the other side of what we're
you know another example of a way that
the problem spins a different way
small but slow and this is what we call
Sid H which is super single oddity
diffie-hellman okay that's probably a
scary term but let me explain what we're
doing here this is a different
collaboration you'll notice that it was
Microsoft and Google on one of them it's
I've got some folks from Amazon on this
one who are working with us along with
researchers at Waterloo and Versailles
and Rob out University and here we're
looking at a different type of problem
on elliptic curves so those of you who
may have seen elliptic curves and the
pictures of how I do point addition it's
a similar sort of problem what I'm
trying to do is build a different type
of diffie-hellman on it and I get small
keys but it's relatively slow and here's
the though okay so a little bit more
math that I promised arm the basic idea
in um in Supercenter scientific helmet
is I take two elliptic curves that have
the same order and are not identical but
are similar in structure and I am trying
and I'm playing with mappings from one
curve to the other that maintain the
structure you might remember when you
took an algorithms class those all those
problems that you had to show where I've
got a graph and I've got another graph
and the graphs aren't identical but they
have the same structure and I can show
if I do a cyclic path and one it maps to
a cyclic path and another it's kind of a
similar sort of scheme here except I'm
doing this over curves that are a very
high order and I am trying to show
mappings and the analogy to thinking
about this to what you may have seen
with diffie-hellman is if I'm doing
diffie-hellman over finite fields Alice
and Bob each use a secret exponent and
the hard problem is to do a discrete log
right Alice chooses a secret and raises
a generator to her secret sends it to
the other side Bob takes that and raise
it to his secret power and they've
agreed because G to the a to the B is G
to the B to the a in elliptic curves we
do a complete it's an
that acceptance point addition on
elliptic curves in this space we're
doing the same thing with isogen YZ
we're applying two maps to elliptic
curves and if I gave you a diagram like
a diffie-hellman diagram everybody
starts with a public curvy zero Alice
moves horizontally Bob moves vertically
so Alice has some secret map gets a
curve Bob has a secret map five B gets a
curve and then they swap information and
they end up at the point in the lower
right but they've only they have not
passed enough information publicly to
let anybody who only sees the
information going across the wire to
compute that and I'm simplifying here a
bunch but basically we are able to use
this property of mapping between curves
of similar structures to build up a
similar analogy to what we do with
diffie-hellman now now we can set that
aside let's look at some performance
numbers and think about what the
trade-offs are if I'm running RSA today
with three kilobit keys I chose three
kilobits just to give you something that
was roughly the same size as this on a
good implementation on a core i7 running
at three and a half 3.4 gigahertz takes
me 4 and 1/2 milliseconds to do an RSA
key exchange and I end up sending about
384 bytes each way on the wire Alice to
Bob and Bob to Alice if I go to elliptic
curve and this is part of the reason why
cell phones tend to use elliptic curves
I can do equivalent security strength in
1.4 milliseconds and I'm only sending 32
bytes each way I don't have anything
that makes both the time requirements
and the size requirements with any of
the problems that we're looking at so if
you take New Hope which is are the best
sort of ring based lwe scheme out there
it's really fast but it's sending 2
kilobytes of data across each way you
take Frodo worried about the same speed
is e C D H but I'm sending 11 kilobytes
of data across the wire if I go to Sid H
I can get down to 500 bytes of data
that's great but it's going to take me
56 milliseconds and now we think we
might be able to another factor 5 out of
that but we're not going to be able to
necessarily hit the times so if I am
looking at deploying this into an
existing system part of
challenges I may not have the I may have
made engineering assumptions in my
implementations that I'm about to go
break when I try to deploy one of these
the situation gets a little bit worse in
signatures and let me talk about picnic
which is our code name for post quantum
non-interactive zero-knowledge
picnics a lot nicer um this is another
collaboration where researchers at
Microsoft are working with four other
institutions to come up with a signature
scheme that actually isn't based on any
number theoretic problems the way to
think about this scheme is that we are
using the hard problems of finding hash
collisions and we all know about hash
collisions because we've seen hash
collision attacks get used in places and
we understand how you know the how sha-1
has now fallen because it's been
demonstrated at actual collision and
sha-1 has been demonstrated and if you
have knowledge of a block cipher key or
you have knowledge of a hash collision
or a hash preimage we can actually build
that using a whole bunch of heavy
lifting in theoretical cryptography to
build something called a zero knowledge
proof and a zero knowledge proof is
exactly kind of what it sounds like I'm
able to prove convince you that I know
some secret without actually showing you
the secret and there's a whole body of
theoretical work in this space and what
we do is we are able to conduct they
start as interactive so I can convince
you I'm going to prove to you that I
know a fact you may query me a bunch of
you ask me a bunch of questions and I'm
able to only answer them and convince
you of that fact in multiple rounds if I
know the secret but I don't actually
relate to you the contents of the secret
itself that was kind of where zero
knowledge proof started and then in the
cryptographic theory space they turned
in a non-interactive where you sort of
capture all of the rounds into a package
and you can send the entire proof across
with many rounds of this of
interactivity sort of packaged up into
one non interactive send and we can do
that and build a signature scheme out of
that and we actually have code and we've
demonstrated this work in an open SSL
and it's slow and it's big so there's an
RSA 4096 bit signature if you were doing
that let's say you're a root CA that's a
common key size that you'd use for your
ca right Microsoft's roots are all 4096
bit RSA keys takes about six
milliseconds to sign with a good RSA
operation verifications very quick
because that's part of the way that the
trade-off works in RSA if you choose
your encryption exponent and properly
and you send about 512 bytes of data
across our schemes are currently you
know ten times slower five ten times
slower twenty-nine milliseconds 17
milliseconds one verify but I got to
send 120 kilobytes of signature across
now that hundred twenty-five kilobytes
of signature turns into a really large
x.509 server certificate open ssl we'll
deal with it but other systems may not
necessarily expect so and if you just
kind of throw those around because we
have made implicit assumptions about the
sizes of our authentication information
that may no longer hold now it gets even
worse for some of the other schemes this
is just a sampling of some of the
alternative post quantum schemes that
are currently floating around that
people are considering and you can see
that some of them want to send megabyte
keys across some of them want to spend
73 seconds to do computations I don't
think you really want to do that there's
trade-offs here and part of what's going
to get sussed out is in the
standardization effort is how do we pick
what the best trade-off is and there may
not be a single answer and depending on
upon what your engineering situation is
like you may have a very different
situation for example if you've got very
low bandwidth you may be willing to
spend a lot of time computing to send
very few bits across and with this cheap
but your compute power isn't you choose
a different sort of thing okay so now I
want to spend a little bit of time about
what do I think is going to happen sort
of looking ahead here ah and where do I
think things are going to go let me
first start with it's great to play with
these in the lab but until you actually
deploy them in real systems nothing
really matters so the first thing
everybody does is say let's do an
implementation we think the implication
is secure let's go try to
deploy it in the system and where's
everyone go first OpenSSL why because 99
and 44 100% of the internet secured over
TLS and that's the open-source
implementation or variants of open SSL
that everybody uses
so everybody plugs in there and sees how
well it works and these are numbers off
of saying off a test that we did and
integrating these various schemes into
open SSL with Apache on the server side
and all the code on this is available
I've got links at the end on it the key
point I want you to take away from this
is really simple this orange line here
is what we're all doing today with
elliptic curves and I've got one byte
kilobyte 10 and 100 kilobyte payloads in
terms of connections per second that I
can actually do using that scheme so
higher is better here that orange line
is sort of your baseline if you're
willing to throw away the classical
scheme where you today and just go with
the ring learning with eret you can
actually go faster but none of us
believe that that's actually got enough
maturity yet to do that so we're looking
at combination schemes where we would do
both belt-and-suspenders we would do
what we currently do today mixed with
the post quantum scheme in there we slow
down a little bit with some of our non
ring schemes we slow down a little bit
more entries another competitor out
there they're a little bit slower but at
most I'm paying a factor to cost if I
had to deploy an algorithm today and I
had to make my best guess I do have
things that we could put into the
OpenSSL stack and kind of put out we
would have to pay a performance cost on
doing that and we wouldn't know really
enough about the security of it but if
you said Brian we have to deploy
something today there are some
trade-offs and you could and we could do
something and open SSL hat we have
demonstrated we've actually got a full
demonstration with all of our algorithms
using the signature scheme as well and I
can do an open SSL and n handshake and
the code works pass is more data across
the certificates are a lot larger but we
can actually make that go now
okay everybody starts with open SSL but
there is more to the world than just TLS
ok um and I don't just mean I
and s mom and things like that so
everyone had started by doing their own
patches and there's lots of patches to
OpenSSL out and then Douglas stability
master said this is really kind of
stupid
why don't we define one API for everyone
to plug their post quantum schemes in
and then we'll integrate that into
everything so he started something
called the open quantum safe project
it's public it's up on github it's a
common API for all of these schemes and
we and now lots of other teams are
plugging into open quantum safe and then
we integrate that into things like open
SSL OpenSSH we just finished doing key
exchange on that codes coming shortly
and we're looking at integrating the
standard API into a lot of other
protocols as we need them to kind of
make things available and all of our all
of the things I've talked about so far
and other schemes from other teams are
available through this so if anyone in
here is actually looking at wanting to
play with this code start with oqs up on
on github and then start there because
that'll be your easiest way to start
integrating in a lot of different
options and then you can play mix and
max and test in your environment I'm
doing ok 10:30 so I just have a couple
more slides and I want to go to QA
because there tend to always be a lot of
questions about bottom here's the
takeaways I want you to come away with
off of this one quantum computers are
coming maybe not for a decade or more
maybe not for a little bit longer than
that but eventually within the
protection lifetime of data that we are
currently generating and saving today
and frankly even if it's a cold fusion
type thing where we never actually see a
quantum computer built merely the belief
that it is possible is going to cause
people to want this type of protection
so one of the things that that I am
dealing with on a regular basis are
customers who believe that the
capability will be in someone's hands in
a not-too-distant future even if not
certainly known publicly and that in and
of itself creates the need for quantum
resistant algorithms okay this is why
we're planning now because we have seen
how long it takes us to transition
from even for much simpler algorithms
okay we're still not all on shot too
we're still getting rid of sha-1 heck I
still have people inside of Microsoft
who come to me every so often with an
md5 hash function used somewhere in a
Microsoft codebase we acquire a little
company and we do the first code review
on their code and all of a sudden
they're using md5 all over the place or
Triple DES or something right um it
takes a long time once the systems
deployed and in fact frankly IOT is only
going to make this worse because we're
gonna start putting algorithms into
light switches that go into walls that
have no update paths and we're not gonna
be able to update them in 30 years that
are going to go for Oken so the most
important fact that I want you to take
away today is that to be rare for this
transition we have to have crypto agile
systems that is we have to have
engineering systems that are easy to
plug into play plug and play with new
cryptographic algorithms and change
things out and don't make assumptions
about key sizes or how long it takes to
do an operation or something like that
core algorithms in the IETF tend to be
pretty good at this the TLS community
has lots of cipher suites in fact they
have too many cipher suites in TLS 1.3
is going to restrict a bunch of those
but if you're building a system today or
you're specifying a system or you're
buying a system ask your vendor what are
you doing in terms of crypto agility how
do you move between algorithms how easy
is it to reconfigure if something new
comes along that I have to move to
because something new will come along
writeln is just going to standardize
something in six to seven years and
that's going to start the process so
that's sort of the most important
message don't build assumptions into
code and systems based on what the
algorithms are that we're using today
because those assumptions no longer hold
ok practical engineering options
actually do exist today we don't know
enough about them to want to use them by
themselves because they just haven't
baked long enough so hybrid schemes that
mix classical algorithms that were well
understood over the past thirty years
along with the new schemes is probably
the way we're going to go for the first
decade of deployment I expected for the
for at least the first ten years after
we start rolling these out
we're going to be doing hybrid schemes
and paying a little extra performance
costs on TLS where we mix and match a
classical RSA or elliptic curve schema
with one of these post quantum schemes
and eventually we may have enough
confidence in the post quantum schemes
to drop the RSA des love the curve but
that won't happen anytime soon it's
going to take a long time to update
software stacks speaking as someone who
worked on elliptic curve and Microsoft
took us a long time to build that out in
the stack it's real easy to say hey we
have support for the algorithm deep down
at the lowest levels of Windows it's
very different saying you can send a
secure email message out of Outlook and
and using elliptic curve algorithms or
you can spin up an entire software stack
or you can make sure that all of the
messages that you send back and forth
are our securities in the cuantas
algorithm and so for example consider
taxi 2.0 I did tell you I was going to
talk about make a taxi post quantum uh I
never heard a taxi before coming here
okay but I took a look at the protocol
because I wanted to see what taxi was
doing for transport and I went by the
way those are really large specification
documents um uh uh they're they're
interesting that they're there oh a
suspect's all right um so what taxi does
is when you look at it and you dig down
deep into what the transport is it
actually does something completely
reasonable it says we're going to build
on TLS 1.2 and 1.3 and we're gonna and
we suggest that if you're doing
certificate operations you stick to P
kicks out of the ITF all reasonable
sorts of things to assume because what
it does it pushes the problem on dealing
with anything on to the IETF groups that
specify TLS and P kicks alright and so
if you solve the problem at your TLS
layer you've solved the problem except
here's the issue with this all of your
underlying protocols need to be updated
to post quantum and that just puts
pressure on the TLS group to do that and
specify and this is what sort of every
standard that I've worked with that
builds on top of TLS does is it says use
TLS and then maybe it specifies a you
know it does a profile of it and says
well this is the way we're going to use
TLS in soap this is the way we're going
to use TLS in this this is the way we're
going to use TLS and that
this is what we're going to use TLS in
taxi 2.0 so at some point taxi three-arm
there's going to be a prote of a profile
that says when you're using TLS 1.3 it's
going to be these cipher suites with
with the minimum of this sort of quantum
resistance and if you're doing
certificate operations this is what
you're going to have to do inside of
peak X right there's going to be some
profiles that get specified on that but
in general all that does that puts a
dependency where if you're shipping taxi
software or speaking software you're
going to need your underlying stats to
get updated that's fine that just adds a
dependency in right and so for your TLS
stack to be updated your underlying
systems under there need to be updated
and that just kind of builds frankly
depending upon when we think we start to
see a quantum resistant out computer out
there or a quantum computer out there
the easiest response is probably going
to be to wrap everything in VPNs I
suspect and one of the things that I'm
trying to keep in my back pocket are PQ
enabled VPNs that I can tunnel
everything else over because I can throw
those tunnels up quickly if I need to
and I don't have to modify the entire
stack that is not the most efficient way
to do it because I'm adding yet another
wrap of encryption around everything but
if the guys in Asscher come to me and
say we need to secure the VPNs between
our data centers against a potential
quantum enabled adversary my easiest
response to them is to say let's put
some PQ enable VPNs down and that's the
first response before looking at all the
details in the software stacks and I
suspect we will see some of those
options get deployed pretty quick and we
can do we can do this with open VPN or
with other VPN technologies it's really
no different at an algorithm level but
that's probably going to be what the
simplest deployment is that you start to
see um finally I just want to reiterate
that all of this work is being done in
the open so crypto abhors crypto
algorithms of secrecy in code you should
be able to inspect your crypto
algorithms um Microsoft is doing all
this work without any IP we're not
pursuing any of that because the crypto
community abhors that generally as well
our work and the work of our
collaborators is all up either on
publicly accessible download pages from
Microsoft or or up on github if you go
out to github and search for this you'll
find lots of work if you are thinking
about playing with any of this code hey
that's fantastic be we're happy to
answer questions about it see please
contribute back test your systems out
find out where things work or not no one
knows what's actually going to come out
of the nist process i actually expect
the IETF will start standardizing things
on a quicker pace then NIST because NIST
is going to take six years and frankly
that's a bit too long but that process
is going to continue and that's kind of
where I want to leave things here and
start to open things up for questions
um so actually I'll go to questions and
I'll just leave it back in case anyone
wants to copy the URLs down I want to
thank you very much for listening to me
today and letting me throw a little bit
of math at you and I will be happy to
take any questions you've got about
quantum computing or quantum resists
encrypt or where things go thanks very
much
[Applause]
okay yeah
it's wrecking so I have a question for
you when you are showing those timing
and everything else obviously you do
have assumptions on capabilities or the
processor what is your prediction how
low those capability capacities will go
because the still bunch of stuff that is
built with 8-bit for bit processors
correct
so those timing numbers in fact if I go
back to them for example this is gonna
take me a little while to go back here
you'll see though on for example on the
key exchange ones we are all assuming
like reasonable speed core i7s right so
these are pretty fast processors okay so
it is absolutely the case that you have
to look at a wide range of processors
and if you're looking at a very small
IOT device that's got a four bit or an
8-bit processor you know that you're not
going to get these kinds of speeds and
things are going to and and your
trade-offs are going to be different and
you may choose something where I really
need very small cycle times and I'm
willing to pay a space cost because
that's a trade-off or you may you may go
the other way right um the other thing I
want to point out is that it is possible
that we will see depending on what's
chosen for Standardization specific
instruction sequences you know
instruction to get defined for new
processors just like intel has done this
for AES and for sha-2 now that's not
going to help your 4-bit microcontroller
frankly okay um not much may help your
format microcontroller um but some of
these don't like like the lattice
schemes don't really require much more
than than matrix multiplication and they
may be well-suited even if you're
spending a lot of data you might say in
that environment I'm willing to pay the
cost of having enough memory around to
hold larger keys and buffer because I've
only got a small amount of compute I'm
sure there's also someone from an ARM
processor manufacturer who would be
happy to sell you a better processor to
in that environment you know that's a
real trade-off because we're starting to
see you know 32 and 64-bit processors
show up in
cables right all over the place and so
there's a question about what's the
capability in past NIST competitions
NIST ended to fix the platforms that
they cared about as an 8-bit
microprocessor and a 32-bit
microprocessor and I actually think that
was a bit of a mistake because their
standards going to be around for a long
time and the processors move a lot
faster so you really got to kind of
predict where the processor advancements
are going to go but if I'm talking about
satellite communications and I'm
launching something and I need to have a
post quantum secure channel between a
ground station and a satellite and I
really care about bandwidth and I'm not
gonna be able to update the hardware
then yeah I may make a very different
trade off on that but yeah these are all
none of these are as performant as
what's being used today and so if you're
struggling to do RSA or elliptic curve
today you're going to struggle a little
bit more that's my answer other
questions
after the first quantum break it out of
the decryption how quickly the
development will be into coming into
mass scale or actually I would say even
low-end nation-state scale a decryption
oh that depends upon who's got the
capability okay
so one of the so first - there's a pre
question there before yours which is are
we going to know when the first break
happens yes okay and I get asked that
question by the way--by execs at
Microsoft where I go Brian how are we
going to know and I'm like well if it's
a nation-state we may you know if it's
an intelligence community we may not or
we may have to infer it if it's an
academic community that does it they'll
publish a paper and they'll get Awards
and we'll know you know if I can build a
quantum computer at scale if I'm able to
construct nine or ten thousand logical
quantum bits which is what I need to go
after this I'm going to be able to build
twenty thousand right by the time you
get to that scale we're struggling to
build a few and to keep a small number
coherent if you saw the engineering
problems to build many then you're going
to be able to turn out more quantum
computers now they may be really
expensive you may not have a lot of
people to buy them and they may be
tasked with other problems neatly we do
this way what's the market for selling
quantum computers that are tasked with
breaking crypto there's probably three
buyers out there I can think of off the
top of my head okay and they all have
three or four letters in there in their
agency names um you know I mean
Microsoft doesn't have an interest in
buying a quantum computer or building
one to break crypto we want to make the
capability available right we you know
if we had one we wouldn't make that
available as part of you know cloud
services rent quantum computing time for
solving new problems but I think it
would fall pretty quick and really in
the as far as cryptographers are
concerned all you got to do is
demonstrate at once okay
mark Stephens in March of this late
February this year demonstrated a sha-1
hash collision okay that was a
breakthrough moment for sha-1 we knew
that was coming
I had somebody working with mark for
about three or four years because we
figured that that was where that was
going to come out and that's why we've
had
collision detection code for sha-1 that
we've made available and we're now
integrating into in the systems as soon
as you demonstrate it once the
assumption is that the algorithm is
broken so if you if someone demonstrates
that they can factor with a quantum
computer say a 2048 bit RSA number as
far as the cryptographic community
concerned 2048 bit RSA is dead and since
I'd only need to double the number of
quantum bits to go after 4096 bit RSA
we'd assume that's dead too so it'll
happen very quickly
how will the post quantum computing era
change the discussion on government
access to crypto and ha and will there
be a will you see solutions make
government access to crypto keys that is
and will you see possibilities for
individuals to be able to secure the
communications in the post a quantum
error so that's a very good question I
also do get called in to these sort of
law enforcement conversations because
law enforcement says hey you know what
can we do to get access these sorts of
things it's a cat-and-mouse game what
happens right now the I think for
individuals the moves going to be this
is why we're looking at these types of
algorithms because they're algorithms
where we don't think that having access
to quantum computing helps break it now
that doesn't change the general debate
over whether or not law enforcement
should have access on a general mass
scale to keys in certain types of
devices the properties of these
algorithms that we're talking about are
similar from a law enforcement
perspective to what we're using today
with RSA and elliptic curve okay so you
know at the gross level there isn't much
difference there now
if law enforcement has access all of a
sudden to say a quantum computing
capability and can break classical then
there's devices that they're now going
to and protocols and keys that they're
now going to be able to crack and the
move to quantum resistant algorithms
would then thwart that just like the
other cat-and-mouse
we've seen Pappa before but you know in
a lot of cases that's not the way you
get around stuff right the math works if
you do it properly and a lot of the ways
the folks are able to get access to
systems they want to it by bypassing and
by breaking and I don't think that's
going to change anything I mean I'm not
giving you any sort of guarantees about
the security of systems implementing
this right you know crappy
implementations of crypto are going to
be just as vulnerable as they are today
whether they're implementing RSA or a
post quantum scheme um and if you don't
secure your systems and an attacker can
break in and go get your private keys
off the system it doesn't matter what
algorithm is being used so I don't
really think that changes I do think
that that conversation continues and I
don't have a way just like every other
cryptography will tell you I don't have
a way to secure the system so that only
the good guys have access to the
encryption keys and not the bad guys I
mean we can talk about that and
engineering sorts of things but I don't
think that this particular problem
changes the nature of that debate okay I
think we're just about out of time I
certainly didn't know I'd be having to
do math this early on a Friday morning
but thank you very much thank you all
coffee break
you