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.
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.
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...
I was mainly curious if any asymmetric algorithms exist which are not easily analyzed by algebraists, et al. According to the comment by tveita, this does not appear likely, and I am sorry to hear it. I don't discount what you say about mathematical algorithms being easier to analyze, so flaws are shallower. However, I have seen smart people do quite amazing things with mathematics in my life. People who spend years studying algebra or number theory learn so many patterns that the good ones can pull unbelievably clever arguments seemingly out of pure intuition. That is somewhat disconcerting to me because something like RSA or ECC is precisely the sort of problem those people can apply that intuition and pattern recognition towards. I obviously don't know of an asymmetric algorithm which is analogous, but something like AES is a nightmare to analyze algebraicly (it really does have that "jumble of shit" look to it when written out as an operator). That seems to me to offer some small resistance to the math genius with the spooky intuition. My main point was how dangerous a smart person can be with a problem that his/her brain is geared for, so I was curious if any algorithms existed which are not easy for a mathematician to attack.
This is understood. RSA depends on prime factoring. (EC)DH depends on discrete logarithms. These problems have been studied by the kind of people you mention, from all over the world, an in some cases massive speedups and breakthroughs have been made. But even after all those years, the problems are still "hard enough". That's what gives them confidence.
I'm not even sure what you would imagine the alternative would be. An algorithm that isn't amendable to mathematical analysis?
Even for symmetrical ciphers, which look far less like pure math, analysis proceeds very much along mathematical lines (differential/linear cryptanalysis), or in some cases, via algebra as well: https://en.wikipedia.org/wiki/XSL_attack
I can't really say what I imagine the alternative to be (if I could, I'd write it up), but I do know that if it had an inherent complexity in it's mathematical structure, I would image it to be more resistant to attack by a good mathematician than otherwise. At present we cannot prove that any of these algorithms is actually NP complete and the best device in existence to prove the conventional wisdom wrong sits between two ears. I think any algorithm designed to make the human brain less effective at analyzing it necessarily adds security, although I wholeheartedly cede the point that it also makes the flaws in said algorithm harder to find, so there is obviously a trade-off inherent to this approach. I also agree that any analysis will ultimately take a mathematical flavor (it is an algorithm of course, math is essentially the only trick humans have come up with here), but that isn't to say we can't craft one which makes that analysis fiendishly difficult. Thanks for the XSL link, I'm not a cryptographer, so wasn't aware of that.
I think the issue is that the additional properties required for asymmetric key cryptography (as opposed to symmetric) are hard to gain without introducing some structure.
What do mean by this? I don't think complexity classes give any provable security to asymmetric cryptography. It cannot be proven that the difficulty of breaking any of the currently used (or known?) asymmetric key cryptography is not in P (It can't even be proven to be NP-complete).
Asymmetric crypto clearly is in NPcomplete. What one can not prove yet is that some crypto system is in NPcomplete \ P (since this would imply P != NP).
To be in NP-complete a problem must both be in NP and every problem in NP must have a polynomial time reduction to it.
This means that NP-complete is fully contained in NP and in fact smaller if P!=NP.
For example P is contained in NP and if P!=NP then no problems in P are in NP-complete.
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.
The Discordians promulgated a code that might be a bit more mathematically resistant. It involves this series of steps:
CONVERSION:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
STEP 1. Write out the message (HAIL ERIS) and put all the vowels at the end (HLRSAIEI)
STEP 2. Reverse order (IEIASRLH)
STEP 3. Convert to numbers (9-5-9-1-19-18-12-8)
STEP 4. Put into numerical order (1-5-8-9-9-12-18-19)
STEP 5. Convert back to letters (AEHIILRS)
They assert 100% unbreakability, which isn't true, but on a sufficiently long message one's anagram checker might give out, and then there is the task of ordering the words so generated...
Mind you, decryption by the intended recipient is equally complex.
Not 100% unbreakable in general, but I think it does pretty well in the real world. There are plenty of messages that Eve simply can't decrypt with complete confidence. For example, she can't tell ATTACK WILL AT DAWN from ATTACK DAWN AT WILL. She'd have to resort to priors to guess which of those was intended.
On what should they be based, if not a sound foundation that lends itself to rigorously proveable statements (I carefully say only proveable, not proven) and the well developed intuition of a community of experts? To say that, because mathematicians understand and can think about something, they will be able to solve it, seems to be denying the existence of long- (and still-) unsolved elementary problems.
Are you happier with the state of symmetric crypto, which, despite relying on conjectures (like the existence of pseudo-random functions) tends not to rely on _algebraic_ ones?
Personally, I don't have particular worries about the hardness assumptions of asymmetric crypto, and I think of them a bit like I think of bitcoin (hear me out). Yes, it is certain that eventually someone will solve the discrete log problem for any given algebraic structure (either by rendering all crypto that relies on it broken, or (less likely) proving it fundamentally secure), but for now, we know that this is hard (since it has been open for a while), and we're also incentivizing people to make mathematical discoveries.
I'd also claim that the "crypto community" (at least the academic side of it) and the "technology community" are not the same, and (at least to me) often feel opposed. Cryptologists write papers filled to the brim with dense and precise mathematical assumptions and reductions; technologists skim the papers, ignore the assumptions, and implement half-assed, unaudited versions of the systems in question and claim them secure (pardon my cynicism).
As to what the community thinks about mathematical public key crypto, they hail it as the greatest innovation since sliced bread and the herald of modern cryptography. Prior to modernity, cryptography was very ad-hoc and depended on what the author's intuitions; modernity introduced precise definitions of what it meant for a system to be secure and raised the bar. It also relies heavily on the concept of a hardness reduction, i.e. a proof that breaking a cryptogrpahic primitive is at least as hard as solving a yet-unsolved math problem.
Specifically about algebraic problems, I have a (low confidence) intuition that they are unavoidable in public-key crypto precisely because of the need for an algebraic structure relating the public and private keys. With this in mind, I'd rather have algorithms which rely on known hard to solve problems (demonstrated hard by having years of mathematical effort poured into them with minimal result) to those which rely on problems no one has ever bothered to look at.
A final question: you are unhappy with public key crypto that relies on algebra; would you be happier if it relied on some other branch of mathematics? Analysis? Topology (okay, so that's still algebra)? Complexity theory (a secure cryptosystem that relied only on P!=NP would be a holy grail for several reasons, but I don't know of any attempts to find one)? Would you feel safe using a cryptosystem that was secure if and only if the Riemann Hypothesis were true? If the RH were false? The Collatz Conjecture?
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?
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.
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.
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.
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.
Matt Green's blog post discusses this possibility, and a plurality of the paper is dedicated to debunking it. To explain how, I'd have to restate stuff that's in the paper and already on this thread, so it'd be better if you just re-read it and then said what part of the arguments you found weren't persuasive.
I read the Koblitz/Menenzes paper a second time, and again it doesn't really discuss the possibility of a kleptographic vulnerability. Yes, it discusses weak curves and the possibility of extant or (NSA-internal) speculation of a classical or quantum analysis technique at length - but those are fundamentally different from a security standpoint.
A kleptographic vulnerability (one which cannot be exploited without breaking a cryptographically strong problem) is entirely different from the plain "ECC believed strong but actually weak" situation. Once the latter vulnerability is known anyone could break it, but the former vulnerability is strong even if the theoretical basis for the backdoor is discovered.
It's the same fundamental difference between building a computational-theoretical hard algorithm and security-by-obscurity. The NSA is not dumb enough to bet on their trick remaining obscure - that stuff inevitably gets rediscovered, whether it's 5 years or 20 years. But it's easy to precompute E in the DUAL_EC_DRBN algorithm, while it's cryptographically strong to try and reverse it after the fact. Trapdoor functions work like one-way secure hashes (eg SHA) by design - easy in forwards, computationally infeasible (as a design goal) in reverse.
The patent on the concept of using that as a backdoor (although not in that exact phrasing) was filed in Jan 2005 [1] (years before the selection of the NIST curves in FIPS 186-3) and it's reasonable to believe the NSA would know of the existence of the backdoor since the filing at a minimum - if not before. It was published for public comment in 2007 [1] but didn't gain much publicity until granted in 2013(!) [2] after Snowden had gotten the disclosure train rolling.
If you have a specific page/paragraph reference you'd like to cite: please do, it's a topic I feel strongly about since the consequences of a compromised kleptographic backdoor could be rather extreme for anyone who uses those curves.
Dual EC specifies two standard curve points. The "kleptographic" back door is the relationship between them, i.e. the knowledge of d in the equation P = dQ. This hidden relationship was apparent to cryptographers pretty quickly, see http://rump2007.cr.yp.to/15-shumow.pdf.
What would it mean for a curve to have a "kleptographic" back door? Only one base point P is defined in the curve parameters, so there is no hidden relationship to take advantage of. It is possible there are weaknesses in the NIST curves, but if so:
1. They must lie in the curve parameters themselves, i.e. something anyone could conceivably discover.
2. They must rely on a significant advance in ECDLP, e.g. a new class of weak curve.
What if the NIST curves were backdoored not by the NSA as a whole, but a rogue individual within the NSA, with the goal of making that backdoor available to a foreign power and/or the highest bidder?
It seems unlikely to me, because the NSA has so many brilliant people working for them, but it also seems like (at least superficially) it would explain just about every element of their reaction to this situation. They're used to being years or decades ahead of everyone else (e.g. differential cryptanalysis), and being caught off-guard would be an uncomfortable position for them.
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.
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.
The problem is fundamentally that the most top-security ever possible is an offline piece of paper locked in a Mission Impossible-resistant bankvault that only the President has the capability to open.
But then you can't actually use it to do anything and its existence is purely a downside. And you can't put it online - in any fashion - without exposing it to some possibility of compromise. Whether that's by one-or-more sysadmins who take a massive bribe (compromising two decades of SCI-level USG secrets => name a number and we'll pay in Billions), or users who can perform sidechannel attacks, and so on.
Everyone knows what happens once you expose real systems to real users/admins (should be read as "attackers"). You cannot design a black box that miraculously requires no administration and is not vulnerable to any sidechannel attack when your threat category is state-level actors.
I actually suspect the NSA does fall into the category of "altruistic actors" here. Their number-one concern is making sure that nobody can decrypt the things that nobody should be reading. I don't think they're above pulling a kleptographic backdoor if there's a computationally-strong guarantee that nobody else can break it (perhaps while learning a hard lesson about socially-strong security) but at the end of the day I do trust that they won't be broadcasting State Secrets in something that will be publically accessible within a decade.
When dealing with a state actor like the NSA you need to reverse Hanlon's Razor - they may be malicious, but they're not stupid. They know when the jig is up and it's time to cut their losses.
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.
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.
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?
Loosely speaking, you need n + epsilon qubits and 4n^3 operations to break RSA-n, whereas you need ~6n qubits and 360n^3 operations to break ECC-n. For n = 256, you need around 1536 qubits, whereas you need at least 3072 for RSA-3072.
This suggests a criterion to reject P-256: it needs fewer than 2048 qubits to break. P-384 is above this threshold, at around 2.5k qubits. Hey, it's as good speculation as any.
Does this mean that barring a quantum-hard alternative we could get effectively quantum-hard crypto by using crazy key sizes like RSA-131072 or ECC-4096?
> However, it will require major advances in physics and engineering before quantum computing can scale significantly. When that happens, of course P-256 and P-384 will fall first. But, as the head of cybersecurity research at a major corporation put it, “after that it’s just a matter of money” before RSA-3072 is broken. At the point when P-384 is broken it would be unwise to use either ECC or RSA. It is not likely that the gap between quantum cryptanalysis of a 384-bit key and a 3072-bit key will be great enough to serve as a basis for a cryptographic strategy.
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.
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.
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.
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.
"[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.