Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Dual_EC_DRBG Backdoor: a Proof of Concept

Soulskill posted about 7 months ago | from the this-is-how-we-do-it dept.

Encryption 201

New submitter Reliable Windmill sends this followup to the report that RSA took money from the NSA to use backdoored tech for random number generation in encryption software. From the article: "Dual_EC_DRBG is an pseudo-random number generator promoted by NIST in NIST SP 800-90A and created by NSA. This algorithm is problematic because it has been made mandatory by the FIPS norm (and should be implemented in every FIPS approved software) and some vendors even promoted this algorithm as first source of randomness in their applications. If you still believe Dual_EC_DRBG was not backdoored on purpose, please keep reading. ... It is quite obvious in light of the recent revelations from Snowden that this weakness was introduced by purpose by the NSA. It is very elegant and leaks its complete internal state in only 32 bytes of output, which is very impressive knowing it takes 32 bytes of input as a seed. It is obviously complete madness to use the reference implementation from NIST"

cancel ×

201 comments

Bah (2, Interesting)

colinrichardday (768814) | about 7 months ago | (#45838767)

Who can you trust?

Amish (5, Funny)

Anonymous Coward | about 7 months ago | (#45838915)

shun anything electronic, or electric for that matter. Substinance farm and read dead-tree books for leasure.

Re: Amish (2)

hoifelot (798854) | about 7 months ago | (#45838945)

Trees are the new black!

Re: Amish (2, Funny)

Anonymous Coward | about 7 months ago | (#45840355)

Trees are the new Red-black [wikipedia.org] !

FTFY!

Re:Amish (2)

Em Adespoton (792954) | about 7 months ago | (#45839475)

shun anything electronic, or electric for that matter. Substinance farm and read dead-tree books for leasure.

Only read illuminated books though, not printed books. Otherwise, you're no better than the Luddites (who, while known for destroying printing presses and automated looms, weren't actually against the technology, just against it only being in the hands of the rich and powerful, to the detriment of the working class).

Re:Amish (5, Interesting)

cold fjord (826450) | about 7 months ago | (#45839751)

shun anything electronic, or electric for that matter. Substinance farm and read dead-tree books for leasure.

Spooked by NSA, Russia reverts to paper documents [usatoday.com]
Kremlin returns to typewriters to avoid computer leaks [telegraph.co.uk]

Only one of the many "benefits" from the leaks, not to mention:

Snowden revelations lead Russia to push for more spying on its own people [pri.org]

Re:Bah (0)

Anonymous Coward | about 7 months ago | (#45839087)

Trust is a weakness. In an ideal world, you can trust everyone. The harsh reality is that we don't live in an ideal world, and thus the ideal becomes different.

The richest countries in the world is rich BECAUSE of trustworthiness. So you gotta ask yourself: WHO profits from a country shooting its own feet?

Captcha: cashed

Re:Bah (2)

MobSwatter (2884921) | about 7 months ago | (#45839297)

Trust is a weakness for the world of spooks, not everyone lives in their world, but everyone seems to be a target for their affections at any cost...

Re:Bah (1)

Mister Liberty (769145) | about 7 months ago | (#45839145)

Whom?

Re:Bah (3, Funny)

Anonymous Coward | about 7 months ago | (#45839683)

Ghostbusters!

Re:Bah (0)

Anonymous Coward | about 7 months ago | (#45839967)

In the case of elliptic curve cryptography, trust those that specify exactly how they came up with the particular constants used. The NIST standard fails to do this.

Another view on teh RSA / NSA thing... (5, Informative)

QuietLagoon (813062) | about 7 months ago | (#45838799)

RSA doesn’t quite deny undermining customers’ crypto [freedom-to-tinker.com]

Reuters reported on Saturday that the NSA had secretly paid RSA Data Security $10 million to make a certain flawed algorithm the default in RSA’s BSAFE crypto toolkit, which many companies relied on. RSA issued a vehement but artfully worded quasi-denial. Let’s look at the story, and RSA’s denial....

Re:Another view on teh RSA / NSA thing... (0)

cold fjord (826450) | about 7 months ago | (#45839867)

Doesn't really look like a "qasi-denial."

RSA Response to Media Claims Regarding NSA Relationship [rsa.com]

Recent press coverage has asserted that RSA entered into a “secret contract” with the NSA to incorporate a known flawed random number generator into its BSAFE encryption libraries. We categorically deny this allegation.

We have worked with the NSA, both as a vendor and an active member of the security community. We have never kept this relationship a secret and in fact have openly publicized it. Our explicit goal has always been to strengthen commercial and government security. .....

RSA, as a security company, never divulges details of customer engagements, but we also categorically state that we have never entered into any contract or engaged in any project with the intention of weakening RSA’s products, or introducing potential ‘backdoors’ into our products for anyone’s use.

Re:Another view on teh RSA / NSA thing... (4, Insightful)

thue (121682) | about 7 months ago | (#45839983)

You need to read it like a lawyer. Take the first claim for example

> Recent press coverage has asserted that RSA entered into a “secret contract” with the NSA to incorporate a known flawed random number generator into its BSAFE encryption libraries. We categorically deny this allegation.

Note what is not denied:

* It is not denied that the contract existed
* It is not denied that they set Dual_EC_DRBG as default as a result of the contract
* It is not denied that the contract was secret (they do later deny that their relationship with NSA in general was not secret, which is correct, but does not preclude one contract from being secret)

They only thing they deny is that they knew that Dual_EC_DRBG contained a backdoor when they made the secret contract to set it as the default.

The same with their other non-denials.

Re:Another view on teh RSA / NSA thing... (1, Interesting)

cold fjord (826450) | about 7 months ago | (#45840111)

It short, your reading as a lawyer doesn't produce anything helpful in furthering the claim that they deliberately weakened RSA.

The didn't make a "non-denial." It appears to be quite explicit. I suggest following the link and reading the original.

Re:Another view on teh RSA / NSA thing... (3, Insightful)

gargleblast (683147) | about 7 months ago | (#45840819)

They didn't make a "non-denial." It appears to be quite explicit.

The only thing explicit is that RSA denied a bunch of highly specific scenarios. Let me highlight one word:

Recent press coverage has asserted that RSA entered into a “secret contract” with the NSA to incorporate a known flawed random number generator into its BSAFE encryption libraries.. We categorically deny this allegation.

Now change that one word to from "known" to "unknown". Did they deny that?

Plausible deniability. [wikipedia.org] The only truth with a hole in it!

Re:Another view on teh RSA / NSA thing... (0, Flamebait)

cold fjord (826450) | about 7 months ago | (#45840927)

Now change that one word to from "known" to "unknown". Did they deny that?

I can play that game too. Change that one word from "known" to "fried chicken recipe." Did they deny that?

Re:Another view on teh RSA / NSA thing... (0)

Anonymous Coward | about 7 months ago | (#45840931)

It short, your reading as a lawyer doesn't produce anything helpful in furthering the claim that they deliberately weakened RSA.

At this point the burden of proof is on RSA, even without considering their past misdeeds. If they can't make a blanket denial, then we should believe that the scenario is "The NSA paid us to do something, to not ask why, and not tell anybody about it."

YES! (0)

Anonymous Coward | about 7 months ago | (#45838815)

Excellent, proof now what happens?

Re:YES! (2, Informative)

Anonymous Coward | about 7 months ago | (#45838859)

Someone creates an angry blog post and someone else submits a petition to change.org. Then nothing.

Re:YES! (1)

Anonymous Coward | about 7 months ago | (#45838893)

And some people generate new key pairs

Re:YES! (0)

Anonymous Coward | about 7 months ago | (#45838905)

The damage was already done. Whenever anything is mentioned about terrorism or child porn, I know it's just a coverup. I'm actually rooting for the terrorists now, whoever they are.

Re:YES! (1)

GameboyRMH (1153867) | about 7 months ago | (#45839177)

They are us. Some really bad people are slightly inconvenienced as a side-effect, but are by no means stopped (See: Tsarnaev brothers, zero evidence of attacks stopped by the NSA).

Re:YES! (0)

Anonymous Coward | about 7 months ago | (#45838997)

I honestly don't see anything we can do but boycott RSA, but then what will change?.

We could demand they fix the flawed code but can you trust that it won't just be replaced with an even more clever piece of coding, the flaw is genius.

We could demand real privacy, but its a dream we lost that right once we became meshed in social media and the need to share.

We could demand limits on spying/collecting data, but what about the terrorists that want to hurt the US, so they need to hurt the rest of the world instead of working with them.

Safe encryption is hard to find their are new projects and pipeline projects that exist, and company's working on tier own in-house encryption.

Re:YES! (2)

MobSwatter (2884921) | about 7 months ago | (#45839221)

Philip Zimmerman, PGP. Older versions 6.5.8 might be okay, something open source. However there is all this worthless security infrastructure in place already that has been rooted. There needs to be compensation for fraud.

Re:YES! (4, Insightful)

Will.Woodhull (1038600) | about 7 months ago | (#45839283)

For a start, we could at this point reasonably demand that everyone who has accepted a salary from NSA be branded on the forehead with a scarlet letter, so that anyone with any sense would know not to hire them for any position involving trust. Let them work as street sweepers. As persons who sort garbage into different recycling streams. We know these persons cannot be trusted. Identify them, remove them from their current jobs, and place their names on a very public list of persons who cannot be entrusted with anything, in any endeavor.

There needs to be some amount of personal responsibility in the NSA, yet with the obvious exception of Snowden, there is no evidence of any such thing. One good place to start is to hold those who were involved in creating this monster accountable for ethical / moral turpitude.

Re:YES! (1)

Behrooz Amoozad (2831361) | about 7 months ago | (#45839573)

mod this isnightful.

Re:YES! (1)

Anonymous Coward | about 7 months ago | (#45840689)

We could also brand the asses of the sanctimonious jackasses around here who feel the need to impose their versions of integrity and morality on the rest of us. You and your ilk are assholes and, like all those who claim to own the high moral ground, are not as relevant as you think you are. But, you are smarter than most; all we need to do is just ask you.

We need another 15 stories of stale news about "teh NSA is bad; Snowden is a saint" so that you and the hive can express your indignation and outrage and thus make yourself feel superior to those you like to call "the sheeple."

Re:YES! (0)

cold fjord (826450) | about 7 months ago | (#45840877)

I had hoped that Slashdot had mainly passed beyond the "nutter" phase after the "truthers" have mainly cleared out. Apparently that was over optimistic.

Re:YES! (1)

dgatwood (11270) | about 7 months ago | (#45839295)

We could demand real privacy, but its a dream we lost that right once we became meshed in social media and the need to share.

That's a fallacy. I choose what I share on social media. Granted, I can't control what other people share about me, but that was just as true before social media; we just used to call it gossiping. That's why you have to be careful who you trust with things that you consider secret—keep your secrets secret and all that.

Re:YES! (0)

Anonymous Coward | about 7 months ago | (#45839447)

That's a fallacy. I choose what I share on social media.

No you don't. Social media sites like Google+ and Facebook vacuum up information about you from everywhere, even things you never intended to be made public like links you've clicked on.

Re:YES! (5, Informative)

Em Adespoton (792954) | about 7 months ago | (#45839677)

That's a fallacy. I choose what I share on social media.

No you don't. Social media sites like Google+ and Facebook vacuum up information about you from everywhere, even things you never intended to be made public like links you've clicked on.

Indeed -- you choose what you share on social media (to a degree), but most people aren't aware of the value of what they're sharing in the first place, and they have almost no control over what is shared about them. This is not the same as gossiping, as gossip involves the game of telephone -- there's no documented evidence that it's true. But when a date-stamped geolocated image of you in a nightclub shows up on your friend's blog with facial recognition indicating that it's you in the picture, and you called in sick that day, that's not gossip; that's evidence -- especially since that photo can then be flagged up for people who are following YOU (including co-workers and possibly your boss), even though you had nothing to do with the publication of the photo.

And this is before we get into whether your privacy settings have been changed by the service host since the last time you reviewed them, and whether others who don't need to honor those settings have found anything interesting in "your" files hosted in an international cloud server system.

If you choose to share nothing on social media, then at least none of the links can be verified, and it's closer to gossip. As soon as you start to share anything though, the metadata is enough of a net to snag all the bits of data about you that are published by others.

Re:YES! (1, Insightful)

deviated_prevert (1146403) | about 7 months ago | (#45839935)

No you don't. Social media sites like Google+ and Facebook vacuum up information about you from everywhere, even things you never intended to be made public like links you've clicked on.

Which to the NSA is useless information overload, with RSA keys being easily hacked it leads down a completely different path than the average Joe on the net, I would think that the NSA is much more interested in targets of value. The fact is most people who use Google+ or Faceplant have nothing of any real value to be had especially for security agencies. If you are a consumer and all of a sudden your posting habits make advertising money for Brin and Zukerberg who gives a rats ass. Here we are with a bunch of so called information gurus telling us that are consuming habits are a valuable commodity. Personally I listen to Igor Stravinsky and if in watching and listening to a youtube vid suddenly Google comes back and advertises a concert somewhere of a performance of Le Sacre Du Printemps then good for them.

AND BY THE WAY nice shift off the topic and away from the bastards at the NSA subverting RSA keys and a not so cunning redirect to attack instead Google services as being somehow associated with the information sink hole in Washington that is the NSA.... If however I frequent neo nazi sites and post hate speech on the net then as far as I am concerned being on the radar of the NSA is not that bad a thing...UNLESS OF COURSE I AM A MORON WHITEY TIGHTY BORN AGAIN NAZI MYSELF OR A CLOSET TERRORIST.

However being much more concerned about my bodily fluids and essences, instead I am against the fluoridation of our precious water and bodily fluids. The encryption key is found in PURITY OF ESSENCE from which all things will be revealed. GOOGLE IS EVIL DON'T FORGET IT only through the use of Microsoft Windows and Bing can true encrypted PURITY OF ESSENCE be acheived. RSA keys the NSA have absolutely nothing to do with this thread. WOOOF

Re:YES! (1)

MobSwatter (2884921) | about 7 months ago | (#45839125)

Currency implosion, wouldn't worry so much about your paychecks not cashing, the oil peddling masters balls that you've been licking is contaminating water aquifers and rendering US soil uninhabitable so there won't be much food grown or water to drink to buy with a paycheck that doesn't cash anyway, genius.

Re: YES! (1)

PC_THE_GREAT (893738) | about 7 months ago | (#45838899)

People use something else, until a new scandal crops up.

What if you do believe? (1)

Anonymous Coward | about 7 months ago | (#45838887)

Can you still read the linked article? Or am I not allowed? I can't tell anymore what is allowed under the law and what isn't, since the US Gov feels free to interpret the law as it chooses.

So just like xorshift64 then (2, Interesting)

Anonymous Coward | about 7 months ago | (#45838891)

xorshift64 is a simple random number generator with a period of 2**64 - 1 (you cannot use 0).
The 64 bit random number that it produces is the same as its complete state.

Hmmm (1)

koan (80826) | about 7 months ago | (#45838907)

Meaning what? That encryption was good enough to keep likes of the NSA out even with their resources, and so they compromised it?
Or something even more insidious.

Re:Hmmm (1)

viperidaenz (2515578) | about 7 months ago | (#45839019)

or they just wanted to make it easier/faster to break.

Re: Hmmm (0)

Anonymous Coward | about 7 months ago | (#45839535)

That is what he said.

Re:Hmmm (1)

MobSwatter (2884921) | about 7 months ago | (#45840127)

Yeah, like in milliseconds through injection of a secondary curve. How else could real time acquisition of voice/data be efficient enough to handle growth in traffic through the intertubes.

Re: Hmmm (1)

hoifelot (798854) | about 7 months ago | (#45839033)

Could you give an example of what you think would constitute "more insidious?

Re: Hmmm (5, Insightful)

MobSwatter (2884921) | about 7 months ago | (#45839541)

Business Intelligence, for the purpose of corporate espionage. You also have to take into consideration that the NSA does answer to someone, and that someone was corporate sponsored before they were even put on a ballot to be voted on. They were put up to this, and continuance of the program likely has little to do with terrorism as the program has proven fruitless even after intelligence information was given about events prior to them being given/developing these tools but they in fact failed to respond accordingly to prevent them, this includes 9/11.

Re:Hmmm (1)

mikael (484) | about 7 months ago | (#45839959)

With certain file encryption algorithms, they asked that the salt and/or hashed password were tacked on at the end of the file. That sped up decryption enough that their resources could decrypt the file, but not so much that anyone else could figure out it was compromised.

Re:Hmmm (1)

fatphil (181876) | about 7 months ago | (#45840405)

From the patent linked to from article:
"""
[0047] Escrow keys are known to have advantages in some contexts. They can provide a backup functionality. If a cryptographic key is lost, then data encrypted under that key is also lost. However, encryption keys are generally the output of random number generators. Therefore, if the ECRNG is used to generate the encryption key K, then it may be possible that the escrow key e can be used to recover the encryption key K. Escrow keys can provide other functionality, such as for use in a wiretap. In this case, trusted law enforcement agents may need to decrypt encrypted traffic of criminals, and to do this they may want to be able to use an escrow key to recover an encryption key.
"""

Good article (5, Informative)

Okian Warrior (537106) | about 7 months ago | (#45838947)

The link above [0xbadc0de.be] is a very good introductory article on EC cryptography. If you know a little math but have no background in elliptic curves, this is a good introduction. Well worth reading.

Clearly explained at an introductory level, with Wikipedia links for the assumed terms.

Topical, singular (ie - it's the first one currently, a news "scoop" if you like), technical, and important.

Lots to like here - Slashdot needs more articles like this.

Re:Good article (1)

Wizel603 (1367631) | about 7 months ago | (#45839347)

Too bad I've already given up on Slashdot and left. Really, I'm not here. You don't see me.

Re:Good article (5, Funny)

Em Adespoton (792954) | about 7 months ago | (#45839689)

Too bad I've already given up on Slashdot and left. Really, I'm not here. You don't see me.

Weak are your Jedi powers, my son.

Re:Good article (1)

cbiltcliffe (186293) | about 7 months ago | (#45839775)

Hey.....did you guys hear something? I thought I heard a voice say something, but I couldn't quite hear what it was....

Re:Good article (1)

MobSwatter (2884921) | about 7 months ago | (#45840011)

I think is what the powers that be behind the NSA directives, and it said, "Whose ur daddy, bitch?".

Re:Good article (1)

ISoldat53 (977164) | about 7 months ago | (#45839431)

Edward Frenkel's new book, "Love & Math" also has a good explanation of the math of elliptic curves that non mathematicians can understand.

Re:Good article (3, Informative)

neokushan (932374) | about 7 months ago | (#45839621)

Just to add to this, if you want a good primer on Elliptic Curve Cryptography in general (and not just this exploit), this article from Cloudflare is pretty great even if you don't have a mathematical background. It also explains RSA quite well, so it's a good general crypto primer:

http://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography [cloudflare.com]

is RSA soon an open vault? (1)

hoifelot (798854) | about 7 months ago | (#45839011)

It seems to me that anything we thought were encrypted and could be, and was, considered secure in that embodiment, is soon subject to revelation. I'm no expert, but I'm losing faith in these algorithms. Please tell me it's going to be okay. PS: if you are NSA, I don't need your reassurances.

Re:is RSA soon an open vault? (4, Informative)

gnasher719 (869701) | about 7 months ago | (#45839107)

It seems to me that anything we thought were encrypted and could be, and was, considered secure in that embodiment, is soon subject to revelation. I'm no expert, but I'm losing faith in these algorithms. Please tell me it's going to be okay. PS: if you are NSA, I don't need your reassurances.

Don't worry. It was known for quite a while that this algorithm _might_ have been backdoored. There are basically three possibilities:

1. The NSA didn't know that it could be backdoored when they created it. So there is no backdoor, and the NSA is kicking themselves for that missed opportunity, or for the embarrassment. 2. They knew about it, but intentionally didn't create a backdoor. 3. They knew about it and created a backdoor.

From looking at the algorithm, we cannot possibly know which one is the case. Obviously it would be totally insane to use this algorithm. But that _was_ known for quite some time.

Re: is RSA soon an open vault? (1)

hoifelot (798854) | about 7 months ago | (#45839193)

So what is a viable alternative, assuming one would like to maintain the private/public key feature?

Re: is RSA soon an open vault? (0)

Anonymous Coward | about 7 months ago | (#45839465)

mandate the inclusion of a hardware random number generator in new series computers, with verifiable values for its randomness in sequences produced, and standards to which such devices need to conform.

really, such a thing could be sold in a USB keyfob form factor and be just fine. just use americium decay as the signal generator, similar to whats in a smoke detector. define it as a composite HID class, with a type descriptor and a virtual serial port.

from what I can see here, the flaw is not in the concept of public key, the flaw is in keypair deduction, based on the faulty random source. Replacing the radom sequence generator with one that produces really real random sequences would neatly solve the problem.

Re:is RSA soon an open vault? (4, Insightful)

sjames (1099) | about 7 months ago | (#45839533)

But looking at it from a motivation standpoint, only option 3 would be worth paying $10 million for.

Re:is RSA soon an open vault? (1)

citizenr (871508) | about 7 months ago | (#45839981)

1. The NSA didn't know that it could be backdoored when they created it. So there is no backdoor, and the NSA is kicking themselves for that missed opportunity, or for the embarrassment. 2. They knew about it, but intentionally didn't create a backdoor. 3. They knew about it and created a backdoor.

From looking at the algorithm, we cannot possibly know which one is the case. Obviously it would be totally insane to use this algorithm. But that _was_ known for quite some time.

Except for the 10mil paid to RSA in secret and 2005 patent describing use of this algo for _this exact purpose_.

OpenBSD (1)

McGruber (1417641) | about 7 months ago | (#45839101)

Does this mean that OpenBSD has suffered a 3rd remote hole in its default installation? (http://it.slashdot.org/story/07/03/15/0045207/remote-exploit-discovered-for-openbsd)

(I don't understand the implications of Aris' blog above, so I'm hoping someone can explain it to me & other OpenBSD users.)

Re: OpenBSD (4, Interesting)

Richard_at_work (517087) | about 7 months ago | (#45839179)

No, because OpenBSD doesn't just use this PRNG as the source of randomness for its encryption implementations, it has used other sources mixed in for a long time. There was a recent story about FreeBSD switching to other sources and De Raadt being all cocky about other people finally doing what OpenBSD has done for years.

FIPS (4, Informative)

sunderland56 (621843) | about 7 months ago | (#45839123)

FIPS is a large group of standards - literally, the Federal Information Processing Standards. Any requirement is not "mandated by FIPS", it is mandated by one particular standard - which may or may not apply to any contract.

FIPS 140-2 Annex C, for one, lists quite a few acceptable random number generators; for that standard, I see no requirement for Dual EC DRBG.

Re:FIPS (5, Informative)

Anonymous Coward | about 7 months ago | (#45839211)

FIPS is a large group of standards - literally, the Federal Information Processing Standards. Any requirement is not "mandated by FIPS", it is mandated by one particular standard - which may or may not apply to any contract.

FIPS 140-2 Annex C, for one, lists quite a few acceptable random number generators; for that standard, I see no requirement for Dual EC DRBG.

There's still no requirement for Dual EC DRBG (so the summary is misleading) but Annex C is also somewhat misleading.

FIPS 140-2 is modified by SP 800-131A which describes algorithm transitions (see FIPS 140-2 Implementation Guidance G.14) and therefore any new FIPS 140-2 module submitted after Dec 31, 2013 can only use an RNG from the SP 800-90A standard; not any of the other RNGs listed in Annex C.

However SP 800-90A specifies four different DRBG algorithms, only one of them being the suspect Dual EC DRBG. So even today new modules aren't forced to use it. (And if fact I believe NIST posted a warning on their 140-2 website strongly recommending that people not use the Dual EC DRBG)

Re:FIPS (1)

Anonymous Coward | about 7 months ago | (#45839229)

If I've been understanding the news releases lately RSA Inc. specificaly made this particular PRNG the default in its cipher suites sold to basically everyone. And they claimed that this was done to conform to FIPS compliance. So whether or not it really was required or not, doesn't matter. They convinced (or tricked) lots of people into using it by default.

How long until someone cracks the backdoor key? (4, Interesting)

gman003 (1693318) | about 7 months ago | (#45839131)

Actually read TFA, enough flew over my head that I can't personally verify the math, but if true, well holy fucking shit. Once someone brute-forces the backdoor "key" used by the NSA, it looks like the entire system is cracked. Even if it takes a while to brute-force, once you have that you can open any encryption using that curve.

Given that cracking this open would be so useful to both other monitoring agencies, and to criminal hackers, it's sure to happen eventually, if it hasn't already. I'm sure China could throw one of their supercomputers at it.

I'd be curious to know just how hard it would be to brute-force the backdoor key itself. There didn't seem to be anything in TFA about that, and I can't figure out the math myself.

Re:How long until someone cracks the backdoor key? (4, Informative)

gnasher719 (869701) | about 7 months ago | (#45839267)

Actually read TFA, enough flew over my head that I can't personally verify the math, but if true, well holy fucking shit. Once someone brute-forces the backdoor "key" used by the NSA, it looks like the entire system is cracked. Even if it takes a while to brute-force, once you have that you can open any encryption using that curve.

It's quite possible that this cannot be brute forced. The only way is to create the back door at the time that the random number generator is created. In the end, that is the _first_ requirement: That an arbitrary attacker, given a complete description of the algorithm, cannot brute force it.

Re:How long until someone cracks the backdoor key? (3, Informative)

jader3rd (2222716) | about 7 months ago | (#45839449)

It's quite possible that this cannot be brute forced. The only way is to create the back door at the time that the random number generator is created. In the end, that is the _first_ requirement: That an arbitrary attacker, given a complete description of the algorithm, cannot brute force it.

From what I understand the whole point of algorithms like this is that brute force is the only option (without knowing the key). If there was some other mathematical way of determining the key the hackers would use that; so the goal is to create an algorithm where the secret key has to either be known, or brute forced. The only way to find the secret key is to literally try every possible number and hope that the computer stumbles across the right one eventually.

Re:How long until someone cracks the backdoor key? (1)

thue (121682) | about 7 months ago | (#45839287)

According to Dan Shumow and Niels Ferguson's 2007 presentation [cr.yp.to] , finding the private key e corresponds to solving one instance of the elliptic curve discrete log problem [washington.edu] , which is believed to be a very hard problem indeed, and probably not even doable for a any current supercomputer.

Re:How long until someone cracks the backdoor key? (1)

MindStalker (22827) | about 7 months ago | (#45839723)

If its not doable how then did NSA supposed to have done it? Its not like they came up with the key at random then invented this algorithm to fit it, the fact that there is a backdoor key is a quirk of the mathematics.

Re:How long until someone cracks the backdoor key? (3, Informative)

gman003 (1693318) | about 7 months ago | (#45839951)

From my understanding, the ability to have *a* backdoor is a quirk of the math, but the "key" depends on the parameters of the elliptic curve. Those parameters for this specific implementation were written by the NSA (under the guise of their mandate to secure American communications) and standardized by NIST. TFA had a full proof of concept using parameters he had generated, which worked.

Re:How long until someone cracks the backdoor key? (2)

thue (121682) | about 7 months ago | (#45840375)

If you can choose P and e, then you can easily calculate Q=eP. It it only if you start with P and Q given that you can't find e.

Re:How long until someone cracks the backdoor key? (3, Informative)

Dr. Blue (63477) | about 7 months ago | (#45840421)

If its not doable how then did NSA supposed to have done it? Its not like they came up with the key at random then invented this algorithm to fit it, the fact that there is a backdoor key is a quirk of the mathematics.

It's basically public-key crypto: you can create a keypair and publish the public key - that's essentially what this is, where the point Q in the Dual_CD_DRBG spec is really just a public key. There's a private key as well - it's far to expensive to compute it from the public key (basically 2^128 time), but they didn't have to do that since they generated the private key first.

And it's really not a "quirk of the mathematics" - it's really pretty straightforward if you understand elliptic curves, and it has been well-known how to do this since 2007 or earlier. I think a lot of academic cryptographers didn't really worry about it when Shumow and Ferguson pointed out the potential backdoor, because it's really a pretty crappy technique anyway - academic cryptographers, who quite frankly often don't know what is used in practice, assumed no one would use this. Then it turns out that RSA used it as the default tehnique in BSAFE. Oops.

Re:How long until someone cracks the backdoor key? (5, Informative)

Anonymous Coward | about 7 months ago | (#45839331)

(Hi. I'm the one Dan was replying to, from another thread. Proof on request, but /. mangles PGP signatures, amongst many other things.)

No, it'd take a Rho attack of 2^127.8 complexity to break that key. Not happening. Way more likely is that someone simply steals the key from the NSA - a daunting prospect - but not particularly useful if all you wanted to know is that there is a backdoor, not to actually use it. There is, and people have been pointing that out since 2006.

I was... surprised at Dan's response. I did not actually expect a response to noting that the backdoor in Dual_EC_DRBG was, and I'll quote myself here, "a backdoor that couldn't have been more obvious if you'd erected a flashing neon sign and driven a mounted parade with a marching band through it", because I didn't think anybody was in disagreement about that. Apparently I was wrong.

My own reply to him, pointing out that even if you mind your Ps & Qs (in the way that he patented, mind you), Dual_EC_DRBG still sucks: http://www.ietf.org/mail-archive/web/cfrg/current/msg03689.html [ietf.org]

I don't have a reply to that yet. In all fairness, it has been the Christmas and New Year period, and it's been kind of a busy one this year, and there's some procedural things to sort out that are probably going to take some time (and input from the crowd here would probably only make things worse, right now). Meanwhile, we have recommendations to make about TLS - in short, use it, but for God's sake, turn off RC4 because it's shit and probably worse than the BEAST attack people tended to use it to avoid - and some new things to roll out with that before the big work on TLS 1.3; with encrypted ClientHellos and pinned certificates to stop random CAs impersonating sites high on the wishlist.

An update, by the way: after re-opening the comments period, having been openly informed of the Snowden disclosures (albeit years after cryptographers warned them), NIST have agreed to remove Dual_EC_DRBG from SP 800-90A. So that's something, at least.

/akr

Re:How long until someone cracks the backdoor key? (2)

cold fjord (826450) | about 7 months ago | (#45840825)

I suggest anyone interested in this controversy read the following:

How a Crypto ‘Backdoor’ Pitted the Tech World Against the NSA [wired.com]

Although this is in regard to GCHQ, it probably applies to NSA as well: ‘We Can Trust GCHQ On Encryption’ [techweekeurope.co.uk]

Re:How long until someone cracks the backdoor key? (0)

Anonymous Coward | about 7 months ago | (#45839339)

I'd be curious to know just how hard it would be to brute-force the backdoor key itself. There didn't seem to be anything in TFA about that, and I can't figure out the math myself.

Given that this was done by RSA+NSA, I assume they made it so hard its completely intractable. They know their stuff, and its in their interest to prevent it from being cracked. They could have botched it though, but that seems unlikely: they do have a majority of the world's cryptography budget on their side.

Re:How long until someone cracks the backdoor key? (1)

MobSwatter (2884921) | about 7 months ago | (#45839771)

Yep, nothing like doing security work and finding one's pants are already around your ankles.

This is pretty freaking huge, if true (2, Insightful)

Anonymous Coward | about 7 months ago | (#45839139)

Please, people who understand EC properly, verify & reproduce this ASAP. If so this is yet another thing (one the BIGGEST things) the NSA has denied about the content of the Snowden leaks.

Plus RSA needs to really step up and be honest about just what occurred inside their walls wrt. FIPS and this algorithm.

At this point, I think the longstanding rule that 'only a fool writes his own crypto' is getting weaker.. I would amend it to "only a fool writes his own crypto, or uses ones supplied by anyone without full, independent audit and full control over magic constants..."

Captcha: bilked

Re:This is pretty freaking huge, if true (1)

MobSwatter (2884921) | about 7 months ago | (#45839619)

RSA needs to really step up and be honest about just what occurred inside their walls wrt. FIPS and this algorithm.

This will never happen if they were subject to the NSL, they would be legally bound from doing such.

Dual_EC is not mandatory (1)

jgreen1024 (975555) | about 7 months ago | (#45839235)

Dual_EC_DRBG is *not* mandatory under FIPS 140-2. As of today (January 1), some of the older RNGs are no longer permitted for new FIPS validations, effectively leaving you with only SP800-90A (DRBG). However, there are four different DRBGs contained within 800-90A. Nothing says you need to implement all four of them. One is good enough. Out of the four, only one of them (Dual_EC) is considered suspect.

Re:Dual_EC is not mandatory (0)

Anonymous Coward | about 7 months ago | (#45839477)

Thank goodness it wasn't actually mandatory, that's probably why, as it turns out, nobody using OpenSSL has even seen this bug which renders that implementation broken (if I read correctly):

http://marc.info/?l=openssl-announce&m=138747119822324&w=2

Pretty sad even independent of the NSA issue... the algorithm was so obscure or untrusted already that no one even noticed it's been broken in OpenSSL for a long time :/

The maths is easy for a fifth grader (0)

Anonymous Coward | about 7 months ago | (#45839273)

If you want to check that its random, just sample the output, brute force it and see if it puts out the whole range of possible values in equal amounts

Re:The maths is easy for a fifth grader (2)

VortexCortex (1117377) | about 7 months ago | (#45839479)

You moron. My PGP encrypted email passes the Diehard tests for randomness -- Doesn't mean it's actually random bits.

Re: The maths is easy for a fifth grader (-1)

Anonymous Coward | about 7 months ago | (#45840471)

If you are seeing lots of morons maybe stop looking in the mirror. The article is about a random number generator, and to test whether it is random you look at its output. Pgp encryption is two way therefore not random. The bits produced by encrypting something is a different story.

Re: The maths is easy for a fifth grader (2, Informative)

Anonymous Coward | about 7 months ago | (#45839551)

Incorrect.

Randomness will assume a gaussian curve distribution, given enought samples, over sufficient time.

A generator algorithm that produces a uniform flat distribution would expose predictable patterns in output that could be exploited.

Re: The maths is easy for a fifth grader (0)

Anonymous Coward | about 7 months ago | (#45840521)

Um nope sorry, over time there may be bumps here and there but more time will flatten. If its a Gaussian curve its biased

Re:The maths is easy for a fifth grader (2)

black3d (1648913) | about 7 months ago | (#45839571)

And when you're done in 50000 years with our current supercomputers, let us know the results. The number of possible combinations is a bit over 170141183460469231731687303715884105728. Good luck with your bubble-sort.

Nice maths (0)

Anonymous Coward | about 7 months ago | (#45840247)

If it takes 50000 year's with today's computing power, and if we apply Moore's law to that, then wouldn't you have to divide remaining number of years by say 2 every 2 years? So wouldn't your impressive 50K turn into 30 years? Years = (Years - 2 / 2) until Years 0 would only give you 15 iterations.

Re:Nice maths (1)

black3d (1648913) | about 7 months ago | (#45840497)

No, not really - and as I was writing it I thought "I bet someone's gonna bring Moore's Law into this and then I'm going to have to explain". So I'll explain - the 50,000 years was a figure thrown out there. Really, as long at time taken > life expectancy, OP won't be able to find a result. The actual time to perform that many encryption cycles would be in the millions of years. If Moore's Law progresses over time that would certainly be brought down, but not within OPs lifetime. Then you've got to compare the data set. Nevermind that physically storing that many 32-bit strings would take more atoms than exist on our planet. The point was simply that OPs suggestion was ridiculous.

Your assuming non quantum computer use (0)

Anonymous Coward | about 7 months ago | (#45840683)

With quantum computers I would guess that this could become trivial with enough qubits

Re: The maths is easy for a fifth grader (1)

Anonymous Coward | about 7 months ago | (#45840959)

By that definition even this is random:

int rand()
{
        static int seed = 0;
        seed++;
        return seed;
}

Outputs full range of values? Check!
Must be random.

More interesting facts (5, Informative)

thue (121682) | about 7 months ago | (#45839401)

I have been adding various facts to the Wikipedia article on Dual_EC_DRBG [wikipedia.org] . A good deal of the most interesting points have not been reported in mainstream media.

* The ANSI group which standardize Dual_EC_DRBG were aware of the potential for a backdoor.
* Three RSA Security employees were listed as being in that ANSI group, making RSA Security's claim innocence claim shaky, since it is less likely that RSA Security didn't know about the back door when NSA paid them $10 million to use Dual_EC_DRBG as default.
* Two Certicom members of the ANSI group wrote a patent which describes the backdoor in detail, and two ways to prevent it.
* Somehow the ways to prevent the backdoor only make it into the standard as non-default options.
* Somehow the people on the ANSI group forget to publicize the potential for a backdoor. Especially Daniel brown of Certicom (co-author of the patent), who also wrote an attempt at a mathematical security reduction for Dual_EC_DRBG, but somehow forgets to explicitly mention the backdoor. The conclusion in Brown's paper also seems very determined to hype Dual_EC_DRBG, whereas the other papers about Dual_EC_DRBG seem excited to hype the errors they find.
* The potential backdoor only becomes public knowledge in 2007.
* Daniel Brown writes in December 2013 [ietf.org] that "I'm not sure if this was obvious." and "All considered, I don't see how the ANSI and NIST standards for Dual_EC_DRBG can be viewed as a subverted standard, per se.".

Certicom is the main inventor and patent-holder for elliptic curve cryptography. The two Certicom employees failing to warn or prevent the backdoor they clearly know was possible doesn't reflect well on Certicom.

Re:More interesting facts (-1, Flamebait)

cold fjord (826450) | about 7 months ago | (#45840045)

In short, as is the case with many conspiracy theories all you have is a collection of things that are suggestive, not definitive. You basically concede that if you implement the amended standard the crypto is good. Nobody has found any proof that a backdoor actually exists, only that it may be possible. Even if it is possible, nothing shows that NSA actually has one. The things that you've collected could support many possible theories, including the possibility that NSA only paid RSA to promote what appeared to be a highly promising crypto technology. For all that anybody actually knows the NSA could have chosen the form of the curve with the perceived potential backdoor as a spoof to entice Russia or China to waste a large compute farm trying to find the backdoor when it doesn't exist, and it could otherwise be working on something productive. There isn't any way of knowing, and Bruce Schneier has said that Snowden's leaks don't show that NSA has weakened crypto. Snowden himself said that protecting your data with cryptography still works. Somehow I doubt any of that will make it in with your "updates" to Wikipedia.

By the way, did you hear that NSA "fiddled" with the DES standard? They made mysterious changes to the proposed S-boxes to the standard. Any idea what happened there?

Re:More interesting facts (4, Informative)

thue (121682) | about 7 months ago | (#45840165)

> In short, as is the case with many conspiracy theories all you have is a collection of things that are suggestive, not definitive.

When you design a standard, one of the design criteria is that it does not allow for even a potential a backdoor. See fx https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number [wikipedia.org] . It is most definitive that Dual_EC_DRBG should never have been approved given the knowledge available at the time of how to prevent any possible backdoor.

Re:More interesting facts (1, Interesting)

cold fjord (826450) | about 7 months ago | (#45840563)

You exaggerate things, which is consistent with much of the discussion on this. I suggest reading the whole article at the link.

How a Crypto ‘Backdoor’ Pitted the Tech World Against the NSA [wired.com]

Jon Callas, the CTO of Silent Circle, whose company offers encrypted phone communication, delivered a different rump session talk at the Crypto conference in 2007 and saw the presentation by Shumow. He says he wasn’t alarmed by it at the time and still has doubts that what was exposed was actually a backdoor, in part because the algorithm is so badly done.

“If [NSA] spent $250 million weakening the standard and this is the best that they could do, then we have nothing to fear from them,” he says. “Because this was really ham-fisted. When you put on your conspiratorial hat about what the NSA would be doing, you would expect something more devious, Machiavellian and this thing is just laughably bad. This is Boris and Natasha sort of stuff.”

Indeed, the Microsoft presenters themselves — who declined to comment for this article — didn’t press the backdoor theory in their talk. They didn’t mention NSA at all, and went out of their way to avoid accusing NIST of anything. “WE ARE NOT SAYING: NIST intentionally put a back door in this PRNG,” read the last slide of their deck.

The Microsoft manager who spoke with WIRED on condition of anonymity thinks the provocative title of the 2007 presentation overstates the issue with the algorithm and is being misinterpreted — that perhaps reporters at the Times read something in a classified document showing that the NSA worked on the algorithm and pushed it through the standards process, and quickly took it as proof that the title of the 2007 talk had been right to call the weakness in the standard and algorithm a backdoor.

Re:More interesting facts (1)

Anonymous Coward | about 7 months ago | (#45840301)

By the way, did you hear that NSA "fiddled" with the DES standard? They made mysterious changes to the proposed S-boxes to the standard. Any idea what happened there?

The DES case is well understood: Wikipedia [wikipedia.org] has a pretty good description of what happened. The S-Boxes were intentionally chosen to be optimal against differential cryptanalysis, which was not public knowledge for another 20 years, which seems like the NSA was making the algorithm stronger... but they also argued for a shorter key length, presumably because they wanted DES to be not too hard for them to break.

On Dual_EC_DRBG, the problem is that there are known ways to make it provably secure and they weren't used. That's a huge red flag and simply bad practice even if there isn't a backdoor. Magic numbers in cryptography are generally very suspect and as a rule should be chosen/used in a way to guarantee that they are not chosen to be weak.

Re:More interesting facts (2)

cold fjord (826450) | about 7 months ago | (#45840727)

The DES case is well understood

The DES case is well understood NOW. DES was at the subject of conspiracy theories, suspicion, and fear for nearly 20 years, just in the same way that this controversy is likely to go.

The ironic thing about the DES controversy is that it was secretly stronger than many people knew, not weaker, and there are people that adopted other far weaker encryption schemes out of fear and suspicion rather than use DES. The secret techniques that DES was hardened against made cracking many of those other encryption much easier. I wonder how many secrets were lost because people went to those other encryption methods that were vulnerable to the secret cryptanalysis techniques that DES was immune to?

Here is a though provoking piece for you: ‘We Can Trust GCHQ On Encryption’ [techweekeurope.co.uk]

The NSA is fucking stupid! (4, Insightful)

LazLong (757) | about 7 months ago | (#45839907)

So, they introduced a backdoor into software that can be/is used to secure US nuclear secrets, in the hopes only they would be able to take advantage of it? This is just another variant of "security through obscurity." Really, really fucking stupid!

RELIABLEWINDMILL (0)

Anonymous Coward | about 7 months ago | (#45840311)

RELIABLEWINDMILL sounds like a project classification. Wonder who submitter is?

random(Dual_EC_DRBG()) (1)

xeoron (639412) | about 7 months ago | (#45840407)

If you use more than 1 sequence of randomness while using the required standard, is that code viewed as compliant?
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...