You can be sure that our numerate friends at the NSA have spent some quality time trying to find an efficient factoring algorithm over the past few decades.
As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. And given the stakes it's really not likely to be the possibly untested problem that this author speculates about.
> As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed.
After the Enigma was cracked, the government was terrified that the Axis would find out. If they knew they were cracked, they could change the cipher and set back the Allies significantly.
So they spent a ton of effort obscuring their own intelligence.
Whenever a decoded Enigma message told them where a U-boat would be, they sent a "spotter" boat whose job is was to be seen seeing the U-boat before it was attacked. That way there was a plausible source of information for the U-boat's location. (These spotters were so "effective", the Germans suspected there must be many more of them in the area then there actually were.)
One time they weren't able to get a spotter there in time and Churchill himself made the call to attack anyway. To cover for that and avoid arousing suspicion, they sent a radio dispatch to a fake spy thanking him for the intel, so that the message could be intercepted by the Germans.
That is just so fascinating... do you know where I could read more about this sort of thing. I don't care about time frames. Vietnam, I suspect, may have some interesting crypto treasures...
cryptonomicon by Neal Stehpens is a fiction but has a lot of this kind of thing in it. Not sure how accurate. Code book by Simon Singh. "The Man Who Never Was" is a boot I have never read but should because it's great ww2 espionage story. I'm sure others will kick in some suggestions.
No! It does not at all follow from NSA/USG's policy interests that NSA doesn't have secret factoring improvements. As the last few years of crypto research have shown, there's a big difference between having a break and being able to operationalize the break. It's plausible that NSA could have something that is tractable against an individual target, but not against massed targets. In fact: if they have a secret factoring improvement, this is the most likely shape of the problem for them.
In 1996 I asked Robert Morris Sr if he was worried that so much crypto was dependent upon factorization. "Worried? I'm not worried, but I can tell you that if US Military lives are at stake, we don't use algorithms that depend on factorization."
From that I would infer and speculate that the NSA found a pragmatic solution to factorization long ago.
> From that I would infer and speculate that the NSA found a pragmatic solution to factorization long ago.
Or they judge that a pragmatic solution is within the realm of possibility, and they don't want take the chance of being caught with their pants down. They probably have the resources to take on many extra operational costs to avoid theoretical risks. One of the quotes on his Wikipedia pages is: "Never underestimate the attention, risk, money and time that an opponent will put into reading traffic."
>As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed.
"assume with good confidence" - this is very naive.
They're not going to advertise their super secret breakthrough by acting like they no longer care about encryption. Such a secret is going to be compartmentalized in the organization etc.
Fortunately, those slides leaked. The lower levels talked about cryptanalysis and supercomputers. The TS/SCI/ECI stuff said they were backdooring crypto at the company level using FBI locally and CIA/ISA foreign. Also note their own Type 1 systems allow these ciphers with most sensitive stuff and EKMS using a variation of Photorus called Firefly. Safe bet that good implementations of the stuff still work.
That's a lot of detail, which I'm not familiar with as a causal observer, but its irrelevant.
The slides show the capabilities of one layer of the onion, but its surely naive to assume that's everything?
A total mathematical factoring break is a holy grail.
I mean, they made a hollywood movie about this! In the 90s!
Sneakers: "There isn't a government on this planet that wouldn't kill us all for that thing." Obviously, that's a movie, not real life, but the sentiment is valid.
It's possible. Yet, someone has to be able to use that stuff. The Sentry Eagle leaks showed that, as I predicted, they developed most of this stuff in Special Access Programs that compartmentalize things away from even TS clearance. Then, as capabilities are developed, people with TS/SCI clearances are briefed on one or more based on their need to know. Some are so high up they get briefed on all of them. That was Sentry Eagle:
As you can see, the descriptions represent their most guarded secrets that can do the gravest damage. There could be an extra layer that basically has that one fact in it. I doubt it given how many different angles of attack & severity these docs cover. We also saw that predicted damage adding up after the releases of such leaks. It's more believable given it's the exact kinds of things I'd expect a post-9/11 agency to be doing if they couldn't break RSA, etc. They'd do it anyway for deniability but these are so secret they'd rather let targets go to preserve them. The secrecy level was already tight enough to cover preserving RSA so long as insiders on highest levels kept quiet.
My thing with this argument is that not only would you have to keep your entire organization in the dark (possible, see response to Snowden) but also have to successfully recruit every academic in that space, nationally and internationally, in order to prevent them from also coming to the same conclusion. Yes it's possible, and the tinfoil hatter in me wants to think it's true, but there's too many moving parts for me to think it likely.
I think employees of the NSA will be used to the idea of compartmentalization.
> successfully recruit every academic
Why that ridiculously high bar?
Original article estimates 100 mathematicans have examined factoring in detail. Googling says NSA has 600 on staff. Maybe they just did a lot of work on the problem. Also, a large dedicated group may outperform the scattered efforts distributed throughout the research community.
> there's too many moving parts for me to think it likely.
Guess you're right, it'd be like as if they [insert implausibly complex project which the Snowden leaks showed they actually do.]
You're conflating the NSA with the rest of the government, namely the FBI. I believe some spokesperson from the NSA has even gone on record lately against the FBI's desires to criminalize [applied math]. The NSA is an organization that tackles the world as it is.
Compromised standards, TAOed equipment, global passive adversary, exploiting OPSEC fails. Even if the highest compartments of the NSA were able to instantly factor any RSA key, these alternative methods would still be useful for plausible deniability as well as general use by less-privileged compartments.
The FBI is lucky to receive any of the NSA's scraps (and if they did, it would be some vague tip to start looking in the right place), hence being left to push for criminalization to facilitate their actual investigations.
And that required about 357 years of mathematics to be able to prove it, as well. With the recentish GI announcement, I'm hopeful factoring and discrete log will fall within the next decade or two, but it's likely going to involve a bunch of subtle perspective shifts on several different fronts combined with new machinery in math to show.
>As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed.
I think the real issue with relating their position on legislation to their ability to break any given algorithm (Or the problem on which it is based) is this: Legislation will survive a new, more secure algorithm. Breaking one algorithm is subject to being patched out or the algorithm being entirely replaced. A broken system is a short-term investment, legislation is long-term (With the assumption that the government enforcing the legislation sticks around).
As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. And given the stakes it's really not likely to be the possibly untested problem that this author speculates about.