Bitcoin and the NSA

[samablog]

I posted the following on my blog, but I figured that people here would be able to point me to the answers more easily.  I apologize in advance if this has been discusses ad nauseam already.


Bitcoin utilizes something called elliptical curve encryption in its processes. I remember back in the day, attending Bob Hettinga’s “Digital Commerce Society of Boston” meetings, and hearing this discussed then That was about 15 years ago now. I’m not a cryptographer, but from what I remember, elliptical curve encryption offered extraordinarily strong encryption without requiring an extraordinary amount of processing power. It was envisioned at the time that this method of encryption would be extremely useful in mobile devices.

My question is simple: Has the NSA broken elliptical curve encryption yet? And if they have, would they have it within their power to destroy Bitcoin?

If the NSA has broken elliptical curve encryption, they surely wouldn’t announce such a capability. But it does mean that if the US Federal Government wanted to, they could crush Bitcoin in seconds flat, inflating it beyond measure. By doing so, they would announce to the world that they can break elliptical curve encryption, but maybe that would be worth doing in certain circumstances.

But put aside the NSA for a moment. Theoretically, there is also what I would call the MC Frontalot problem as well. In his song, Secrets From The Future, he writes:

You can’t hide secrets from the future with math.
You can try, but I bet that in the future they laugh
at the half-assed schemes and algorithms amassed
to enforce cryptographs in the past.

The point being, that even the best cryptography today is likely to be broken, even by brute force, at some point in the future. So my question is, how is the Bitcoin development community planning to work around the MC Frontalot problem? IPhysical currency gets recalled and re-issued with new anti-counterfeiting measures added periodically, but what's the equivalent for Bitcoin?  I assume somebody has already asked this question, but I thought I’d ask it here in any event.

[1714920000]

1714920000

[1714920000]

1714920000

[gusti]

I'm not a cryptography expert  at all, but I understand that is easy to change btc in the protocol, from sha256 to whatever other technology, if the old one happens to be cracked.

[kgo]

No the NSA hasn't broken it.  In fact, ECC is the only public key algorithm that they've cleared for use by the government itself to secure top secret documents.

http://www.nsa.gov/ia/programs/suiteb_cryptography/

[Stephen Gornick]

Related discussion here:
  http://bitcointalk.org/index.php?topic=2699.0

[samablog]

Thanks guys

[MoonShadow]

My question is simple: Has the NSA broken elliptical curve encryption yet?

Unknowable.

And if they have, would they have it within their power to destroy Bitcoin?

No.  At best, they would have the power to steal bitcoins from individual accounts.  Both the merkle tree inside of the blocks, and the blockchain itself, uses secure hashing, not public/private keypair encryption.  So if SHA256 (the hash that Bitcoin presently uses) were broken in the future, this would not expose the individual account balances of all users, but only those of the most recent blocks in the blockchain.  Likewise, if the public/private keypair encryption that Bitcoin presently uses was broken, this would expose the accounts of individual users that the attacker was willing to commit resources to break open; but would not expose the blockchain itself to attack, nor the whole of the Bitcoin user base.  If both are broken at the same time, we would be in trouble.  However, if either is broken (or even appears to be subject to breaking in the near future) then each is modular and can be replaced with another method within the same class of encryption.  Bitcoin is not 'married' to elliptical curve encryption, per se.

Also, the hashing methods used for the blockchain can be different than those used for the merkle tree, or even two different secure hashing methods used for each block; because the blockchain is currently secured using a SHA256 hash of a SHA256 hash of the block's header.  Which would further seperate sections of Bitcoin from the risk of any one part of the system being broken.

[Gavin Andresen]

To steal your bitcoins by breaking crypto (as opposed to getting your private key), somebody would have to:

1. Break RIPEMD160.  Because your bitcoin address is a RIPEMD160 hash...  AND
2. Break SHA256.  Because your bitcoin address is a RIPEMD160 hash of the SHA256 hash... AND
3. Break the ECDSA elliptic curve encryption signature algorithm, to figure out the private key that corresponds to the public key that they got from breaking (1) and (2).

That's assuming that you don't re-use bitcoin receiving addresses (your public key is revealed the first time you spend coins that were sent to that address).  If you do re-use the same receiving address, then they just need (3).

I don't spend any time worrying about whether or not the NSA (or anybody else) can break ECDSA.

[MoonShadow]

To steal your bitcoins by breaking crypto (as opposed to getting your private key), somebody would have to:

1. Break RIPEMD160.  Because your bitcoin address is a RIPEMD160 hash...  AND
2. Break SHA256.  Because your bitcoin address is a RIPEMD160 hash of the SHA256 hash... AND
3. Break the ECDSA elliptic curve encryption algorithm, to figure out the private key that corresponds to the public key that they got from breaking (1) and (2).

Thank you for clearing this up.

[ByteCoin]

They wouldn't have to break RIPEMD160. If they broke SHA256 suitably they could create blocks of arbitrarily high difficulty with very little effort which would enable them to take control of the block chain.
When you send your transaction to spend the coins, you reveal your public key for which they would then solve the discrete logarithm problem to find your secret key. They would ensure that your transaction was never included in a block but their transaction spending your money could confirm very quickly.
I suppose that if you never try to spend the money, they can't steal it directly but they could inflate the value away.

ByteCoin

[MoonShadow]

They wouldn't have to break RIPEMD160. If they broke SHA256 suitably they could create blocks of arbitrarily high difficulty with very little effort which would enable them to take control of the block chain.

This would be a good reason to change one of the SHA256 hashings of the block headers to a completely different secure hashing algorithem now, preempting this possibility completely.

[Phinnaeus Gage]

Bump!

[MysteryMiner]

If NSA can break the crypto, the same can both russians and chinese and probably dozens of other countries. All spy agencies are compromised by spies. I mean by double agent spies, who pass NSA secrets to russians and chinese and vice versa. If you or NSA think that they have no moles or people leaking secrets of all magnitudes to foreigners, you are simply naive.

If any agency are capable to do that, that news will surface eventually. As result my conclusion is that the crypto is not broken by anybody.

[goodlord666]

Why would anybody like the NSA want to destroy Bitcoin? They're probably as intrigued by it as us and would rather want it as secure as us.

[stevegee58]

Why would anybody like the NSA want to destroy Bitcoin? They're probably as intrigued by it as us and would rather want it as secure as us.

Read "A Lodging of Wayfaring Men" for your answer.

[cypherdoc]

the fact that the article published a map of the facility makes it highly suspect to me.  perhaps they're playing Ben's game of perception management.

[rjk]

the fact that the article published a map of the facility makes it highly suspect to me.  perhaps they're playing Ben's game of perception management.

+1, or else they figured that it couldn't hurt in these days of satellite imagery.

[goodlord666]

Why would anybody like the NSA want to destroy Bitcoin? They're probably as intrigued by it as us and would rather want it as secure as us.

Read "A Lodging of Wayfaring Men" for your answer.

Thanks, but no.

[triplehelix]

i don't understand the line of thinking.  the US government could for all intents and purposes crush bitcoin with less funds, just manipulating the market and such, then with the funds required to build the computer hardware, man hour compensation, and electric consumption required to break encryption and use it in any way with enough breadth to damage bitcoin.

[rjk]

i don't understand the line of thinking.  the US government could for all intents and purposes crush bitcoin with less funds, just manipulating the market and such, then with the funds required to build the computer hardware, man hour compensation, and electric consumption required to break encryption and use it in any way with enough breadth to damage bitcoin.

The line of thinking is that this hardware is targeted at AES, not SHA256, and as far as we know has nothing to do with Bitcoin at all. Not sure why OP thinks it is related.

[triplehelix]

i don't understand the line of thinking.  the US government could for all intents and purposes crush bitcoin with less funds, just manipulating the market and such, then with the funds required to build the computer hardware, man hour compensation, and electric consumption required to break encryption and use it in any way with enough breadth to damage bitcoin.

The line of thinking is that this hardware is targeted at AES, not SHA256, and as far as we know has nothing to do with Bitcoin at all. Not sure why OP thinks it is related.

i would say its pretty obvious that the government and its agencies are far far more interested in communications than bitcoin.  we might all love bitcoin, but there is a serious case of over inflating its importance to organizations outside our relatively small group.

[stevegee58]

It's reasonable to assume that if any alternate currency were to really become popular it would get the negative attention of TPTB.  Think about it: one day the USG starts to notice an unexplainable drop in revenue.  They start digging to find out the cause of this anomaly and find a growing underground economy with a non-USD currency.

For crypto currencies, agencies with lots of computing power would become heavily involved in the effort to try to disrupt or destroy it.

It's what would happen if BTC really became mainstream.

[triplehelix]

It's reasonable to assume that if any alternate currency were to really become popular it would get the negative attention of TPTB.  Think about it: one day the USG starts to notice an unexplainable drop in revenue.  They start digging to find out the cause of this anomaly and find a growing underground economy with a non-USD currency.

For crypto currencies, agencies with lots of computing power would become heavily involved in the effort to try to disrupt or destroy it.

It's what would happen if BTC really became mainstream.

i fully acknowledge that there may at some point be some negative attention given to bitcoin from the US government.  i laugh at the idea that at this point, right now, bitcoin is seen as such a threat that billions are invested to "crush it".

[rjk]

It's reasonable to assume that if any alternate currency were to really become popular it would get the negative attention of TPTB.  Think about it: one day the USG starts to notice an unexplainable drop in revenue.  They start digging to find out the cause of this anomaly and find a growing underground economy with a non-USD currency.

For crypto currencies, agencies with lots of computing power would become heavily involved in the effort to try to disrupt or destroy it.

It's what would happen if BTC really became mainstream.

i fully acknowledge that there may at some point be some negative attention given to bitcoin from the US government.  i laugh at the idea that at this point, right now, bitcoin is seen as such a threat that billions are invested to "crush it".

+1

[stevegee58]

i fully acknowledge that there may at some point be some negative attention given to bitcoin from the US government.  i laugh at the idea that at this point, right now, bitcoin is seen as such a threat that billions are invested to "crush it".

Or the USG has been anticipating this and is seeking to smother it in the cradle.  (BTW I don't think they're that good at planning.)

[herzmeister]

guess they'll be building large rainbow tables of everything they'll ever intercept. that will mean to avoid plain text offenders at all cost. ssl needs to be upgraded too right?

[ptshamrock]

Why would anybody like the NSA want to destroy Bitcoin? They're probably as intrigued by it as us and would rather want it as secure as us.

Read "A Lodging of Wayfaring Men" for your answer.

yeah man   awesome read!

[Gleb Gamow]

I think the NSA has somehow implanted a chip in bitcoiners designed to activate when they become the hot topic of the day.