Has the NSA already broken bitcoin?

[cypherdoc]

Legislation Seeks to Bar N.S.A. Tactic in Encryption

http://www.nytimes.com/2013/09/07/us/politics/legislation-seeks-to-bar-nsa-tactic-in-encryption.html

well that's good news.

the NSA is so full of hubris.  it doesn't understand that it's spying activities are ultimately going to hurt US corporations just like Huawei. 

once they start lying and hiding, everything starts to unravel.

this is why we need Bitcoin.

[niko]

ECDSA curve parameters in Bitcoin are standard ones, recommended by NIST. I wonder where they came from. Is there any rationale behind these particular constants, or they magically appeared out of nowhere, akin to dual_ec_drbg?

[theymos]

Interestingly, Bitcoin is one of the only users worldwide of the ECDSA curve called secp256k1, which is not a verifiably-random curve. Unlike SHA-256's constants, we don't know for sure where secp256k1's curve constants came from. This curve was specified by SECG, which is a group that includes NIST.

It's very unlikely that this curve is particularly weak in any way, but it may be prudent to offer users the option of using different crypto. (This can be done in a backward-compatible way.)

An USA certificate? Why isn't the admin getting a not-USA as fast as possible?

It doesn't matter which CA you use. The CA system is structured such that any CA can compromise sites using any other CA. All HTTPS is unsafe if any CA is compromised (if you trust the CA system blindly).

[TippingPoint]

I discussed this with Satoshi. There is no particular reason why secp256k1 is used. It just happened to be around at the time.

However it sounds like there's no real consensus that the k1 curve is really a terrible thing and indeed it may even be helpful in future as ECDSA verification is the primary CPU bottleneck for running a network node. So if Koblitz curves do indeed perform better we might end up grateful for that in future ...

highlighting added

[TippingPoint]

The NSA recommends Elliptic Curve Cryptography in an article on their site.
http://www.nsa.gov/business/programs/elliptic_curve.shtml

So we could debate the significance of that recommendation, in light of recent disclosures.

For current cryptographic purposes, an elliptic curve is a plane curve which consists of the points satisfying the equation

    y² = x³ + ax + b

along with a distinguished point at infinity, denoted ∞.  The entire security of ECC depends on the ability to compute a point multiplication and the inability to compute the multiplicand given the original and product points.

The hardest ECC scheme (publicly) broken to date had a 112-bit key for the prime field case and a 109-bit key for the binary field case. For the prime field case this was broken in July 2009 using a cluster of over 200 PlayStation 3 game consoles and could have been finished in 3.5 months using this cluster when running continuously. For the binary field case, it was broken in April 2004 using 2600 computers for 17 months.

Cryptographic experts have also expressed concerns that the National Security Agency has inserted a backdoor into at least one elliptic curve-based pseudo random generator. One analysis of the possible backdoor concluded that an adversary in posession of the algorithm's secret key could obtain encryption keys given only 32 bytes of ciphertext.
https://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[marcus_of_augustus]

The NSA recommends Elliptic Curve Cryptography in an article on their site.
http://www.nsa.gov/business/programs/elliptic_curve.shtml

For current cryptographic purposes, an elliptic curve is a plane curve which consists of the points satisfying the equation

    y^2 = x^3 + ax + b

along with a distinguished point at infinity, denoted ∞.  The entire security of ECC depends on the ability to compute a point multiplication and the inability to compute the multiplicand given the original and product points.
https://en.wikipedia.org/wiki/Elliptic_curve_cryptography

This is like Goldman Sachs recommending stocks to their clients they know they are going to be selling short ...

Basically any NSA recommendations have lost ALL credibility, and they are not going to get it back any time soon, if ever. They have not been dealing in good faith and ALL trust in any of their algos, methods, hardware, math, keys, certificates, etc ... everything NSA (inlc. google and other compromised commercial proxies)  are now suspect.

They should now be considered the the national INsecurity Agency.

[TippingPoint]

This is somewhat reminiscent of a scene from the movie Little Big Man

https://www.youtube.com/watch?v=xWGAdzn5_KU

Jack Crabb: General, you go down there.

General Custer: You're advising me to go into the Coulee?

Jack Crabb: Yes sir.

General Custer: There are no Indians there, I suppose.

Jack Crabb: I didn't say that. There are thousands of Indians down there. And when they get done with you, there won't be nothing left but a greasy spot. This ain't the Washite River, General, and them ain't helpless women and children waiting for you. They're Cheyenne brave, and Sioux. You go down there, General, if you've got the nerve.

General Custer: Still trying to outsmart me, aren't you, mule-skinner. You want me to think that you don't want me to go down there, but the subtle truth is you really *don't* want me to go down there!

[Carlton Banks]

all of this aside, I think if the NSA had the ability to disrupt the security model of Bitcoin's fundamentals, they would have done it by now. Unless it is just a massive project to crash the world economy, force everyone onto cryptocurrency and only then start pwning the private keys of people they don't like. In which case, why at all sow any seeds of doubt now? Not convinced.

[TippingPoint]

I think if the NSA had the ability to disrupt the security model of Bitcoin's fundamentals, they would have done it by now.

But doing so would have risked revealing their possession of backdoors to other forms of commonly-used computer security as well.  At least that would have been a concern until Snowden revealed the extent of their access, very recently.

from http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115

This is how it works: There are a bunch of constants -- fixed numbers -- in the standard used to define the algorithm's elliptic curve. These constants are listed in Appendix A of the NIST publication, but nowhere is it explained where they came from.

What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.

The researchers don't know what the secret numbers are. But because of the way the algorithm works, the person who produced the constants might know; he had the mathematical opportunity to produce the constants and the secret numbers in tandem.

If this story leaves you confused, join the club. I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard. It makes no sense as a trap door: It's public, and rather obvious. It makes no sense from an engineering perspective: It's too slow for anyone to willingly use it. And it makes no sense from a backwards-compatibility perspective: Swapping one random-number generator for another is easy.

I discussed this with Satoshi. There is no particular reason why secp256k1 is used. It just happened to be around at the time.

However it sounds like there's no real consensus that the k1 curve is really a terrible thing and indeed it may even be helpful in future as ECDSA verification is the primary CPU bottleneck for running a network node. So if Koblitz curves do indeed perform better we might end up grateful for that in future ...

highlighting added

http://bitcoin.org/en/alert/2013-08-11-android
We recently learned that a component of Android responsible for generating secure random numbers contains critical weaknesses, that render all Android wallets generated to date vulnerable to theft.

http://www.foxnews.com/politics/2013/09/08/nsa-can-access-most-smartphone-data-report-says/?test=latestnews#ixzz2eLU9Ne6Q
The U.S. National Security Agency is able to crack protective measures on iPhones, BlackBerry and Android devices, giving it access to users' data on all major smartphones, according to a report Sunday in German news weekly Der Spiegel.

The documents outline how, starting in May 2009, intelligence agents were unable to access some information on BlackBerry phones for about a year after the Canadian manufacturer began using a new method to compress the data.  After GCHQ (British) cracked that problem, too, analysts celebrated their achievement...

We know that NSA has been peeing in the pool.  Some of the accidents, errors, and oversights that we are learning about may be deliberate acts.

[Carlton Banks]

I think if the NSA had the ability to disrupt the security model of Bitcoin's fundamentals, they would have done it by now.

But doing so would have risked revealing their possession of backdoors to other forms of commonly-used computer security as well.  At least that would have been a concern until Snowden revealed the extent of their access, very recently.

Well, I still think that as per the Android PRNG issue, people have lost their pocket change as a sacrifice to everyone elses improved understanding of what is and isn't possible. Someone pointed out that the politics of currency isn't the NSA's raison d'etre, and that remains so until and if they are assigned a cryptocurrency takedown notice form the people who do make it their business. In the meantime, I'm glad that the discourse about the ECDSA vulnerabilities is playing out amongst the core development team, and if we need to change things, then change they will. It's not the ideal circumstances to have to alter the cryptographic underpinnings, but I don't know how else we could have expected such a change in perspective to play out. It could be worse than a single government source of (still not definitively a) compromise.

[TippingPoint]

Yes.  I agree that the core development team is in the best position to evaluate all of this, in the light of recent public disclosures. 

[vesperwillow]

Indeed. So, Edward Snowden already knew how effective NSA are at code-breaking and how pervasive their surveillance is, and yet he still managed to use e.snowden@lavabit.com to e-mail Glenn Greenwald for a Hong Kong meet, catch a plane to Hong Kong (the story goes that he only had a passport in his own name), and only once it was on every hourly newsreel did they start to try and apprehend him? You'd think that a highly paid contractor with high levels of access and clearance would have been getting watched as a matter of routine. Reality does not fit the story properly.

I can assure you folks aren't monitored quite like you'd imagine, not everyone at least.

Lots of discussion about broken crypto on here, some really good stuff with legitimacy too. Some of it is a little off the mark but close.

Best advice I will give, which is what I've been taught and live by: Presume none of your encryption matters, with regard to what you store and transmit.

Also, presume what's being suggested to use as the best encryption, is a bit of a double ruse. On one hand, some folks will look at that and think "they want me to use this.. because there's a way around it.. so I won't use it and will look at something else" ... which could also be equally compromised. The old salesman's technique, park the sedan next to the sports car and tell the guy all the reasons why he doesn't want the sports car. He'll buy the sports car.

[ageisp0lis]

I've written a speculative piece exploring the implications of this subject:
http://motherboard.vice.com/blog/what-do-the-latest-nsa-leaks-mean-for-bitcoin - What do the latest NSA leaks mean for Bitcoin?

[becoin]

all of this aside, I think if the NSA had the ability to disrupt the security model of Bitcoin's fundamentals, they would have done it by now. Unless it is just a massive project to crash the world economy, force everyone onto cryptocurrency and only then start pwning the private keys of people they don't like.

There is a very simple reason. Bitcoin was created to be a substitute for gold. The US government has a lot of computing power but run out of gold. They owe a lot of gold to other nations but will never pay it back in gold.

[marcus_of_augustus]

Indeed. So, Edward Snowden already knew how effective NSA are at code-breaking and how pervasive their surveillance is, and yet he still managed to use e.snowden@lavabit.com to e-mail Glenn Greenwald for a Hong Kong meet, catch a plane to Hong Kong (the story goes that he only had a passport in his own name), and only once it was on every hourly newsreel did they start to try and apprehend him? You'd think that a highly paid contractor with high levels of access and clearance would have been getting watched as a matter of routine. Reality does not fit the story properly.

I can assure you folks aren't monitored quite like you'd imagine, not everyone at least.

Lots of discussion about broken crypto on here, some really good stuff with legitimacy too. Some of it is a little off the mark but close.

Best advice I will give, which is what I've been taught and live by: Presume none of your encryption matters, with regard to what you store and transmit.

What do you know that the rest of us don't?

... and after all your hidden wisdoms all you can come up with is, "don't expect privacy in your communications" ... huh, that's it?

NSA has done to crypto-science the identical to what some weak minds and ethically challenged have done to climate science ... subverted it for political motivations.

In the final analysis, the massive databases they are generating have zero difference to the system of dossiers that Stasi built up ... they manage to delude themselves it is because they have 'protections' about when the dossiers are allowed to be pulled.

The problem is not when/who gets to pull the dossier on whomever, it is the fact that they even exist in the first place. Until the databases are destroyed or corrupted beyond usefulness we are living in a Stasi state ...

[vesperwillow]

What do you know that the rest of us don't?

... and after all your hidden wisdoms all you can come up with is, "don't expect privacy in your communications" ... huh, that's it?

If you're expecting folks to just come out and say they work for various departments and this is what they're basing their knowledge/experience on, I doubt you'll ever see that answer. I wish I could help you more. I'm sure many of us here wish they could do more.

The problem is not when/who gets to pull the dossier on whomever, it is the fact that they even exist in the first place. Until the databases are destroyed or corrupted beyond usefulness we are living in a Stasi state ...

Absolutely agree. This is just the tip of the green stem in the corner of the field. The briar has yet to fully engulf it, but it will; it's going to be far worse. Not necessarily in our lifetime, it's been about 100 years in the making.

If folks do enough research they'll find pieces of the puzzle and can loosely see that over the past century and a half,  'idiocy' of the US political system, and how a lot of international relations have panned out,  was always planned to look like a circus spectacle, all the  while pulling off one of the greatest slights of hand of all present history. This isn't even conspiracy talk from the looney bin.. I've trolled this forum, and many others, and lots of people have pieces to the puzzle, some have put a few of them together. The reality is most don't realize the big picture, everyone is caught up in small political wars and finger pointing.

Some folks would say Orwel's 1984 was a great novel. Others would say, it was the subtle leaking of a greater plan. Those who understood and heeded the warning signs would know what to expect, and if desired, when to leave.

Zoom out, zoom really far out, and look at the big picture. This doesn't necessarily help this discussion, it's not meant to be the words of an oracle. I just hope it piques interest and gets people to dig. If folks are really curious, and some of you are good at digging, I suggest continue digging.

[marcus_of_augustus]

Why can't you just tell us what the big picture is you that are seeing? 

[moni3z]

Schneier has been emphatically telling whoever will listen lately to avoid elliptic-curve crypto engineering, or to increase the key sizes, due to math tricks involved he believes are probably ripe for mathematical breakthroughs. Most ECC is patented anyways by Certicom and requires licensing. The NSA has been pushing ECC lately as well in their Suite B protection which is probably Suite (B)ackdoored so they can spoof signatures and handshakes.

Still I doubt the NSA would want anything to do with bitcoin besides use it to pay their own spies in Iran and Russia."Comrade, here is your 1000BTC for political blackmail purposes. Please get picture of Putin wearing lipstick passed out drunk in a dress".

[niko]

What do you know that the rest of us don't?

... and after all your hidden wisdoms all you can come up with is, "don't expect privacy in your communications" ... huh, that's it?

If you're expecting folks to just come out and say they work for various departments and this is what they're basing their knowledge/experience on, I doubt you'll ever see that answer. I wish I could help you more. I'm sure many of us here wish they could do more.

Your signature fits perfectly the self-portrait you just painted.

If I've been helpful or have made your day somehow and you want to give back, donations of all amounts are kindly accepted:BTC 15gmyvVQdvbz1RcAKqbpq6KTxHGxaJLY8p LTC LLNjd2njEeLQWuPxhvedBapky8grpMNjEBFTC 6qgo29SUvfNnXR5aMDvq9UySfa2eovJsBc DGC DHWWHx9Ac95p3izn3uKW1LZr5MzMw9XPPX

[moni3z]

I also don't buy the 'NSA recommends this so it must be a trick to get us to use something else!'. Whatever NIST recommendations are is what is put into commercial software/hardware blackboxes.