## Subtitles section Play video

• 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

• 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

• 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