9 ms·

NSA Backdoors and Bitcoin (2013)

95 points by maxwell 7y ago

api 7y ago
I still doubt that there's a backdoor in the NIST curves because they're still widely used and recommended for top secret information, among other reasons. If there were a backdoor and it leaked (or the math behind it was independently rediscovered!) the result could be catastrophic. Snowden showed that the NSA is absolutely vulnerable to leaks.
- garmaine 7y ago
  A trapdoor back door would require knowing some secret value. It is very much possible that this secret value could remain secret by not being written down in any electronic document. It would exist on some code breaking hardware, but like the cocoa cola recipe it could be known by only a few people in the world and still be useful.
  - ev0lv 7y ago
    Somewhere exists a hardware key that breaks the blockchain encryption. This is a sweet movie idea.
    - bonestamp2 7y ago
      Seems like the typical heist movie at first, but the main action arc is just to steal the hardware key. Steeling the actual (digital) coins is then the most boring part of the film.
      - whoopdedo 7y ago
        That's why you make the thieves be white-hats hired by the government to steal the key. Then it becomes a cloak-and-dagger affair where you have to unravel who's working for who and which side is really the bad guy. And decrypting cryptocoins is too obscure. For maximum effect, make the key able to break all encryption.
        chowells 7y ago
        Someone already made Sneakers.
        0xcde4c3db 7y ago
        I think that's the joke.
        chowells 7y ago
        Yes? When someone puts some effort into making an indirect reference like that, they appreciate their work having been noticed. That's the role my comment was performing.
    - garmaine 7y ago
      We know this not to be true. The origins of the secp256k1 curve used to be nothing up my sleeve numbers for the parameters which matter.
  - nullc 7y ago
    The construction of the NIST curves essentially preludes trapdoors. It doesn't completely preclude having a purposefully weak curve based on some publicly unknown weakness. ... but at the same time it also doesn't preclude the the curves having been selected to be stronger against some publicly unknown weakness (as was done with DES). [Not that I'd recommend them.]
    - deleted 7y ago
      [deleted]
    - garmaine 7y ago
      Greg, do we know that to be true of all use cases though?
      - nullc 7y ago
        Would you clarifying your question a bit? My comment was pointing out that those NIST curves like P-256 and P-224 can't have a trapdoor-- meaning a hidden secret key that allows the NSA and only the NSA to compromise the use-- in the curve themselves. Some application of the curve could have its own trapdoor, as dualECdrbg did.
        garmaine 7y ago
        Well the NIST curves use random primes, and they're not the obvious, largest possible primes that meet the necessary security requirements. So maybe they were chosen according to their susceptibility to some unknown attack (or, charitably, their non-susceptibility). I think we agree up to this point. But when the space of potential attacks is an unknown-unknown, can we really constrain with confidence what attacks might exist? Maybe the prime group was chosen to have some relationship to a composite group for which the NSA knows the prime factors? I know this doesn't jive with our current understanding of number theory, but the point is it is hard to speculate about unknown-unknowns. Can we be certain that every crazy thing we think of is ruled out by our proven, not conjectured understanding of number theory?
- secfirstmd 7y ago
  And Shadowbrokers showed the danger of when their code and exploits get leaked.
tptacek 7y ago
This is silly. secp256k1 and secp256r1 are curves (or, standards based on parameters describing a curve). Dual_EC is a PKRNG that uses curves. You don't need curve magic to see the problem with Dual_EC; it's an RNG that works by transforming its state with a public key encryption primitive, which begs the obvious question "who holds the private key?". Dual_EC was so obviously problematic (and so slow) that many people, Schneier included, questioned whether it actually was a backdoor at all (full disclosure: I'm one of those people). To believe the NIST curves generated from random numbers are backdoored, you essentially have to believe that there is a class of curves susceptible to some hitherto unknown attack that is large enough that NSA could find it by brute forcing hashes, but not so large that any other researcher got any inkling that the vulnerability existed. In particular: unlike Dual_EC, which is straightforwardly a backdoor, with its own special key, for NIST curves to be "backdoored" there has to be some underlying vulnerability in a particular curve structure to exploit. This isn't my argument, by the way; it's shoplifted from Koblitz and Menezes. You shouldn't use the NIST curves! They're hard to implement securely. Curve25519 has better ergonomics and is much safer out of the box. But conspiracy-theoretic stuff linking Dual_EC to NIST curves is always painful to read.
- mantap 7y ago
  I don't think it's really a conspiracy theory. Recall that before the Dual_EC affair, the reputation of the NSA was that they were a benevolent force that helped strengthen DES against differential cryptanalysis before it was publicly discovered. The Dual_EC affair marked a turning point where people started to seriously consider the possiblility that the NSA was a malevolent actor weakening primatives for their own benefit. Also the problem with Dual_EC wasn't just the bad design, but that they had (reportedly) paid RSA corporation to use it.
  - tptacek 7y ago
    I find comments like these absolutely baffling. I learned what the NSA was from Schneier's Applied Cryptography, which I bought when I was a senior in high school, back in 1994. Throughout the book, NSA is depicted as adversarial to cryptography. They're the NSA of the Clipper chip, and of global bans on cryptography, and "this t-shirt is a munition". There has never been a point in my professional life where NSA wasn't the global adversary. Until I started talking about this stuff on HN, it never would have occurred to me that anyone would think NSA had this benevolent reputation. Based on the timing, I suspect that's not because I'm encountering people with different priors about NSA, but rather that I'm talking to people with no priors about NSA.
bcaa7f3a8bbc 7y ago
Pseudorandom parameter selection of NIST P-curves, including secp256r1 has created much controversy within the cypherpunk community in the early 2000s. the theory is that the NSA discovered a class of secret curves with an unknown special weakness, and then bruteforced the random seed that would generate the weak curve. [0] On the other hand, secp256k1's parameters were not generated by random seeds. [1] I think the important fact is not whether secp256r1 has a backdoor, but the decision of selecting secp256k1 by Satoshi Nakamoto for the use in Bitcoin. At the time, secp256k1 was the only widely-implemented non-P curve in various crypto libraries, and almost nobody used it at the time. It seems the entire decision of using secp256k1 was made to avoid secp256r1. This is another piece of evidence that Satoshi Nakamoto must have beee active in the 1990-2000 cypherpunk community, so that he was well-aware of those discussions. This should shed some light on his possible identity. -- [0] DJB's paper how to manipulate curve standards [2] is DJB's attempt of creating the strongest argument for this claim. But even in his analysis, overall it's not too plausible, there's little evidence that such a class of secret curves exists and it required huge computation (2^80), it's on the edge of what was possible, but the pseudorandom parameter selection is certainly technically unfavorable as he demonstrated. [1] https://safecurves.cr.yp.to/rigid.html https://safecurves.cr.yp.to/rigid.html [2] https://eprint.iacr.org/2014/571.pdf https://eprint.iacr.org/2014/571.pdf
- pg_is_a_butt 7y ago
  > It seems the entire decision of using secp256k1 was made to avoid secp256r1. This is another piece of evidence that Satoshi Nakamoto must have beee active in the 1990-2000 cypherpunk community, so that he was well-aware of those discussions. This should shed some light on his possible identity. I was well aware of all that, at the time and now, without being active in the cypherpunk community. Granted, I was in college for a CS and math degree, but the cypherpunk community was pretty loud if you were listening at all.
  - bcaa7f3a8bbc 7y ago
    Yes, it's another way to interpret his choice. "Satoshi being a member of the Cypherpunk" is only one possibility. It's entirely possible that he wasn't active at all, and his familiarity of Cypherpunks was from his learning, not from the participation.
LinuxBender 7y ago
If there are fears and doubts, perhaps it would be safest to just assume the transport is clear text in risk ranking and adapt other counter-measures to fill perceived gaps. For really sensitive flows, perhaps dark fiber + non standard ciphers + encrypting the payload with application layer encryption using non standard or custom ciphers. I mean, why not, if it's your own B2B flows. Take an existing cipher / protocol and make a few subtle changes. It's just math. For end-user encryption, that would take some more thought and would probably get into layers of turtles.
- robbya 7y ago
  There's a lot of ways to get encryption wrong. A few subtle changes could undo a very deliberate countermeasure for a somewhat obscure vulnerability. I don't think that's good advice.
  - LinuxBender 7y ago
    I agree, but I would probably do it anyway if I were mitigating someones concerns. It could be a layer on top of the standard ciphers / protocols. I certainly would not do this for end-user comms. For B2B if you control both ends, maybe its a risk worth taking. Each entity would have to weigh the risks.
- arcticbull 7y ago
  Rolling your own crypto is dreadful advice. You’re making tweaks to something to avoid a backdoor you don’t know exists and in the process likely opening yourself up a gaping hole in the middle.
  - LinuxBender 7y ago
    Oh I would not suggest rolling your own crypto. Rather, just fork openssl and make a very subtle change to each formula. For in-house use of course. Ages ago, I used to change up a rubix-cube for a friend. The more I changed it, the quicker he could solve it. If I made just a very subtle change, it would take him up to an extra 7 seconds to solve it.
NelsonMinar 7y ago
So this article is six years old. Any update on the supposition? I guess no one's figured out yet whether the recommended magic number is a back door or not. My money is definitely on corrupted. Odd the article doesn't mention the obvious conclusion; that Bitcoin was designed by NSA, or folks with intimate knowledge of NSA's back doors. I've long maintained that a US government agency is the most likely developer of Bitcoin (mostly because no one else could sit on that kind of $$$ forever). NSA is the most obvious agency. The question is.. why? I can speculate on lots of reasons.
- cyphertruck 7y ago
  Bitcoin was designed by an individual with intimate knowledge of the state of the art in suspicions of NSA backdoors. You are assuming Satoshi is sitting on money. Satoshi took care to hide it’s identity, and thus would have switched mining to different addresses very early in bitcoins history. It would have been obvious to Satoshi that spending from a known address would blow it’s identity, so only did so for testing. Satoshi may well be a billionaire and spending bitcoin every day. People seem to take comfort in this idea that bitcoin was created by a government... because bitcoin seems radical when you first learn about it. However the attempts to create it date back a couple decades before it was created. Satoshi combined existing inventions with just the new element of his time chain. But even if the NSA were behind it, what could they do? Anything they could do could also be done by someone with a math breakthrough. So whether the attacker is the NSA or not bitcoin has to be robust against it. So where is bitcoin vulnerable? It’s easy to imagine vulnerabilities in the cryptography, but hard to produce them. Further, if you did, it doesn’t necessarily affect bitcoin. This is bitcoin’s genius. It’s not software, it’s a set of incentives. Show an error in the software, it will be patched and bitcoin will carry on. Worst case is a hard fork.
  - real_satoshi 7y ago
    > Bitcoin was designed by an individual with intimate knowledge of the state of the art in suspicions of NSA backdoors. Insiders at the NSA (or any other TLA, foreign or domestic) also fit this description. The strongest position is to know both the truth, and the most compelling misconceptions.

95 points by maxwell 7y ago

api 7y ago

I still doubt that there's a backdoor in the NIST curves because they're still widely used and recommended for top secret information, among other reasons. If there were a backdoor and it leaked (or the math behind it was independently rediscovered!) the result could be catastrophic. Snowden showed that the NSA is absolutely vulnerable to leaks.

garmaine 7y ago
A trapdoor back door would require knowing some secret value. It is very much possible that this secret value could remain secret by not being written down in any electronic document. It would exist on some code breaking hardware, but like the cocoa cola recipe it could be known by only a few people in the world and still be useful.
- ev0lv 7y ago
  Somewhere exists a hardware key that breaks the blockchain encryption. This is a sweet movie idea.
  - bonestamp2 7y ago
    Seems like the typical heist movie at first, but the main action arc is just to steal the hardware key. Steeling the actual (digital) coins is then the most boring part of the film.
    - whoopdedo 7y ago
      That's why you make the thieves be white-hats hired by the government to steal the key. Then it becomes a cloak-and-dagger affair where you have to unravel who's working for who and which side is really the bad guy. And decrypting cryptocoins is too obscure. For maximum effect, make the key able to break all encryption.
      - chowells 7y ago
        Someone already made Sneakers.
        0xcde4c3db 7y ago
        I think that's the joke.
        chowells 7y ago
        Yes? When someone puts some effort into making an indirect reference like that, they appreciate their work having been noticed. That's the role my comment was performing.
  - garmaine 7y ago
    We know this not to be true. The origins of the secp256k1 curve used to be nothing up my sleeve numbers for the parameters which matter.
- nullc 7y ago
  The construction of the NIST curves essentially preludes trapdoors. It doesn't completely preclude having a purposefully weak curve based on some publicly unknown weakness. ... but at the same time it also doesn't preclude the the curves having been selected to be stronger against some publicly unknown weakness (as was done with DES). [Not that I'd recommend them.]
  - deleted 7y ago
    [deleted]
  - garmaine 7y ago
    Greg, do we know that to be true of all use cases though?
    - nullc 7y ago
      Would you clarifying your question a bit? My comment was pointing out that those NIST curves like P-256 and P-224 can't have a trapdoor-- meaning a hidden secret key that allows the NSA and only the NSA to compromise the use-- in the curve themselves. Some application of the curve could have its own trapdoor, as dualECdrbg did.
      - garmaine 7y ago
        Well the NIST curves use random primes, and they're not the obvious, largest possible primes that meet the necessary security requirements. So maybe they were chosen according to their susceptibility to some unknown attack (or, charitably, their non-susceptibility). I think we agree up to this point. But when the space of potential attacks is an unknown-unknown, can we really constrain with confidence what attacks might exist? Maybe the prime group was chosen to have some relationship to a composite group for which the NSA knows the prime factors? I know this doesn't jive with our current understanding of number theory, but the point is it is hard to speculate about unknown-unknowns. Can we be certain that every crazy thing we think of is ruled out by our proven, not conjectured understanding of number theory?
secfirstmd 7y ago
And Shadowbrokers showed the danger of when their code and exploits get leaked.

tptacek 7y ago

This is silly. secp256k1 and secp256r1 are curves (or, standards based on parameters describing a curve). Dual_EC is a PKRNG that uses curves. You don't need curve magic to see the problem with Dual_EC; it's an RNG that works by transforming its state with a public key encryption primitive, which begs the obvious question "who holds the private key?". Dual_EC was so obviously problematic (and so slow) that many people, Schneier included, questioned whether it actually was a backdoor at all (full disclosure: I'm one of those people). To believe the NIST curves generated from random numbers are backdoored, you essentially have to believe that there is a class of curves susceptible to some hitherto unknown attack that is large enough that NSA could find it by brute forcing hashes, but not so large that any other researcher got any inkling that the vulnerability existed. In particular: unlike Dual_EC, which is straightforwardly a backdoor, with its own special key, for NIST curves to be "backdoored" there has to be some underlying vulnerability in a particular curve structure to exploit. This isn't my argument, by the way; it's shoplifted from Koblitz and Menezes. You shouldn't use the NIST curves! They're hard to implement securely. Curve25519 has better ergonomics and is much safer out of the box. But conspiracy-theoretic stuff linking Dual_EC to NIST curves is always painful to read.

mantap 7y ago
I don't think it's really a conspiracy theory. Recall that before the Dual_EC affair, the reputation of the NSA was that they were a benevolent force that helped strengthen DES against differential cryptanalysis before it was publicly discovered. The Dual_EC affair marked a turning point where people started to seriously consider the possiblility that the NSA was a malevolent actor weakening primatives for their own benefit. Also the problem with Dual_EC wasn't just the bad design, but that they had (reportedly) paid RSA corporation to use it.
- tptacek 7y ago
  I find comments like these absolutely baffling. I learned what the NSA was from Schneier's Applied Cryptography, which I bought when I was a senior in high school, back in 1994. Throughout the book, NSA is depicted as adversarial to cryptography. They're the NSA of the Clipper chip, and of global bans on cryptography, and "this t-shirt is a munition". There has never been a point in my professional life where NSA wasn't the global adversary. Until I started talking about this stuff on HN, it never would have occurred to me that anyone would think NSA had this benevolent reputation. Based on the timing, I suspect that's not because I'm encountering people with different priors about NSA, but rather that I'm talking to people with no priors about NSA.

bcaa7f3a8bbc 7y ago

Pseudorandom parameter selection of NIST P-curves, including secp256r1 has created much controversy within the cypherpunk community in the early 2000s. the theory is that the NSA discovered a class of secret curves with an unknown special weakness, and then bruteforced the random seed that would generate the weak curve. [0] On the other hand, secp256k1's parameters were not generated by random seeds. [1] I think the important fact is not whether secp256r1 has a backdoor, but the decision of selecting secp256k1 by Satoshi Nakamoto for the use in Bitcoin. At the time, secp256k1 was the only widely-implemented non-P curve in various crypto libraries, and almost nobody used it at the time. It seems the entire decision of using secp256k1 was made to avoid secp256r1. This is another piece of evidence that Satoshi Nakamoto must have beee active in the 1990-2000 cypherpunk community, so that he was well-aware of those discussions. This should shed some light on his possible identity. -- [0] DJB's paper how to manipulate curve standards [2] is DJB's attempt of creating the strongest argument for this claim. But even in his analysis, overall it's not too plausible, there's little evidence that such a class of secret curves exists and it required huge computation (2^80), it's on the edge of what was possible, but the pseudorandom parameter selection is certainly technically unfavorable as he demonstrated. [1] https://safecurves.cr.yp.to/rigid.html https://safecurves.cr.yp.to/rigid.html [2] https://eprint.iacr.org/2014/571.pdf https://eprint.iacr.org/2014/571.pdf

pg_is_a_butt 7y ago
> It seems the entire decision of using secp256k1 was made to avoid secp256r1. This is another piece of evidence that Satoshi Nakamoto must have beee active in the 1990-2000 cypherpunk community, so that he was well-aware of those discussions. This should shed some light on his possible identity. I was well aware of all that, at the time and now, without being active in the cypherpunk community. Granted, I was in college for a CS and math degree, but the cypherpunk community was pretty loud if you were listening at all.
- bcaa7f3a8bbc 7y ago
  Yes, it's another way to interpret his choice. "Satoshi being a member of the Cypherpunk" is only one possibility. It's entirely possible that he wasn't active at all, and his familiarity of Cypherpunks was from his learning, not from the participation.

LinuxBender 7y ago

If there are fears and doubts, perhaps it would be safest to just assume the transport is clear text in risk ranking and adapt other counter-measures to fill perceived gaps. For really sensitive flows, perhaps dark fiber + non standard ciphers + encrypting the payload with application layer encryption using non standard or custom ciphers. I mean, why not, if it's your own B2B flows. Take an existing cipher / protocol and make a few subtle changes. It's just math. For end-user encryption, that would take some more thought and would probably get into layers of turtles.

robbya 7y ago
There's a lot of ways to get encryption wrong. A few subtle changes could undo a very deliberate countermeasure for a somewhat obscure vulnerability. I don't think that's good advice.
- LinuxBender 7y ago
  I agree, but I would probably do it anyway if I were mitigating someones concerns. It could be a layer on top of the standard ciphers / protocols. I certainly would not do this for end-user comms. For B2B if you control both ends, maybe its a risk worth taking. Each entity would have to weigh the risks.
arcticbull 7y ago
Rolling your own crypto is dreadful advice. You’re making tweaks to something to avoid a backdoor you don’t know exists and in the process likely opening yourself up a gaping hole in the middle.
- LinuxBender 7y ago
  Oh I would not suggest rolling your own crypto. Rather, just fork openssl and make a very subtle change to each formula. For in-house use of course. Ages ago, I used to change up a rubix-cube for a friend. The more I changed it, the quicker he could solve it. If I made just a very subtle change, it would take him up to an extra 7 seconds to solve it.

NelsonMinar 7y ago

So this article is six years old. Any update on the supposition? I guess no one's figured out yet whether the recommended magic number is a back door or not. My money is definitely on corrupted. Odd the article doesn't mention the obvious conclusion; that Bitcoin was designed by NSA, or folks with intimate knowledge of NSA's back doors. I've long maintained that a US government agency is the most likely developer of Bitcoin (mostly because no one else could sit on that kind of $$$ forever). NSA is the most obvious agency. The question is.. why? I can speculate on lots of reasons.

cyphertruck 7y ago
Bitcoin was designed by an individual with intimate knowledge of the state of the art in suspicions of NSA backdoors. You are assuming Satoshi is sitting on money. Satoshi took care to hide it’s identity, and thus would have switched mining to different addresses very early in bitcoins history. It would have been obvious to Satoshi that spending from a known address would blow it’s identity, so only did so for testing. Satoshi may well be a billionaire and spending bitcoin every day. People seem to take comfort in this idea that bitcoin was created by a government... because bitcoin seems radical when you first learn about it. However the attempts to create it date back a couple decades before it was created. Satoshi combined existing inventions with just the new element of his time chain. But even if the NSA were behind it, what could they do? Anything they could do could also be done by someone with a math breakthrough. So whether the attacker is the NSA or not bitcoin has to be robust against it. So where is bitcoin vulnerable? It’s easy to imagine vulnerabilities in the cryptography, but hard to produce them. Further, if you did, it doesn’t necessarily affect bitcoin. This is bitcoin’s genius. It’s not software, it’s a set of incentives. Show an error in the software, it will be patched and bitcoin will carry on. Worst case is a hard fork.
- real_satoshi 7y ago
  > Bitcoin was designed by an individual with intimate knowledge of the state of the art in suspicions of NSA backdoors. Insiders at the NSA (or any other TLA, foreign or domestic) also fit this description. The strongest position is to know both the truth, and the most compelling misconceptions.