How NSA backdoored Dual_EC_DRBG without weakening it

General discussion for topics related to the FreeBASIC project or its community.
Post Reply
Wayne Diamond
Posts: 4
Joined: Sep 24, 2013 7:07

How NSA backdoored Dual_EC_DRBG without weakening it

Post by Wayne Diamond »

The Edward Snowden leaks revealed that the NSA had made significant strides against the TLS layer, which protects many of the Internet's "secure" communications including HTTPS. It is now almost certain that at least a part of that breakthrough stride comes as a result of the NSA inserting a backdoor into the PRNG Dual_EC_DBRG

If you're unfamiliar with this, here's a news article from The Guardian

I love cryptography, I find it fascinating, but Im not a professional mathematician or cryptographer, so when it emerged that the NSA had BACKDOORED the algorithm WITHOUT WEAKENING it I was interested why...

Today a very good post emerged, which explains the backdoor in a fairly easy way to understand, how it's implemented, why it's not able to properly be detected, and all without getting heavy on the maths:
http://www.lapsedordinary.net/2013/09/2 ... ptography/

It's very similar to the RSA problem of calculating primes, but using elliptic curves for this PRNG...
Summary snippet:
If the elliptic curve is large (which the one used in this NIST standard is), it will take you a long time to compute e. Think in terms of millions of years. So no one knows e and no one can know e.

No one? Well, if you simply choose a point P on the curve and choose a (very large) number e, you can use that to compute a point Q. If you then give out these P and Q to someone, they will still need a million years to compute e. But you know it.

And that’s exactly what the NSA did. They provided the P and the Q in the standard. They, as has become clear from Snowden’s documents, know e. We don’t. And we can’t even compute it.

Keep in mind though, not everyone is convinced the algorithm has been backdoored!...
http://www.wired.com/threatlevel/2013/0 ... kdoor/all/

</x-files.mp3>
agamemnus
Posts: 1842
Joined: Jun 02, 2005 4:48

Re: How NSA backdoored Dual_EC_DRBG without weakening it

Post by agamemnus »

It's a fallacy. Of course it's not secure. If someone hacks the NSA and steals this "e", then what?
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: How NSA backdoored Dual_EC_DRBG without weakening it

Post by MichaelW »

They provided the P and the Q in the standard.
If this is the way it works, and I’m not sure that it is, then even if the NSA did not provide the P and Q, someone did, so how is this a new problem?
Lachie Dazdarian
Posts: 2338
Joined: May 31, 2005 9:59
Location: Croatia
Contact:

Re: How NSA backdoored Dual_EC_DRBG without weakening it

Post by Lachie Dazdarian »

Great article on lapse ordinary.
marcov
Posts: 3455
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: How NSA backdoored Dual_EC_DRBG without weakening it

Post by marcov »

MichaelW wrote:
They provided the P and the Q in the standard.
If this is the way it works, and I’m not sure that it is, then even if the NSA did not provide the P and Q, someone did, so how is this a new problem?
The assumption was that the P and Q were chosen for their strength. The (afaik only alleged?) association of the choice with NSA could mean that it was not chosen for its strength, making it problematic.
Richard
Posts: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: How NSA backdoored Dual_EC_DRBG without weakening it

Post by Richard »

While game theory involving the possibilities of “who might know what” is fascinating, any conclusion reached through that fascination can only be ephemeral. It will ultimately be shown to be unreliable and a futile waste of a valuable resource called time. You may as well search for the end of a rainbow.

The ongoing stability of a “power balance” requires we employ spies and be able to read others ciphers. That has been true for millennia, and must always be true since, by definition, unstable regimes will always fall in the end. If we could not read other's mail, then we would have to offensively, “shut them down”, in order to maintain our own defensive security. The alternative to stability is anarchy.

Cryptographic security requires significant misinformation to dilute and smother the truth. Winston Churchill wrote “In wartime, truth is so precious that she should always be attended by a bodyguard of lies”. It is never possible to certainly tell the difference between a fact and a good fiction. Mark Twain wrote “It's no wonder that truth is stranger than fiction. Fiction has to make sense.”

If it takes too long to break a good scrambler or cipher system, a story will be spread to the users that it has a secret weakness or a trap door. The users will then migrate to another system, hopefully a deliberately convenient one, the one with your well prepared trap door.

The less solid information there is available, the more interpretive freedom is possible. There is no information about UFOs because they are, by classification, unidentified. Almost anything is therefore a possibility. Likewise, searching for listening bugs or hidden cameras is a waste of time. If you search and find one, there will probably be others you do not find. It is a better strategy to assume they are always present and to not bother searching for them. Use them as a conduit for misinformation to destabilise your opposition.

Demonstrating your intelligence, awareness and using a secure cipher system, makes you a target. To live a comfortable life requires that you avoid encryption and appear to be a little bit silly.

1. Simple people and innocent people can accept that all encryption is totally secure.

2. Clever people and guilty people should accept that all encryption is weak and everything is recorded.

Innocent or guilty, you should act appropriately.
srvaldez
Posts: 3374
Joined: Sep 25, 2005 21:54

Re: How NSA backdoored Dual_EC_DRBG without weakening it

Post by srvaldez »

very well said Richard.
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: How NSA backdoored Dual_EC_DRBG without weakening it

Post by MichaelW »

Richard wrote: Demonstrating your intelligence, awareness and using a secure cipher system, makes you a target.
Demonstrating a lack of intelligence and awareness and failing to secure personal/financial information makes even innocent people a target, for criminals.
Richard
Posts: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: How NSA backdoored Dual_EC_DRBG without weakening it

Post by Richard »

Good security requires there be a difference between appearance and reality.

We live in a dangerous world - fuel that paranoia.
dodicat
Posts: 7979
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: How NSA backdoored Dual_EC_DRBG without weakening it

Post by dodicat »

Fool's Paradise is the best place to appear in, I'll tell you, it's no lie.
Post Reply