Has the NSA already broken bitcoin?

[wormbog]

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.

[joecascio]

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.

[Taras]

I don't believe it... I could never think of any sci-fi-ass machine capable of cracking SHA256. Of course with Snowden's verification, how could it be false? I'm horrified. Are our savings subject to overnight destruction?

2014 edit - No, they aren't. Go home.

[davidpbrown]

meh.. Snowden himself suggested encryption used properly does work. That article is alluding to obvious hacking and the illusion of security.. https and pwning of Skype; M$; VPNs and third parties etc - requiring providers to allow a backdoor to information they hold.

[qxzn]

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.

can anyone think of a lower risk way to test...?

[DeathAndTaxes]

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.

SHA is not an encryption protocol.  You can't encrypt messages with SHA.

[dree12]

No, there is no backdoor.

The SHA-2 functions use the square roots and cube roots of small primes.

See: http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

[davidpbrown]

Better article here.. http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=all&_r=0

and then the Guardian.. http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security

[DeathAndTaxes]

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.

[joecascio]

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.

[casascius]

I believe bitcoin is vulnerable to a well-funded 51% attack, for no other reason than the awareness that the productivity of ASICs scales more exponentially than linearly as funding increases.

I believe bitcoin would quickly recover from a successful 51% attack as "proof of stake tiebreaker" is introduced as a remedy.  For example, a remedy that would bring instant results might be a new rule that allows known entities as well as past miners (via their coinbase keys) to publish endorsement signatures on blocks they see/create.  These blocks are given a much greater weight than ones without such a signature.  Entities doing a good job of endorsing blocks would have their signatures weighted more, and any entities creating disruptive signatures (or at least their public keys) would quickly be banished by the community.  The disruption would be days, and at the most, weeks.  After the disrtuption, Bitcoin will be permanently stronger.

As an end unto itself, engaging in a 51% attack would be so futile as to not be worth it.  As always, a 51% attack constitutes nothing more than the ability to prevent transactions from confirming as well as reversing them... not stealing or creating bitcoins (other than via mining).

But being able to cause the days/weeks disruption at a time of one's choosing may be a very valuable tool for a state's (or banking industry) arsenal.  There's value in temporarily disrupting the network to somebody, and that value is in the eye of the beholder.

To that end, that's where I'd think of what the NSA (or any other state actor) may have put effort.

The question is, does someone, somewhere, have a lot of dormant mining power sitting there just in case?  I say it's safe to assume yes, and it's just a matter of when will it be worth it for them to use that to cause a temporary disruption to Bitcoin.  If you have only got one chance to rock the world of Bitcoin, it's reaosnable to assume you're going to want to time it for maximum value.

Even if so, I don't think anyone's bitcoins sitting in safe wallets (consisting of properly-generated properly-stored offline addresses that have never been used for sending payments) are at risk... only thing at risk is the temporary loss in confidence and in turn the USD/BTC value if/when such an entity decides to pull off such an attack.

[Alpaca Bob]

"Dual_EC_DRBG or Dual Elliptic Curve Deterministic Random Bit Generator[1] is a controversial pseudorandom number generator (PRNG) designed and published by the National Security Agency. It is based on the elliptic curve discrete logarithm problem (ECDLP) and is one of the four PRNGs standardized in the NIST Special Publication 800-90. Shortly after the NIST publication, it was suggested that the RNG could be a kleptographic NSA backdoor."

(...)

"In 2013, the New York Times published that "'classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency.'"

Source: http://en.wikipedia.org/wiki/Dual_EC_DRBG

I unfortunately have little technical/under the hood-ish know-how of bitcoin, but is this Dual Elliptic Curve stuff not exactly what bitcoin relies on in some way or another?..

[dree12]

"Dual_EC_DRBG or Dual Elliptic Curve Deterministic Random Bit Generator[1] is a controversial pseudorandom number generator (PRNG) designed and published by the National Security Agency. It is based on the elliptic curve discrete logarithm problem (ECDLP) and is one of the four PRNGs standardized in the NIST Special Publication 800-90. Shortly after the NIST publication, it was suggested that the RNG could be a kleptographic NSA backdoor."

(...)

"In 2013, the New York Times published that "'classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency.'"

Source: http://en.wikipedia.org/wiki/Dual_EC_DRBG

I unfortunately have little technical/under the hood-ish know-how of bitcoin, but is this Dual Elliptic Curve stuff not exactly what bitcoin relies on in some way or another?..

Random numbers are only used for key generation, and the DEC algorithm is not used for that in most clients.

[anti-scam]

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.

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

[casascius]

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.

[DeathAndTaxes]

"Dual_EC_DRBG or Dual Elliptic Curve Deterministic Random Bit Generator[1] is a controversial pseudorandom number generator (PRNG) designed and published by the National Security Agency. It is based on the elliptic curve discrete logarithm problem (ECDLP) and is one of the four PRNGs standardized in the NIST Special Publication 800-90. Shortly after the NIST publication, it was suggested that the RNG could be a kleptographic NSA backdoor."

(...)

"In 2013, the New York Times published that "'classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency.'"

Source: http://en.wikipedia.org/wiki/Dual_EC_DRBG

I unfortunately have little technical/under the hood-ish know-how of bitcoin, but is this Dual Elliptic Curve stuff not exactly what bitcoin relies on in some way or another?..

Simple answer is no it isn't used by Bitcoin at all.  However it does provide a very good counter example of how difficulty it is to hide backdoors in public algorithms.  The algorithm noted is rather rare, I don't know of a single widespread usage of it and even still a cryptographer found and reported a vulnerability less than a year later.  SHA-2 has been around 20 years and is conservatively millions times more widespread and subject to much more peer review and cryptoanalysis and nobody has found even a theoretical flaw yet.

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

The use of two hashing algorithms created at different times by different entities provides a significant defense in depth.   

The irony is that many alt-coins claim utility because they are an insurance policy if Bitcoin is comproimsed however since they also use ECDSA, RIPEMD-160 and SHA-256 any compromise of Bitcoin (not matter how unlikely) would render those altcoins just as compromised.

[anti-scam]

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.

Post-quantum crypto, not quantum crypto

[DeathAndTaxes]

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.