7 ms·

A riddle wrapped in a curve

159 points by wbond 11y ago

rockdoe 11y ago
So the conclusion is that the most reasonable theory is that the NSA has made an advance on ECDLP making them believe they can get faster Pollard-Rho (potentially n^1/3) or that they found signs the curve structures are weak? Pretty mind blowing.
- tptacek 11y ago
  Not really. The paper goes into much more detail, and the most reasonable theory in the paper is that if you believe there are going to be practical quantum computers in 15-20 years, there are lots of agencies and businesses that have secrets that need more than 15-20 years of protection, so the switch to PQ crypto needs to happen sooner than later.
  - rockdoe 11y ago
    Hmm, that's not the vibe I get. The blog indeed doesn't say it is necessarily the most reasonable theory, but goes in depth towards only one: "I’d like to focus on what I think is the most intriguing hypotheses in the paper. Namely, that the NSA isn’t worried about quantum computers at all, but rather, that they’ve made a major advance in classical cryptanalysis of the elliptic curve discrete logarithm problem — and panic is the result." As for the viability of practical quantum computers, the original paper says: "If practical quantum computers are at least 15 years away, and possibly much longer, and if it will take many years to develop and test the proposed PQC systems and reach a consensus on standards, then a long time remains when people will be relying on ECC. But the NSA’s PQC announcement makes it clear that improved ECC standards (for example, an updated list of recommended curves) are not on the Agency’s agenda." "However, for such users the NSA statement recommends using an additional layer of AES to provide quantum resistance, without waiting for quantum-safe public-key standards. In any case, the statement is directed at the general public and obviously is going to have a big impact in the private sector. If the NSA had wanted to give advice that was intended only for high-security government users, they would have done so." The latter paragraph seems to contradict your conclusion directly. I read the paper as saying that in the case you describe, it would have been reasonable for the NSA to continue ECC work while fleshing out post QC alternatives. But this did not happen.
    - tptacek 11y ago
      The banking system is as important a target as the government. The paper stipulates that QC might be ~15 years out. It is the case that if QC is 15 years out, then even though there's no immediate danger to ECC and RSA, the switch needs to happen soon, because there are secrets that have more longevity than that. Apart from "the banking system is important", that's not conjecture; it's just simple logic applied to the paper.
jfindley 11y ago
This is deeply alarming, and (at least to me) very unexpected. For the minute I'm assuming that we shouldn't be changing anything right now - it seems a bit drastic to immediately abandon ECC right now based on this - but this is only my assumption. I'm waiting hopefully for more comments on this from the crypto community.
TerryADavis 11y ago
We like to laugh at those dummies in the Bible. I'll bet the IQ of humans in Greece with the oracle was about 80IQ. They were subhuman. Can you believe the mass delusion that they would kill thousands of sheep. It's like crushing 1,000 brand new BMWs because somebody says it causes blessing! http://biblehub.com/2_chronicles/7-5.htm http://biblehub.com/2_chronicles/7-5.htm 22,000 cattle and 120,000 sheep What a retard-nigger!
charrisku 11y ago
As a mathematician (though not a cryptographer), I have a great deal of difficulty trusting cryptographic protocols which have a mathematical basis. Whether they are based on factoring, elliptic curves, or any other mathematical concept, they always "smelled" sketchy to me for the very simple reason that they are easy to formulate in terms of mathematical ideas, hence naturally lend themselves to the thought process of an algebraist or a number theorist. In short, these problems look like precisely the sort of questions a mathematical genius would find tractable. Without any solid proof that they are actually computationally hard to break, it seems like they are inherently dangerous to rely upon because they look like fair game to the next Ramanujan. I'll also go out on a limb here and also say that I think the technology community has a bias towards thinking something like "math == hard" is true, so gives added weight towards using these same protocols. I know many people here have deep knowledge of both cryptography and software development, so I'd be very interested to hear other people's thoughts on these issues. Can anyone speak about options to math-based public key algorithms, or ways to inject some skepticism into the tech community about these algorithms, so perhaps alternatives can start being implemented? A public key algorithm which doesn't lend itself easily to algebraic analysis would feel much safer to me.
- tveita 11y ago
  In practice, relying on a clearly defined mathematical problem that is thought to be hard to solve has worked out a lot better than the common alternative of throwing a bunch of random shit together and hoping the result is too complex for anyone to understand. For asymmetric cryptography there is no alternative not based on math. Even snake oil cryptography mostly deals in symmetric crypto like "unbreakable" ciphers and hashes, because you can't make a working asymmetric encryption scheme by mashing together whatever operations your schizophrenia tells you to.
- rockdoe 11y ago
  Pretty much all of crypto is based on and analyzed by math (at the very least computing and complexity theory), so I'm not clear at all what you're saying here. People prefer algorithms with a clear mathematical basis because they're easier to analyze, so the flaws surface easier and it's clearer what breakthroughs would break them. Cryptographers have been looking for algorithms that are NP-hard for example, because having a "breakthrough" in them having to require P=NP is a large hurdle. But it's not the end of the story, because it turns out that a problem being NP-hard doesn't mean it isn't easy to crack (worst case vs actual case). Your comment reads a bit as saying "we shouldn't use maths to compute things". But maths is what computers do...
vox_mollis 11y ago
cperciva vindicated? edit: For context, Colin has maintained a conservative position regarding ECC for quite some time now.
- tptacek 11y ago
  No. The crypto Colin advocates for also falls to QC.
  - sdevlin 11y ago
    The post talks about hypothetical improvements in non-QC approaches to the ECDLP.
    - tptacek 11y ago
      Didn't it read dismissive about that to you?
      - sdevlin 11y ago
        The paper or the post? I think the paper is maybe slightly dismissive, closer to neutral: "it is conceivable the NSA has found ...". The post seems more enthusiastic: "the most intriguing hypotheses in the paper" "Beginning with the smallest of the standard curves, P-256, which would now provide less than the required 128-bit security. Did I mention that as part of the recent announcement, NSA also deprecated P-256?" He backtracks a little in the following paragraph ("Of course, there’s no reason to believe ..."), but I think the conspiratorial tone is pretty well established by then. It's also just the fact that he spends about a third of the post talking about this explanation without really covering any of the others. If I hadn't read the paper, I'd come away with the impression that this is the main theory they put forth.
  - vox_mollis 11y ago
    The article discusses the hypothesis that the NSA has broken ECC classically, and is lying to us. But conspiracy theories aside, does 3072 bit RSA fall along with 256 bit ECC with the same quantum difficulty? Don't you have to have coherence of substantially more qubits in the former case?
paulmd 11y ago
One possibility I didn't see discussed - the NIST curves are indeed kleptographically backdoored, and someone has managed to steal the key. That's always worried me about backdoored crypto - as advantageous as such a key would be for the NSA, it would be absolutely catastrophic for an adversary to get it. And if you are using it, a possibility of it being stolen inherently exists. The problem with this theory is that in the event of compromise you'd expect the NSA to deprecate all of the curves, and not just P-256. It is also possible that this backdoor is not a magic bullet, and it merely makes an attack computationally feasible instead of decrypting it outright. It does smell a lot more like there's been an advance in analysis, whether classical or quantum.
- rockdoe 11y ago
  you'd expect the NSA to deprecate all of the curves, and not just P-256 You could argue that that is indeed what the announcement was doing. It was unrelated to P-256 being dropped. (P-256 being dropped does point to the whole "it's not as hard as we thought it was" theory)
  - api 11y ago
    Maybe they backdoored P-256 and they think the backdoor may have leaked. That would inspire panic, especially since quite a few financial networks and military systems are protected by it.
    - jerf 11y ago
      In some ways, this would be the best possible outcome. If they have it rubbed in their face that a backdoor simply can not be secured even with their full resources (as one imagines this would be the highest top secret possible), then maybe they'd flip from using their resources on trying to backdoor our stuff back around to using their full resources to help us. I suspect this falls into the "too good to be true" category.
      - paulmd 11y ago
zmanian 11y ago
It seems likely in a post Quantum computing world, we will have signatures and key exchange protocols at least good enough for software signing and secure communications. But ECC has many ancillary properties for constructing homomorphic and zero knowledge proof based systems that don't have an post Quantum equivalent.
- JoachimSchipper 11y ago
  Lattice cryptography - although I wouldn't want to rely on it in 2015 - is quite flexible and does support such advanced systems. Also, homomorphic encryption and zero-knowledge proofs are almost entirely unused (and, due to the enormous overhead of FHE in particular, unusable) in practice. We'll deal.
api 11y ago
Is NIST P-256 the same curve that Bitcoin uses? https://en.bitcoin.it/wiki/Secp256k1 https://en.bitcoin.it/wiki/Secp256k1 Edit: NO, but it's a relative and has a similar background. Bitcoin is an interesting player here because it's in effect the largest bug bounty in history. If someone could crack it, they could slowly manipulate its price and bleed money out of the Bitcoin ecosystem to the tune of (conservatively) tens of millions of dollars before someone noticed that something more than a Bitcoin price crash was occurring. I'd assume that anyone sophisticated enough to actually break Bitcoin would also be sophisticated enough to use that break to do this by e.g. cracking wallets and slowly draining them or creating price-manipulating transactions. So I'd expect any leakage of an ECC break that was actually practical to use in the real world (as opposed to an 'academic' break) to show up in the form of an enigmatic draining of the Bitcoin piggy bank.
- lisper 11y ago
  > they could slowly manipulate its price How? The only way you can drive the price of bitcoin (relative to some other currency) is to buy or sell it for that currency. You can't manipulate the price simply by moving bitcoins around. What you could do, of course, is drive the price down by making it known that BTC had been cracked. You could probably even do this so that it played out over a period of days before people were really convinced it was cracked and the whole ecosystem collapsed. But it's hard to see how anyone could profit off this. AFAIK there's no way to short bitcoin.
yuhong 11y ago
Still it is pretty interesting that NIST P-224 has weaknesses that the other ones don't. I wonder why?
lisper 11y ago
I just read the full original paper, and this seems like the most likely explanation to me: "[T]he main considerations might not have been technical at all, but rather Agency-specific — that is, related to the difficult situation the NSA was in following the Snowden leaks. The loss of trust and credibility from the scandal about Dual EC DRBG was so great that NSA might have anticipated that anything further it said about ECC standards would be mistrusted. The NSA might have felt that the quickest way to recover from the blow to its reputation would be to get a “clean slate” by abandoning its former role as promoters of ECC and moving ahead with the transition to post-quantum cryptography much earlier than it otherwise would have." I spent >10 years working for the government, and this scenario is entirely consistent with my experience there.

159 points by wbond 11y ago

So the conclusion is that the most reasonable theory is that the NSA has made an advance on ECDLP making them believe they can get faster Pollard-Rho (potentially n^1/3) or that they found signs the curve structures are weak? Pretty mind blowing.

tptacek 11y ago
Not really. The paper goes into much more detail, and the most reasonable theory in the paper is that if you believe there are going to be practical quantum computers in 15-20 years, there are lots of agencies and businesses that have secrets that need more than 15-20 years of protection, so the switch to PQ crypto needs to happen sooner than later.
- rockdoe 11y ago
  Hmm, that's not the vibe I get. The blog indeed doesn't say it is necessarily the most reasonable theory, but goes in depth towards only one: "I’d like to focus on what I think is the most intriguing hypotheses in the paper. Namely, that the NSA isn’t worried about quantum computers at all, but rather, that they’ve made a major advance in classical cryptanalysis of the elliptic curve discrete logarithm problem — and panic is the result." As for the viability of practical quantum computers, the original paper says: "If practical quantum computers are at least 15 years away, and possibly much longer, and if it will take many years to develop and test the proposed PQC systems and reach a consensus on standards, then a long time remains when people will be relying on ECC. But the NSA’s PQC announcement makes it clear that improved ECC standards (for example, an updated list of recommended curves) are not on the Agency’s agenda." "However, for such users the NSA statement recommends using an additional layer of AES to provide quantum resistance, without waiting for quantum-safe public-key standards. In any case, the statement is directed at the general public and obviously is going to have a big impact in the private sector. If the NSA had wanted to give advice that was intended only for high-security government users, they would have done so." The latter paragraph seems to contradict your conclusion directly. I read the paper as saying that in the case you describe, it would have been reasonable for the NSA to continue ECC work while fleshing out post QC alternatives. But this did not happen.
  - tptacek 11y ago
    The banking system is as important a target as the government. The paper stipulates that QC might be ~15 years out. It is the case that if QC is 15 years out, then even though there's no immediate danger to ECC and RSA, the switch needs to happen soon, because there are secrets that have more longevity than that. Apart from "the banking system is important", that's not conjecture; it's just simple logic applied to the paper.

jfindley 11y ago

This is deeply alarming, and (at least to me) very unexpected. For the minute I'm assuming that we shouldn't be changing anything right now - it seems a bit drastic to immediately abandon ECC right now based on this - but this is only my assumption. I'm waiting hopefully for more comments on this from the crypto community.

TerryADavis 11y ago

We like to laugh at those dummies in the Bible. I'll bet the IQ of humans in Greece with the oracle was about 80IQ. They were subhuman. Can you believe the mass delusion that they would kill thousands of sheep. It's like crushing 1,000 brand new BMWs because somebody says it causes blessing! http://biblehub.com/2_chronicles/7-5.htm http://biblehub.com/2_chronicles/7-5.htm 22,000 cattle and 120,000 sheep What a retard-nigger!

charrisku 11y ago

As a mathematician (though not a cryptographer), I have a great deal of difficulty trusting cryptographic protocols which have a mathematical basis. Whether they are based on factoring, elliptic curves, or any other mathematical concept, they always "smelled" sketchy to me for the very simple reason that they are easy to formulate in terms of mathematical ideas, hence naturally lend themselves to the thought process of an algebraist or a number theorist. In short, these problems look like precisely the sort of questions a mathematical genius would find tractable. Without any solid proof that they are actually computationally hard to break, it seems like they are inherently dangerous to rely upon because they look like fair game to the next Ramanujan. I'll also go out on a limb here and also say that I think the technology community has a bias towards thinking something like "math == hard" is true, so gives added weight towards using these same protocols. I know many people here have deep knowledge of both cryptography and software development, so I'd be very interested to hear other people's thoughts on these issues. Can anyone speak about options to math-based public key algorithms, or ways to inject some skepticism into the tech community about these algorithms, so perhaps alternatives can start being implemented? A public key algorithm which doesn't lend itself easily to algebraic analysis would feel much safer to me.

tveita 11y ago
In practice, relying on a clearly defined mathematical problem that is thought to be hard to solve has worked out a lot better than the common alternative of throwing a bunch of random shit together and hoping the result is too complex for anyone to understand. For asymmetric cryptography there is no alternative not based on math. Even snake oil cryptography mostly deals in symmetric crypto like "unbreakable" ciphers and hashes, because you can't make a working asymmetric encryption scheme by mashing together whatever operations your schizophrenia tells you to.
rockdoe 11y ago
Pretty much all of crypto is based on and analyzed by math (at the very least computing and complexity theory), so I'm not clear at all what you're saying here. People prefer algorithms with a clear mathematical basis because they're easier to analyze, so the flaws surface easier and it's clearer what breakthroughs would break them. Cryptographers have been looking for algorithms that are NP-hard for example, because having a "breakthrough" in them having to require P=NP is a large hurdle. But it's not the end of the story, because it turns out that a problem being NP-hard doesn't mean it isn't easy to crack (worst case vs actual case). Your comment reads a bit as saying "we shouldn't use maths to compute things". But maths is what computers do...

vox_mollis 11y ago

cperciva vindicated? edit: For context, Colin has maintained a conservative position regarding ECC for quite some time now.

tptacek 11y ago
No. The crypto Colin advocates for also falls to QC.
- sdevlin 11y ago
  The post talks about hypothetical improvements in non-QC approaches to the ECDLP.
  - tptacek 11y ago
    Didn't it read dismissive about that to you?
    - sdevlin 11y ago
      The paper or the post? I think the paper is maybe slightly dismissive, closer to neutral: "it is conceivable the NSA has found ...". The post seems more enthusiastic: "the most intriguing hypotheses in the paper" "Beginning with the smallest of the standard curves, P-256, which would now provide less than the required 128-bit security. Did I mention that as part of the recent announcement, NSA also deprecated P-256?" He backtracks a little in the following paragraph ("Of course, there’s no reason to believe ..."), but I think the conspiratorial tone is pretty well established by then. It's also just the fact that he spends about a third of the post talking about this explanation without really covering any of the others. If I hadn't read the paper, I'd come away with the impression that this is the main theory they put forth.
- vox_mollis 11y ago
  The article discusses the hypothesis that the NSA has broken ECC classically, and is lying to us. But conspiracy theories aside, does 3072 bit RSA fall along with 256 bit ECC with the same quantum difficulty? Don't you have to have coherence of substantially more qubits in the former case?

paulmd 11y ago

One possibility I didn't see discussed - the NIST curves are indeed kleptographically backdoored, and someone has managed to steal the key. That's always worried me about backdoored crypto - as advantageous as such a key would be for the NSA, it would be absolutely catastrophic for an adversary to get it. And if you are using it, a possibility of it being stolen inherently exists. The problem with this theory is that in the event of compromise you'd expect the NSA to deprecate all of the curves, and not just P-256. It is also possible that this backdoor is not a magic bullet, and it merely makes an attack computationally feasible instead of decrypting it outright. It does smell a lot more like there's been an advance in analysis, whether classical or quantum.

rockdoe 11y ago
you'd expect the NSA to deprecate all of the curves, and not just P-256 You could argue that that is indeed what the announcement was doing. It was unrelated to P-256 being dropped. (P-256 being dropped does point to the whole "it's not as hard as we thought it was" theory)
- api 11y ago
  Maybe they backdoored P-256 and they think the backdoor may have leaked. That would inspire panic, especially since quite a few financial networks and military systems are protected by it.
  - jerf 11y ago
    In some ways, this would be the best possible outcome. If they have it rubbed in their face that a backdoor simply can not be secured even with their full resources (as one imagines this would be the highest top secret possible), then maybe they'd flip from using their resources on trying to backdoor our stuff back around to using their full resources to help us. I suspect this falls into the "too good to be true" category.
    - paulmd 11y ago

zmanian 11y ago

It seems likely in a post Quantum computing world, we will have signatures and key exchange protocols at least good enough for software signing and secure communications. But ECC has many ancillary properties for constructing homomorphic and zero knowledge proof based systems that don't have an post Quantum equivalent.

JoachimSchipper 11y ago
Lattice cryptography - although I wouldn't want to rely on it in 2015 - is quite flexible and does support such advanced systems. Also, homomorphic encryption and zero-knowledge proofs are almost entirely unused (and, due to the enormous overhead of FHE in particular, unusable) in practice. We'll deal.

api 11y ago

Is NIST P-256 the same curve that Bitcoin uses? https://en.bitcoin.it/wiki/Secp256k1 https://en.bitcoin.it/wiki/Secp256k1 Edit: NO, but it's a relative and has a similar background. Bitcoin is an interesting player here because it's in effect the largest bug bounty in history. If someone could crack it, they could slowly manipulate its price and bleed money out of the Bitcoin ecosystem to the tune of (conservatively) tens of millions of dollars before someone noticed that something more than a Bitcoin price crash was occurring. I'd assume that anyone sophisticated enough to actually break Bitcoin would also be sophisticated enough to use that break to do this by e.g. cracking wallets and slowly draining them or creating price-manipulating transactions. So I'd expect any leakage of an ECC break that was actually practical to use in the real world (as opposed to an 'academic' break) to show up in the form of an enigmatic draining of the Bitcoin piggy bank.

lisper 11y ago
> they could slowly manipulate its price How? The only way you can drive the price of bitcoin (relative to some other currency) is to buy or sell it for that currency. You can't manipulate the price simply by moving bitcoins around. What you could do, of course, is drive the price down by making it known that BTC had been cracked. You could probably even do this so that it played out over a period of days before people were really convinced it was cracked and the whole ecosystem collapsed. But it's hard to see how anyone could profit off this. AFAIK there's no way to short bitcoin.

yuhong 11y ago

Still it is pretty interesting that NIST P-224 has weaknesses that the other ones don't. I wonder why?

lisper 11y ago

I just read the full original paper, and this seems like the most likely explanation to me: "[T]he main considerations might not have been technical at all, but rather Agency-specific — that is, related to the difficult situation the NSA was in following the Snowden leaks. The loss of trust and credibility from the scandal about Dual EC DRBG was so great that NSA might have anticipated that anything further it said about ECC standards would be mistrusted. The NSA might have felt that the quickest way to recover from the blow to its reputation would be to get a “clean slate” by abandoning its former role as promoters of ECC and moving ahead with the transition to post-quantum cryptography much earlier than it otherwise would have." I spent >10 years working for the government, and this scenario is entirely consistent with my experience there.