In other words: if there may or may not be a backdoor, but the NSA is showing an awful lot of interest in the alleyway behind the building, there's probably a backdoor.
You can defeat most of the backdoors they put in by picking your own random numbers. In ECC, the private key is just the random number. You can start with a random number given by the library, do an sha256sumk on this with the time of the system in milliseconds, grab another random number from the system, then sha256sum those two numbers together. That's pretty unpredictable. People are HONESTLY afraid to "pick their own random number" and they SHOULD BE. But remember F (random_number) = another random number and if the function F is a hash, it's not reversible. You can take random numbers and add your own (perhaps not at all secure) numbers as well to operating on a potentially compromised random number, which isn't really random.
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.
Yeah as soon as I see him on thumbnail I watch that. I don't know what it is but his talks is more like inviting to think and get excited together than teaching to someone without knowledge: I don't know most of what he talked about but somehow I feel like I got the ticket to be included in enjoying excitement of some sort
+Keiji Ikari A quick Google suggests that current estimates for the number of atoms in the *observable* universe (which is much larger than the amount of universe we can see, mind) is on the order of 10^80, or about 1000 fold larger than 2^256.
Getting quite close (in relative terms) isn't actually that hard. Every 10 bits is about three magnitudes. 256/10*3 = 76.80. Actual result 1.15e77 or 77.06 if you take the log of it. That's being off by a factor of less than two. Now being able to pronounce that number is something very different though ;) .
Ah, oops... I remembered the "80" part of "10^80", but assumed it was 2^80 and "rounded up" to 2^128... I also recall someone saying there were enough UUIDs, or IPv6 addresses (which are 128 bits, minus a few for special things) for every atom in the (observable) universe, but that clearly must be a mix up as well...
Well ... from all the items you listed as "suspicious" my suspicion actually dissapeared. I have no doubts now that it is indeed a backdoor by whoever is paying to implement it (I guess NSA).
P and Q were specified by the NSA and its the NSA that was throwing its weight around to get this standard implemented in commercial cryptographic libraries, you don't even need to guess here.
@@johanlarsson9805 Ohhh, now that video makes a whole lot more sense. Computerphile did not specify how an attacker would be able to reverse a key from just sniffing the operations running in a CPU, but if the objective is to figure out how many times a point was moved in an elliptic curve, this would be a way to do it
all the ecdsa/P-xxx algorithms are inherently flawed, lookup secure-secure-shell which is a guide on how to choose secure algorithms for SSH. The much more secure/robust algorithm called curve/ed25519 is what is recommended.
Excellent video Dr. Pound. You have a great way of explaining things at just the right level of detail. Making notes on 132 column tractor feed paper is just an aded bonus! Keep up the great work.
true randomness can only be acheived via nuclear decay or even just listening to the most common truly random thing most of us have heard; radio/tv static.
@@themanofiron785 I'm no expert on this matter so I really shouldn't be defining anything, but, based on what I understand it's like this: any closed system cannot be truly random, and since the universe is a closed system it itself cannot be truly random. Obviously even if that's accurate the amount of "variables" that exist in the universe make it pretty much infeasible to replicate any given state, but again I'm no expert so I may just have some facts mixed up or I'm just completely wrong.
When I was in collage our security teacher could not explain most of the things well. I find these videos very educational and interesting. Thanks for explaining these 😆😆😆
I find it astonishing that a standard can go through and still be used with so many "that's suspicious". Just one suspicious thing should be enough to just ignore it and use something else..
As far as I can tell, that's usually how it goes. But security isn't always the top priority, sometimes speed is. So it's a balancing act... Except in this case, where 1000 times slower and there possibly (definitely) being a backdoor was ok :') I don't think the community at large uses stuff like this tho, although I guess companies might?
Elliptic curves have one big advantage. You can get along with verry little memory and at least i don't know a common side channel attack. Which makes them great for embedded stuff like machines. The potential back door on the other hand is nothing great as machines usually run for a view decades.
"If there's someone who knows this e, and it's not me..." That's exactly what you'd say if it WERE you, isn't it? Seems pretty suspicious to me. You don't see many people denying they know that number, do you?
I think there is a very important detail missing in the video: we know *absolutely for sure* that e exists (since the group of points has prime order and so it is cyclic and every element except the identity is a generator). What we do not know is if the NIST knows it (in the sense that we do not know if they picked P and Q randomly or rather they chose P and a number e and then took eP as the second point Q).
Many operating systems use the date/timestamp of the startup time as the random seed, which ensures a unique seed always, unless your battery is knackered. Sun workstations would sample the noisy analog audio input.
NIST: Please use this type of padlock. We thoroughly tested it, it's very secure. NSA: Yeah, and if you use this and only this type of padlock, then have some money from us. IT security researcher: Someone might know how to crack this type of lock. NIST: Haha! I swear, we tested it and there is no flaws. It's the best padlock. Honestly, mate. Just use this exact type of lock. Researcher: Could I adjust it to use my own type of key cylinder? NIST: Definitely not! That wouldn't be safe any more!
I don't get it. Why would the NIST tell developers to use a specific P and Q and not generate their own? Do they really think that won't raise instant red flags? It'd be like if the guy installing your home security system told you your PIN had to be 1234, no exceptions.
Wouldn't it raise just as many red flags if they were willing to let developers pick their own P and Q and certify whatever they chose? They'd be giving the green flag for developers to put their own back doors in. The real problem isn't that there could be a backdoor built into these P and Q values. The real problem is that ANY p and q values are suspect regardless of who picked them. And before anyone says "just use another rng to generate them", that doesn't work either, because that assumes that you can believe the person who says that they generated them from another rng. Sure maybe YOU would choose honest values with no back door, then again maybe the NIST did as well. You want to choose your own so that you know they didn't put a back door in. Maybe they want you to use theirs so that they know that you didn't put a back door in. Who can be trusted? Honestly, the fact that this type of back door CAN exist, effectively makes the entire process fundamentally flawed.
+phiefer3 If the whole idea is that Q must not be divisible by P, why not derive them from twin primes? The main issue here is that NIST didn't explain HOW they got these numbers.
You should go back and watch the original video on elliptic curves. When they say "multiple", they're not talking about simply multiplying or dividing a number by another number, they're talking about jumping being able to move some number of times from one point and end up at another point. (ie if you start at Q and then move e times you end up at P). And the video makes a little bit of a mistake when he says "if" they're a multiple, because the way elliptic curves work, there's almost definitely some number of jumps that can be made from any point on the curve that will land you on any other given point on the curve. In other words, there WILL be some e such that P=eQ. Now calculating the e of a given pair of points is prohibitively difficult, and would be pretty secure, but choosing points for a given e would be extremely simple. (as mentioned in this and the other video, elliptic curves are similar to hash functions in this way, it's simple to start at some point Q, pick a very large e and then calculate a P to create your back door, but doing it backwards to find the e of a pair of points is much much more difficult).
Great video, great channel! I don't understand half of the things described(wish I had a bigger interest in mathematics as a kid) but somehow I can follow the principles mentioned. Thanks, and keep posting!
I have been watching Dr Pounds videos for quite a while now on this channel and I must say I love the way in which he explains things. Please convince this man to also explain other things like political stuff or so! I know he might not be an expert in those fields, but I feel like computer scientists might have a super logical take on things. (And I just love his voice.
we did this 'back door' mathematics in seismic processing - called deconvolution... 1> we know the original source signal (dynamite or vibrator) 2> we run the source through the earth 3> record the signals... 4> deconvolute the original source and you get a 2d slice of the earth's structure...
SSL certificates. So whenever you visit an online shop or "secure" website, you'll see the certificate, usually next to the address. If it says ECS or something similar, the NSA know what you're doing.
BIG Dave Every company based in the USA needs to give any detail that they detain if queried. Google, Facebook, Amazon, Apple, etc. Not only do they exploit your data, they give it to PRISM, a gigantic mass surveillance organization that is managed by the USA, and it is a known fact they collect data that passes by the Internet, so yeah, ECS is like their golden boy. They collect encrypted data, but they can’t use it. Now imagine they use ECS, the NSA would have access to all data. Better off using Axolotl
With "this standard" you mean the RNG function talked about in this video? Pretty much none. As it was either not used in the first place anyway or has been withdrawn for some years now. Especially what "BIG Dave" says is completely wrong, SSL does not use Dual_EC_DRBG.
whuzzzup As mentioned in the video, it actually was used in the real world by companies paid by the NSA. For example, it was used by default in stuff produced by RSA, inc., which notably included many security fobs.
since computers take counters, regular clockspeeds and therefor timedependent states into account it is actually difficult to guarantee absolute randomness for parameters. Of course if a random generator seems to be deterministic in any way (dependent calculation times for specific bit lenghts is enough - timing attacks) it is to be discarded.
Basically, "If you don't use this, that may have a backdoor, and instead use your own to make it more secure, we'll say you're less secure..." Well that makes sense...
When I worked at NFR Security, we had a co-worker Jason Wright (immortalized in the Wikipedia page on IPSEC). He was an OpenBSD-associated dev that wrote our ethernet drivers. He was publicly accused of inserting code into OpenBSD to weaken its random number generator on behalf of the FBI. We came in that morning, and he had to make a public statement about how it was a nonsense accusation. All his commits to OpenBSD were given strong scrutiny. I think there were minor bugs found in the commit, but no clear evidence that he managed to break random number generation in OpenBSD.
Oh yeh , the 2nd mos interesting person on computerphile , afte the one and only ledgend, Professor Brailsford, well 3rd if we are counting Brian Kernighan
So if Dual EC has a back door, even theoretical, then it must, by definition, already be broken. Therefore the NIST accreditation for being extra secure is worthless. Ironically, using your own P&Q becomes more secure, since e is less likely to be known. But then, e will always be known since e=P/Q. Whether e was explicitly choosen or implied. If P&Q are choosen randomly, what random process would we use to choose them? Now we're just going around in circles until we disappear up our own .....
There are groups going through the effort of brute forcing the 2^96 possibilities of private keys to crack open bitcoin addresses. Maybe, if we make a great leap in computational power, some day we could start a cloud computing project to find e. Maybe...
It makes sense if Alice creates Q and 'e` and finally P as eQ. She transfer these values to Bob. He creates the seed ''s' and can create random Bits. Alice can verify these random Bits without knowing the seed 's'. There are some possible application of this. Alice can't predict the random bits before the first value (rQ). It's maybe useful.
Any standard which is essential and has been put under a doubt san never again be considered safe. As far as I'm concerned, this back door can not be excluded to exist through a combination of suspicion and circumstances thus this particular generator can not be trusted.
Hmmm. The NSA has tried several times since the 1990s to establish a master key back door in the crypto algorithms they promote. So, this is just another attempt. I guess this is also the reason why many countries are trying to establish their own proprietary algorithms in the financial and data comms areas. They often forbid the use of the classic US algorithms. But then all these cryptoligists in the NSA have to have been working on something. I remember the publication of the book on differential crypto Analysis in the early 1990s. This made short work of many symmetric Algorithms. However it did not for DES. In fact differential Crypto Analysis in DES was by orders of magnitude harder than brute force. Little Reminder DES was developed published in the late 1940s. Differential crypto Analysis was only discovered by Academia in the late 1980s.
Has anyone published a correlation study? If e exists it should show up in a large set of P’s and their associated Q’s, at least as a R-squared not equal to zero.
Or maybe, it has no backdoor, the other options have backdoors. And the NSA know if they place a heavy, obvious interest on the one that COULD be weak, even after public articles saying so, and paying people to try and use it, that people will instead flock to the other options, which then ACTUALLY have backdoors the NSA already have access to. The police do this sometimes. They have public statements saying that they're on a mass search for someone who they actually aren't searching for, they're actually just watching town exits. But because the person thinks they're being looked for, they get worried and try to leave, only to walk right into the police who knew they'd try to leave. Just look how many people get caught at the airport. As soon as the police say they're searching the last known area, they're actually searching the airport and just saying that as bait to get them there.
A very important point you forgot, NIST Removed that Algorithm from the list of Random Number Generator back in 21-Apr-2014, so it is not used anymore.
This seems like an easy problem to solve? Why not do the whole process twice, once with their (NSA/NIST) P and Q, once with your own P and Q. That way, you would have to know both your e as well as their e, which neither you nor they know?
It probably is easy to solve in that way, but then of course when the NSA goes to pull some conversations from someone's "encrypted" chat logs and it doesn't work, a Cisco CEO wouldn't get that new yacht they've had their eye on all summer.
So, is this particular standard used now? If so, how widely? How long do we expect it to be in place? What is the consensus on its upcoming alternative?
It is possible to state, with high confidence, the address of a building in England, in which, with very high confidence, there is a person who knows “e”, at least to the extent that their computer contains that number, probably in an encrypted form.
If NSA has generated the Point P as eQ from the Point Q and they might have stored the number 'e'. It is possible. But on the other hand, why to use elliptic curves in case the number 'e' is really unknown? I makes no sense, because hash functions are much faster.
Dr. Pound, could you please do a video on security tokens? I trust your videos to get the details right. Most of the videos on security tokens discuss selling features or legal basis. I’m interested in understanding the mechanics and limitations of the model. Sort of like what you did with these excellent videos on elliptic encryption.
Why not use a seeding from say some source of white noise or even the cosmic microwave backgound which I assume will have a suitably high degree of randomness attached.
Hardware implementation and ensuring the noise pool cannot be tainted. There are dedicated randomness modules you can use, but typically hard drive seek times, user mouse input and all sorts of unpredictable events are used to generate noise.
It might just be that the specific values need to be used for FIPS compliance because they are good values and they don’t want someone to implement their own back door values. It might be a case where the attack was known to the NSA and that influenced policy but no shenanigans are going on.
Its not proven _impossible_ on a classical computer. The general consensus is that it is impossible (short of brute force, which of course can solve any key finding problem given enough time.. but when multiple ages of the universe is not enough time, that's not really an issue worth considering.) On a quantum computer however, its not only theoretically possible but we know how to do it (Shor's algorithm.) I'm not sure that we have discovered any functions that are suitable for classic cryptography that (provably) can't be broken by a quantum computer. I don't think we have.. though I'm also pretty sure we haven't yet proven that such a function can't exist and is just waiting for us to find it. Discovering a cryptographically strong (and fast enough to be practical) classical function that can also be provably unbreakable by a quantum computer would lead to a significant overhaul of the computer security industry, and would remove the need for quantum cryptography (which is a very hard problem.. not because of the math, but because _everyone_ would need a quantum computer to do their cryptography and that's just not going to be practical in the foreseeable future.)
that's the standard discrete log problem (using integer factorization), not the elliptic curve discrete log problem, which as far as i know doesnt have a theoretical quantum algorithm associated with it.
All people really should know about this and understand the implications it has, I find it extremely worrying that we live in a world that is too complicated for >90% of the population to understand.
/me wondered about if other curves such as Curve25519 might have been similarly affected, thankfully not AND the bad one's not in use anymore, afaik...
So is there a way to ensure that our systems don't use elliptic curve cryptography? Or would that require that everyone we exchange information with also not use it?
Technically you could probably edit an open source browser like chromium to not use it. However there really isnt any need, this standard has now been abandoned and elliptic curve cryptography is fine to use
In the realm of IT security "There could be a backdoor" means exactly the same thing as "There definitely is a backdoor".
You could even see the NSA badge portrays an eagle actually holding the key.
@@lingmui3255 lol
...there is one
Murphy warned us.
Mister Potatohead !
In other words: if there may or may not be a backdoor, but the NSA is showing an awful lot of interest in the alleyway behind the building, there's probably a backdoor.
You can defeat most of the backdoors they put in by picking your own random numbers. In ECC, the private key is just the random number. You can start with a random number given by the library, do an sha256sumk on this with the time of the system in milliseconds, grab another random number from the system, then sha256sum those two numbers together. That's pretty unpredictable.
People are HONESTLY afraid to "pick their own random number" and they SHOULD BE. But remember F (random_number) = another random number and if the function F is a hash, it's not reversible. You can take random numbers and add your own (perhaps not at all secure) numbers as well to operating on a potentially compromised random number, which isn't really random.
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.
So True!! I wish all my proffs were like Mike!! Everything he says makes instant sense!
Yeah as soon as I see him on thumbnail I watch that. I don't know what it is but his talks is more like inviting to think and get excited together than teaching to someone without knowledge: I don't know most of what he talked about but somehow I feel like I got the ticket to be included in enjoying excitement of some sort
Anybody who knows things can explain them
Why do you say you “STILL have respect for Mike” ?? Did other people _lose_ respect for him or something??
@@MrSkinkarde No you stuttering red faced gimp, that's not so.
8:36: My favourite part.
-"256 bits worth! Which is... uhm..."
*tries to calculate 2^256 in his head*
-"Lots."
-"Yeah!"
:D :D :D
IIRC it's on the order of "[number of atoms in the universe] SQUARED". (Correct me if I'm wrong though.)
+Keiji Ikari A quick Google suggests that current estimates for the number of atoms in the *observable* universe (which is much larger than the amount of universe we can see, mind) is on the order of 10^80, or about 1000 fold larger than 2^256.
Getting quite close (in relative terms) isn't actually that hard. Every 10 bits is about three magnitudes. 256/10*3 = 76.80. Actual result 1.15e77 or 77.06 if you take the log of it. That's being off by a factor of less than two.
Now being able to pronounce that number is something very different though ;) .
Ah, oops... I remembered the "80" part of "10^80", but assumed it was 2^80 and "rounded up" to 2^128...
I also recall someone saying there were enough UUIDs, or IPv6 addresses (which are 128 bits, minus a few for special things) for every atom in the (observable) universe, but that clearly must be a mix up as well...
It's not just about calculating 2^256. Not all points on the curve are valid.
Best quote I heard was 'Random number generation is too important to be left to chance'
😄 Well spotted.
Dr Pound is still the best one to explain stuff on computerphile. I love those Cryptography videos!
True dat
Well ... from all the items you listed as "suspicious" my suspicion actually dissapeared.
I have no doubts now that it is indeed a backdoor by whoever is paying to implement it (I guess NSA).
P and Q were specified by the NSA and its the NSA that was throwing its weight around to get this standard implemented in commercial cryptographic libraries, you don't even need to guess here.
NSA is really sneaky. Sometimes, it ain’t (ECC or PRISM) too sneaky, but things like the hdd malware were really evil
It appears that it was exploitable. Google portsmash, an attack described in the last few days which deals with eliptic curves.
@@johanlarsson9805 Ohhh, now that video makes a whole lot more sense. Computerphile did not specify how an attacker would be able to reverse a key from just sniffing the operations running in a CPU, but if the objective is to figure out how many times a point was moved in an elliptic curve, this would be a way to do it
Oh, that naughty NSA, always getting its pointer up our backdoors
They're a spy agency. *It's their job* to do stuff like this.
i think you missed a joke there
@@RonJohn63 actually its HALF their job. Their other job is to ensure the communication security of the United States... a bit of a conflict isn't it?
@@chad1755 I'm pretty sure "ensure the communication security of the United States" was tacked on a *lot* later.
That is graphic
I'd seen papers and articles on this before, this is the first time I've understood what the issue is. Great work!
The NSA really need's to mind their P's and Q's
all the ecdsa/P-xxx algorithms are inherently flawed, lookup secure-secure-shell which is a guide on how to choose secure algorithms for SSH. The much more secure/robust algorithm called curve/ed25519 is what is recommended.
@@recodebrain792 you know thisisn't reddit right
@@v1Broadcaster HAHA
Or, more accurately, they SHOULDN'T.
The best teacher in cryptography. Can we have more Dr. Pound videos please? 😁🙂
Excellent video Dr. Pound. You have a great way of explaining things at just the right level of detail. Making notes on 132 column tractor feed paper is just an aded bonus! Keep up the great work.
NIST: we did not find any evidence of 'e' in our design process
Mike: did you look?
NIST: um well no not really
Appendix C?
big black car is coming for you in 3...2...1
Black car more like predator drone
more like big black van
BBC is coming for you in 3…2…1
I love how he says it’s “very interesting” yet we all know he means “very, very concerning”.
"Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. "
John Von Neumann
true randomness can only be acheived via nuclear decay or even just listening to the most common truly random thing most of us have heard; radio/tv static.
@@storm37000 True randomness can only be achieved via Quantum Mechanics (specifically, Heisenberg's Principle of Uncertainity)
@@themanofiron785 some might argue that even quantum mechanics isn't truly random (but for whatever it's needed for it's probably random enough)
@@hayden.A0 In that case you should probably define random.
@@themanofiron785 I'm no expert on this matter so I really shouldn't be defining anything, but, based on what I understand it's like this: any closed system cannot be truly random, and since the universe is a closed system it itself cannot be truly random. Obviously even if that's accurate the amount of "variables" that exist in the universe make it pretty much infeasible to replicate any given state, but again I'm no expert so I may just have some facts mixed up or I'm just completely wrong.
When I was in collage our security teacher could not explain most of the things well. I find these videos very educational and interesting. Thanks for explaining these 😆😆😆
Excellent explanation. Should be watched by everyone who is using any kind of computer.
Hey, please do a video on lattices or post-quantum cryptography!
I subscribed this channel just because this man's accent
I find it astonishing that a standard can go through and still be used with so many "that's suspicious". Just one suspicious thing should be enough to just ignore it and use something else..
As far as I can tell, that's usually how it goes. But security isn't always the top priority, sometimes speed is. So it's a balancing act...
Except in this case, where 1000 times slower and there possibly (definitely) being a backdoor was ok :')
I don't think the community at large uses stuff like this tho, although I guess companies might?
Elliptic curves have one big advantage. You can get along with verry little memory and at least i don't know a common side channel attack. Which makes them great for embedded stuff like machines.
The potential back door on the other hand is nothing great as machines usually run for a view decades.
I mean the NSA were very probably paying them to put it through, right?
@@Ping727 No probably, they did.
"If there's someone who knows this e, and it's not me..."
That's exactly what you'd say if it WERE you, isn't it? Seems pretty suspicious to me. You don't see many people denying they know that number, do you?
@@andymerrett 😆😆😆😆
Shoutout to my main man, the FBI guy!
Good job coming up with this. I couldn't have!
All these interesting caviats and niche applications is what makes ECC so amazing
Always love the Dr Mike Pound videos 😄👌
I saw on Engadget yesterday that MIT made a chip that solves the 1000x slower problem. Thanks for the great explanation video!
Definitely one of the most interesting Computerphile videos I've seen. And Dr Pound is superb at explaining this stuff.
I think there is a very important detail missing in the video: we know *absolutely for sure* that e exists (since the group of points has prime order and so it is cyclic and every element except the identity is a generator). What we do not know is if the NIST knows it (in the sense that we do not know if they picked P and Q randomly or rather they chose P and a number e and then took eP as the second point Q).
Get in the van.
Many operating systems use the date/timestamp of the startup time as the random seed, which ensures a unique seed always, unless your battery is knackered. Sun workstations would sample the noisy analog audio input.
Gotta love mike
This is the best video I've watched in a long long time. Bravo.
NIST: Please use this type of padlock. We thoroughly tested it, it's very secure.
NSA: Yeah, and if you use this and only this type of padlock, then have some money from us.
IT security researcher: Someone might know how to crack this type of lock.
NIST: Haha! I swear, we tested it and there is no flaws. It's the best padlock. Honestly, mate. Just use this exact type of lock.
Researcher: Could I adjust it to use my own type of key cylinder?
NIST: Definitely not! That wouldn't be safe any more!
I don't get it. Why would the NIST tell developers to use a specific P and Q and not generate their own? Do they really think that won't raise instant red flags?
It'd be like if the guy installing your home security system told you your PIN had to be 1234, no exceptions.
Wouldn't it raise just as many red flags if they were willing to let developers pick their own P and Q and certify whatever they chose? They'd be giving the green flag for developers to put their own back doors in.
The real problem isn't that there could be a backdoor built into these P and Q values. The real problem is that ANY p and q values are suspect regardless of who picked them. And before anyone says "just use another rng to generate them", that doesn't work either, because that assumes that you can believe the person who says that they generated them from another rng.
Sure maybe YOU would choose honest values with no back door, then again maybe the NIST did as well. You want to choose your own so that you know they didn't put a back door in. Maybe they want you to use theirs so that they know that you didn't put a back door in. Who can be trusted?
Honestly, the fact that this type of back door CAN exist, effectively makes the entire process fundamentally flawed.
phiefer3 aha thanks for the clear explanation.
+phiefer3 If the whole idea is that Q must not be divisible by P, why not derive them from twin primes? The main issue here is that NIST didn't explain HOW they got these numbers.
You should go back and watch the original video on elliptic curves. When they say "multiple", they're not talking about simply multiplying or dividing a number by another number, they're talking about jumping being able to move some number of times from one point and end up at another point. (ie if you start at Q and then move e times you end up at P).
And the video makes a little bit of a mistake when he says "if" they're a multiple, because the way elliptic curves work, there's almost definitely some number of jumps that can be made from any point on the curve that will land you on any other given point on the curve. In other words, there WILL be some e such that P=eQ. Now calculating the e of a given pair of points is prohibitively difficult, and would be pretty secure, but choosing points for a given e would be extremely simple. (as mentioned in this and the other video, elliptic curves are similar to hash functions in this way, it's simple to start at some point Q, pick a very large e and then calculate a P to create your back door, but doing it backwards to find the e of a pair of points is much much more difficult).
> Why would the NIST tell developers to use a specific P and Q and not generate their own?
Because the NSA told them to. Simple as that.
I learn so much from your channel. thanks for just being here :D
Great video, great channel! I don't understand half of the things described(wish I had a bigger interest in mathematics as a kid) but somehow I can follow the principles mentioned. Thanks, and keep posting!
lol, that sounds as dodgy as, er.. Doctor Dodgy, the head of Dodgy Research at Dodgy University*
* thanks Blackadder :-)
"I have a cunning plan!" prof. Baldrick at Dodgy University
Dr. Quack, Medical doctor
That's about as dodgy as research from Ball State. Bollocks!
Blackadder strikes again made brats @ twitter are furious and immediately proves him to be correct.
Well done. You explained it very well sir!
Finally Im able to understand computerphile's videos :)
I have been watching Dr Pounds videos for quite a while now on this channel and I must say I love the way in which he explains things. Please convince this man to also explain other things like political stuff or so! I know he might not be an expert in those fields, but I feel like computer scientists might have a super logical take on things. (And I just love his voice.
"Computers don't operate in a random way."
Ever used Windows?
🤣
LoL
Predictably random.
Or any sort of GUI or x-server on Linux
Mike should be doing all the videos, he's fantastic.
we did this 'back door' mathematics in seismic processing - called deconvolution...
1> we know the original source signal (dynamite or vibrator)
2> we run the source through the earth
3> record the signals...
4> deconvolute the original source
and you get a 2d slice of the earth's structure...
10:01 is the money shot, had to pause it a minute to take in the explanation.
What are common usecases of this standard today?
SSL certificates. So whenever you visit an online shop or "secure" website, you'll see the certificate, usually next to the address. If it says ECS or something similar, the NSA know what you're doing.
BIG Dave Every company based in the USA needs to give any detail that they detain if queried. Google, Facebook, Amazon, Apple, etc. Not only do they exploit your data, they give it to PRISM, a gigantic mass surveillance organization that is managed by the USA, and it is a known fact they collect data that passes by the Internet, so yeah, ECS is like their golden boy. They collect encrypted data, but they can’t use it. Now imagine they use ECS, the NSA would have access to all data.
Better off using Axolotl
With "this standard" you mean the RNG function talked about in this video?
Pretty much none. As it was either not used in the first place anyway or has been withdrawn for some years now.
Especially what "BIG Dave" says is completely wrong, SSL does not use Dual_EC_DRBG.
whuzzzup As mentioned in the video, it actually was used in the real world by companies paid by the NSA. For example, it was used by default in stuff produced by RSA, inc., which notably included many security fobs.
Nice comments there
I just love this channel. Thanks so much for all your effort.
since computers take counters, regular clockspeeds and therefor timedependent states into account it is actually difficult to guarantee absolute randomness for parameters. Of course if a random generator seems to be deterministic in any way (dependent calculation times for specific bit lenghts is enough - timing attacks) it is to be discarded.
You can always connect to a quantum random number generator ;) Only... is your connection secure? Hmm.. chicken, meet egg.
It's the legend!
Basically, "If you don't use this, that may have a backdoor, and instead use your own to make it more secure, we'll say you're less secure..." Well that makes sense...
This video is simply spectacular!
When I worked at NFR Security, we had a co-worker Jason Wright (immortalized in the Wikipedia page on IPSEC). He was an OpenBSD-associated dev that wrote our ethernet drivers. He was publicly accused of inserting code into OpenBSD to weaken its random number generator on behalf of the FBI. We came in that morning, and he had to make a public statement about how it was a nonsense accusation. All his commits to OpenBSD were given strong scrutiny. I think there were minor bugs found in the commit, but no clear evidence that he managed to break random number generation in OpenBSD.
Oh yeh , the 2nd mos interesting person on computerphile , afte the one and only ledgend, Professor Brailsford, well 3rd if we are counting Brian Kernighan
So if Dual EC has a back door, even theoretical, then it must, by definition, already be broken. Therefore the NIST accreditation for being extra secure is worthless. Ironically, using your own P&Q becomes more secure, since e is less likely to be known. But then, e will always be known since e=P/Q. Whether e was explicitly choosen or implied.
If P&Q are choosen randomly, what random process would we use to choose them? Now we're just going around in circles until we disappear up our own .....
Where is this used and can we avoid it? Can I check if a given website uses it for TLS?
So is there a Great Mersenne Prime type project to seach for e ??
There never will be. Even with all the computation power in the world, 2^256 possibilities is way to many to brute force.
There are groups going through the effort of brute forcing the 2^96 possibilities of private keys to crack open bitcoin addresses. Maybe, if we make a great leap in computational power, some day we could start a cloud computing project to find e. Maybe...
@@tigerresearch2665 Two words: "Quantum Computing".
Robert Thompson
Chinese Government wants to :
*_bake that quantum cake_*
This guy should just take over the channel at this point
It makes sense if Alice creates Q and 'e` and finally P as eQ. She transfer these values to Bob. He creates the seed ''s' and can create random Bits. Alice can verify these random Bits without knowing the seed 's'. There are some possible application of this. Alice can't predict the random bits before the first value (rQ). It's maybe useful.
...I'd be willing to bet at least half of the money in my bank account that that standard has at least one backdoor...
if your bank account is secured by this algorithm, then you're betting all of it
i love the way they advertised the energizer battery !
El is the ruler of this MATRIX of the computer cube of Saturn
Great video. Sounds like the real life version of Dan Brown's book "Digital Fortress". A great read. Happy holidays guys and gals
your vids are worth gold!
Dr Pound's hand gestures in this video are so... man this sounds weird... but they're so nice to watch hahaha
2007 - yes it's some time ago. 15 years and no one could find the value of 'e', though the elliptic curve EC and the two points P and Q are published.
It seems ECC is really secure. Of cause there is no proof, but it looks unlikely that this curves can be cracked somehow.
Any standard which is essential and has been put under a doubt san never again be considered safe. As far as I'm concerned, this back door can not be excluded to exist through a combination of suspicion and circumstances thus this particular generator can not be trusted.
could I be friends with dr. Mike Pound?
Twist. "e" is just Euler's number
Hmmm. The NSA has tried several times since the 1990s to establish a master key back door in the crypto algorithms they promote. So, this is just another attempt.
I guess this is also the reason why many countries are trying to establish their own proprietary algorithms in the financial and data comms areas. They often forbid the use of the classic US algorithms.
But then all these cryptoligists in the NSA have to have been working on something.
I remember the publication of the book on differential crypto Analysis in the early 1990s.
This made short work of many symmetric Algorithms. However it did not for DES. In fact differential Crypto Analysis in DES was by orders of magnitude harder than brute force.
Little Reminder DES was developed published in the late 1940s. Differential crypto Analysis was only discovered by Academia in the late 1980s.
This man is my hero
Has anyone published a correlation study? If e exists it should show up in a large set of P’s and their associated Q’s, at least as a R-squared not equal to zero.
Absolutely fascinating, great video!
Being slow can be an advantage. It makes brute force attacks harder.
Or maybe, it has no backdoor, the other options have backdoors. And the NSA know if they place a heavy, obvious interest on the one that COULD be weak, even after public articles saying so, and paying people to try and use it, that people will instead flock to the other options, which then ACTUALLY have backdoors the NSA already have access to.
The police do this sometimes. They have public statements saying that they're on a mass search for someone who they actually aren't searching for, they're actually just watching town exits. But because the person thinks they're being looked for, they get worried and try to leave, only to walk right into the police who knew they'd try to leave. Just look how many people get caught at the airport. As soon as the police say they're searching the last known area, they're actually searching the airport and just saying that as bait to get them there.
A very important point you forgot, NIST Removed that Algorithm from the list of Random Number Generator back in 21-Apr-2014, so it is not used anymore.
Beautiful.
I read somewhere that Bitcoin uses different P & Q in its elliptic curve calculations, which would be interesting!
In how many year will we have the computing power to solve for e and deternine if it was a back door? Will it ever be in reach?
You dont have that many atoms in universe squared.
With the normal computers we have right now? So many, that "never" is the best answer.
whuzzzup No I didn't say with the computer we have right now.
This seems like an easy problem to solve? Why not do the whole process twice, once with their (NSA/NIST) P and Q, once with your own P and Q. That way, you would have to know both your e as well as their e, which neither you nor they know?
It probably is easy to solve in that way, but then of course when the NSA goes to pull some conversations from someone's "encrypted" chat logs and it doesn't work, a Cisco CEO wouldn't get that new yacht they've had their eye on all summer.
Almost at 1 million!!
NIST withdrew Dual_EC_DRBG from its standards in 2014? So what is the problem now?
Simply fascinating.
So, is this particular standard used now? If so, how widely? How long do we expect it to be in place? What is the consensus on its upcoming alternative?
Anyone who thinks the NSA would push or even publish a cryptography approach that they didn't have their own back door for is ignorant or naive.
Dial 25519 for assistance.
woop woop! independent cryptography science community to the rescue!
dude you have some serious impingement in your left shoulder. Great vid by the way
It is possible to state, with high confidence, the address of a building in England, in which, with very high confidence, there is a person who knows “e”, at least to the extent that their computer contains that number, probably in an encrypted form.
If NSA has generated the Point P as eQ from the Point Q and they might have stored the number 'e'. It is possible. But on the other hand, why to use elliptic curves in case the number 'e' is really unknown? I makes no sense, because hash functions are much faster.
So, it looks very likely that the NSA did really install a backdoor.
"We all thought SHA1 was unbreakable, and then what happened"
Best nerd quote of the year.
Dr. Pound, could you please do a video on security tokens? I trust your videos to get the details right. Most of the videos on security tokens discuss selling features or legal basis. I’m interested in understanding the mechanics and limitations of the model. Sort of like what you did with these excellent videos on elliptic encryption.
Why not use a seeding from say some source of white noise or even the cosmic microwave backgound which I assume will have a suitably high degree of randomness attached.
Hardware implementation and ensuring the noise pool cannot be tainted. There are dedicated randomness modules you can use, but typically hard drive seek times, user mouse input and all sorts of unpredictable events are used to generate noise.
It might just be that the specific values need to be used for FIPS compliance because they are good values and they don’t want someone to implement their own back door values. It might be a case where the attack was known to the NSA and that influenced policy but no shenanigans are going on.
What does the NIST have to say about all this?
Is it theoretically possible to solve the elliptic curve discrete log problem?
Its not proven _impossible_ on a classical computer. The general consensus is that it is impossible (short of brute force, which of course can solve any key finding problem given enough time.. but when multiple ages of the universe is not enough time, that's not really an issue worth considering.)
On a quantum computer however, its not only theoretically possible but we know how to do it (Shor's algorithm.) I'm not sure that we have discovered any functions that are suitable for classic cryptography that (provably) can't be broken by a quantum computer. I don't think we have.. though I'm also pretty sure we haven't yet proven that such a function can't exist and is just waiting for us to find it. Discovering a cryptographically strong (and fast enough to be practical) classical function that can also be provably unbreakable by a quantum computer would lead to a significant overhaul of the computer security industry, and would remove the need for quantum cryptography (which is a very hard problem.. not because of the math, but because _everyone_ would need a quantum computer to do their cryptography and that's just not going to be practical in the foreseeable future.)
that's the standard discrete log problem (using integer factorization), not the elliptic curve discrete log problem, which as far as i know doesnt have a theoretical quantum algorithm associated with it.
All people really should know about this and understand the implications it has, I find it extremely worrying that we live in a world that is too complicated for >90% of the population to understand.
very good channel
As an end user what can I do to make sure none of my devices and programs are using dual ec drbg?
Choose RSA-4096 + AES-256 when given the choice. If not given a choice, consider the platform insecure.
Whats about the Bernstein Curves? Do you think these have also a "back-dor"? ( f.i. curve25519 and ed25519 )
Since Epileptic Curves cause Crashes, I'd say they can make great Back Doors.
/me wondered about if other curves such as Curve25519 might have been similarly affected,
thankfully not AND the bad one's not in use anymore, afaik...
So is there a way to ensure that our systems don't use elliptic curve cryptography? Or would that require that everyone we exchange information with also not use it?
Technically you could probably edit an open source browser like chromium to not use it. However there really isnt any need, this standard has now been abandoned and elliptic curve cryptography is fine to use
@@JadeNeoma thanks for the info lol i forget i ever asked this