Dear viewer, these subtitles were generated by a machine via the service Trint and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/323 Thanks!
All right, sorry for the technical
difficulties, for the actual useful part
of the talk. I'll turn things over to
Tanya here. Well, I'm Tanya.
That's just in case it wasn't clear.
So this is about Corrupter and some of
the curves. So
we hope this is a gentle enough
introduction. If it's too boring.
Well, it's late in the evening.
Take a short nap and wake up every once
in a while to check whether it's still
comprehensible.
So why cryptography?
So when you when you skip to on the
Internet of electronic payments,
then, for instance, you see an SSL
certificate. That's where crypto is in
there. If you have an E passport on
identity card, that is using
signatures.
If you're using tools to
send secret data, then you actually want
to have encryption.
And so when you have an exchange,
then you use, say, RSA, or if you
Halman or DH and
the ESSI and the age and the
in the act is a is what this talk
is about today.
There's also a huge clump of
crypto, which is secret key cryptography,
which is really cool stuff.
It's much, much faster than anything
we're going to tell you about today.
But it requires that the two parties who
want to talk to each other already know
each other, that they have done some key
exchange. We're going to show you how to
do the key exchange. And afterwards, the
symmetric crypto, that's what's
going to happen maybe next year.
OK, so within
public crypto, why would you want
to use what has caused
all sorts of people to be interested in?
The basic answer to that is an attack
strategy called index calculus.
Now, this is if you want to factor
somebody's RSA keys, if you want to break
somebody's original non elliptic diffie
Hulman, then you use index calculous.
It's all sorts of fancy math and
algorithms that come into it.
And the bottom line is it keeps getting
faster and faster.
So we don't even know how fast it's going
to end up being. Here's some of the
history of when these algorithms were
developed.
Nineteen seventy five was one of the
first index calculus algorithm C
Freck for factoring big numbers.
And then there were all sorts of events
since 1977, 82, 1994.
You've heard about the Crypt Apocalypse
last year. And this is something where
this is one of the newest advances
in index calculus.
That's not something that matters for
breaking RSA, but it's just an example
of how index calculus, this general
strategy is something that keeps getting
more refined, more sophisticated and
faster and faster.
I mean, this is not the whole story, if
you look at academic literature, there's
also lots of improvements.
I mean, we're happy if we can factor
twice as fast.
But these are the big steps when
you look at the security of to typical
sizes of ours.
So this is a 10 24,
which you still see a lot on the
Internet. And there's hours a 2014,
which hopefully your bank is using.
Then there's two rows of numbers.
So I two columns of numbers where you can
see how much the security has decreased.
So back in 1975,
so the chief algorithm would still take
two to 120 to do the
same work that well, many years later
was a number filled.
SIFISO in the 80s, would
only take to the 80s.
So there's a big decrease from two to 120
operations down to 80.
And actually it's not just losing 40
in the exponent, it's much bigger than
that. It's something which takes
170 down to 112.
So it's not just a linear decrease,
it's more than linear decrease in the
exponent.
So in 85,
when basically the
number two was or the
felt safe was in work, Miller
was proposing elliptic curves.
So as a different as an alternative
to factorization based methods.
So Factorization or the Fellman
would be broken by all of these
algorithms.
And then Miller says, well,
I've looked at this new primitive at
elliptic curves and
it is extremely unlikely that an index,
Keiko's attack on the elliptic curve
method would ever be able to work.
So we can completely ignore
all of these improvements, all of these
methods that made
factorization and find field
basti for Hollman so much weaker.
OK, so
to get into elliptic curve cryptography,
the gentle way to get into it
is Klok cryptography.
Now this is a picture of the clock.
Do you actually have a clock to show
people in case you're not used to what a
clock used to look like some sort of
circular thing?
You know, if you think a clock is like
showing, you know, some digits next to
each other, this is what a clock used to
look like. For most people, it's X
squared plus Y squared equals one.
It's kind of broken.
That's why we let
the elliptic curves
that we're going to show you later in the
talk. Those do not include the clock.
The clock. Cryptography is not an example
of elliptic curve cryptography, but
it's really, really close.
So we're going to start with clock
cryptography. And then once you're
comfortable with that, then we'll make
one little change and then that'll be
elliptic curve cryptography.
All right. So he has to prove that I
passed kindergarten.
He has some points on the clock.
So that is the 12 o'clock that's
up there. I learned now also became
a mathematician sometime afterwards.
And mathematicians like to work with
coordinates.
So the twelve o'clock point has
zero in the X direction and
one in the Y direction.
I know the one because it should suppost
should satisfy X squared.
So zero squared plus Y square
is one, so why is one.
But there's many more points.
So there's also the six p.m.
there.
It's when you start having breakfast,
lunch.
There's a three o'clock point.
There is the nine p.m.
point. There is.
Oh what's that.
I didn't learn that part in kindergarten,
so it's it's half
up. Well, then look up for the one
half goes over. That looks like
the two o'clock point, then
this is kind of flipping the coordinates.
So now X is one half.
So we're somewhere over here and the
negative.
So there would be five o'clock
and more points and more points and more
points.
Wasn't supposed to be gentle.
Is a gentle.
OK, OK, so hey, hey, at some points,
you didn't say, oh, I'm sorry, so
what I guess you want to tell you about
more points like this? Three fifths.
Four fifths. I mean that when you really
have to use some fancy math to see that
one has three fifths squared plus four
fifths squared, it's one
that is another point on the clock.
And it's not obvious which O clock it is.
You have to really look at your watch to
figure that. Always bailing out of the
tricky stuff.
I'm sorry. Now you're bailing out of the
tricky stuff. Bailing out of the tricky
stuff.
You mean, OK, OK, you really want me to
do the square root of one half square and
one half? No, no, no, it's just
I don't know where that point is, but I
know it's on the clock. OK, you can
figure out where the three fifths four
fifths point is in terms of time.
You can make this a little more
complicated
by parametrized in the clock.
So when people take points on
the clock, they're thinking of time
moving forward, like there's two o'clock,
three o'clock, and you can add those and
get five o'clock, two hours after three
o'clock or three hours after two o'clock,
and that's five o'clock.
And here's a picture, which is something
like maybe that's one thirty plus two
o'clock is giving you three thirty,
something like that.
So those are some points, P1, P2 and P3
on the clock and you can add P one and
two to get P three.
And here comes the really horrendous
math part, which fortunately we're going
to throw in a moment, which is
trigonometry.
So if you want to do the
point on the clock, which
has an angle of Alpha time
of Alpha starting from twelve o'clock,
then that point is X equals sign
of Alpha, Y equals cosine alpha.
And then if you remember, there were
these horrendous trig formulas for sign
of the sum of two angles and
cosine of the sum of two angles and
sign of Alpha one plus Alpha two is a
sign of alpha one, cosine of Alpha two
plus cosine of Alpha one sign of Alpha
two. And there was something else like
that for the for the cosine.
So you can add points on the clock
using these sine and cosine formulas.
Now usually a convince people to come
over to the crypto side to tell them,
well, you can forget all of those
nondescript mathematics.
We like discrete mathematics with the
discrete guys.
So there won't be any signs and cosigns
wandering around.
So, well, let's get rid of them
so we don't want to have
signed cosine. We actually would like to
work with normal clock numbers.
What I have over there with a sign
one cosine two
and so on.
Well, those are just my X and Y
coordinates. All I said here was that the
X coordinate is a sign of
Alpha. The Y coordinate is the cosine
alfalfa.
So then in this whole mess here with the
trigonometry formulas, I can just
replace every sign of Alpha
by the corresponding X and every cosine
of Alpha, but the corresponding Y,
which makes this much nicer,
shorter, no trigonometry
edition formula.
So edition on the clock.
If somebody gives you two points x1 y one
extra y two, then all you're going to do
is you take the X calling off the first
point in the wake of the second point,
multiply those, take the Y quadrant
of the first point X squared off the
second point, multiply those and
then add those together.
That gives you the new X cornet
y.
Well we went through the
pain once and now we can just forget
about where it came from.
And then we do the same thing with the Y
coordinate, which is the product of Y
coordinates minus a part of the X
coordinate.
OK, so here's some examples
of Clock Edition, we still don't have the
computer helping out here.
So this is going to be some more painful
arithmetic. Two o'clock plus five
o'clock. We all remember this is going to
be on the test. Two o'clock was this
squared of three quarters, one half that
she was talking about at the beginning.
And five o'clock was one half and minus
square root of three quarters.
And if you plug those into the formulas,
they're all right. I'll try this X1 is
square to three quarters and why one is
one 1/2 and X
two is one 1/2 and Y two is minus squared
and three quarters. If you do X one times
Y two, that's the square root of three
quarters times the minus square root of
three quarters, which is minus three
quarters. And then the Y one x2
sounds like one half times one half,
which is one quarter.
Add those together and it's something
like minus one half and you do a similar
calculation. You get the second part of
the result and you realize the two
o'clock plus five o'clock with these
formulas is what you wanted it to be,
namely seven o'clock.
And similarly, you can do five o'clock
plus nine o'clock, which I think I will
skip. Maybe you would have like to go
through that one. But let's try another
example. You can take three fifths and
four fifths and add it to itself.
That's what that two times three fifths,
four fifths means.
And three fifths. Four fifths plus three
fifths. Four fifths.
And you can just well plug those
into the formulas and you don't have to
know which oclock it is.
You just get some answer out of that.
Twenty four. Twenty fifth and seven.
Twenty fifth. And you can keep adding
more and more copies of this
point to itself.
Three times three fifths.
Four fifths. So that's the point.
Plus itself plus itself again.
And just plug it into the formulas and
you get something with
well more digits and as you keep adding
more and more copies you get more and
more digits in the denominator there, the
six twenty five. And it keeps getting
bigger.
You can also try adding any point
you want without even knowing what it is
to 12:00, 12:00
with zero comma one.
And if you plug those into the formulas,
you get twelve o'clock plus three o'clock
at 3:00 o'clock plus five o'clock.
It's five o'clock, twelve o'clock plus
anything. Is that thing back again.
And that just pops right out of the
general formula for adding two point
one last example of how you can
work with this addition formula.
If you take, say, ten o'clock plus
two o'clock, that should be twelve
o'clock and while ten plus
two is twelve, if you take anything
that's sort of opposite, like that was
ten and two. If you take nine and three
or eleven and one and anything where it's
the same height, same Y coordinate, but
the Xs are negative, those will add
together to get twelve o'clock and you
can just try plugging X one, Y one
and minus one one into the formula.
Let's try that.
If you say X two is minus one
and Y two is why one.
And you plug that into the formula, then
you see the first call, the first
coordinate of the answer here is
X one times Y two was Y
one and then Y one is minus
X one times X two.
Let's see, let's X two.
Sorry, x2 is minus X once you get minus
X one, Y one and x1 one which
adds up to zero, which is
what we wanted for twelve o'clock.
And then with a little more work, the
second part here, why one y two.
That's why one times Y one
and then minus X one x two that's
minus X one times minus X
one is plus X one squared.
So Y one squared plus X one squared
which equals one.
So the second part of the answer is one.
So just a little bit of playing around
with additions and multiplications and
you can use this formula to add all
sorts of points.
OK, now let's make this even more
discrete. Let's forget about like
the circle, which has infinitely many
points. You can just take any real
number and just take scrotes.
Let's do this with a very small set of
elements. Let's do Cluck's over
find fields.
So I'm now just restricting myself
to the numbers. Zero one, two, six.
So that's what this F7
is there, and I will
also want to add those numbers, I want to
multiply those numbers.
Now, if I multiply those numbers, say two
times five, this is bigger.
That's 10. That's bigger than the say
that they have available there.
If only allowing six is the largest
number, then 10 is not in the set.
So then I will reduce I will take the
remainder. Moraldo seven.
So we promise some python snippets.
So here is how we can, for instance, find
all those elements.
So I'll just run through all X
between zero and seven or Y between
zero and seven and just check whether
X, X plus Y times Y
is one.
If so, I print the Tuval X Y
and then Bush return and you get those
points and those points.
Now for the picture we didn't use
026, we would like to keep the symmetry.
So here we used minus
three to plus three.
So minus three is over here, plus
threes over here, minus three in the Y
direction, plus three in the right
direction. So this is a point zero one,
the same point that we had on the clock
before.
This is the one zero.
And this year then is the clock
point. I see the find field clock
two to.
OK, if you want to use clock
edition with the same clock
edition function that you might have
written, which will show you in a moment
to add points on the clock over
the reels, then it's
helpful if you can write plus and minus
and times which automatically do this
reduction, what, seven and 12
in Python, you can set up a plus and
minus one times for an F seven type
and F seven class, which are separate
from the usual plus minus in times four
for integers. If you want to set this up,
first thing to do is, well, here's an F
seven class which will read an
integer X and initialize
construct an F seven element, which
is that integer mod seven stored
in the component of this
new instance.
For instance, if you take F7 of
seven, it'll compute seven mod
seven and
the remainder there is a quotient is one
remainder of zero and put zero
into self doddington.
Then this Sture and repr, maybe not the
most professional ways of printing
things. You might want to print something
like print out the fact that this is all
seven. We're just printing the integer
that you get if you take seven and
initialize one of these things, seven,
eight, seven, zero and ten mod seven.
That was the example you had a moment
ago. That gives you a remainder of three
and twenty mod seven.
Subtract a seven, subtract seven again.
You get a six so you can put in anything
you want into this F seven.
Any integer you want, you get that
integer mod seven and now
we can add in some more functions
to F seven instances.
For instance, you can have any quality
test by thousands default.
Equality is pretty stupid.
So you tell it. What I actually want
equality to do is compare these
different parts of
the of the F seven values
and then, OK, now this F seven type
has been augmented with an equality and
you can see that F seven of ten and F
seven if three are equal to each other, F
seven and zero and f seven or two are not
equal to each other.
So we got zero through six expresses
the possibilities for the values
of a variable with this type.
And then here goes the
addition, subtraction and multiplication.
What you can see. Let's look at the
addition. That's the typical case you
take to A and B coming in
and then take the integer
inside a zero through six, integer inside
zero through six. Adam together, get
zero through twelve and then put that
back into the F7 constructor.
And so now you've got zero through six
again. And there are some examples at the
bottom of well two plus five is zero,
two minus five is minus three,
which is four if you're programing
and C by the way, beware the percent
doesn't do the mod that we want
mathematically. Python's percent does the
right thing and C it'll give you negative
numbers. Percent in Python always gives
you zero three six or zero through
whatever number you took
and two times five.
That was that example again of ten which
Mod seven gives you three.
OK, so now we have seen a small clockwork
with just all the elements we could just
run through. Well, Florentin elements and
try them now.
Everything the dangers showed with the
python set up, I can replace by
seven by a larger number three.
That's also a problem.
And now I would like to define the
addition of curve points.
So this is just what we did on the
real clock before.
Now I'm going to plug in elements,
what, a million and three.
So I take my point and I
do the x1 y to buy one x1
x2 and so on, and then I return
the plot.
So let's take an example of
this. So one of those
many points I plug in, the X squared is a
thousand, remember, it's a
thousand multi-million three
and then I check is there y coordinate
which fits with this.
And now in this case nice enough to
works.
Well yeah kind of.
So if I have a thousand that gives me
a million when I scored and two
gives me four and that's just one
larger than a million three.
So that's a valid point.
So I can now take this point
and add it to itself.
Just plug it into the addition that gives
four thousand seven, I can edita
itself again, I can edit again,
again, again till I get to say six times
the point.
So six times a point means take
the point plus a point plus a point.
In the end, I have six copies,
add them together and I get this point.
Now, of course, when you see this girl
like, oh, wait a second, do I really need
to do all these five editions?
No. If I, for instance, had stopped
at P three,
it's three times a point and
then do the additional P three plus
P three. So that's three copies plus
another three copies.
That's also six copies.
So these two things give me the same.
So if I want to do this well,
professionally, here is how I would
define the scale on my application.
OK, so this is a recursive function
for computing end times be
you have any point in any scalar,
any integer end that you want and in
non-negative integer. And we're only
going to work with with non-negative
integers here. And you take that in.
If it's zero, then you return the 12
o'clock point.
If it's one, you return the point one
times VSP and then well
if N is even
then that ends to
Pisin, slightly changing its notation
over the years as a right way to take
an integer, divide it by, to throw away
the remainder so that in
two event is even that's exactly an over
two and this recursively computes
and over two times be like three times P
for instance if any equals six.
And then does clock add a few
Macu, to double that and over two times
be getting ENPI.
If N is odd then that and
over two is well enough
to means take away the remainder of
one you get and minus one divided by two
and then take that time to be double
that. That gives you and minus one times
op ed piece of that.
That's that if and is in Mattoo
is non-zero then you add Peter Q
And finally you get end times in all
the different cases.
And then we tried this for some six
digit number n which isn't shown here on
the slide. It's secret, it's secret.
And it took something like 30
clock editions, not very many multiple
occasions to compute.
And times it was very fast, instantly
comes out. And there's the answer.
There's the X and Y coordinates of N
times P for whichever
secret and it was.
And now it's not
so obvious how to figure out what the end
is. If you see this end times fee then
working backwards to the end, you know
what P is? You know what end times fee is
and is not too big, OK is only a million
possibilities. This is not some really
fancy computation, but it's still it'll
take a moment to do it.
It's something where the computer all
have to chug along through some
computations and well, maybe you can try
to make that faster, but then we could
try to make the numbers bigger instead of
a million three. We could still do end
times P when is much bigger and the
million and three is a much bigger
problem.
So there's a little challenge if you'd
like to try figuring out what this is,
this is harder than than sending an
estimate to that phone number that
doesn't work.
All right. Now, let's assume that we make
this much, much harder.
So we make it so hard that we feel like
we want to use it for crypto.
So if somebody would like to standardize
clock cryptography, then here's what you
do, is you start by standardizing a
big primary.
So like big not a million, like
really big, like several thousand
bits.
And you also standardize base points.
So that means this P on the previous
slide, the P where we say, well, we give
you P, we give you end times P, we just
don't give you N.
So let's assume that somebody gives you a
little P, which is the prime and this
base point big P, X and Y
coordinates which are on the clock.
Then what Alice and Bob are doing is they
want to communicate.
So I would like to send something over to
the lab here.
I'm Bob.
Then Alice picks.
Well I pick my secret a compute
eight times the base point.
Now that's a computation you just saw on
the previous slide. It's still still
visible there.
So that's just like logarithmic
time the size of L
of A and then I sent this over
to them and now I guess I have to
compute.
I take my own big secret, which I'm not
going to tell anybody and I do my
computation of times that same standard
X, Y and I send back my bedtime's
X Carmeli over Dallas.
All right.
So now I have his B times
the base point. He has my items, the base
point. Now I still remember what my abels
I know. Take this a and
the the new point that he just send me
and plug this point into the application.
So I'm doing the same steps, the same
well at the point of itself
and sometimes at the point to
the point you send me.
So the same steps here except for
now this is the point that you send me
is no longer the base point.
And this way I compute eight times B
times P.
OK, now I get her eight times X, comma
Y, and I take my secret B and multiply
by the eight times X Y
and I get my B times eight times
they point X come away
and now we've got the same result.
Now we've got she's computed a B
times X, Y, I've computed by times X,
Y, which is the same thing.
They're both eight times B multiples of
X Y, eight times B, copies
of X Y added together.
And now we use a shared secret to encrypt
data.
All right. We also have a picture of this
just if we don't make good else is
involved. So you see how the message is
flying.
Now, if you're the eavesdropper,
you want to figure out what we've been
doing, you can't see.
What I'm doing here, you can see what Dan
is doing here, all you can see is what
sent here and you know what
the little P is and what the base point
is.
At least we wish so well,
so there are some caveats,
don't use just any.
Many choices of unsafe
wanting to.
This is still the clock, and we said at
the beginning, clocks are not allowed to
curves and only elliptical.
So actually the clocks are pretty much
the same as during, say, hours.
I'll find the field when it comes to
security.
So if you want to match something which
is are is a three thousand seventy two
bits, then your clock needs to
have the prime of the clock
needs to have four thousand five hundred
thirty six. So half as many bits as
they a number.
That's not actually what you wanted.
And then.
OK, third warning is timing
attacks, a lot of you were at
the talk earlier about life, about her
attacks against SSL, where
a lot of the information coming out of a
server under attack or a client
under attack is from timing.
The attacker doesn't just look at the
eavesdropping of eight times X, Y and B
times X Y.
The public sees the attacker sees how
long it took you to do computations.
A lot of times the attacker can even see
how long it took you for each individual
operation that you were doing, because
there is electromagnetic emissions or
radio emissions or cash effects
on virtual machines that
affect other virtual machines running
under the same hypervisor on the same
physical hardware.
And then you get to, as an attacker,
see all sorts of fine grained information
about the time that Alison Bovver taking.
You don't exactly see this computation,
but you see the physical effects of this
computation. Just imagine if it
is right here.
She can hear she can sense
what the computations are doing.
You can actually hear the audio buzz
from your CPU if you put a good enough
microphone next to it.
And that depends on the computations it's
doing. There's some real examples of
timing attacks here.
Two of the three examples that we
selected are examples.
One of them is the lucky 13 attack,
which was not against another
different kind of timing attack.
Just to give you the idea of timing,
attacks are really important.
This is a big part of what's going wrong
with real deployed crypto beyond
it's on usability and other little
problems.
The fix for this particular
problem, you have somebody seeing the
timing is to always
do computations in constant time.
So no matter what your scalar is, you're
not allowed to spend a different amount
of time depending on that scale.
And if you just always follow this rule
that every secret you have no secret
timing of anything, then the attacker
doesn't learn anything. All your timing
is public.
Of course, it's a bit of a hassle to do
computations that way.
You can always do it, but it slows things
down quite a bit.
All right. I mean, that's easier said
than done, but let's.
Go back to why, number two, let's assume
that Constantine rotation takes care of
one. Number three, let's go back to one.
Number two, clocks are not elliptic.
And let's turn this circle, this clock
into an elliptical of.
All right, so we take the circle and
push inwards now, mathematically,
what we're doing is we introduce one
extra term instead of having X squared
plus Y squiggles one.
We say X plus Y square
equals one minus 30 times
X Y squared.
So this extra term here.
It's a difference between a circle
and an Edwards curve or
an elliptical.
So this particular curve is called an
Edwards curve, but it's an example
of ellipticals.
Now, if I want to add points now,
then let's remember what it looked like
on the circle.
So on the circle, I have the neutral man
at the top. I keep that.
So that was he adding anything to 12
o'clock doesn't change the value.
That's still the same here.
Now, here was just adding P1,
P2 getting P3 by these
formulas.
Now, this won't generally work
on the elliptic curve
on elliptic curve because this is
minus 30 x y square.
We also need to introduce a little tweak
down here. So there's now a denominator
if you take the equals zero.
Then, well, the formula changes
to the circle and also the
addition formulas just change the circle
because all this 30 here is zero.
So let's just divide by one.
So the circle comes out as a special case
for this elliptic curve.
But now we take minus 30 and
have a nice little curve and the
different forms are not much versus
just a little extra room there.
OK, you can take if you want any
prime number P seven
million and three, something much bigger,
you can take any non
square deal that's
like that minus 30 any D.
That's not a square of anything
modulo P.
That's something you can check quickly
and then write down the curve.
X squared plus Y squared equals one plus
the X squared Y squared.
This is an elliptic curve
and it's just that extra little D that's
all the extra complication.
If you felt like OK, you understand clock
cryptography, then the extra little
complication is all you need for
elliptic curve cryptography.
There's the addition formula just
translated from the math formulas.
A couple of slides ago into Python looks
very much the same as before, except the
X three and Y three have that D coming
in at the Denominator's.
Now you might complain about this saying,
wait a minute, when you divide, are
you are you necessarily able to divide
what happens if you divide by zero?
Maybe these formulas don't always work.
And that's an important point.
It's something which you have to watch
out for. If you're dividing by something,
then you're not allowed to divide by
zero.
But it turns out that
the denominator's they're the one plus
the one next to Y when Y two and the one
minus the X one, X to Y when Y to
those are never equal to zero.
These formulas are complete.
They always work, which is what you
expect. I mean, you think formulas should
always work. It's kind of annoying if
there's exceptional cases.
But well in
elliptic curve cryptography, there's
actually lots and lots of exceptional
cases that people often worry about.
And one of the reasons that we like
this kind of elliptic curve is that
there's no exceptional cases.
The addition laws, what we call complete.
If you look at how the
math part of the proof works, then it's
important here that that D was not a
square. But again, that's something you
can easily check.
And once you've settled on a D, that's
not square that everybody can use, then
you will never have exceptions in the in
the in the formulas.
If you have your being
square, then you
can write down the same formulas and most
of the time they work, but you have
exceptional cases and we're going to see
lots and lots more about exceptional
cases. And what's annoying
about those is not just well, it's hard
to program, but if you make any mistakes,
it's going to be hard to find those
mistakes and test for those mistakes.
And if an attacker thinks about it more
and can give you some points that exploit
those mistakes, this often breaks
real s.E.C.
So it's better to take a curve where the
D is not square and then you don't have
to worry about this at all.
OK, quick aside, with our fine
field every second D it's not
a square, so it's not a big restriction,
it's just removing half of the
possible D
divisions are also very slow.
So when you, when you implement those who
saw before in the Piceance group, you
didn't even include divisions.
We do have them online, but it's like,
well, it takes a while.
It's unpleasant.
It's takes even longer if you're worried
about Konstantinov reputation.
So let's get rid of divisions.
It's like, doctor, doctor, my knee hurts
and you say, well, don't use them.
But Mathie here, we actually
can avoid using divisions.
If you remember how you worked with with
fractions, Alawa B plus C of
A D, then you keep them as friction.
You just multiply the denominator and you
cross multiply the numerators and you can
add.
So we can do the same with all points,
so we're going to introduce an extra
coordinate, the Z Kornet,
this is just the denominator.
So instead of storing X Y as a point,
we know store X, Y and Z.
Were the X and Y means
the old X and Y are X divided by the
end, Y divided by C, or
you can be a little bit more adventurous
and actually get some somewhat
better speed and also introduce an extra
coordinate called T, which is X Y
divided by XY.
And if you're interested in how to do
this efficiently and actually get
computer verified from this, please visit
the explicit Fondas database on the
link there to see how we actually do
the then.
OK.
Let's now go back to how Krypto
looked, but let's replace the clock with
an elliptic curve just makes that
extra little complication in the
formulas. There's also an extra choice to
make. So it's not just standard is
a problem for everybody to use, but
you also have to standardize this D,
which is not a square for everybody to
use. This has to be a safe choice.
Remember that warning, number one, that
there's lots of unsafe choices.
There's all sorts of standard criteria
that you have to check to make sure that
these are safe choices of curves.
We'll say a bit more about standards at
the end of the talk.
And then Alice, as before, has
her secret key and
multiplies that secret key by
X, comma Y and oh,
I'm skipping ahead of what this slide
says.
The slide says that Alice has also
bobs publicly V times X
Y, and this all sounds just like
it was on the clock.
Alice now takes the B times X Y
and then multiplies
her by. That gets eight times B times X
Y and then.
Remember that eight times B times X Y as
a secret to use to encrypt and
authenticate data, and more concretely,
now that we've got elliptic curves, we
don't have to worry about an index
calculus breaking everything.
We don't need to have thousands of bits.
Here's some actual real sizes for
elliptic curve cryptography, including
all the secret key encryption and
authentication.
The public key.
You can have a prime, which is just
two hundred fifty six bits long and
will say later that you can squish X
and Y into together just 256
bits and then that reduces
Alice's public key eight times
XCOM y down to just
thirty two bytes that Alice is going to
send along to Bob.
And then there's a little bit of extra
stuff for a nonce, a random number.
So you don't end up encrypting the same
message the same way every time you send
it, someone would be able to see that
encryption repeating.
There's also an authenticator so that Bob
can verify that the packet is
correct.
And then Bob receives
this packet, says, oh
yeah, it's a packet from Alice.
There's Alice's public key.
If Bob didn't know the shared secret
already, Bob takes Bob's secret
multiplies by the public.
He gets the same B times eight times X
Y and then does secret key cryptography,
verifies the packet coming in, verifies
the authenticator using the nonce and
Alice's public key and at that point has
verified that. Yes, this is from Alice.
Of course, if Bob's never heard of
Alice's public key before, then doesn't
know who that Alice is.
But he gets continuity between the
different uses. And then when you add in
certificates or other public key
infrastructure, you actually know who
you're talking to.
Everything happening here, all of the
public key and secret key stuff is
so fast that we can afford to do this
for every single packet going through the
Internet.
Well, at this moment, we haven't actually
told you yet what to use.
So here's a safe example.
You shut up.
So this is a safe example, which then
shouldn't advertise because it's his own,
but I can say it's a good example.
So if you take as your prime a big
it has 255 bits.
It's a very nice primatial computations
modulus prime afast because it's
very close to a part of two.
So when you do this mod
this operation, they're
reducing what this number is very fast
and then D looks reasonably
small. And here you have an Edwards
curve.
Also, he is not taking the same
deal, but putting a minus there
and putting also minus in front of the X
squared is
another curve. Actually, it's pretty much
the same curve.
So for every X Y that you had before
on the first curve, he not have a
square root of minus one X
Y, same Y, slightly different
X. So you're just taking a little
tweak. It's the first curve in disguise.
And actually we have lots of ways
of writing elliptic curves.
So he has a whole list of of different
ways of writing curve.
So the first thing that we showed you,
Safadi, the clock where you're squishing
in the corners is
an Edwards curve.
If I now would like to have an extra term
here like this minus one here, I
generally reserve an E coefficient here.
Then I can put in
minus one, for instance, that is called a
twisted Edwards curve.
But then there's also some other things
which you still find in the normal
textbooks, which are called vicious
curves. They look like that.
And then there is Montgomery curves,
which you can think of as a special case
of Biota's curves.
They have a similar y square equals
extubate shape, but they are some
slightly different terms here.
And when you have one of the curves, you
can go from one to the other and back,
for instance, to go from a Montgomery
curve to an Edwards curve.
There are other formulas.
OK, what you'll typically
find in standards for XY
for historical reasons.
OK, stand back. That's going to be
horrible is via Strus
curves. Now here's the addition
law. Here's how you add two points.
Arenavirus stress curve.
Oh, that isn't too bad.
All right, there's only six different
cases, let's go through them.
No, no, let's not go through them.
This is if
you just take one piece of this, then it
might seem like it works most of the
time. The first formulas work most of the
time until you do something crazy like P
plus P and then it doesn't work.
And then you have more and more
exceptional cases.
And some of these cases you don't even
realize at first.
And then you try writing code for this
and it's just it goes on and on and then
you try testing it and you're not sure
you've gotten all the tests. Right.
But OK, that's what you find
in standards.
All right.
Much nicer than Biota's Montgomery
curves, it's another of our favorite
curves. So here you see
the entire arithmetic, except for I
didn't show you how I will do the
constant time conditional swap
here.
So there is a conditional bid here which
swaps the two with the X3.
We can do this second time just
replaces instruction by something which
says it stays or it swaps.
That's a whole addition on Montgomery, so
for every bit you do these
few steps and you run through the 255
bits that are staged there.
So that's another nice case of
arithmetic, you know, so
that here we only use an
X coordinate for the Edwards
crew if we had X and Y.
So there are some differences in what
we're doing with them.
All right, so then announce we're going
to talk about standards.
So how do you get your standards from
so how to defend yourself against
somebody who comes with a mathematician?
Mathematicians go people that know all
kinds of attacks, and if you want to see
these attacks, we have some girls at the
end, but we know those attacks
and all of those standards.
Long list of things basically agree
on certain properties that you want.
You have to have
what these standards guarantee you.
If if you pick one of those standards,
then it will.
The curve will be secure
for the following attacks.
Somebody sees the result of your
computation, knows the base point,
knows you're public key and is
not able to figure out what you're A
or B was.
So this is called the elliptical,
discrete logarithm problem.
And we have filed papers
over papers to study the hardness of
this.
So that's what we as mathematicians do,
study how hard it is on a certain curve
to break that elliptical, discrete log
from one thing.
For instance, you want that your point
when you add it to itself many, many
times that
for a long, long, long time you get
different points.
Until you get back to the same point,
say, after L'il Times, you're back.
That is the order of the point that
should be allowed. No, we're not.
I mean, like two to two hundred fifty or
something really large.
And yet they're all the script.
So that's one of the criteria.
There's many more.
OK, so let's see.
You're an implementer.
You take any of these standards and
again, they all pretty much say the same
thing. Minor differences in details, but
they all protect you and you
implement the standard and you say, OK,
we're in Germany, let's take the brain
pool curse, because that's what's used in
the German passports.
All right. So we take brain pool up to
50. Sixty one.
It tells you some big prime number,
256 bits long.
It tells you a very strong curve.
Y squared equals execute minus three X
plus something big.
And then it tells you the base point XCOM
Y to use. And then you look
at this and realize all the nice formulas
we were telling you with no exceptional
cases like Edwards and Montgomery,
those formulas don't work for
this curve.
If you have a curve compatible with the
formulas, you standardize that curve,
then every point you can add successfully
and you just forget about all the
exceptions. But you need a curve that
works with those formulas.
And unfortunately, this
curve doesn't work with Edwards and
doesn't work with Montgomery.
So you have to go back to that messy
via stress series of formulas.
So you OK, you're very careful.
You do exactly what the formula say.
You figure out test cases for everything
you have correctly implemented the virus
stress edition, all six cases and
time, and you do everything
Konstantine.
So not going to leak any information to
an attacker.
And then you have something
which is painfully slow,
but you're confident about the security
until the attacker
comes along.
Hey, let's do this. You Halman.
Here's my point.
OK, I'll take my
I guess I'm Ellis' I.
I'm sorry. So now I'm Alice, I've got an
A I take my eight times the
point that she sent me, which is her
public key, and
that's not the original X Y time
different from Y prime that she said.
And I send back my eight times that
X Y, and
then I've done this computation
correctly.
And then I've now
used the the encryption
authentication mechanisms that somebody
told me to use standard mechanisms.
And I've encrypted some data and sent
that through the network.
I'm on the network.
I see his his RSG same encrypted
message. Now what he doesn't know
is that no matter what is a
is.
They're not actually that many different
points. I didn't give him a point on the
brainpower curve, I gave him a point on a
much nicer curve. Look, it only has a
five year.
The brain could cover something much,
much bigger. This is a frantic curve.
Also, this point only has four thousand
ninety nine different copies,
which means.
He's not actually computing what he
thinks he's computing, oops.
Now, the reason that this works is that
in this whole mess of the virus curve,
there's no A6.
So no matter whether it's the sex, which
is the huge number for the baneful curve
or the five, which is a nice curve
I gave him, it doesn't matter.
He'll just use those formulas.
And then.
The AI gives me one
of those ninety 99 different points
from which I learn a module
four thousand eight at night tonight.
Let's do this again.
She's going to send me another point.
Hi. He has another point.
So I take that new X from Prime.
I compute my eight times that I send back
the something encrypted using
that shared secret.
And now she does
the same kind of computation.
She has secretly sent me a point that has
small order and I never noticed that it
had smaller. So now she's figured out my
secret modulo some other
number.
And again.
And again and again.
And this happens 20 times maybe.
And then she uses the Chinese
remaindered theorem to figure out my
whole secret.
Even getting a few of these leaks is
enough information that it does a
lot of damage to the security of the
system. And, well, if this happens 20
times, then,
well, I'm screwed.
So what do people normally say
in response to this?
They say, oh, didn't you notice the
footnote in the standard that said when
you have a point coming in, you have to
check whether it's on the curve because
somebody might have been trying this evil
attack. So this is blaming the
implementor, which is how we get secure
systems by blaming the implementor.
That's good.
If something's gone wrong with the
system, then it's the implementors fault
for not checking.
Don't even get me started on Sturr
copy, you should have checked
the length of your string you were oh,
I'm sorry, wrong talk.
You should have checked that this point
was on the curve.
You should have checked it had the right
order. Another kind of attack like
this. You should have, by the way, paid
patent fees to Sadik-Khan.
OK, OK, let's not is saying
I mean, if you do this, you might get a
phone call saying we have a patent
on point validation.
Yeah. So instead of blaming
the Implementor for not jumping through
these hoops, why don't we get rid of the
hoops? Why don't we design the crypto,
why don't we design the curves so that
it's not actually possible for
somebody to screw this up?
We know how implementors
think we are implementors.
We know what we do wrong.
And it's not that creative.
I mean, we keep making the same mistakes
again and again and again.
So let's actually protect against those
mistakes and design a system that's
robust against those which for s.E.C.
Says you take your X,
comma, Y coming through the network.
Don't allow an X, comma Y to go through
the network. Just have an X.
And then why was Y
squared equals something you could if you
want to communicate why, you can send one
bit that says whether it's plus or minus
the square root of whatever Y is the
square root of or don't
bother sending Y at all.
Remember, those Montgomerie formulas
don't even need to to look at the Y.
So this if you just send along an X,
then there's very few possibilities
for the attacker to
choose, points to try
to fool you the way that we were fooled a
moment ago.
There's a couple more of these rules
which make which the the curve selector
and the protocol designer can put in,
which mean that you as an implementer
have a much easier time, like the
protocol designer can tell you to
always multiply the
SCALARS, the A and B, the secrets that
you're using for Diffie helmond always
multiply those by what's called the cool
factor of the curve.
There's this base point that has Ordell
Hasle different multiples.
There's going to be say four times L
or eight times L points total on the
curve. You're only seeing all of them.
And to make up for that gap and avoid
some other fancier attacks, you always
multiply your secrets and B by eight
and that completely protect you against
these attacks. And that's something that
can be put into the protocol and test
it. And similarly,
the curve designer can always
choose curves to be what are called
Twist's secure.
There's still a little bit of wiggle room
if somebody's sending you a compressed
point. And this twist security
says that, well, basically
the wiggle room lets you choose between
two different curves.
There's this curve and then a sibling of
the curve, what's called the twist of the
curve and the curve designer
can make sure that both of those are
secure.
Both of those have these big primes.
There's an L and a sibling L and
a cofactors small factor in another
small co factor.
And if the curve designer chooses one of
these twiss secure curves, then the
attacker has no flexibility left to
fool you. The attacker won't get any
information about your secrets.
And B, well, so then
why is this not happening?
Well, actually, it's kind of happening.
So there is some motion to get like
the next generation of easy standards.
So next generation, meaning curves,
we don't choose ourselves in the foot.
When you tried to implement them in the
simplest way with the simples
implementation is also a secure
implementation.
Turns out usually when you're on
something more secure, it gets slower.
In this case, the bonus is it gets
faster.
Or in 2010, Adam Langley from Google
was posting to the Tila's made list
saying, Hey guys in Abacus
Crypto has made some advances.
Wouldn't it be nice to have like
fifty five of nineteen as he named Curve,
then not much happened.
We did some work proposing
good methods to we
think it's good methods to generate
curves and well,
thanks to Snowden last September,
the suddenly motion coming into this
from other people going like given
that the discursive kind of their
respectability where we think, oh, maybe
the NSA is not just the good guys,
shouldn't we have enough emotion?
Luckily, there's lots of other people
saying, hey, look, it's not because
you're paranoid. We don't know whether
the Oscars are bad from a security point
of view, but they're certainly not
pleasant from implementation point of
view. We could be faster.
We could be more secure.
And so there's, well, a few
quotations and there's a draft
and then we make another coup.
If if somebody wants to have really
paranoid security level at seventeen.
But if.
Yeah.
And what if it's mockers.
We have a safe house page bla bla bla bla
bla stuff finally.
OK, a is moving on.
There was some and it's
a guy who was the leader of a psychology.
Sociology is the crypto research working
group from the Internet Engineering Task
Force.
Except for these and
as a culture will still be there to
advise them, you know, tell them whom
to listen to.
Now the hope was that we could finish
this on a happy note saying it's
all good now.
It's, hey, there's a happy
note here. Microsoft has chosen curse.
So once Microsoft stepped in,
that's the end of the discussion.
Embrace, extend, extinguish, stop
arguing. Oh, sorry.
Well, so the final slide would have
been something nice. But at the moment
it's just the discussion continues.
Thank you for your attention.
Thank you very much.
OK, we only
have very, very few minutes for Q&A,
so please quickly line up at the
microphones. We have like three to four
minutes, so be really quick short
questions only don't ask about your
thesis. Just ask questions.
OK, Mike to go.
Are you actually aware of any attacks
or weaknesses in any of the next
180 secesh to
sorry. Any weaknesses in.
Could you repeat curves included in this
one. Eighty six dash to.
Yeah. So for instance next
to twenty four is not Twist's secure.
Anything else that's the only
one that's known to be a problem?
Look, all of these are if you're willing
to do the work of implementing very, very
carefully and you check for
a point coming in, being on the curve,
having the right order, et cetera, et
cetera, if you're willing to do a lot of
work, has something that's slow
and fragile, hard to test, hard to
implement, then you can do something
secure with the next elliptic curves.
Then the steps forward that are
part of modern are
do something that's faster and
easier to implement correctly.
And that's something that, well, most
people are happier with.
Thank you.
OK, Internet, please.
Yeah, very short question.
If you read the NSA, could you influence
your own stand so that you could break
it? And how would you do that?
Well, short answer, the nice thing about
standards is that there's so many to
choose from.
Is that the answer?
OK, Mike, which one
I mean, three answers, if I'm
free to choose, say, the NCSA
to the French standard, there's no
justification given whatsoever.
I can feed you whatever I want.
OK, this Mike, I can't see the number
because there's too many people, how
do you come up with the killing of
45 bits and how do you know it's secure?
It's just the absence of something
like Enoch's calculus.
So the key to the fact
that index calculous doesn't apply
is what allows you to get away with
very small key sizes compared to
RSA and then something like two
fifty six bits that's coming from saying,
well, the biggest computations that
someone can do with current computer
technology ten years from now, computer
technology using say a sixty
five megawatt power substation, that
biggest computation they can do would
still not break a two hundred bit
elliptic curve. So we feel very
comfortable using two fifty six.
So for the, for
the text that we know how to do all
the numbers, I'd say of course that's
theodolite PTO.
So there you can see like how many
operations to do the 200 you need to do
for breaking a full forty one
414. But Kolff.
OK, we are unfortunately out of time.
So please again thank our speakers.