Why bitcoin isn't going to make it: The National Security Agency

[kjj]

Schneier has commented on this plenty of times.  You should go read his thoughts, but if I recall correctly, he thinks that this isn't the 70s any more.

Once upon a time, the NSA was so far ahead of everyone else that it was like they had alien technology.  Over the decades, cryptography research has spread out.  The NSA still tries to recruit the best, but not everyone is interested or available.  The NSA may still be the global leader, and very likely is, but now they are merely years ahead of the game, not decades.

Also, the techniques have changed.  Both new systems and new attacks are devised by teams, typically spread across many institutions.  And systems are built to be resistant even to hypothetical impractical attacks.  Attack progress comes in small parts, chopping off a few bits here and there, taking a 2²⁵⁶ attack down to 2²³⁷ or whatever.  New systems are devised in the decades between the very impossible attack and the merely totally impossible one.

Also, the NSA doesn't really need to do crazy secret stuff any more.  High security systems for military and government is mostly about good technique and good management (key management in particular).  If anyone can break our stuff, or anyone's stuff, it means that they have developed whole new branches of mathematics, and done so in secret.

[DeathAndTaxes]

kjj nailed it.  The 21st century is far more open (and getting more open/decentralized everyday) then the 20th century was.  Today finding even an academic flaw in say sHA-256 is the equivalent of winning the nobel prize in cryptography.  It instantly elevates you to the elites of the field.  SHA-256 has been extensively studied not just by countless governmental and corporate researchers but tens of thousands of academics all over the world.   The idea that the NSA has a "lock" on cryptography is ... well sad.  The irony is that the people claiming to be anti-state end up spreading so much FUD about the invincibility of the state that they end up being the biggest supporters of the state.  

Is the NSA doing crypto-analysis of modern cryptographic functions?  Sure but it is no longer a the largest area of research. Modern cryptography is an amazingly well built "lock".  Breaking these modern locks is increasingly difficulty expensive and time consuming. However at the same time despite having access to these superior locks, many people still leave the window unlocked (sideband vulnerabilities), or hide the key under the mat (poor key security).   The ROI% on going "around" the lock pays a much higher dividend then going through the lock and that is where the big dollars are being spent. 

Even with a large budget the NSA does have finite resources and is limited by real world constraints like energy density, and computing efficiency.   Even if NSA did (after billions and decades) "break" SHA-256 most systems will no longer be using it in a decade or two.  A huge amount of resources spent on something which has an amazingly short shelf life.  The NSA does a lot of defensive cryptanalysis.  It isn't trying break SHA-256 so much as make sure it can't be broken.  The NSA knows that US interests will use SHA-256 for the next decade or so.  It is looking for flaws that others might also be looking for so it can advise other agencies on the relative security and make recommendations on upgrades.

Lets look at SHA-1 as an example.  SHA-1 is considered cryptographically degraded.  It shouldn't be used for any new systems and existing systems should migrate to new ciphers as quickly as possible.  Still even if bitcoin only used SHA-1 (vs SHA-256 & RIPEMD-160 double hash) it likely would be secure from most attack even today.

http://en.wikipedia.org/wiki/SHA-1#Attacks

The estimated cost to perform a preimage attack on a SHA-1 hash is on the order of $3M per collision.  Given the average value of an active Bitcoin address is <$3M it would cost more to exploit the known vulnerability and produce an alternative public/private keypair which could spend from a Bitcoin address then the address would be worth.

this vulnerability was first outlined in academic papers back in 2005 and is a carryover from the vulnerability known to exist in SHA0 since 1998. Should Bitcoin drop SHA-256 and go to the less secure SHA-1? No but it does give us some insight into how well built these locks are and how long it takes to develop a theoretical vulnerability into something which can be exploited in the real world. Over a decade of cryptanalysis later and the only real world attack vector involves millions of dollars worth of computing time.  I would point out the all powerful NSA wasn't able to prevent the publishing of any of these papers outlining flaws in this and other algorithms.  Even if at one time only the NSA knew about this vulnerability they weren't able to keep a lid on it.  Others found out and were able to move to more secure algorithms.

[BitcoinINV]

I don't understand cryptography lol but I understand open source, what's to stop someone from making something entirely new that NSA can't touch? While I can understand the fear I am also very skeptical because a lot of the people who work in government are, lets face it, old white people who couldn't open up a word document without any help.

Never underestimate the intellectual capacity of an angry child with an internet connection and a keyboard.

 Thats the damn truth lol

[Ente]

Thank you, kjj and DnT,
for your well written explanations and patience! :-)

Even though this question will come back again and again, I (have to) believe many people learned from it! :-)

People, I highly suggest you read through a mainstream cryptography book.
It actually is fun, mindboggling, and really opens up a whole new world of understanding! The principles you will learn are a universal concept! No, you don't have to read/write/understand code for this, it *is* an entertaining and relaxed read!

Ente

[axus]

Without knowing anything, I'm certain NSA has had the equivalent of Avalon/BFL ASICS for years.  They probably have a plan laid out for 51% attack, if such a thing were needed.  But, it hasn't been necessary.

CIA and others probably would like to use Bitcoin for anonymous payment, so they don't need to have all those shell companies.  But the total value of all Bitcoins isn't worth enough, yet.  Probably they are buying/mining some right now for the future. 

Thinking from other perspectives, it's almost certain that Chinese government will take over Avalon technology.  Bitcoin is too small now, but when it becomes big enough to matter, they will seize control of it and mass produce their own.  So, I hope BFL and other companies succeed so that the "power" doesn't belong to one country.

[niko]

They created SHA256 and they likely have a hold on ECDSA. Historically, they have had a hold on cryptography by over 20 years in future technology. They usurp almost all cryptography talent and beyond before the private sector can even touch it. My gut tells me the NSA already has exploits into all the technologies bitcoin utilizes. I think we're fucked for now. Cryptocurrency may not die as an idea but bitcoin may fall before it can truly succeed. 

Can you provide two or three examples where NSA completely broke two major crypto primitives comparable to SHA256 and ECDSA?

[Littleshop]

Without knowing anything, I'm certain NSA has had the equivalent of Avalon/BFL ASICS for years.  They probably have a plan laid out for 51% attack, if such a thing were needed.  But, it hasn't been necessary.

CIA and others probably would like to use Bitcoin for anonymous payment, so they don't need to have all those shell companies.  But the total value of all Bitcoins isn't worth enough, yet.  Probably they are buying/mining some right now for the future. 

Thinking from other perspectives, it's almost certain that Chinese government will take over Avalon technology.  Bitcoin is too small now, but when it becomes big enough to matter, they will seize control of it and mass produce their own.  So, I hope BFL and other companies succeed so that the "power" doesn't belong to one country.

Doubtful.  They have a huge signal processing, pattern matching and storage network.  A network so big that it is causing power delivery issues.  Why would they try to crack something that is uncrackable.  The NSA is one of the smarter three letter agencies out there and probably LOVES bitcoin because of the open block chain. 

If bitcoin is on the NSA rader,  the NSA could know more about the blockchain contents then other single entity or person.

[Boussac]

@Fool
This is yet another FUD thread.
If you knew how ECDSA works, you would realize that the sentence "a hold on ECDSA" does not make sense.
Go search for SHA256 collisions and come back when you found one: I'd be interested even though that would still not mean an exploitable hack per se.

[Killdozer]

Guys, cmon, this is a very thin trolling 
Just read the first post and think about it 

[ralree]

They created SHA256 and they likely have a hold on ECDSA. Historically, they have had a hold on cryptography by over 20 years in future technology. They usurp almost all cryptography talent and beyond before the private sector can even touch it. My gut tells me the NSA already has exploits into all the technologies bitcoin utilizes. I think we're fucked for now. Cryptocurrency may not die as an idea but bitcoin may fall before it can truly succeed.

In order for cryptocurrency to work we need a thriving, free civilization with no hegemony that usurps most R&D and capital. We need the latest and greatest cryptography and we just don't have it.

Bitcoin as it stands may just turn into a fringe money laundering operation for the CIA and NSA before it no longer serves its purpose.

I'm glad you cited so many sources for this information.  It's annoying when people just make random claims because of baseless fear. 

[ralree]

Guys, cmon, this is a very thin trolling 
Just read the first post and think about it 

Your avatar image is out of date - should say $27.

[CurbsideProphet]

I suppose it's plausible but unlikely.  First, SHA256 and ECDSA is not unique to Bitcoin, coming out and openly cracking it would compromise financial systems around the world.  With a money supply equivalent of roughly $250-$300 million, Bitcoin is still peanuts and not a perceived threat.  At least not on the level to force some government agency to take this type of step.  It's easier to orchestrate a 51% attack anyway.  That would take Bitcoin down solely, and not damage the encryption itself (that is used widely).

The only reason I say it's plausible is because of history.  Just because a code is broken doesn't mean it will necessarily be known right away.  The Enigma cipher was broken by Poland in 1932.  They didn't share that news with the world until 7 years later and there was a world war going on for gods sake.  So yeah I suppose it's plausible but highly unlikely.

[vdragon]

First, this network is small (not so many users). Second, it doesnt operate with a lot of money/value. Third, CIA might also benefit from it

[Matthew N. Wright]

Third, CIA might also benefit from it

This. Why does anyone think "anonymous" is anyone but the CIA? Why does anyone think Tor was created by hackers when it's major funding is provided continuously by the US government (the FBI if I recall correctly)? Why would anyone think that Bitcoin is anything but awesome for what the CIA does-- which is to pretend that there are bad guys doing what it is that they did themselves.

[deeplink]

The NSA still tries to recruit the best, but not everyone is interested or available.

Yes I heard their recruiting interviews don't always work out.

http://www.youtube.com/watch?v=l8rQNdBmPek

[Aseras]

No government is going to publicize they have broken an encryption algorithm. Remember the Enigma machines? They broke that and relied on it for quite a while and went at all lengths to keep it a secret.

[Sukrim]

The enigma wasn't used in banking applications...

[rebuilder]

No government is going to publicize they have broken an encryption algorithm. Remember the Enigma machines? They broke that and relied on it for quite a while and went at all lengths to keep it a secret.

That doesn't mean they have broken, or can break modern crypto.

[tvbcof]

On the other hand if you have the means to break SHA256(SHA256)) (=mining) and ECDSA (=Bitcoin private keys), why waste that on Bitcoin?
Don't get me wrong, maybe Bitcoin becomes a big threat for the establishment in the future - but there are far more valuable targets.

Another thing to consider:
Not every great cryptographer is from the USA, there are other countries with smart people out there as well... of course NSA will be ahead a bit with cryptoanalysis (I read recently an interesting article about Bitcoin mining with SAT solvers) and breaking codes just because of the ressources they have - still that doesn't mean they can magically "break" mathematics. Current crypto is considered strong enough that it makes much more sense to attack the implementation (side channel attacks) than the actual algorithm. as bitcoin however only consists of data, not hardware they need to attack the mathematics behind ECDSA and SHA256. This doesn't require a huge budget, this requires brilliant people which can show up anywhere on the globe.

Lastly:
Even though a lot of crypto nowadays is public and 100% open source still only few people understand every detail behind and even fewer then really start questioning established truths or trying out if assumptions actually hold. I bet there are some algorithms out there that are considered quite secure but that have some flaws that are very well hidden and only surface after you start from scratch and test everything. Also there's a huge class of proprietary algorithms that are "secure by obscurity" and usually easily broken because they contain rookie mistakes.

I sense that a) a good percentage of the truly brilliant minds for cryoto work are in academia, b) a lot of these folks have strong ethics and principles, and c) deep insights and results related to cryptography are a pinnacle of success in that environment.  So, I have much more faith in the strength of open-source cryptographic algorithms than my native ability to analyze them otherwise allows.

I do believe that if Bitcoin failed to to cryptographic exploits, it would freeze up for a time, but be relatively quickly re-implemented with the pre-exploited block chain forming the basis for it's distribution.

I have significant questions and fears about the viability of Bitcoin, but core cryptographic attack is not really one of the reasons why.

[CurbsideProphet]

The enigma wasn't used in banking applications...

Did I say it was?