Yeah, we talked about elliptic curves And how we can use them as a sort of drop-in replacement for the mathematics in things like diffie-hellman key exchange and the digital signature algorithm and so on. There's another interesting story that people are asking me to talk about which is the story of the Dual EC-DRGB or the Dual Elliptic Curve Deterministic Random Bit Generator, which is a pseudo-random generator for generating random numbers. Most of the time you do programming, you don't need something that's truly random, right. If you're writing a computer game, and you need the AI to act in a kind of unpredictable way, a normal general mathematical random number generator, but just move some bits around and produces numbers between a minimum and a maximum Should be fine For cryptography that is not the case for cryptography What you need to not be able to do is predict anything to do with what it's going to output it needs to be as Random as you can and of course the problem of computers is they aren't random? They don't operate in a random way So if I produce any mathematical function or any logic circuit that produces something that looks random the problem is it isn't actually random What a normal operating system will do is combine an Actual source of randomness so for example the decay on over radioactive isotope or my mouse clicks which are kind of random Or my typing which is sort of the pace of which is a bit odd? and It'll combine that actual randomness with something that produces a very long stream of random bits for use by Applications on a machine like these. Oh these are called cryptographic random number generators. We're not talking about the actual randomness today We're talking about the generators for generating these random bits but they used all the time if you go onto if you perform a Handshake on the Internet you're going to be generating a random number used once you're going to be generating the private part of a Different key exchange and so on so these need to be unpredictable if I can predict your private diffie-hellman key Then I can just get straight in on your conversation That's not a good thing the way Normally a random number generator like this works is a bit like this so we have some kind of state Which we'll call s and that's the current internals for our random number generator, and that is a secret now This is seeded based on real random date so for example the keyboard taps or the hard disk Latency and things like this on a computer now what we do I ask this random number generator to generate some random bits for me, and it passes this state Through a function G. Which is a one-way function like a hash function and this produces some seemingly random bits? Which I can use in my application for something secure now if I ask it to produce G of s again It's going to be the same thing the hash is always the same So what happens is at this point? We pass s through another function f of s And it comes back down here to be s plus 1 and so the state gets updated. This is in general What a random number generator will do so we seed the random number generator With something actually random and we keep doing that whenever we can, but it doesn't happen all the time And then we can update the state and we can generate Random bits as required now usually these are different functions But often hash functions of what we use the reason is because it has to be one way What we absolutely want to make sure is that I can't work out as an attacker what this state is because if I can I? Can predict the next random value you're going to be that could be your password, but you're generating on your password manager So I've seen this output. This is something you sent in the clear. Let's say a random number or something I've seen it Can I calculate what the state is well no because it to do that I have to reverse this one-way function this hash function So I can't do it. I'm stuck here That's the idea now in the early two-thousands the National Institute for Standards and technology's in the US Published a list of four new random number generators the idea being that these would be adopted by the kind of key players who are actually building these libraries like open SSL so most of these were kind of standard like like I'm Showing you here one of them was based on elliptic curves and was a little bit unusual And so it kind of piqued everyone's interest and though I say peak devil and suspicion at the time this was called the dual Elliptic curve drbg which I was going to call Julie C from now on otherwise I'm going to get very tongue-tied it works very much like this using elliptic curves just to remind you when we talked about elliptic curves an elliptic curve looks a bit like this and it has a formula of the type Y squared is XQ plus a X plus B The idea is that this can be used to perform a one-way function like our hash if we have a point here P on our curve. We can produce a multiple of P Let's say here. Which is a P, and if I give you that you can't tell me? What a was right? That would be solving the elliptic curve discrete log problem very very difficult right That's all we really need to know about the mathematics for this particular one so we could replace these two one-way Functions with these elliptic curve functions this point addition and kind of get the same kind of structure going and the and the nice thing About it If it worked would be that this is kind of mathematically Provable in some sense because we know how difficult this problem is we don't know for sure what the difficulty of this hash function is Because no one's broken it yet right we all fought sha-1 with unbreakable and then what happen All right So how does Julie C work all right? So we have our two random variables on our curve right P? Thank you. It doesn't matter where they are for this example They just points on the curve, so those each have an X and a y-coordinate We have a state for a random number generator s. That is not a point on the curve It's just a number so what we do we want to use s to generate some random bits But then we also need to update the state and their state has to remain secret remember So the first thing we do is we calculate s P all right, so we're moving P around the curve s x right and that gives us our R is Just the x coordinate of this so this is going to be a point on the curve we take the x coordinate and that's our number now ah It's sort of an intermediate variable we're going to use it to generate our random bits, so we calculate our Q and we take the x value so our Q X in some sense and we scrap the first 16 bits of that we take the least significant bits of that from 16 to the end I'm using sort of Python notation. Why not write what sort of size and in bits is that number? They're going to be approximately 256 bits because they're modulo upon bits 256 bits and this particular curve now this has been our random number Right so so far so good. We've got some random bits out We then use our we pass it through P again, so we say our P. Don't doesn't so why and that? Produces our new s but by taking just VX again So what we've got is the exact same framework that I showed you at the beginning We've got a state. We update the state by moving It around the elliptic curve a bit and taking just the x coordinate But we also can output some bits in principle Which is not a terrible idea for a random number generator except for actually this is much slower than a normal hash based one by about a thousand times right which For you know for someone who really cares about security Maybe they would be able to accept that but in fact actually there are some other bigger problems with this that mean that the thousand times is really the Good part of the deal in SATs in some sense Remember that the whole point of this is that if I get this in the clear? I can't reverse to find this internal state the reason I can't do that is because first of all I don't know what our Q was and even if I did I Can't go backwards through this to find R. And then go this way right so we can't reverse that because that is a one-way function Remember just because of the elliptic curve problem if I was an attacker how might I attack this well the first thing is to notice Is for 16 bits it's not actually very many So I can brute-force through the possible our Q's quite quickly to to the 16 operations 65,000 operations even on a laptop not going to take very long so I go through and I find all the possible X's for this random data And only some of them are going to adhere properly To that elliptic curve formula where we can find an actual Y that goes with them. All right? So let's say we go from 65,000 to 10. We have 10 candidates That's a real problem, so we found that our Q fat alone Wouldn't actually be much of a problem So then the question becomes can we reverse this discrete log problem and find our way into this state Which would be a huge issue and the answer is? If these two a random no we can't do that all right if P And Q are truly random we have to brute force it we have to start with as one doesn't work ours, too Doesn't work and how many how many of those are there? 256 bits worth which is not Yeah, it gets a bit more complicated that not all point to valid on the curve and so on but is a lot of them Now what if there was a secret mathematical relationship between would that change anything? What if he was actually equal to some multiple of hue like this now it will be very difficult to prove that Because if we can't solve that problem we'd have to find that a by brute force ago Or there is a relationship between the two brilliant Right we don't know but the problem was that when this standard came out It was implied that the NSA were the ones that generated these points And they did not explain how they did it you remember the video on nothing up my sleeve numbers Let's pick a number at random I don't know 24, and then did some trick with it you think well that's great but clearly 24 wasn't random There's something up the sleeve. We're not sure about it. If this is true. If there's a secret e Which we can multiply by Q to get to P, then? Here's what happens? We have our Q because we've derived it from bith here All right, we can calculate e Our secret e times our cue, it's associative so it's actually our times EQ EQ is P so we've got R Of P which is this and we've calculated the internal state? Right this should be impossible to go backwards from here to get to here. It's trivial if we know this secretly Right which is kind of worrying? What's more interesting about this It's not so much the mathematical backdoor, but could exist it's wherever it exists. No one knows and What happened when this NIST standard was announced so when it was announced? Cryptographers said well first of all this is not enough bits. You're cutting off here right. There's a slight bias in the output We don't like it. It doesn't look random enough. That's a problem. It's a thousand times slower. That's a problem All right, this didn't worry too much about this. They said it's fine. Why we're gonna put it in then in 2007 dan sumo and Niels Ferguson from Microsoft did a short talk Explaining that this backdoor could exist you know that should have killed this off straight away But the problem was but it was an agreed standard in this it was starting to be implemented in some of these libraries And that's deeply concerning. We don't know whether this exists Hypothetically it could all right But no one can find this e so how can we know but then the Snowden leaks came along? And it looks even more suspicious money was changing hands between the NSA in companies to have them install this as their star For a number generation. That's deeply suspicious and so The strong opinion should he be consensus of the cryptographic community is that this is indeed a backdoor? someone knows that a but it isn't me and But we don't know for sure, but it's a really interesting issue because There could be a backdoor But they might not now of course when you're using this you can generate your own P&Q and Then it's not it hasn't got a backdoor. Well if you put it in yourself But the interesting thing was in my list standard they said you have to use this P, and Q if you don't we won't Give you a fits accreditation for being extra secure which is also suspicious So it's a really interesting read if you read the history of this People were coming up with problems. They were publishing papers saying that's not right and They were being ignored and the standard was put through anyway, which is you know very interesting? if I was on stage I Don't do magic right, but if I was on stage and I said to you let's pick a number at random I don't know 24 And then did some trick with it you think well that's great but clearly 24 wasn't mathematics to do with lines and the tangent of this curve It's actually not very complicated the point is of what we're doing is by multiplying G By both numbers or adding it to itself this point addition. We're moving around this curve
Betteridge's law of headlines.
secp256k1 (selected by ethereum, bitcoin, etc) vs secp256r1
I guess it's safe unless the vulnability is in the EC somehow.
I still have deep respect for Mike as a teacher. He keeps things engaging yet understandable, raises some good questions while explaining some and letting you research some others. It's a delightful blend of in-depth and clear and I know how stupendously hard it can be to be this charismatic blend of interest. I always immediately watch videos of Mike.ο»Ώ