Elliptic Curve Cryptography for those who are afraid of math

[Music] hey everybody going down to the last talks of the day I know you got super excited woo or not maybe you want this to go on for another all week like instead of doing RSA you could just do [Music] bides once again just want to thank our sponsors uh without them this would not be possible um if you have any feedback about the conference please go to bid.com feed back um if you have any spe specific session feedback if you go on the schedule click on the spe session there's a big s a feedback survey button that you can click and provide feedback um we have one more raffle going on at the end of the day uh it's $150 Amazon

gift card uh if you just go out there provided by Jim Alto so go out there and uh put your name in the box if you want to and we'll raffle that off at the end of the day um we are also done with with uh everybody checking in so we have a few extra t-shirts shirts so it's first come first serve um so if you're interested in a volunteer security shirt um feel free to go and check and and uh and give it grab one uh now we have uh Martin grutin a virus bulletin he's going to be presenting elliptic curve cryptography for those who are afraid of math please give me a warm welcome

Applause to

Martin thank you when I was in my late teens my dream was to become a professional mathematician one day and I actually went to study mathematics and after that I worked some years as a mathematician um doing research in an area called algebra geometry which includes the study of elliptic curves life doesn't always go the way you plan it and for some reason kind of randomly about 10 years ago I find myself working for a security company and then I discovered that these elliptic curves that I like so much uh they play an important role in cryptography so what I'm going to do today is I'm combining my two backgrounds and talk and I will explain

how elliptic curve crypy works but leaving out all the boring details um I need to make some disclaimers first thing I want to make make clear crypto is hard and it takes a lot of mathematics to to learn crypto and even more to learn Li the Cur cryp though you can't do it in 25 minutes you're not going to learn anything that you can apply tonight tomorrow in the next year so sorry about that um I also want to make clear I'm not a cryptographer um I I think I understand it well enough to explain it but I I don't shouldn't call myself a cryptographer and finally to to make uh to help explain to to help to make sure that um

I don't stumble over uh small details uh I'm cutting a few Corners here and there so apologize to the penants in the room okay okay every introduction into letic curve starts with this formula y^2 = X CU + a * x + B and that's a prime number P because in crypto there are always prime numbers and I think this is unhelpful because this doesn't really matter so please don't uh try to remember this formula but do remember that there are some choices to be made if you chuse a different a or a different b or a different P you get a different elliptic curves and some are more suitable than others um what is important is this

figure this is what the elliptic curve looks like um you see it against the Cartesian axis and you can see that it looks bit funny and it is symmetric in the horizontal axis and on the elliptic curve there are points and these points play an important role and you may remember from secondary school is points can be represented in a um by two coordinates and I will assume and that's one of these things where I'm cut in Corners that a computer represents a point by a number so points and numbers are the same thing so an important operation uh takes a point p and a point q and it takes the line through p and Q and it's a fact you

just uh need to believe me that always a third point on the curve uh that's also on this line and I said the curve is symmetric in the horizontal axis so you can take the mirror image of that point the third point and we call this P plus Q I cannot stress enough that this is not supposed to make any sense mathematics students when they first learn this it doesn't make any sense uh to them either uh I'm not explaining to you what p+ Q is I'm just defining something called p+ q and and why is this p+ Q it will never make sense during this talk but it will become a little bit clear in in two

minutes um and this is called Point addition on a curve um there's a special case if you want to add a point P to itself to get p plus P so what you do in this case is you take the tangent line the unique line that touches the curve at at B there's always unique line and there's another extra point on the curve and also on the line you take the mirror image of that point and that point is p plus p and we actually call this 2 * p and that's Point doubling and we can combine this we can combine uh Point addition and point doubling by adding p and two uh two plus two * p

uh so we take the third point we take the mirror image and we get 2 p plus p and we call that as you will expect probably three * p and we can continue we get four * p and five * P I'm not showing the construction here six times p and this operation is called integer multiplication so we can to add points together we just Define that and we also Define how we multiply points and it turns out that whatever you would expect from addition and multiplication all these rules uh work there's some edge cases you have to consider and everything falls into place mathematics is often very nice like that H and it

means and you don't have to remember this the points on a curve from something called an aan group and that's very useful for crypto and especially has a very nice property is that we can do this multiplication very fast so if you want to go from a point P you want to compute 100 time P you would expect that it needs 999 steps 99 additions and actually uh um you can do this in eight steps um this may go a bit a bit too fast for you uh don't worry about this just believe me that you can do this in eight steps but if you've ever implemented fast exponentiation in a programming language it's the very same

principle and if the numbers are even bigger uh what you earn is is much more so U multiplying by a billion takes 50 steps and and actually even less if you do it slightly faster and multiplying by the enormous numbers you you see in crypto uh takes a few hundred steps most uh on the other hand the opposite operation is very slow so what I what I mean is if you are given two points on the same curve p and Q and you know that Q is n * P for some number n which may be 100 which may be 15 uh quintilian uh the really the only way to find this number n is to try if if P two times P

three times P until you get Q This is extremely slow and if numbers are very fast then computers simply can't do this uh unless they got millions of years so this combination of multiplication being very fast and division being very slow this is called the discrete logarithm problem for elliptic curves and that's the basis of all elliptic curve cryptography um the most probably the most common implementation is elliptic curve def Helman and um It's a situation where Alis and Bob want to agree on a secret key over a public Channel and I wrote write agree uh in inverted commas because it they don't so much agree they actually generate some secret key together over a public

channel uh for example Alis being is a web browser B is a web server and they they need to get a key so that they can encrypt a TLS session so what happens is that Alis and Bob first agree publicly over an certain elliptic curve to use and a point p on that curve and Alice chooses a large secret random number a a very large number and B chooses a large random number B and they both keep these numbers secret they don't tell them to each other they don't share them with anyone now Alis computes a times P so a times the point p p and as I said before even if a is very large which it will be

she can do this very fast and she shares this answer with B with Bob and Bob computes B * P for his number B and shares this with Alice and again he can do this very fast now Alice take this point B * P which Bob gave her and she multiplies it by a by her number and she gets a * B * p and likewise Bob computes B * a * B and as I said before mathematics all the the ma that you would expect uh works so a * B * B and B * a * B they are the same number and if you think a little bit about the disc logorithm problem and that's probably

something you should think about later uh you will know that anyone who could intercept the full communication can't uh crack this key so this is a way to generate a secret key um this is used a lot in um https in if your browser connects to a secure web server and if you're very bored you can read rfc's defining uh TLS and elliptic curve Dey Helman in there and you can actually find the numbers that are and the points that are shared uh with wire shark uh but it's it's a bit boring and I didn't have time to um explain it in this talk there's a second implementation that's random number generators and as you probably know computers in

are inherently bad at Randomness that's kind of a feature of computers they they are do things extremely predictable now computers can do things randomly for example they uh write something to dis and measure how long it takes and in measure in Nan seconds taking the last two digits that's kind of a random number but that's not good enough computers especially servers that need a lot more Randomness so there's something called a random number generator as an input it takes some true Randomness then it uses this through Randomness puts it into some kind of mechanism some algorithm it generates some output part of it is usually then uh the true random output and the rest of the original

output is is then fed back into the uh mechanism and so on and the next yeah and I always imagine this like some machine that that CHS out random numbers if you input a random number once and you can use elliptic curse for that um remember that the discrete logarithm problem um one way to look at it is if you get a point a number n and for a given point p and you take n * P this doesn't tell you anything about n so basically it looks very random so N is a random number then the next number the n * P the point SL number is again very random so how does it work so we start

with a number n zero that's like a true random number one that the computer has access to but not enough then we take n0 * P to get a number N1 and we take N1 * P get another number Point SL number N2 Etc and the output of the random number generator is just N1 N2 N3 that's just a series of random numbers so these are random numbers except there's one problem a property of random number generat is that they sometimes share the random numbers publicly uh which means that that an adversary uh sometimes has access to N1 and that's not that's not a bug that's a feature but if if they have access to N1

they can compute N2 and N and3 because the speed is public so if they have access to N1 they can crack the whole random number uh generator which you don't want because random numbers are supposed to be unpredictable but we can modify this algorithm a bit by using an extra point so now we have an elliptic curve with two points p and Q and we take n zero and because I'm going to formalize things a bit it's a 32 BYT seed so 32 bytes of proper Randomness and again we take n0 * P to get N1 but now we don't just take N1 we take N1 * Q it gets another 32 BYT Point SL

number we throw away the first two bytes and we get another 30 bytes and that's your random output and we get this again we take N1 * p and to get N2 and N2 * Q uh and 30 bytes thereof that's the next random output and remember that the discrete logorithm problem basically means that you can't go from N1 * Q to N1 so you can't crack this and I should say um credit where credits you this the idea of this slide and the next one uh to present it this way is based on a talk I once saw by Dan Bernstein Nadia hinger and Tanya Lang now there's an interesting fact they said there is a is a large number D

so that P equals D * q and the discret logarithm problem says that you can't crack D but imagine someone somehow has access to this number D what can they do well firstly and that's unrelated to this D um they only have the 30 bytes out of 32 but there's only 65,000 possibilities it's actually very easy because the point has to be in a curve and it's very easy to uh to actually get the full random output so the full 32 bytes and let's call this R1 so and at first has that's a property has access to R1 now um I claim that D * R1 this magic number D that U imagine someone has access to

it hypothetically is the same as N2 so why is that true it's actually quite simple um so N2 is by definition N1 * p and uh that P was D equals P equal D * Q as we said uh you can change the order as we've already used before so that's equal to D * N1 * q and N1 * Q is R1 so someone who has access to D and someone who can read R1 which is something that you assume will sometimes happen can compute R2 N2 sorry and can compute the next random number and the next random number and again has cracked the algorithm so the million dollar question or perhaps the 10 million question is

who knows D well this is this is actually algorithm that that's a standard for that and um it's defined as you get it on the internet and it says on the second page or so uh n who uh wrote the standard gratefully acknowledges and appreciates contributions by Mike Bole and Mary base from NSA oops as you all as most of you probably have guessed this is uh the algorithm duly c drbg um which has been making the news a lot in recent years and and I should also point point out uh I suggested that it was a good idea to use elliptic cures for random numbers actually it isn't uh Matt Green has written a great blog post about this

for example it is an extremely slow algorithm so even if no if you thought no one knew d uh it was still a bad idea so this made the news again recently at uh Juniper and um Juniper uh I'm not suppose you I don't suppose you can't read this but jenniper had already publicly said somewhat hidden on his website that they used uh dual C but they use different points so in its screen OS operating system they used different points p and Q um and in theory that's fine I mean apart from the fact that it's a very slow random number generator but but okay I mean that's that's their problem that's not your problem as a customer if

they need to put extra memory and then computer power in there well it's their problem so in theory it's okay to use different points but in practice you still have a potentially broken random number generator and it turns how that someone somehow managed to change the points p and Q to different P andq not the P andq that the NSA had generated where they knew the number D but p and Q were supposedly this adversary China Russia whoever uh knew the number D that had the showed the relationship between this B and Q um so after du cdbg people have been wondering rightly is anything else that the NSA or others have up their sleeve

and actually um it's good to to point out that the curves that are used in uh elliptic curve Dey Helman in your browser that's called p256 that's that's a curve with a point on it um they use some content that are not fully explained and we can't fully exclude that there is a back door that there weren't Chen that were chosen by nist again who are very close to the NSA that RA in the back door and that probably isn't such a back door um but we should really aim as a matter of principle almost to use curves uh that have only use content that are that are obvious that that are not mysterious very small numbers um if

you ever see curve 25519 which Dan Bernstein invented uh that's such a curve and it it's also extremely easy to implement um if you want to read more about this and if you want to basically um see the theory that the NS has back doored uh all these curves debunked uh that's a great paper by Neil kobit and Alfred manes so to round off um I hadn't mentioned this but elliptic curve cryptography is actually a very good idea in general uh because you can do with much smaller Keys um computers are getting faster and using RSA or standard Dy Helman you need to increase the size of your keys um 256bit elliptic curve crypto gives about the same security s

372 bit RSA so uh it doesn't take as much CPU it doesn't take as much memory it doesn't yeah take much space to store keys but there's also a big weakness and um is that it uses complicated math I mean it's it's not the most complicated math ever but that's a kind of math that most ma students of mathematics will never uh come across and it's often implicitly s that that that the fact that elliptic curve crypto uses complicated is um is a strong point and actually I think it's a weakness I mean if you use crypto that you don't understand then you basically need to trust someone else and RSA is is a lot

more basic and I think there are enough people to understand this uh elliptic crypto that that we should use it but we should be wary of that uh you should really consider this a weakness um I've talked way too fast because I didn't think I would have six minutes left for questions but uh there should be time for questions I'll be speaking at another conference in town uh on Thursday morning about a different topic and I'm on Twitter and email and thank

[Applause] you

yeah

if we consistently use wellknown derivations for constants or extremely obvious constants is that enough to at least create the correct incentives for disclosure like if somebody does realize that there exists a d and the D is dangerous if we have fully public derivations does that make us reasonably safer uh in practice yes and and the problem isn't here that there exists a D um you can generate two random Curves in in a way random points on a curve uh so that we know there is a d but you can you can kind of show no one can find the D this way because my two points are the first two obvious points that satisfy something and we know there's a d but we

also know we can't compute it that's a discrete logarithm problem yeah can you say anything about vulnerability of RSA versus ECC to Quantum cryptography I mean Quantum Computing yeah I was worried that someone would ask about Quantum Computing I know very little about Quantum Computing I think ellip know um elliptic curve typography in general uh is vulnerable to Quantum Computing attacks uh yeah so elliptic yeah almost simar in a similar way that uh RSA is I am the afraid of math part of your audience can you back to the slide on P * 2 p * 3 sorry on the can you go back to your early slide keep going yeah getting that further P plus

Q There here when you draw the first line yes how do you know the angle to draw it is it still the same angle as the line from p through q and you're just moving it to a different point on the Curve so sorry I I I I couldn't hear your question when you transition from here to the next slide this one yes when you draw that line yes is it just keeping the same angle for that line and moving the starting point to a different point on the curve um no it is it is um coincident that the angle is more or less the same no it for any point on a curve and

that's a property of for any curve not even elliptic curves uh there's a unique line that that goes go through the point and that goes through the that that only goes through it once that touches it there it's called a tangent line that it's like basically you take two Co points and you move them closer together and you look at what what happens to the line through these points and at some point the the points fall together and there's a unique line so I see so the tangent line will change depending on where on the curve you put that point P thank you

yeah any other

questions on the quantum Computing as far as I've been able to tell from everybody the answer out there is that for RSA it's definitely susceptible and for elliptic curves uh we don't know yet um nobody's figured out how but everybody worries because it's a short enough thing that if they do figure out how then it'll be a problem about Quantum yeah but but right now it looks like it's probably not vulnerable I have been told that shes algorithm which is used to crack RSA and in at least in theory it works against litic curves but uh there are um yeah there are practical issues I mean there are people who think we might never be able to crack some crypto even

with Quantum Computing I'm I'm I'm not an expert I mean I worry about cont Computing mostly because now I understand the crypto with con Computing I won't understand it anymore yeah have to trust other people and that's yeah that's freaky any further [Music] questions thank you