Factoring may be easier than we think
math.mit.edu
math.mit.edu
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.
It took mathematicians 357 years to prove Fermat's Last Theorem.
"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.
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.
https://leaksource.info/2014/10/17/sentry-eagle-nsa-core-sec...
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.
Last part they didn't play so well. ;)
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.]
It would be quite the bluff though.
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.
I wouldn't be so confident if I were you.
edit: spelling
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).
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.
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."
If they have succeeded wouldn't the very best thing for them to do is to appear "keen on controlling encryption"?
EDIT: Missed the sentence in the article where this is hinted at.
I see the article kindly submitted here is the equivalent of an amateur blog post, just a note posted to one personal webpage that happens to be served up by the MIT server. This is a case when the Hacker News protocol for displaying a domain for the submitted article was misleading rather than helpful. The author is gainfully employed and highly educated in related disciplines,
but he hasn't worked for a long time in this aspect of number theory, so the note is just thinking out loud, nothing more.
Dismissing his ideas because of his lack of credentials? How many software stories are upvoted despite their authors lacking PhDs in computer science?
> the Hacker News protocol for displaying a domain for the submitted article was misleading rather than helpful
Dr. Cohn is a professor at MIT in the department of mathematics.
I'm not a professional mathematician (recreational learner, at best) and part of the reason I didn't pursue a career of interesting problems like this is because I don't want to do so as a cog in academia or a spook at the NSA.
Am I wrong? Are there people who've had experiences that contradict my cynical perceptions?
http://blogs.wsj.com/atwork/2014/04/15/best-jobs-of-2014-con...
http://www.npr.org/templates/story/story.php?storyId=1001428...
There's also the possibility of new algorithms which are fast for some products of two primes, but not all. There are lots of problems, such as linear programming, where the worst case is exponential but the average case is far faster. Even something that allowed easy factoring of only 1% of products of two primes would be useful to an attacker.
If quantum stuff comes first, then we can go to lattice based systems (which are the leading candidate as far as I know - please correct me otherwise, I am familiar with lattice based systems but have not done research for a better base).
If factoring is solved first, we can stick with elliptic curves.
That's hardly a consolation, since all that we've encrypted and shared until then will be trivial to break as long as people have them in encrypted form (which is very easy to do).
So the next best case is that most of the details recovered by such breakage are irrelevent to those still alive. I think thats far more likely anyway.
His main claim is that others that say it's hard are not necessarily right either, and have no proof for that.
Even the NSA is wary of elliptic curve public key crypto; isn't ECC significantly more vulnerable to Shor's algorithm?
[1] https://www.nsa.gov/ia/programs/suiteb_cryptography/index.sh...
edit: formatting, spelling
Meanwhile: everything you can reasonably use today is broken in post-quantum world.
With Optalysys and D-Wave, I expect quantum computing to become mainstream within the next ten years.
[1] http://security.stackexchange.com/questions/48022/what-kinds...
I suggested, upthread, not using RSA (which depends on the hardness of factoring) and using ECC instead. How AES does post-quantum is not responsive to that advice.
Am I wrong? Were you just joking?
> I believe you to be wrong about the idea that tenably factoring 1024 or 2048 bit moduli implies a solution to the elliptic curve discrete modulus problem
Probably. This mathy stuff is way over my head. I'm just repeating what I read in Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer [1] published by Peter W. Shor on behalf of AT&T Research in 1995. Supposedly his proof is valid, predicated on the existence of quantum computers. Quantum computers actually exist [insert epistemological joke here].
The lack of any usable asymmetric algorithms is a much greater concern.
ECC is used with smaller bit lengths which makes it easier to get a sufficient quantum computer.
Of course I may have a fundamental misunderstanding here, and if so, I'd love to be enlightened.
Shor threatens RSA and ECC. Neither RSA nor ECC are considered post-quantum schemes. If quantum computing is really your threat model, you want to be doing what Google did: run both a pre-quantum and a post-quantum key exchange and mix the results with a KDF.
Which post-quantum approach you choose, I don't care. (I'm a quantum computing skeptic).
What you do not want to do is build a cryptosystem using solely a post-quantum key exchange algorithm, or, even worse, try to build a cryptosystem without any asymmetric key exchange at all. In both cases, implementation errors --- some of which, in the latter case, are probably inevitable --- will doom your system immediately.
I feel like the idea that you'd use ECC out of concern for advances in factoring or conventional discrete log isn't my own, but I'm not careful enough with this stuff to know the best thing to cite.
As always, I comment on crypto stuff principally to see if I can goad you into correcting me. :)
Most factorization algorithms require you to find either a loop or a quadratic congruence (mod n). What changes is the way they try to find these
https://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factori...
http://blogs.discovermagazine.com/fire-in-the-mind/2013/02/2...
...or maybe not.
As others have noted, I have no real evidence for my views. To me this is a total WTF? The author is ignorant of the subject and like so many experts outside their fields supposes that the field that has suddenly piqued their interest cannot, must not, be all that complex.
Factoring some numbers is very, very easy. Factoring other numbers is computationally hard. The consensus in the field is that there are no shortcuts. See, e.g., [1] and [2].
[1] http://www.cs.virginia.edu/~kam6zx/is-it-secure/the-hardness...
[2] https://en.wikipedia.org/wiki/Integer_factorization
Next, I shall write a brief article declaring that warp drive is likely far easier than everyone thinks. Please upvote it when I submit it to HN....