Placeholder Image

字幕表 動画を再生する

  • 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

Yeah, we talked about elliptic curves

字幕と単語

動画の操作 ここで「動画」の調整と「字幕」の表示を設定することができます

B1 中級

楕円曲線のバックドア - コンピュータマニア (Elliptic Curve Back Door - Computerphile)

  • 0 0
    林宜悉 に公開 2021 年 01 月 14 日
動画の中の単語