NSABITCOIN

NSA Backdoors and Bitcoin

Many cryptographic standards widely used in commercial applications were developed by the U.S. Government’s National Institute of Standards and Technology (NIST). Normally government involvement in developing ciphers for public use would throw up red flags, however all of the algorithms are part of the public domain and have been analyzed and vetted by professional cryptographers who know what they’re doing. Unless the government has access to some highly advanced math not known to academia, these ciphers should be secure.

We now know, however, that this isn’t the case. Back in 2007, Bruce Schneier reported on a backdoor found in NIST’s Dual_EC_DRBG random number generator:

But today there’s an even bigger stink brewing around Dual_EC_DRBG. In an informal presentation(.pdf) at the CRYPTO 2007 conference in August, Dan Shumow and Niels Ferguson showed that the algorithm contains a weakness that can only be described as a backdoor.

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.

This is important because random number generators are widely used in cryptographic protocols. If the random number generator is compromised, so are the ciphers that use it.

Thanks to the heroic work of Edward Snowden we now know that Dual_EC_DRBG was developed by the NSA, with the backdoor, and given to NIST to disseminate. The scary part is that RSA Security, a company that develops widely used commercial encryption applications, continued use of Dual_EC_DRBG all the way up to the Snowden revelations despite the known flaws. Not surprising this brought a lot of heat on RSA which denies they intentionally created a honeypot for the NSA.

UPDATE: RSA was paid $10 million by the NSA to keep the backdoor in there.

All of this has been known for several months. What I didn’t know until reading Vitalik Buterin’s recent article Satoshi’s Genius: Unexpected Ways in which Bitcoin Dodged Some Crytographic Bullets, is that a variant of an algorithm used in Bitcoin likely also contains a NSA backdoor, but miraculously Bitcoin dodged the bullet.

Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) for signing transactions. This is how you use your private key to “prove” you own the bitcoins associated with your address. ECDSA keys are derived from elliptic curves that themselves are generated using certain parameters. NIST has been actively recommending that everyone use the secp256r1 parameters because they “are the most secure”. However, there appears to be some funny business with secp256r1 that is eerily similar to the backdoor in Dual_EC_DRBG.

Secp256r1 is supposed to use a random number in generating the curves. The way it allegedly creates this random number is by using a one-way hash function of a “seed” to produce a nothing up my sleeve number. The seed need not be random since the output of the hash function is not predictable. Instead of using a relatively innocuous seed like, say, the number 15, secp256r1 uses the very suspicious looking seed: c49d360886e704936a6678e1139d26b7819f7e90. And like Dual_EC_DRBG, it provides no documentation for how or why this number was chosen.

Now as Vitalik pointed out, even if the NSA knew of a specific elliptic curve with vulnerabilities, it still should have been near impossible for them rig the system due to the fact that brute-forcing a hash function is not feasible. However, if they discovered a flaw that occurred in say, one curve in every billion, then they only need to test one billion numbers to find the exploit.

However, the kicker in all this is that the parameters for secp256r1 were developed by the head of elliptic curve research at the NSA!

The unbelievable thing is that rather than using secp256r1 like nearly all other applications, Bitcoin uses secp256k1 which uses Koblitz curves instead of pseudorandom curves and is still believed to be secure. Now the decision to use secp256k1 instead of secp256r1 was made by Satoshi. It’s a mystery why he chose these parameters instead of the parameters used by everyone else (the core devs even considered changing it!). Dan Brown, Chairman of the Standards for Efficient Cryptography Group, had this to say about it:

I did not know that BitCoin is using secp256k1. Indeed, I am surprised to see anybody use secp256k1 instead of secp256r1.

Just wow! This was either random luck or pure genius on the part of Satoshi. Either way, Bitcoin dodged a huge bullet and now almost seems destined to go on to great things.

About these ads

11 thoughts on “NSA Backdoors and Bitcoin

  1. Pingback: Edward Snowden Revelation’s Has Caused the #NSA to Erode Our Security Foundation’s | Ace News Services

  2. Thanks for the Article! It’s important to note that we’re not talking about traditional backdoors, but using weak seeds that give the NSA or anyone else aware of the weakness a strong foothold in cracking that which seems solid and safe. Even with something open source, this makes it nearly impossible to notice the weakness in the code – you have to know about the specific problem with the standard itself.

    My big concern is with client side scripting for wallet generation. You point out that the Bitcoin devs dodged a bullet with choosing a less well established algorithm standard. But so many wallet generators are available now – including bitaddress.org which you used in a recent video tutorial. How do I – the neophyte bitcoin user, and non-mathematician – verify that these resources are using the same standard as Bitcoin itself and not some weaker method that might give a hacker a window to exploit? Is there a forum or body that vets these resources? I really like the advantages of a client side generator I can run in a browser offline – but which ones are verified as true to the Bitcoin methods you talk about in this article?

    Thanks again – I really appreciate this blog!

    • Thanks Daedahl.

      I could be wrong but I was under the impression bitaddress.org uses window.crypto in the rng instead of math.random() is known to be insecure.

      I’ve played around with the bitaddress.org code and didn’t notice anything fishy, although I’m far from a security analyst and the code is dense. I kind of rely on the fact that the JS dependencies that are used are open source. So far nobody has documented any vulnerabilities.

  3. “… but miraculously Bitcoin dodged the bullet”.
    Really?
    NIST recommended fifteen elliptic curves. It is hard to believe that ten of them are intentional cripples, while the five Koblitz curves are rock solid. If secp256r1 is flawed, as you convincingly claim, then secp256k1 is likely to be flawed too, since it was chosen by the same trickster.

    • The point was that some people are suspicious of R1 because it has features that resemble the backdoor in dual_ec. It might not have one, but there is suspicion. I don’t know about the other R1 curves I’ve only read that about 256.

    • Hi Anthony,

      Looks like you don’t have comments enabled on your site so I’ll just reply here:

      I you’re blog post there were a number of misconceptions about Bitcoin, I’ll try to clarify them quickly.

      Bitcoin enables fraud and other criminal activities.
      Not any more so than other currencies. The dollar is still the preferred medium for criminals. You refer to Bitcoin being used to buy drugs, but considering I’m not a fan of the drug war, I see the breakdown of the war on drugs as a good thing.

      Could Bitcoin be used to launder money from non-drug (real) crimes? Sure, but then again that’s what police work is for. Silk Road was taken down with investigative work not by breaking bitcoin.

      Digital QR codes make it vulnerable to theft.
      The QRs that are usually used represent public keys. Nobody can steal your Bitcoins from that QR. The anchor revealed his private key on TV. Something that obviously shouldn’t be done. Somewhat of a beginner’s mistake.

      Mining Bitcoins is a health hazard and energy sink.
      As far as I know only one person got heat stroke from it back in 2011 and it was a bit of a freak accident.

      Today most mining is done in large server farms not people’s bedrooms. There’s no reason why server farms cannot form the backbone of a global financial system. (They already are).

      There is no central bank for Bitcoin.
      Contrary to the assertion, there is far from a consensus in macroeconomics. Many economists believe central banks are destabilizing rather than stabalizing. The history of the Fed with the two worst economic disasters in world history under its belt and a number of recessions in between has not engendered confidence that they actually have a correct macro understanding.

      If asset bubble and the resulting depressions are causes by ultra low interest rates, then bitcoin will certainly improve economic performance.

      Minting copycat currencies is easy.
      Competition is a good thing. It results in innovation and improvement. In the end, however, the market will o my select one for use as the general medium of exchange. So multiple media isn’t something to worry about.

      Overall I invite you to take a deeper look at bitcoin. I’m free to answer more concerns.

  4. Pingback: Chapter 2: Smart Contracts | Great Wall of Numbers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s