4 ms·
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 worri
by 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 agoyou'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 agoMaybe 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 agoIn 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 agoThe 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.
- blincoln 11y ago<tinfoilhat> 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. </tinfoilhat>
- tptacek 11y agoMatt 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.
- paulmd 11y agoI 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. [1] http://www.google.com/patents/US20070189527 http://www.google.com/patents/US20070189527 [2] https://www.google.com/patents/US8396213 https://www.google.com/patents/US8396213