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!

Are the NIST Standard Elliptic Curves Back-doored?

Unknown Lamer posted about 10 months ago | from the nsa-versus-nist dept.

Encryption 366

IamTheRealMike writes "In the wake of Bruce Schneier's statements that he no longer trusts the constants selected for elliptic curve cryptography, people have started trying to reproduce the process that led to those constants being selected ... and found it cannot be done. As background, the most basic standard elliptic curves used for digital signatures and other cryptography are called the SEC random curves (SEC is 'Standards for Efficient Cryptography'), a good example being secp256r1. The random numbers in these curve parameters were supposed to be selected via a "verifiably random" process (output of SHA1 on some seed), which is a reasonable way to obtain a nothing up my sleeve number if the input to the hash function is trustworthy, like a small counter or the digits of PI. Unfortunately it turns out the actual inputs used were opaque 256 bit numbers, chosen ad-hoc with no justifications provided. Worse, the curve parameters for SEC were generated by head of elliptic curve research at the NSA — opening the possibility that they were found via a brute force search for a publicly unknown class of weak curves. Although no attack against the selected values are currently known, it's common practice to never use unexplainable magic numbers in cryptography standards, especially when those numbers are being chosen by intelligence agencies. Now that the world received strong confirmation that the much more obscure and less widely used standard Dual_EC_DRBG was in fact an NSA undercover operation, NIST re-opened the confirmed-bad standards for public comment. Unless NIST/the NSA can explain why the random curve seed values are trustworthy, it might be time to re-evaluate all NIST based elliptic curve crypto in general."

cancel ×

366 comments

Meta review (5, Interesting)

pr0nbot (313417) | about 10 months ago | (#44818101)

As well as reviewing the standards themselves, I hope someone is reviewing the processes which allowed these weaknesses to get into the standards.

Re:Meta review (5, Insightful)

FriendlyLurker (50431) | about 10 months ago | (#44818141)

it's common practice to never use unexplainable magic numbers in cryptography standards, especially when those numbers are being chosen by intelligence agencies.

Well then, how do we explain the common practice of using magic numbers in cryptography standard, then?

As well as reviewing the standards themselves, I hope someone is reviewing the processes which allowed these weaknesses to get into the standards.

Exactly. A list of people had to be complicit in getting these "magic backdoor" numbers into the standards. The integrity of these people is now highly questionable, and they should be put to task over the issue, removed from decision making posts and in the worst cases, professionally shunned by the community and excluded from all standards processes... the cost of not doing this is a return to business as usual once things settle down.

Re:Meta review (-1, Flamebait)

Anonymous Coward | about 10 months ago | (#44818191)

Also, America is backdoored, through its Legislative Branch via AIPAC and Israel. No matter what happens in Syria, America will go to war for Israel. Grrr, sick 'em! Attack!

Re:Meta review (-1, Troll)

Anonymous Coward | about 10 months ago | (#44818223)

It's "sic", not "sick" doofus.

Re:Meta review (-1, Offtopic)

Anonymous Coward | about 10 months ago | (#44818455)

Excellent point. Slashdot is backdoored as well, as Israel's hasbara corps constantly downvote anything critical of Israel's control over the US government.

Re:Meta review (-1)

Anonymous Coward | about 10 months ago | (#44818745)

Dice.com are government stooges.

Re:Meta review (-1, Troll)

Lumpy (12016) | about 10 months ago | (#44818685)

This message brought to you by the anti-Semite party of america. when you absolutely must hate for no rational reason, at least hate with others that are as delusional as you are.

We owe our thanks to Mr. Snowden (5, Insightful)

Taco Cowboy (5327) | about 10 months ago | (#44818271)

... A list of people had to be complicit in getting these "magic backdoor" numbers into the standards. The integrity of these people is now highly questionable

This, and many other expose, can only come to light, because of the courage of a single person - Mr. Edward Snowden.

If not for Mr. Snowden, would we ever discover the phenomenon of the "magic number" ?

If not because of Mr. Snowden, we wouldn't even begin to question the integrity of those previously highly regarded "very important people".

If not for his courage, how much more damage all of us have to suffer ?

And yet, inside the United States of America, there are still people equating Mr. Snowden as though he is a traitor.

And even here in Slashdot, we have posters posting very stinging attack on Mr. Snowden.

Our country is under attack, and the attacker is our own government, but yet, there are still Americans who will do everything to help deepen the tyranny, all in the name of "patriotism".

I, an American citizen, do owe my deepest thanks to Mr. Edward Snowden, and I do hope that more of my fellow Americans should start acknowledge something very very wrong has happened to America, the country we love so much, and that we should start doing something together, to RIGHT THE WRONGS.

There have been too many comments that essentially convey the message that we, the People of America, have no power to determine our own future, and that our government, is so overwhelmingly powerful that we are ready to become their slaves, rather than stand up and oppose the tyranny.

Is America still the land of the free, and the home of the braves ?

Or has American turned into the land of the enslaved, and the home of the cowards ?

The choice is on your hand, my fellow Americans.

Either we start righting the wrongs now, or we will end up handing over to our children a country of tyranny.

Are we going to let our children suffer because of our cowardice ?

You are the only one who can answer the question.

Re:We owe our thanks to Mr. Snowden (5, Informative)

j3thr0 (189013) | about 10 months ago | (#44818367)

Re:We owe our thanks to Mr. Snowden (5, Insightful)

rvw (755107) | about 10 months ago | (#44818399)

So why has nobody fixed this in the past six years? Thanks to Snowden it's back in the spotlight, and now it seems like action is being taken. That's his legacy. I thank him for that.

Re:We owe our thanks to Mr. Snowden (5, Informative)

IamTheRealMike (537420) | about 10 months ago | (#44818461)

That story is about Dual_EC_DRBG which was indeed strongly suspected of being an NSA back door back in 2007. Snowden confirmed the suspicion. However this story is not about that algorithm. It's about the SEC random curves that are used for signing and other crypto, not random number generation. There are two different algorithms under discussion here.

Re:We owe our thanks to Mr. Snowden (1)

Bing Tsher E (943915) | about 10 months ago | (#44818495)

When it came to light in 2007 why was it tamped down and not dealt with? Is there a history that needs to be audited to explain why it drifted (was pushed?) back into obscurity? Perhaps there's even more value in investigating this. Could there be agents that need to be identified and rooted out?

The above is speculation, but it's the sort of question that should be asked, and our understanding of the matter increased.

Re:We owe our thanks to Mr. Snowden (-1, Troll)

Cigarra (652458) | about 10 months ago | (#44818629)

Thank you Mr. Taco Cowboy (if that's your real name). The FBI should be visiting soon [policestateusa.com] . Please hide your dogs, for their own sake.

Re:We owe our thanks to Mr. Snowden (0)

Anonymous Coward | about 10 months ago | (#44818709)

And even here in Slashdot, we have posters posting very stinging attack on Mr. Snowden.

Not all shills are corporate shills. You don't think the NSA is watching slashdot, or that no NSA operatives are nerds? Anyone who says Snowden is a traitor is either an NSA traitor (spying on our own people IS treason) or has been brainwashed by the NSA's bullshit.

Re:Meta review (1)

Anonymous Coward | about 10 months ago | (#44818299)

Exactly. A list of people had to be complicit in getting these "magic backdoor" numbers into the standards. The integrity of these people is now highly questionable, and they should be put to task over the issue, removed from decision making posts and in the worst cases, professionally shunned by the community and excluded from all standards processes... the cost of not doing this is a return to business as usual once things settle down.

OK, calm down. Last time the community accepted NSA magic numbers, it made DES significantly stronger. I think the lesson here is never trust the NSA.

In the words of a great American philosopher, "Fool me once, shame on you. Fool me twice... um... you're not going to fool me twice!"

Re:Meta review (1)

fsagx (1936954) | about 10 months ago | (#44818447)

The modified constants supplied by the NSA did improve the design from a then unknown (outside the NSA) type of attack. It was not until years later that the reasons became clear. OTOH NSA also significantly shortened the key length....

http://en.wikipedia.org/wiki/Data_Encryption_Standard [wikipedia.org]

Re:Meta review (1)

AHuxley (892839) | about 10 months ago | (#44818531)

RE it made DES significantly stronger?
Banks and businesses where to get a strong version. At some point the "industry" went for a weaker code for wider use.
Just good enough for commercial use, just weak enough for NSA/GCHQ to get in if needed.
http://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27s_involvement_in_the_design [wikipedia.org]
...'to reduce the length of the key from 64 to 48 bits. Ultimately they compromised on a 56-bit key"
It seems the code was helped to be more protected (ie the significantly stronger aspect ) but was not going to be used without a way back in.

Re:Meta review (1)

Electricity Likes Me (1098643) | about 10 months ago | (#44818755)

At the time the performance of DES was a big problem. Processors weren't nearly as fast, the habit of having dedicated coprocessors on portable devices/network cards hadn't yet emerged. There were a lot of good reasons to get the key-size down to something which would actually be usable at the time.

Its still a concern today - AES was selected because it was easier to implement in hardware, amongst other benefits.

Re:Meta review (4, Funny)

Bill, Shooter of Bul (629286) | about 10 months ago | (#44818719)

Wow. You butchered a butchered phrase. Truly, the student has become a more smart man- doesn't need school.

Its " fool me once, shame on - shame on you. Fool me - you can't get fooled again."

Re:Meta review (1)

Warbothong (905464) | about 10 months ago | (#44818305)

it's common practice to never use unexplainable magic numbers in cryptography standards, especially when those numbers are being chosen by intelligence agencies.

Well then, how do we explain the common practice of using magic numbers in cryptography standard, then?

I think the word "magic" is being used with two different meanings here. One meaning is "arbitrary but consistent": those numbers which must be standardised, such as the SHA seeds used to find these curves. The other meaning is "chosen for completely unknown reasons", which describes these particular seed values. The former is a requirement of most cryptographic standards, but the latter should be avoided. If we need to consistently choose an arbitrary number, let it be 1, or pi, or e. Anything else is suspicious.

Re:Meta review (5, Informative)

afidel (530433) | about 10 months ago | (#44818371)

Suspicious yes, but not necessarily bad, remember that the NSA also manipulated the s-box values for DES to make them more resistant to differential cryptanalysis, a technique not yet known by the wider community.

Re:Meta review (5, Interesting)

postbigbang (761081) | about 10 months ago | (#44818625)

Even when pi or rho or other "random" numbers are used for seeds as "magic" numbers, additional hashing and rehashing is needed to give further difficulty to decryption by those NOT having the key numbers.

With each new algorithm there is an army chomping at the bit (pardon the pun) to decrypt it, if not for fun or enlightenment, for the profit of the decrypted information value-- if any.

The problem here is trust. The NSA has blown its trust completely, beyond identifiability. Other initiatives, like SELinux, and security initiatives are now also in question, as well as anything the NSA has touched. They're dirty, and make Americans and the world not trust in their own government. We were supposed to be the good guys, we Yanks, and guess what? It was all a lie. Now the NSA has made an enemy of civil people, and civil people will need to protect themselves extra-governmentally, because the government has proven it's not protecting the interests of its citizenry.

Sorry to astroturf, but seeds are no longer the problem. The problem is trust.

Re:Meta review (5, Funny)

Anonymous Coward | about 10 months ago | (#44818311)

So I can just replace the NSA's magic-numbers with my own generated from RdRand! *ducks*

Re:Meta review (1)

AmiMoJo (196126) | about 10 months ago | (#44818769)

Seriously though, why don't we do this and also depreciate all suspect PRNGs immediately? Every Linux/BSD distro should be scrambling to do it.

Re:Meta review (3, Funny)

Anonymous Coward | about 10 months ago | (#44818317)

Well then, how do we explain the common practice of using magic numbers in cryptography standard, then?

That's easy to explain. Secret orders from secret courts and secret gag orders with secret threats that you will be "relocated" to a secret prison somewhere unless you comply (and keep your objections secret).

Re:Meta review (0)

Anonymous Coward | about 10 months ago | (#44818375)

There is only one problem with your post. Only one person has said the numbers are "unexplainable magic numbers" and that is a person on a TOR mailing list. Just because one person can't explain or doesn't know some thing, it does not follow that the thing is unexplainable. The TOR poster does not mention any other research he did to determine how the random seed was chosen. Also, he does not explain why he 'expected the seed to be some small value like ... "6F" '.

  This is simply a proxy argument by personal incredulity.

Re:Meta review (2)

Qzukk (229616) | about 10 months ago | (#44818663)

how do we explain the common practice of using magic numbers in cryptography standard, then?

They came from the government, and the government is here to help.

Re:Meta review (1)

mwvdlee (775178) | about 10 months ago | (#44818143)

Somehow I don't think these weaknesses were introduced through any formal part of the process.

Re:Meta review (2)

Nerdfest (867930) | about 10 months ago | (#44818203)

... then perhaps a formal process is required.

Re:Meta review (2)

TWiTfan (2887093) | about 10 months ago | (#44818145)

Don't worry, James Clapper has assured us that there is nothing to see here--and that the NSA's petabytes of storage, tens of billions of dollars of CPU muscle, and 35,000 employees are just being used to spy on a few diplomats in some embassy in some country that we don't like anyway (probably one of them commie ones).

Now let's all stop worrying about such silly matters and go buy new iPhones!

Re: Meta review (0, Funny)

Anonymous Coward | about 10 months ago | (#44818209)

Make sure to get an iPhone with fingerprint security.

Re:Meta review (1)

Phisbut (761268) | about 10 months ago | (#44818293)

Now let's all stop worrying about such silly matters and go buy new iPhones!

Yes, let's go buy new iPhones which will read your fingerprints and associate them with your name...

Re:Meta review (1)

Boronx (228853) | about 10 months ago | (#44818569)

When I was a kid in the '80s they tried to fingerprint the whole school "for our protection". I never could figure out how that protected us, but I seemed to be the only person who was concerned about.

I honestly don't remember whether or not they got me.

Re:Meta review (1)

mrspoonsi (2955715) | about 10 months ago | (#44818771)

Time to kick NIST out of the loop. If all indicators are right, that they work to deliberately weaken, and backdoor standards then an alternative is required. And given the secret courts, this cannot be based in the USA.

hmmm (2)

wbr1 (2538558) | about 10 months ago | (#44818107)

Didn't TOR recently upgrade to the 'more secure' elliptic curve crypto?

This shit will not end until this country is bankrupt completely, or taken over (from within or without).

Re:hmmm (0)

Anonymous Coward | about 10 months ago | (#44818137)

This shit is evidence that this country has *already* been taken over (from within and without).

Isn't it time we take back our own country ? (1)

Taco Cowboy (5327) | about 10 months ago | (#44818341)

This shit is evidence that this country has *already* been taken over (from within and without)

Isn't it time we, the American Citizens, take back our own country from those fuckers ?

How much longer should we let those fuckers to ruin our country ?

How much longer do we want to be fooled by those fuckers ?

How much longer can our country last, under those fuckers ?

Re:Isn't it time we take back our own country ? (1)

Ksevio (865461) | about 10 months ago | (#44818403)

Yeah! So who are we running for President?

Re:Isn't it time we take back our own country ? (1)

rvw (755107) | about 10 months ago | (#44818449)

This shit is evidence that this country has *already* been taken over (from within and without)

Isn't it time we, the American Citizens, take back our own country from those fuckers ?

How much longer should we let those fuckers to ruin our country ?

How much longer do we want to be fooled by those fuckers ?

How much longer can our country last, under those fuckers ?

So what are you waiting for? You tell others what to do, and do nothing yourself. That's not going to motivate anybody.
(Disclaimer: I am not a US citizen)

Re:Isn't it time we take back our own country ? (1)

Lumpy (12016) | about 10 months ago | (#44818741)

AS soon as you get off your ass and do something other than bitch. I dont see you at any of the rallys or picketing in front of the whitehouse.

Re:hmmm (4, Insightful)

TWiTfan (2887093) | about 10 months ago | (#44818189)

The sad thing is that there is no way to ever put Humpty Dumpty back together again. The U.S. just permanently lost any position as a leading internet innovator. Nothing the U.S. leaders of industry can do now will ever earn back the trust of the rest of the world. No country or company in their right mind will ever trust a U.S. company with sensitive data ever again, and most of the companies that currently do are likely just biding time until they can find a non-U.S. based alternative (or some way to heavily encrypt their data).

Re:hmmm (1)

Anonymous Coward | about 10 months ago | (#44818339)

And America will threaten and bluster about trade sanctions and how this is hurting US businesses. The rest of the world will point out that's not their problem.

This is a problem of their own making -- by turning your companies into an arm of your security apparatus, they become entities nobody else can trust. It's just sad that it took so long after the Patriot Act was passed for people to realize just how badly the US had decided it was their right to undermine the security of the rest of the world.

By undermining cryptography in general, when someone comes up with the next iteration, hopefully they'll make it in such a way that government agencies don't have ready access to. And hopefully they'll basically tell the government they're not interested in their input on the matter.

At this point, why any foreign government would trust Microsoft any more than something out of Iran I have no idea -- because as much as America likes to keep saying they're the good guys, nobody else can trust them.

You can own that, and when companies start cancelling deals with American companies, don't act like you're surprised or feel it's unfair to you.

It's sad, because the US was the only country in the world for a lot of years defending rights and freedoms -- but have more or less turned the corner and gone the other direction.

Now they've basically reverted to their 'manifest destiny' idiocy and a sense of entitlement about everything.

Re:hmmm (1)

AHuxley (892839) | about 10 months ago | (#44818721)

Others govs may love of all this as many have been invited into the basic telco/phone tracking and deep packet efforts by contractors.
They can tap/log/track and are just as addicted to the daily file updates on all dissidents.
The US has not much to fear as the AC mentioned trade sanctions and US bilateral trade deals would have telco cooperation in the fine print.
If a US brand loses a contract due to "security questions" expect to see a reminder of what trade is in the local press and a powerful court/trade challenge.
Nation by nation the US hope to rebuild its image and branding via new products and soft loans.
Over time sockpuppets, trade deals and charm will solve all?

Re: hmmm (2)

sumdumass (711423) | about 10 months ago | (#44818365)

You will find that the majority of decision makers around the world, whether in buisiness or government, will not care as much about this in the long run as you do.

In other words, what you say should be true in book form but will not be true in practice. Many people/governments will not even bother looking to see who is behind what, they will be looking to see if it is an industry accepted standard and our personal concerns will rarely change those. If it could, we wouldn't see wireless at half these businesses.

Re: hmmm (1)

Boronx (228853) | about 10 months ago | (#44818585)

Their level of concern is proportional to how close their competitors are to the NSA.

Re:hmmm (2)

EmperorOfCanada (1332175) | about 10 months ago | (#44818445)

Will take time. I suspect that companies like Cisco will sigh a breath of relief over the next few months when sales don't plummet. What they won't realizes is that the biggest companies that have no doubt issued directives for an end to end anti-US snooping overhaul will take a while to figure out what needs to be replaced and which products are best. So while these audits and re-architectings take place these companies will continue with business as usual. And even when the plan is deployed I doubt 100,000 employee companies will just toss all their stuff out on Friday to have it all replaced on Monday. They will start with the most critical bits and work their way down the information value chain. So at this point the Cisco type companies will see a slight drop in sales but even still the companies will continue with maintenance contracts to keep their gear going.

But at a certain point you will have an interesting problem. That is that these companies will begin to dump their Cisco gear onto the open market. So along with a sudden drop in sales to key customers you will have a glut of un-trusted gear flood the market.

I use Cisco as an example but you can sub in any American (or American stooge country) networking gear company.

I also expect to see a flourishing of cryptography in various foreign math departments around the world. If I were a Siemens I would be giving fairly large grants to German/Swedish/Norwegian etc math departments to do two things, check for backdoors and to come up with crypto systems that are quite unlike anything that the NSA has recommended.

But switching crypto systems is not as easy as just coming up with something that a bunch of math wizards think is solid. Things like AES crypto is baked right into many modern chip sets at the assembly instruction level. This is why AES based crypto is fantastically fast. So if your new system is different enough yet theoretically computationally equivalent to AES then it will be significantly slower on most chips.

One of the interesting changes that will probably come from this is that people won't trust anything. Thus they will run in 100 different directions. This will be a nightmare for the NSA because even if they can brake every crypto system that comes along they will have to spend the time to break them all.

But there is one system that can't be broken and that is one time pads. You have to physically share the pad but that is not so onerous for most companies as they have trusted employees going from branch to branch all the time. If the border people grab a copy of the OTP then you just toss it in the garbage. Plus one time pads can be layered. So you don't need to trust just one person taking one route.

Re:hmmm (1)

gstoddart (321705) | about 10 months ago | (#44818593)

But there is one system that can't be broken and that is one time pads. You have to physically share the pad but that is not so onerous for most companies as they have trusted employees going from branch to branch all the time.

I just don't see that as being as useful here. Or at least, not solving the general problem in a usable way.

Take a multi-national with say, 20 offices, which seems small ... don't you need a OTP for each pair of offices? That's going to turn into a rather large number of OTPs, plus the fun of trying to manage them all. And that assumes that each office only ever needs one set of crypto keys and doesn't have multiple different encrypted streams (routine stuff, secure stuff, really secure stuff for instance).

And assuming you are trying to run a VPN, you'd need an absolutely enormous OTP to handle all of the traffic you'd generate on a daily basis.

I can see a OTP being useful for stuff which has to be super secure, but I just don't see it being able to keep up with the sheer volume of data companies need to encrypt on a daily basis -- it seems like it would be an almost impossible task.

Of course, what I know about crypto probably fits on a single sheet of paper and comes from a single course 15+ years ago and what I've read in Tom Clancy novels -- so it's possible many of these are solved problems.

Re:hmmm (0)

Anonymous Coward | about 10 months ago | (#44818751)

One-time pads aren't really useful for encrypting large amounts of data. Large lists of random-generated symmetric crypto keys, on the other hand... 10 GiB buys you more than 335 million AES-256 keys, and since you can use an encrypted session set up with one of those keys to transfer as many more keys as you like, the system can be replenished indefinitely.

Re:hmmm (2, Interesting)

Anonymous Coward | about 10 months ago | (#44818549)

The sad thing is that there is no way to ever put Humpty Dumpty back together again. The U.S. just permanently lost any position as a leading internet innovator.

And because having worked for NSA or NSA-linked contractors is seen as a black mark [ycombinator.com] on one's academic career, NSA has also jeopardized its own ability to recruit the next generation of cryptographers.

There's give and take between the SIGINT and COMSEC missions, and nobody here (or within the IC) is privy to all the information. I fear that by the time it's all declassified in 25 years and can be analyzed in context, the decisions made over the past 12 years will have proven to be gross strategic errors that did far more harm than any harm they prevented.

Re:hmmm (0)

Anonymous Coward | about 10 months ago | (#44818727)

The sad thing is that there is no way to ever put Humpty Dumpty back together again

Bullshit.

The U.S. just permanently lost any position as a leading internet innovator

Says who?

Nothing the U.S. leaders of industry can do now will ever earn back the trust of the rest of the world.

HAHAHAHAHA ya, right. Just keep thinking that, buddy.

No country or company in their right mind will ever trust a U.S. company with sensitive data ever again

Ah, the "no true Scotsman" fallacy at work.

and most of the companies that currently do are likely just biding time until they can find a non-U.S. based alternative (or some way to heavily encrypt their data).

1. You know this... how?
2. You assume (wrongly) that the same types of shit aren't being done by other countries. It's a good thing you're not actually in control of anything other than trolling on Slashdot, because you have just demonstrated a complete lack of understanding about how the world works.

Re:hmmm (0)

Anonymous Coward | about 10 months ago | (#44818213)

This shit will not end until this country is bankrupt completely, or taken over (from within or without).

No, it didn't.

Re:hmmm (3, Informative)

Anonymous Coward | about 10 months ago | (#44818231)

Yes, but they are using curve25519 which is not one of the curves recommended by NSA or NIST, and which does not have any unexplained magic numbers in its definition.

Re:hmmm (2)

Anonymous Coward | about 10 months ago | (#44818429)

Yes, but they also use ECDHE TLS p224 to negotiate TLS secret keys. Isn't that recommended by NIST?

I'm not an expert, I'm just asking.

Re:hmmm (1)

intermodal (534361) | about 10 months ago | (#44818715)

One of my biggest fears is that you are correct.

Is Bitcoin Vulnerable? (0)

Anonymous Coward | about 10 months ago | (#44818113)

Elliptic curve cryptography runs Bitcoin. Does the NSA have the ability to steal Bitcoin at will?

Re:Is Bitcoin Vulnerable? (0)

Anonymous Coward | about 10 months ago | (#44818131)

Why would they bother?

Re:Is Bitcoin Vulnerable? (0)

Anonymous Coward | about 10 months ago | (#44818165)

Elliptic curve cryptography runs [Insert program relying in the standard]. Does the NSA have the ability to steal [Insert program relying in the standard] at will? Yes and maybe. It is back to the drawing board for our cryptology standards... trust has been lost.

Re:Is Bitcoin Vulnerable? (0)

Anonymous Coward | about 10 months ago | (#44818621)

The problem is NOT with elliptic curve cryptography, its to do with certain implementations of it. There's more than 1, in fact there are hundreds and the one with the most controversy happens to be the one that the NSA recommended. There are plenty of other implementations that aren't questionable and just fine for crytpto as far as we are aware.

That said, I don't know which version Bitcoin uses.

Re:Is Bitcoin Vulnerable? (0)

Anonymous Coward | about 10 months ago | (#44818185)

maybe, but they probably have a way to figure out the people behind every bitcoin transaction, ever which is a lot more valuable to them

Re:Is Bitcoin Vulnerable? (0)

Anonymous Coward | about 10 months ago | (#44818763)

maybe, but they probably have a way to figure out the people behind every bitcoin transaction, ever which is a lot more valuable to them

Uh, ya that's built into the Bitcoin standard. The only way to hide your tracks is to use an agency which allows you to trade with anonymous accounts. Which is generally known in the Banking industry as "money laundering", and many governments are starting to look at Bitcoin that way as well.

Bitcoin was meant to be de-centralized, not anonymous. If you want to remain covert you have to make use of some sort of middle-man acting as a broker for you, who will protect your identity.

Re:Is Bitcoin Vulnerable? (1)

IamTheRealMike (537420) | about 10 months ago | (#44818307)

Bitcoin uses what the SEC calls a Koblitz curve (secp256k1) for which there is much less design freedom and it seems much less likely that there is any way to back-door those curves. Unfortunately many ECC implementations don't support all the curves, just a few of the plain vanilla random ones. Actually I'm not aware of anything except Bitcoin that uses secp256k1.

Re:Is Bitcoin Vulnerable? (0)

Anonymous Coward | about 10 months ago | (#44818309)

Nope: Satoshi thought of it:
https://bitcointalk.org/index.php?topic=151120.0

djb to the rescue! (0)

Anonymous Coward | about 10 months ago | (#44818117)

Now's your time to shine dan

Here's a thought (0)

Anonymous Coward | about 10 months ago | (#44818173)

Round up a few cryptographers who, at a given time and place must disclose a random (or not) password they have chosen and kept secret until then. Encourage international participation, maybe hundreds of people.

Concatenate all the strings, append a numeric index and hash the result with SHA3. You will get an indexed list of 512 bit values that are provably random, unless all cryptographers of the world are in a grand conspiracy - since each person contributing an input has the possibility to undo any collusion of the others.

Re:Here's a thought (0)

Anonymous Coward | about 10 months ago | (#44818263)

There is no need to round up cryptographers for this job. A bunch of monkeys with typewriters should suffice.

Re:Here's a thought (0)

Anonymous Coward | about 10 months ago | (#44818363)

Who will provide the monkeys ? Have they been trained to type ? Who will organize and supervise the monkey typing session, and guarantee the jumbled letters are really what the moneys intended to produce ?

The typing cryptographers will be able to design systems based on those numbers with the confidence that either themselves or someone they know or respect ensured they were really random.

Why is EC more secure than RSA? (4, Interesting)

pikine (771084) | about 10 months ago | (#44818183)

Color me ignorant, but could someone please explain that elliptic curve is more secure than RSA? Wikipedia even claims that a 128-bit EC key is equivalent to 3072-bit RSA key. Even if it's computation complexity brute forcing discrete log or integer factorization on a non-deterministic turing machine, it should differ by no more than a small constant factor, e.g. 512-bit versus 1024-bit, not by O(sqrt(n)) as Wikipedia claims. Wikipedia is simply quoting NSA [nsa.gov] .

Re:Why is EC more secure than RSA? (1, Redundant)

foma84 (2079302) | about 10 months ago | (#44818277)

Increasing EC key-lenght yelds cyphertext that is more difficult to crack with respect to increasing RSA key-lenght. I don't remeber the numers or proportions, tho, so i'll just use a loose example (don't follow the numbers here strictly):
Doubling the RSA key-lenght will give you a cypher that's polynamialy more difficult to crack, while doubling EC key-lenght will give you a cypher that's exponentially more difficult.

Or something like that.

Re:Why is EC more secure than RSA? (0)

Anonymous Coward | about 10 months ago | (#44818295)

If that's what WP's got, that's what they're publishing: http://en.wikipedia.org/wiki/Wikipedia:TRUTH

If you can prove that the NSA data is incorrect by pointing at a verifiable, reliable source, then edit the article to reflect this. If you don't, then perhaps the opinion on the NSA's research isn't as well-founded as you think it is.

Re:Why is EC more secure than RSA? (5, Informative)

Anonymous Coward | about 10 months ago | (#44818329)

The number field sieve relies on the smoothness of the integers modulo n. Using an elliptic curve group rather than the integers modulo n removes this smoothness, so the fastest algorithms available to determine the discrete logarithms are much slower (I believe they're based on Pollard's rho algorithm).

If that made no sense to you, go brush up on your number theory.

If you don't want to learn number theory, then accept that you are incapable of having an informed opinion on asymmetrical cryptography standards. (Which is okay, we can't all have an informed opinion on every issue; your brain can only hold so much stuff, right?)

Re:Why is EC more secure than RSA? (1)

Anonymous Coward | about 10 months ago | (#44818343)

Because the problem being solved is different and therefore the algorithms used for attacks are different. The best known algorithms for factoring numbers are a lot faster than the best known algorithms for solving the problem that elliptic curve cryptography is based on. These best algorithms aren't just using brute force, by the way - they are not trying out all possibilities.

Re:Why is EC more secure than RSA? (3, Insightful)

gnasher719 (869701) | about 10 months ago | (#44818351)

A 1024 bit RSA key can trivially be cracked in 2^512 operations. An algorithm that uses 2^341 operations (cube root) and involves no more than high school maths was found about 1975. Then we need to go into deep maths, but there are algorithms that are significantly faster, and there is no good reason to think that more progress couldn't be made. 128 vs 3072 is a bit much, but factoring 1024 bit numbers in 2^128 operations doesn't seem impossible.

Re:Why is EC more secure than RSA? (3, Informative)

Anonymous Coward | about 10 months ago | (#44818381)

Public key cryptography is based on mathematical operations which are easy to do but difficult to do in reverse. For example, it is easy to multiply two big prime numbers, but it is difficult to factorize the product. There are multiple such easy-difficult pairs. Currently none of the supposedly difficult problems has been proven to be difficult. It is just assumed that they are difficult because nobody has found an easy way, but people are working on making the difficult problem easier to solve, and advances in that regard weaken the associated cryptographic systems. Significant advances have been made in solving the difficult problem at the heart of RSA (but it's not publicly broken yet.) That's the reason for the recommendation to switch to a different easy-difficult pair for public key cryptography. The different key sizes are the result of the kinds of numbers which form the public and private keys in these different algorithms.

Re:Why is EC more secure than RSA? (1)

Anonymous Coward | about 10 months ago | (#44818393)

The bit size of the key and the bit measure of the security provided by the key are not the same thing. For symmetric cryptos like AES or Blowfish they are often somewhat similar (if there weren't any known cryptanalytic attacks they would be exactly similar), but that's because keys for symmetric cryptos can be chosen as random numbers. They don't have to have any additional structure at all. Public key cryptos are more complicated; they need to have a trapdoor function that makes it possible to encrypt data (but not decrypt) and verify signatures (but not create them) without knowing the private key. This means that the keys must have more structure in order to work with this trapdoor function (a pair of primes in the case of RSA, a point on an elliptic curve in the case of ECC), and more structure means less entropy which means that you need a larger key to get the same amount of security. Public key cryptos differ in how much larger the keys need to be in order to provide the same level of security as a symmetric crypto, and RSA is considerably worse than ECC in this regard. And as an added bonus, RSA operations are also slower to compute than ECC operations at similar levels of security. There are cryptos that are even worse, for example many of the candidates for post-quantum public key crypto need to have keys that are many megabytes large in order to provide the same level of security as, say, a 2048 bit RSA key.

TL;DR: ECC keys are smaller and faster than RSA keys of similar security because of the different structures they are required to have. That doesn't mean that ECC is intrinsically more secure, you can just increase the key size of RSA. But it is more secure for the same amount bandwidth and CPU time, and as we need more and more security to withstand brute force attacks, RSA keys, and in particular the amount of computation required to do RSA operations, becomes unreasonably large.

Re:Why is EC more secure than RSA? (4, Informative)

Anonymous Coward | about 10 months ago | (#44818431)

The discrete log problem on an elliptic curve is believed to be more computationally intensive than the discrete log problem in a ring of integers. For example, see http://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/S0025-5718-1987-0866109-5.pdf and http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=F220DD223483B78B72C9CE243A62ADD7?doi=10.1.1.39.4125&rep=rep1&type=pdf

Factoring integers versus Discrete Log in EC group (2)

betterunixthanunix (980855) | about 10 months ago | (#44818485)

The difference boils down to factoring integers versus computing discrete logarithms in elliptic curve groups. The best publicly known integer factorization algorithm is GNFS which runs in roughly O(2^(n^1/3)), whereas the best publicly known ECDLOG algorithm runs in O(2^(n^1/2)). That is why we need RSA keys that are so much larger than ECC keys.

That, of course, is a theoretical argument. In practice, there are other issues to consider. ECC has a lot of parameters and there are a lot of constraints on the curve you choose; this means there are a lot of things to get wrong. RSA is not technically secure on its own (and the construction used to make it secure is easy to get wrong), but related systems like Blum-Goldwasser (which is based on a related problem, the Quadratic Residuosity Problem) are and they have many fewer parameters. The code for such systems is also simpler, which makes it more straightforward to audit (and harder to hide backdoors).

Re:Why is EC more secure than RSA? (5, Interesting)

lordlod (458156) | about 10 months ago | (#44818785)

The elliptic-curve algorithm is much slower for future quantum based attacks. So it's future-proofing, which is required if you want your secrets to stay secret.

You could get similar results by adopting a 15000 bit RSA key... but that's getting rather large.

A paper with some classical and quantum time estimates, Elliptic-Curve vs RSA: http://arxiv.org/pdf/quant-ph/0301141v2.pdf [arxiv.org]

Not shown to be good (3, Insightful)

Anonymous Coward | about 10 months ago | (#44818193)

Why are people even asking if it's been backdoored? It's already established that no one can explain the constants. It hasn't been shown to not be backdoored. That's enough to prove beyond the shadow of a doubt that it's wrong. Arguing about whether the standard is compromised by mere incompetence or malice, isn't worth spending time on.

If you don't know something is done right, then that alone is irrefutable proof that it has been done wrong. Even if they're good constants.

Re:Not shown to be good (0)

Anonymous Coward | about 10 months ago | (#44818469)

Why are people even asking if it's been backdoored?

Because they are interested in whether the NSA might have access to all that stuff which already got encrypted with it.

Yes, now that the news is out, the obvious thing is to no longer use EC encryption, at least not with those constants. But that doesn't change the fact that it has been used to encrypt stuff, and you simply cannot change the past.

Re:Not shown to be good (2)

somersault (912633) | about 10 months ago | (#44818729)

It hasn't been shown to not be backdoored

You can't really prove that something doesn't have a back door without putting in enough resources to find all the back doors there could possibly be.. so that doesn't make much sense either.

Reference? (1)

LWATCDR (28044) | about 10 months ago | (#44818237)

" Now that the world received strong confirmation that the much more obscure and less widely used standard Dual_EC_DRBG was in fact an NSA undercover operation,"
What confirmation? Really I fear slashdot has become pure click bait.

Re:Reference? (5, Informative)

IamTheRealMike (537420) | about 10 months ago | (#44818273)

Sorry, I could have provided a link for that too. It was in the major Snowden story of last week that revealed the NSA was undermining public standards. The New York Times said this [nytimes.com] :

Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method.

Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology and later by the International Organization for Standardization, which has 163 countries as members.

Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

“Eventually, N.S.A. became the sole editor,” the memo says.

Although the NYT didn't explicitly name the bad standard, there's only one that fits the criteria given which is Dual_EC_DRBG.

Re:Reference? (4, Informative)

afidel (530433) | about 10 months ago | (#44818347)

Bruce Schneier talked about DRBG being a probable backdoor back in 2007 [schneier.com] .

Re:Reference? (0)

Anonymous Coward | about 10 months ago | (#44818441)

Apparently, "strong confirmation" now means "one person not understanding or being able to explain something."

Re:Reference? (0)

Anonymous Coward | about 10 months ago | (#44818697)

The Dual_EC_DRBG algorithms involve the use of constants. It is known there are magic numbers that can crack Dual_EC_DRBG. People don't know these magic numbers and deducing the values of the magic numbers from the constant is too hard. But if you control the standard, you can generate the constants and the magic numbers at the same time.

Replaced security with obscurity (3, Insightful)

Anonymous Coward | about 10 months ago | (#44818265)

The essence of what the NSA did, was to replace cryptographic security with security through obscurity. People who haven't found the back door yet don't know its there. Classic 'security via obscurity' that is the opposite of crypto.

Now everyone knows they're there, we need to replace them damn fast. Waiting for the backdoor to be verified is too late, by then bad actors (I mean ones other than General Alexander) could already have found it.

Replacing these takes time, and so the assumption should be they are vulnerable, because the NSA leaks show the NSA knows they are vulnerable, even if we don't quite know the micro detail of how, yet.

Open letter to the NSA (3, Funny)

aaaaaaargh! (1150173) | about 10 months ago | (#44818313)

Dear NSA,

Since I'm getting tired of these stories and it seems kind of unfair that you're getting all the heat recently, here is my suggestion how you could improve your PR image by doing something to our mutual benefit:

Please use your supercomputers for a few months to aggressively mine Bitcoins and Litecoins. That would make you (virtually) richer than you already are and free me and the rest of the world in future from annoying Bitcoin-mining stories.

If you like this idea, consider donating some Bitcoins to me. You know where to find me.

Thank you for your attention and best regards,

aaaaaaargh!

Re:Open letter to the NSA (1)

Anonymous Coward | about 10 months ago | (#44818349)

P.S.: Don't worry, I will only use them for recreational drug use and not to further damage the image of your agency.

Re:Open letter to the NSA (3, Funny)

Anonymous Coward | about 10 months ago | (#44818607)

They are ALL open letters to the NSA.

Re:Open letter to the NSA (1)

Boronx (228853) | about 10 months ago | (#44818649)

With their computing power, they could just create their own counterfeit bitcoins that would outvote the rest of market, effectively stealing everyone's coins.

secp256r1? That's the combo on my luggage! (1)

Anonymous Coward | about 10 months ago | (#44818327)

"secp256r1" just so happens to be the combination to my luggage.

I guess I should change that.

NSA/GCHQ does Man-in-middle attack on Google (0)

Anonymous Coward | about 10 months ago | (#44818401)

http://www.techdirt.com/articles/20130910/10470024468/flying-pig-nsa-is-running-man-middle-attacks-imitating-googles-servers.shtml

If you missed this one, one of the slides shows NSA & GCHQ has been impersonating Google and similar US services to avoid the need for an on-the-record request.

The old cypher machine vs your new internet? (1)

AHuxley (892839) | about 10 months ago | (#44818407)

The darker crypto history of the 1950-80's would point to long term weak export grade devices.
Why this generation of software and hardware would be allowed to be any different seems to have escaped a few people.
First the govs look at the private leadership, the firms, the brands - help stop communists....
If that fails, go for longterm staff with issues.
If that fails, set up a gov backed front company or standard out spending and undercutting any emerging private experts.
Looking back why did so few not see the lack of public gov interest after US crypto exports laws became more open (after public key cryptography?)
All the world was presented with was vague whispers of way too much unencrypted data with optical, internet and mobile phones...too expensive, too difficult..
The govs appetite never changed and funding in the past ~10 years was epic.

Justified paranoia (5, Insightful)

return 42 (459012) | about 10 months ago | (#44818465)

I think we are all going to have to be a lot more paranoid from now on about the public comments NIST gets on crypto standards. We can count on NSA to continue to try to mess with the standards, but they won't do it openly. They'll use proxies with no traceable connection to NSA. The crypto experts will have to examine these things a lot more carefully. Hanlon's razor [wikipedia.org] won't cut it anymore.

One direction street fuckcluster (0)

Anonymous Coward | about 10 months ago | (#44818477)

If they change these values, I bet it will not be possible to decrypt these text using the same algorithm. So future implementations will have to a) detect version b) use the weak bad-constant version for old text and the new version with good-constants. If theres no way to detect version, this will break a lot of text that will be "unreadable"?

Excellent Summary (1)

Bob9113 (14996) | about 10 months ago | (#44818551)

I was going to submit the same story. I'm glad I didn't; that summary is much better than what I had in mind. Nicely done, Unknown Lamer, IamTheRealMike, and any other editors who helped. Thank you for your effort on this important topic!

What about bitcoin? (0)

Anonymous Coward | about 10 months ago | (#44818573)

Do we think bitcoin is still safe then?

(There was some discussion a while ago about it being an NSA creation, as in this report http://groups.csail.mit.edu/mac/classes/6.805/articles/money/nsamint/nsamint.htm )

Could they have backdoored the protocol itself somehow? Or any of the libraries it relies on in implementation?

If so, does that mean there will come a day when they can just round up all the terrorists, drug dealers etc who have been using it for years ?

Not paranoid *enough* ? (5, Interesting)

pla (258480) | about 10 months ago | (#44818591)

I only see people discussing the first-level implications to privacy and security of the NSA having chosen parameters that lead to a somehow-weak curve. Except - That doesn't take any special NSA magic, they just cheated up front.

Such discussion completely overlooks the much bigger problem here, however - The NSA chose parameters that give a weaker curve. Parameters generated as the output of hashing them with SHA1.

The ability to choose parameters strongly suggests that the NSA has a way to produce input texts that yield a desired SHA1 hash. That takes special NSA magic, and should really count as the FP story here, not the far less impressive trick of stacking the deck in their favor.

Trusting Trust (1)

Anonymous Coward | about 10 months ago | (#44818693)

Ken Thompson's article "Reflections on Trusting Trust" seems to apply here.
http://cm.bell-labs.com/who/ken/trust.html

Even if the numbers are corrected, we have no guarantee that a lower-level system isn't undoing that work. Backdoors can (and probably do) exist in not only compilers, but in hardware. If this is the case, then broken encryption parameters are far less important. For example, git uses SHA1 for encryption. Assuming the scheme isn't already broken, it is likely possible to generate a collision with brute-force (especially if you need only one number). If some link in the git chain were thus broken, a replacement file with a backdoor payload could be injected (eg. in the confusion surrounding the gnu.org repos being hacked). As ken points out, once that initial injection is made (assuming it is of sufficent quality) it can be used to add anything to future compiled versions.

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...