Has the NSA already broken bitcoin?

[Walsoraj]

It is time for bitcoin to move to 512 bit. Or switch to Scrypt (plz baby jesus, no).

[01BTC10]

I'm reading this book right now. Pretty on topic. In this novel the NSA can decrypt any algorithm except one...

[anti-scam]

The NSA created Bitcoin and used ECDSA in it because they already had it broken.

This risk is already mitigated for any bitcoin address that has not been used for spending (i.e. its public key is not yet known).

Even if ECDSA is broken wide open, it doesn't really matter with respect to bitcoins that have been received at addresses that have never been used for spending, because the corresponding ECDSA public key is not known and cannot be determined without also breaking both RIPEMD160 and SHA256 simultaneously.

How would you spend the coins though?

[DeathAndTaxes]

The NSA created Bitcoin and used ECDSA in it because they already had it broken.

This risk is already mitigated for any bitcoin address that has not been used for spending (i.e. its public key is not yet known).

Even if ECDSA is broken wide open, it doesn't really matter with respect to bitcoins that have been received at addresses that have never been used for spending, because the corresponding ECDSA public key is not known and cannot be determined without also breaking both RIPEMD160 and SHA256 simultaneously.

How would you spend the coins though?

Carefully.

Imagine a scenario where current addresses are compromised.  The more likely scenario is some flaw is found which makes ECDSA "weakened".  As long as your public key is unknown you are immune.   Developers could come up with a new address type.  We will call existing addresses type 1 and the new stronger ones type 2.  Future clients would support both address types (backwards but not forwards compatibility).  Yes this would be a hard fork scenario but given the backwards compatibility it wouldn't be very controversial. 

You would need to transfer (spend) your coins from a type 1 address to a type 2 address and that tx could potentially be at risk.  A lot depends on how "broken" type 1 addresses are.  If on average it takes a high end hashing farm weeks to break a single private key well your funds would be "safe" long before the key could be compromised.   However lets assume a highly unlikely scenario where type 1 addresses can be broken quickly and cheaply once the public key is known.  Even then we are talking about a race condition so unless the attacker also had a significant fraction of the network they wouldn't be able to double spend successfully. 

However lets assume that is also true.  Pretty much a worst case scenario.  If your public key is already know you are SOL.  If it isn't you would need to make a "covert" transaction to a stronger address.  One option would be to mine it yourself, another option would be to send the "upgrade" tx securely directly to a mining pool you trust.  This could even be offered as a value added service by a pool (say 1% fee).  If you didn't mine it yourself you would need to trust the pool but you wouldn't need to trust the entire network.

[dree12]

Crazy conspiracy theory:

The NSA created Bitcoin and used ECDSA in it because they already had it broken. When Bitcoin reaches a certain market cap they will reveal this exploit, making everyone's coins irrevocably worthless and irreparably harming the public's perception of cryptocurrency.

Potentially reasonable action:

Maybe it's time to implement some post-quantum crypto in Bitcoin? It would be a propaganda victory at worst. Can the academic complex really be relied on as a canary in the coalmine for crypto breaks? What if the NSA is stealing the best young mathematicians and forcing them into NDAs? Things don't always stay the same. The only problem is that I think most post-quantum algorithms are patented.

Quantum crypto, although "perfect", relies on hardware rather than software. Consequently, it's impractical to use it in Bitcoin.

You are confusing quantum encryption (or quantum key sharing) with post-quantum cryptography. 
http://en.wikipedia.org/wiki/Post-quantum_cryptography

PQC are algorithms which are resistant to attack using quantum algorithms.  The major problem with these is they tend to have very large key and signature sizes.  Conservatively it would mean a 10x to 100x increase in bandwidth, and storage for Bitcoin. 

I stand corrected.

[Dabs]

If SHA2 is broken or ECDSA is broken, Satoshi Dice will go broke overnight, as well as all other casinos that re use addresses.

And almost all Provably Fair gaming will be rigged to death.

Those will be our warning signs.

Of course, if the NSA is smart, they would do this slowly ... ...

[cointoss]

To believe the the NSA has broken SHA-2 would be to believe that the NSA found something the entire rest of the world combined hasn't found for twenty years.

Why would the NSA or any other intelligence agency reveal that it had cracked/compromised an encryption technology? Wouldn't they keep it a secret as long as possible, to collect as much damaging information as possible, just as the allies did in WWII?

[DeathAndTaxes]

To believe the the NSA has broken SHA-2 would be to believe that the NSA found something the entire rest of the world combined hasn't found for twenty years.

Why would the NSA or any other intelligence agency reveal that it had cracked/compromised an encryption technology? Wouldn't they keep it a secret as long as possible, to collect as much damaging information as possible, just as the allies did in WWII?

They may not however SHA-2 has been in a use a long time and a vulnerability would leave financial and communication systems in a country vulnerable.  It would be highly risky for say the UK intelligence community to discover a flaw and then not warn UK companies. If agents for one state can discover the flaw so can another.  It would be like someone building a fortress out of TNT because they believe only they know it is explosive.  To my knowledge no governmental agency (or non-governmental entity) has published any warning about the security of SHA-2 even without disclosing a specific flaw/weakness.

It really isn't accurate to compare encryption in WWII (a niche application over a small period of time with no non-military usage) to SHA-2 (one of if not the most widely deployed algorithms in the world used over an extended period of time in pretty much every aspect of the global economy).  Wouldn't you agree?

[crazynoggin]

Highly highly HIGHLY unlikely that anyone has broken Bitcoin's algorithm. I would never say its impossible because the "impossible" has been achieved in the past, but I doubt you will ever see this impossible.

[hayek]

Remember this is still a government organization.

Yes, they have tons of funding. Do you think the DMV would improve if it suddenly received mountains of funding? Probably not. Most of the government work that requires a brain is contracted out in some way. It's not like the government is capable of attracting talented, intelligent people any other way.

If a private group or academia hasn't found a way to break it yet the NSA definitely hasn't.

[Carlton Banks]

One powerful common sense argument: if academic pursuit is not a powerful enough motivator to find algorithmic exploits or mathematical work-arounds, then the political class's fear of losing control of the most powerful social control mechanism should be more than enough to concentrate minds to the task. What would be the motive for such a convoluted action as developing and seeding a cryptographically governed peer-to-peer money network, with the explicit intention of destroying it at a future date? To make the destruction coincide with other planned earth shaking events, in the belief that it would help to drive home the sense of despair at as many stratifications of society as possible? Don't buy that, there's too much effort and too little benefit, as well as too much risk to the religion that is the modern consumerist monetary system. As it stands, the overall Bitcoin protocol and network is a massive threat to the status quo, there would have to be a plan to change so many aspects of it's mechanics in such quick succession, that I can't see how it makes any sense to introduce Bitcoin for publicly condemning an innovative concept or as an intermediate device to invoke some other deception. The coincidence of it's introduction is curious though, that Satoshi just so happened to be inspired with the right combinations of concepts by the 2007 economic crisis, and that he was already well enough informed about the history and importance of world currencies that he wanted his identity concealed. And that he successfully retained his hidden identity, despite all number of clues he could have littered the web with when he was innocently checking out the CypherPunks newsgroup, or looking at DigiCash and HashCash. This train of thought leads me to a conclusion I have often considered; that Satoshi is a non-US state asset, that the whole Bitcoin project is a genuine attempt by some well intentioned state to jam a spanner in the works of this whole Western governmental world domination agenda. The pieces fit in many ways, but also not in many others, the chief example being the lack of substantive action by the targets in such a scenario. The US and the EU states, as well as their various disparate puppets throughout the rest of the world, could have taken more decisive action by now, if nothing more than out of sheer diabolical desperation. Like much these days, the facts just don't quite fit the connecting story. Watch this space, I guess. All I know for sure is, we are somewhere approximating the right vantage point to see world changing events unfold.

[ronimacarroni]

Settle down guys.
The NSA is not trying to take down bitcoins.
There are already bitcoin businesses that pay taxes, geesh.

[TippingPoint]

http://www.nbcnews.com/id/52931694#.Uik20azLcpk

The NSA has bypassed or altogether cracked much of the digital encryption used by businesses and everyday Web users, according to reports in The New York Times, Britain's Guardian newspaper and the nonprofit news website ProPublica. The reports describe how the NSA invested billions of dollars since 2000 to make nearly everyone's secrets available for government consumption.

In doing so, the NSA built powerful supercomputers to break encryption codes and partnered with unnamed technology companies to insert "back doors" into their software, the reports said. Such a practice would give the government access to users' digital information before it was encrypted and sent over the Internet.

"Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it," Snowden said.

I do not believe that NSA has broken Bitcoin, but watch out for your other leaks.

Start here.
https://prism-break.org/

[OldGeek]

+1 for https://prism-break.org/

[mirthworm]

If someone (NSA, or anyone else) did break the encryption used by Bitcoin, or other cryptocurrencies, that would be all the more reason to switch to Primecoin!

[Ekaros]

Remember. This website is not safe.

Bitcoin probably is.


Just check the certificate in address bar:
The issuer:
CN = GeoTrust Global CA
O = GeoTrust Inc.
C = US


Oh US... I wonder if NSA has the keys...

The web security isn't really a hard thing to crack. You have handful of authorities and if you get to them whole chain unravels... There is points of weakness and USA government has access to those...

[Phinnaeus Gage]

This would be pretty easy to test. Just get a bunch of friends to start exchanging encrypted messages about bombing an embassy or govt office. If these douche-bags can break it, they'd be on you like white on rice.

This is an excellent idea! You go first.

[crazy_rabbit]

SHA-2 is an open algorithm and it uses as it is constants sequential prime cube roots as a form of "nothing up my sleeve numbers".  For someone to find a weakness or backdoor in SHA would be the equivalent of the nobel prize in cryptography.   Everyone who is anyone in the cryptography community has looked at SHA.  Not just everyone with a higher degree in mathematics, computer science, or cryptography in the last 20 years but foreign intelligence agencies and major financial institutions.    Nobody has found a flaw.  Not even an academical one.

To believe the the NSA has broken SHA-2 would be to believe that the NSA found something the entire rest of the world combined hasn't found for twenty years.  For the record SHA-3 is not yet approved for classified networks in the US, only SHA-2 is.  So that would mean the NSA is endangering national security by not declaring SHA-2 degraded.  

Anything is possible but occam's razor and all that.

Well said. There are many more cryptographic experts in the world than at the NSA. It's not a secret algorithm that's controlled by the NSA. It's in the public domain. Anyone can examine it. If you still think the NSA has a secret back door, then there's a good possibility you're a delusional paranoid shit head.

A) No need to be vulgar B) it is reason to double check that our implementation of SHA-256 is secure. There could be ways that different secure SHA-256 systems could become vulnerable, like for example- I'm now tempted to think Androids Random Number problem might have been deliberate. It exposed private keys, but maybe it's exposed so much more that the NSA has found valuable.

[Phinnaeus Gage]

SHA-2 is an open algorithm and it uses as its constants the sequential prime cube roots as a form of "nothing up my sleeve numbers".  For someone to find a weakness or backdoor in SHA would be the equivalent of the nobel prize in cryptography.   Everyone who is anyone in the cryptography community has looked at SHA-2.  Not just everyone with a higher degree in mathematics, computer science, or cryptography in the last 20 years but foreign intelligence agencies and major financial institutions.    Nobody has found a flaw, not even an theoretical one (a faster than brute force solution which requires so much energy/time as to be have no real world value).

To believe the the NSA has broken SHA-2 would be to believe that the NSA found something the entire rest of the world combined hasn't found for twenty years.  Also NIST still considers SHA-2 secure and prohibits the use of any other hashing algorithm (to include SHA-3 so far) in classified networks.  So that would mean the NSA is keeping a flaw/exploit from NIST compromising US national security. 

Anything is possible but occam's razor and all that.

Correct me if I'm wrong and misread sometime off one of news sites, but I understood that the NSA was able to intercept, then index all transmissions prior to the encryption process. To me, this made perfect sense when I read it, for then it wouldn't matter what SHA(?) is used, the information would already be mirrored and stored, somehow allowing the NSA to act as the man-in-the-middle.

[Luckybit]

Just read this disturbing article, based on recent leaks from Snowden:

http://www.propublica.org/article/the-nsas-secret-campaign-to-crack-undermine-internet-encryption

The article talks about the NSA responding to the rise in popularity of internet encryption by, among other things, deliberately weakening the algorithms in use to give themselves a back door to decrypt data. Bitcoin relies on SHA-256, originally created by the NSA. Perhaps there is a weakness that an organization with the resources of the NSA is able to exploit.

If so, that would explain why the major governments around the world seem to tolerate bitcoin. They know they can break it whenever they want. Preferable after the cartels and terrorists get comfortable and start relying on it.

I would say they probably have several ways of breaking Bitcoin but it would be top secret and not be used unless there is a war. It's not going to be used on criminals but if we get into a war with another country and that country thinks Bitcoins will be useful the NSA may have a few surprises.