The NSA's crypto "breakthrough" | Hacker News Reader

The NSA's crypto "breakthrough"

economist.com

78 pointsqubitsam95 comments

Breaking public-key crypto would have to be the biggest coup in SIGINT in the history of ever. Much bigger than cracking the Enigma. Just thinking about the sheer volume of internet traffic at every level and in every country that relies on the security of encryption makes the possibility of it being fundamentally broken a literal nightmare.

I don't think it has happened. But if it had, that would be the kind of secret that would go in the President's book of secrets right along with the existence of National Treasure or the Men in Black. :P Snowden would never have a clue.

Breaking RSA keys up to 1024 bits is one less-outlandish-than-some possibility.

NSA published a note advocating use of ECC in 2009: http://www.nsa.gov/business/programs/elliptic_curve.shtml

NSA's statement wasn't "we've got an RSA-breaking machine" or anything like that; the highlights are 0) folks are using RSA-1024, which public sources only ascribe 80 bits' worth of security to, smaller than the usual margin; 1) RSA gets slow with long keys: according to public sources, 256-bit security requires RSA-3072, which is 64x slower than the equivalent ECC-512; 2) RSA-breaking implementations keep getting gradually better over time, whereas ECC's effort-to-break has basically stood still.

Their own ("Suite B") guidelines for use of public algorithms to protect classified data tell the US government to use ECC, not RSA. (AES-256 is fine, though.) They licensed patents for particular implementation techniques: http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography

Bruce Schneier, reacting to Bamford's statement about a cryptographic breakthrough, said: "Another option is that the NSA has built dedicated hardware capable of factoring 1024-bit numbers. There's quite a lot of RSA-1024 out there, so that would be a fruitful project. So, maybe."

(There's a lot of RSA-1024 out there partly because old 1024-bit SSL certs die hard, and people are lazy about switching to bigger keys if, for example, it would make establishing SSL sessions more expensive.)

Finally, perhaps not related to public-key crypto but really interesting, the XKeyScore deck had the bullet point "Show me all the VPN startups in country X, and give me the data so I can decrypt and discover the users" as one of the things you can tell the system to do. That could just refer to one of those protocols that everyone knows is broken but is still in use (MS-CHAP/PPTP) or to either a protocol/implementation break or something else affecting VPNs we currently think are secure.

Maybe the best argument against a crypto breakthrough is that it's clearly extremely hard (none of the brilliant mathematicians working in the open are close) whereas attacks on implementations and protocols are relatively easy. If you have a big bag of 0-days, have stolen some certificates (as Stuxnet seemed to indicate), and are inside a bunch of service providers, it seems almost redundant to put a lot of effort into factoring big numbers, unless some big technical improvement basically falls in your lap.

The Snowden comment about VPN startups has intrigued me for a while. My theory is that the NSA have filter boxes placed at the exit points of these VPNs. They sit and wait to see what pops out (at the VPN unencrypted endpoint) and then vacuum it all up. Most VPN endpoints are at major networking points. I.e London, New York, Frankfurt, etc.

It is then a simple matter of waiting for a user to leak personable identifiable information. A visit to Facebook or an email account, etc whilst connected to the VPN is all it takes, and then you can group and map browser headers (roughly) to VPN users.

Maybe they can break small key length SSL when they really need to. If there is TLS traffic of interest popping out from the VPN exit, then they store it and process it later, probably in some massive AWS compute intensive cloud service even.

VPN users have to remember that their traffic is protected from your machine as far as the VPN exit node. After that exit point onwards to the requested web server, you are as naked as before. Worse is that it lulls users into a false sense of security.

Not that NSA probably has the resources to do, and are probably doing all of it at the same time. Having smart thinkers spending time trying to come up with analytical solutions isn't that costly in comparison to a lot of other venues of attacks.

And, as a corrolary of this, you presently won't have much to fear if this break has happened, simply because the NSA would only use it _very_ sparingly, like how the allies used the Enigma break during WW2.

Of course, if the cat ever gets out of the bag, that situation would change.

Carrying on from that thought, the various mathematician-employing agencies have now had over 60 years to study the problem of "how much can we use this critical information-revealing tool without exposing its existence?" If they can identify an upper bound on "sparingly", that's immensely valuable.

During WW2, the Allies would crack messages to locate submarines.

Now killing a submarine once you know where it is, is pretty easy. The problem is finding the submarine, and explaining how you were found. To handle that, the Allies used a form of parallel construction. They would send a spotting plane over the area, to spot the sub and give a plausible reason to have located the submarine.

That just moves the problem. Now the Germans start wondering how the spotting planes seem to be so damn good at being in the right place at the right time.

Well, it would be a very well guarded secret. But even then the question is how public key crypto is broken. If they can easily generate exploits for implementations, because they know a essential implementation detail everybody else is missing, then it would be fundamentally different from being able to break RSA directly, or if they have a constructive prove of P=NP.

Remember that factoring primes isn't know to be NP Hard. There is no complexity breakthrough required, we just don't know how to do it quickly. So we don't get P=NP from any factoring breakthrough.

Depends on the breakthrough, we know that multiplication is in P and therefore factorization in NP. So a P?=NP breakthrough may or may not have consequences for integer factorization. ( Actually since I did write that, I wonder if P=NP would invalidate any public key crypto, since efficient encryption should be in P.)

Wouldn't they start moving important web sites off of SSL then? Surely they couldn't be the only ones able to exploit if they found it. Or at least, if they found it, others could theoretically as well.

Can't imagine the NSA or any agency puts anything too important on the Web in the first place.

One of the "nice" things about the NSA: they rely on pretty standard crypto--the same kind the rest of us do!--for their less sensitive, but still classified, secrets. NSA Ciphersuite B (http://en.m.wikipedia.org/wiki/NSA_Suite_B_Cryptography) is built into a lot of gov/mil communications technology. And it's just RSA, ECDHE, and so on--all that same stuff available in TLS.

In other words: if the NSA break one of these "public" algorithms, you'll be able to tell; they'll soon be picking new Suite B ciphers. (There will be a time-delay, but not of the intentional "let's capture+break foreign transmissions before scaring them away from this cipher" kind. Re-securing our own transmissions takes priority, always. Even if it was broken because of some "quantum leap"--pardon the pun--we have to assume our enemies are advancing their own tech at roughly the same rate, so if we can crack it, they can too.)

What I find really interesting about the NSA is their Suite A: classified algorithms (!) used to protect the most sensitive documents (!!) with hilariously bad security records (!!!).

Take for instance the Skipjack cipher (https://en.wikipedia.org/wiki/Skipjack_(cipher)), a Type I cipher ("endorsed by the NSA for securing classified and sensitive U.S. Government information") which was evaluated, for the purpose of security, by "some of the world's most accomplished and famous experts in combinatorics and abstract algebra", and finally declassified due to concerns expressed by other cryptographers about its security.

Biham and Shamir broke it the day after it was declassified.

They broke 16 out of 32 rounds, with an unrealistic amount of chosen-plaintext. It's not really something to write home about. Rijndael was selected as AES when the best known attack broke 7 out of 10 rounds.

They broke 31 out of 32 rounds.

In cryptography, if you break 1 bit, you've broken it. No excuse.

  Skipjack was designed using building blocks and 
  techniques that date back more than forty years.

I think it's safe to assume they have much stronger stuff now.

I'm not sure if this would be true. It's a game theory problem, surely. I'm not especially crypto-literate, but if player A has the ability to read the majority of currently encrypted comms world-wide, broadcasting that ability (by suddenly and dramatically changing their own encryption methodologies) would be a very silly move unless there was a very serious reason to believe somebody else was very close to developing the same abilities... and if they were, then they would also be changing their own encryption standards, which we haven't seen.

So it basically comes down to whether or not we 'assume our enemies are advancing their own tech at roughly the same rate.' The NSA probably has an okay idea of what 'roughly' is, and if you had this ability you wouldn't be showing your hand lightly.

Way more speculatively, I'd be curious to know whether or not it would be possible to add 'next-gen' crypto to existing practices in such a way that it might be transparent?

I also think that since this would be exploited against non-state actors as well as states changes the payouts calculations significantly. Much, if not most, of the value is derived from exploiting non-state actors (i.e. Al Qaeda) who almost certainly would not have this capability or would not be able to keep it quite if they did. By signaling to the state actor on these capabilities, they would be giving up the value of exploiting the information from the non-state actors. So, even if you believed that state actors had these capabilities, it may be better to be kept a secret between the two countries and allow low priority secrets to be exploited than to have the info publicly known and the capability lost.

There is very good reason to believe that once you have developed something someone else is close too. The reason is you found it.

If you check some scientific breakthroughs during the Cold War they were very close on the both sides in the matter of months.

Also with 5% of the world population NSA have limited talent pool. Assuming you are first to the goal in that case is ... overly confident. (Even if we correct for a lot of people that are not easy to tap in the outside populations chances are not on the NSA side). And I am sure a lot of the messages in other countries communications are fake and testing just to see if someone is snooping.

Suite B does not contain RSA.

EDIT: To your latter point, some people would consider this to be a telling fact.

Judging from the wikipedia link, Suite B does not contain a public key cypher. Which either tells us, that the NSA does not use asymmetric cyphers because they are broken. Or that they have a technical reason for it, like being able to do everything they want with key exchange, signature and symmetric cypher. So it is probably worth pointing out, that this speculations are interesting, but ultimately fruitless since we simply do not have enough information.

There's ECDH and ECDSA.

Yes, I should have read the wiki link. However my point was, that Suite B is so generic that we can not really speculate why the NSA did recommend this set of algos and not something else.

They've written up a case for ECC. More elsewhere in the comments, but a key point is "RSA's really slow if you want 2^256 security": http://www.nsa.gov/business/programs/elliptic_curve.shtml

Or non-EC DH, either. (It does include ECDH.)

Perhaps they were simply anticipating DLP progress and wanted to be future-proof?

It's more likely because you can't achieve modern security levels with cryptosystems built on the DLP or IFP at acceptable performance.

Suite B aims for 128-bit or 192-bit security levels; for comparison 1024-bit modulus RSA is currently thought to provide 73-bit security.

(The next natural question is why the internet community is still failing to widely deploy cryptosystems with appropriate security levels. I don't know. But HTTPS, OTR and DNSSEC are all built of cheese in this respect.)

It's telling that RSA is not practical to deploy at 256-bit security today.

By "our enemies" you mean enemies of the USG, I assume.

I agree with your point, but do you think they'd force widespread cipher switch across government bodies? Or leave other government entities using broken encryption so they can more easiler spy?

This depends - in reality all governments are going to be forced to realise what they used to think was security has all along simply been privacy - anyone who could tell what they were upto was too polite / disinterested to do so. He guy with the cottage across from XXX research centre does not care about the tail numbers of the planes landing at night.

But now every plane spotter has instant cross-correlation with every other one - and those secret flights stand out as being, well, private flights.

So long story short, if I did magically invent quantum computing, I would let the rest of the low grade secrets go hang. One of the 3 million (!) security cleared US personnel will throw Assange a copy soon enough - so lets use the advantage, to our advantage.

This of course means that if our security services have the brains and the political muscle, they will need to choose themselves which are the truly secret things and arrange a government in a government to keep it in shape. That's not likely to be a good thing.

as far as i understand it, ciphertext is indistinguishable from random text. and, afaik, this is true of all modern algos. so, how do you notice they switched? you don't.

you only notice once they call upon the more public parts of gov to switch to another 'secure' algo. also, NSA themselves probably use the Suite A algos that we know batshit about.

but, reality check: THIS IS ALL SPECULATION. there is no evidence that they have broken anything.

This article does a few things that make it seem poorly written. First, there's the sentence "But, analysing a particular colossal number and trying to determine whether it possesses prime factors is colossally difficult." No, it's not difficult to determine whether a large number has prime factors. The answer to that question is yes. Determining which prime numbers are factors is extremely hard, and what they should have said.

Second, they use an example from GCHQ's public key cryptography work rather than the more relevant NSA work on differential cryptanalysis, which became public knowledge in the late 1980s, was discovered by IBM in 1974, and which the NSA was already "well aware of" in 1974 [0].

[0]: https://en.wikipedia.org/wiki/Differential_cryptanalysis#His...

Totally tangential, but... I must have seen that exact same photo of NSA headquarters 100 times over the past month, at the head of every blog entry related to it.

It is too much to ask the nation's photographers just to take a few more pictures from different angles? ;) It's as bad as as the Onion's opinion on Snowden ("Nation Demands New Photograph Of Edward Snowden"):

https://www.google.com/search?safe=off&q=%22Nation+Demands+N...

It's really hard to take pictures of the NSA and I wish I was joking. When you drive past it, on say MD's Route 100, there are signs stating not to stop or take pictures and police officers with their lights on at all times on the side of the road. You can't stop here unless it's an emergency. I'm not sure about the laws that back this up but I've never tested them.

In England there's the Official Secrets Act. Signs say something like "a prohibited area as defined by the Official Secrets Act".

There has been some paranoia around photographers taking photographs in public. The London police force had to issue guidelines for their officers about correct procedure. (http://content.met.police.uk/Site/photographyadvice) (http://www.bjp-online.com/british-journal-of-photography/new...)

It's probably not a good idea to stand outside GCHQ's fence and take photos. They'll claim it's to protect secrets - the privacy and secrecy of who works for them, for example. (Because there is mostly carpark between the doughnut and the public road). I don't know if someone would get arrested, but "they" would certainly feel able to use their anti-terror powers and the experience would not be pleasant.

From your own statement, I think we can deduce that the NSA isn't too happy with having its picture taken.

It's a pity that I can't source this specifically, but I vaguely remember reading in either James Bamford's "The Shadow Factory" [1] or his "Body of Secrets" [2] that the NSA once leased an entire office building that had been built near the edge of Fort Meade, simply because the top floors could see onto the campus.

[1] http://en.wikipedia.org/wiki/The_Shadow_Factory [2] http://en.wikipedia.org/wiki/Body_of_Secrets

Show some gratitude. You have no idea how many individuals had to sacrifice their personal lives to get that picture into the commons.

What do you mean? As far as I can tell, it is freely available on NSA's website:

http://www.nsa.gov/about/_images/pg_hi_res/nsa_aerial.jpg

It's just a joke, sorry. I'm well aware humor isn't appreciated around here and actually I understand it because humor is a slippery slope ending in reddit-style banal meme-threads, but every once in a while I can't help myself and karma be damned.

Well have a point back, gave me a chuckle. Been a long day so it was not a high bar ;-)

Perhaps it would sound better as "Many Bantha spies have given their lives to bring us that photo, General Calrissian"

(I'm sure I have that wrong - so a prize to whoever corrects the quote from memory :-)

*Bothans

Banthas are the large beasts-of-burden on Tatooine. Bothans are humanoid aliens with cat/dog-like faces. Why do I know that? I play a lot of Star Wars video and card games :)

EDIT: just googled for the quote. The full one is "Many Bothans died to bring us this information."

Oh yes ... but I now have this irresistible vision of Vader and the Emperor walking through the Death Star landing bay, with a 12 foot long haired Bantha tiptoeing behind the massed ranks of Stormtroopers trying to look inconspicuous in a red cloak and disguise

Maybe it's just me

crypto "breakthrough" post and this is the most important comment?

The Economist:

>Does the NSA have a quantum computer in the basement of its headquarters in Maryland (pictured above)? It is theoretically possible, but pretty unlikely...

A Canadian firm called D-Wave is presently selling a specialised kind of quantum computer—Lockheed Martin, an American defence giant, and Google have each bought one—but it is not suitable for this kind of work.

In-Q-Tel - "About Us"

>"We make investments in startup companies that have developed commercially-focused technologies that will provide strong, near-term advantages (within 36 months) to the IC mission. We design our strategic investments to accelerate product development and delivery for this ready-soon innovation, and specifically to help companies add capabilities needed by our customers in the Intelligence Community.

"D-Wave Systems, Inc., the World's First Commercial Quantum Computing Company, Secures $30 Million in a New Equity Round From Investors Including Bezos Expeditions and In-Q-Tel" [0]

"Burnaby, BC - Milpitas, CA - October 4, 2012 - D-Wave Systems, Inc. today announced that it has closed a $30 million round of equity funding. Bezos Expeditions and In-Q-Tel (IQT) have joined the investment round. Bezos Expeditions is the personal investment company of Jeff Bezos. IQT is the strategic investment firm that delivers innovative technology solutions in support of the missions of the U.S. Intelligence Community."

[0] http://www.dwavesys.com/en/pressreleases.html#investment_201...

The most advanced math a quantum computer has done to date is "factored 21 into 3×7, with high probability (Martín-López et al. 2012)."

Remember: companies are in the game of marketing hype to ride your scifi hopes and dreams. When you see a company saying "quantum" anything, discount their unqualified claims greatly. (Investors are not immune to being manipulated by hype. Claiming "they must be good because they have fancy investors!" provides no more weight to their ability than a hobo claiming he keeps the airplane aloft by snapping his fingers every 3.2 seconds.)

> a hobo claiming he keeps the airplane aloft by snapping his fingers every 3.2 seconds Interesting comparison :p Sounds like it might be rooted in personal experience. Is it?

I think that's for "normal" quantum computers. D-wave is a different kind of quantum computer.

The D-Wave machine is not a general quantum computer.

For example, the quantum computer that factored 21 into 3 x 7 did it by using Shor's algorithm for quantum factoring in polynomial time. The D-Wave machine cannot implement Shor's algorithm.

The D-Wave machine would be more capable on a different problem, one that maps efficiently onto the D-Wave machine's problem space. But we're talking about factoring here.

Sounds like we need a couple more Snowden's to come out from NSA.

Why? Because the government doesn't deserve to have any secret programs whatsoever? I've said it before and I'll say it again: Even if leaking XKeyscore and PRISM was morally justified, leaking the intelligence budget or leaking other programs is probably unwise. Remember that when we talk about leaking, we're talking about weakening the American government. We should at least think about the implications.

I imagine these arguments usually come from a perspective that the US should be as weak as it would be with all its cards on the table; possibly coupled with the idea that if we're spending $500b/yr on defense, going down a few rungs on the power ladder still leaves us above everyone else. It's a very populist idea--that we can trade tactical power (the kind you get from having secrets) for strategic power (the kind you get, supposedly, by having the average voter participating in the decision-making process.) Let alone that the military isn't under congress...

>weakening the American government.

There are some who believe that wasting incredible resources on military / defense is actually weakening the country in light of the fact that we have no superpower enemy with even the remote potential to match our military. This leaves us vulnerable to other novel attacks, as well as just spending ourselves into oblivion. You know, the same way we 'overcame' the USSR's military threat via the arms race when their economy could not match the pace of ours.

Yes, the US gov't should be weakened by any account; given the degree which it has overstepped its stated bounds.

Leaking the intelligence budget was probably the most justified leak. Even if you want a geopolitically strong American government, the intelligence budget tells the public how much effort the USG puts into covert programs. So without it you can not have a meaningful debate about the size of the intelligence agencies. But on the other hand, I do not believe that other agencies can infer much from it, since everybody already knows that there is a quite big budget. So even in a real politics interpretation, the budget tells other intelligence agencies, how nice the chess board is, not what strategy is played.

The American government is collecting as much data about as many humans as it can, which I find morally repugnant. I support efforts to make that more difficult, even if it weakens the American government.

Government strength is relative. Weakening the American government is equivalent to strengthening other Governments. Would you mind telling us which ones you prefer and why they are morally superior?

Several wise men have pointed out the potential foolishness of trading liberty for the pursuit of security. It's not that other countries are morally superior. It's that the government is committing morally dubious acts in my name, and I object.

Weakening the American government is equivalent to strengthening other Governments.

No, building petabyte-scale data centers to spy on you and me is what's weakening the American government. We're not the problem, right?

The NSA is like the drunk who looks for his lost keys under the lamppost, "because that's where the light is." Not only does the American government's idea of a hypersecure state not make us any more free, there's vanishingly little evidence that it accomplishes its purpose of making us any more secure.

The lack of evidence isn't surprising given that they are a spy agency. They may not be protecting the US from terrorism, but there are major geopolitical adversaries at work who have no scruples about using cyberwarfare techniques. There is something akin to the Cold War in play, and the NSA is a significant part of the US's position in that war.

Sorry, 1% of America's GDP is too much to pay for a suit-and-tie version of Anonymous.

How do you know?

We could take a 9/11 in the shorts every year, for what we spend on the tiger-proof rocks sold by the Intelligence Community.

That sounds like a fair trade considering the cost in human lives... except that there's no evidence we're "trading" anything but our own treasure and freedom.

http://youtu.be/ZmwRgTSqT9U

Except no - do you really think that prism and the budgets are really secret? Give some credit to the US adversaries.

I suppose that Snowden leaks were not a great surprise to the foreign governments.

Chances are, if this system exists it will be accessible by only a very small number of people and kept a secret from the others with obfuscation and compartmentalization. So we'd need a very specific leaker out of a small group of people. It would be akin to hoping we'll see the secrets of the "nuclear football".

Now one day over-the-counter quantum computers will probably become a reality. In that age we'll see more information on it because the secret will be no secret at all.

That might happen if you handle dry cleaning for the white house: http://newsbusters.org/blogs/brad-wilmouth/2010/10/21/abc-no...

I'm surprised they didn't mention Reagan. When he got shot the codes were lost in the hospital and found on the floor later.

What secrets about the football? It's a Haliburton aluminum suitcase with a radio, a book describing the options, and a Marine handcuffed to the end of it. This is all from Wikipedia.

From that description you should be able to build one yourself..

Indeed.. but honestly, I'm not hopeful. I would have thought that shenangians on the level going on in the NSA (for as long as they've been at it) would have led to more conscience-burdened folks blowing the whistle either in public as Snowden did, or more covertly.

But who knows. Maybe Snowden emboldened a few people who will be able to shine some light on these things in a more quiet manner.

Sounds like we need a Truth and Reconciliation Commission.

Could it instead be ASIC technology on a massive scale? This might help break some of the hashing through very specialized chips.

According to https://www.schneier.com/blog/archives/2009/09/the_doghouse_... if you built a chip that could could test a password with a single increment of a counter, and that chip was the most efficient chip theoretically possible, and you built a dyson sphere to capture all the sun's energy to run the chip, it would still take 32 years to crack a 192-bit symmetric crypto password.

ASICs may well be involved, but they'd need math advances or implementation bugs rather than just brute force.

In fact if/when someone comes up with a working attack it will probably require ASICs to run cost effectively.

Somewhat misleading title. No answers, just more questions on the topic.

Well, that's important to keep in mind:

There are no answers and there will never be, b/c:

We can never trust/accept any statements from any government, except for admissions of guilt.

There's at least two other significant possibilities:

1) There's an attack against RSA which doesn't involve factorization

2) There's an attack against AES / Serpent / Twofish

I'd say the second is considerably more likely, firstly because the one NSA quote we have on it is "cryptanalyze, or break, unfathomably complex encryption systems" - which sounds much more like a new attack like differential cryptanalysis which provides a general purpose attack against complex symmetric crypto ("unfathomly complex" sounds much more like AES than RSA).

In addition we have numerous quotes in recent days about how GCHQ is working on breaking the encryption on the Miranda hard-drive; which we now know to be a truecrypt drive.

On point 2, NSA still allows the use of AES-256 to protect top secret data: http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography

Another option could be a practical attack on 128bit RC4.

But I don't think the fact they're still using it means it hasn't been broken. Historically countries have sacrificed countless soldiers because saving them would have revealed that the enemy crypto-system had been broken.

Why is everyone assuming the NSA has to be using their own standards, behind close doors?

They don't. They use Suite A, which is an eclectic mix of proprietary algorithms. Firefly/Enhanced Firefly for key exchange (PKI), Joeski (allegedly a pair of algorithms for encrypting and decrypting other ciphers or firmware with the interesting property that encryption algorithm cannot be deduced from the decryption algorithm and vice versa), and a bunch of others. They have different algorithms depending on the specific information channel. Permanent data storage uses one (or perhaps a few), communications traffic uses others, and communications are further split depending on channel bandwidth and presumably long-term classification needs of the data.

They have to recommend Suite B to the government and military in cases where NSA validated hardware can't be used. Examples would be military communications with allies, garden variety agencies that can't afford or can't be trusted with Suite A modules.

As a rule of thumb, I don't take any article that refers to Snowden's leaks as "revelations" seriously. The only new information Snowden revealed is that their programs are called PRISM, upstream and xKeyscore; and if a journalist learned the details behind those programs from Snowden -- when they've been going on for at least a decade -- they clearly don't know much about the subject.

What a ridiculous rule of thumb: Snowden got a lot of closely held information in front of the general public. If that doesn't count as a revelation, your standards are too high.

No, he really didn't. We knew that the USA intercepted any Internet traffic they could get their hands on, and we knew that big data companies were in bed with the NSA. If the talking point is that Snowden got these facts on mainstream news, that isn't a revelation, that's marketing. "Relevation" implies the idea didn't exist beforehand.

So a revelation isn't the revealing of a secret to people who don't know the secret?

(or to put it another way: revealing a secret to a population where the vast majority do not know it)

Snowden revealed the scale of the operation too, and the depth of the rabbit hole.

Not if that information is already publicly and easily accessible to that group. If I was to post a link to an existing but obscure Wikipedia article on Hacker News, it would be as much of a "revelation" as Snowden's "revelations."

What worries me is that the breakthrough might just be a re-interpretation of the law.

In view of this "breakthrough" leak, I am now supposing that Edward Snowden is a willing participant in psy-ops.

"An all knowing deity is a cheap cop."

"algorithsm"

p=np yo

Integer factorization is currently not known to be NP complete, and is expected to not be so. Therefore, even such a breakthrough as posited in the article would have no immediate bearing on the question of P vs NP.

http://en.wikipedia.org/wiki/Integer_factorization#Difficult...

Other way round, multiplication is in P, so integer factorization is in NP. And a breakthrough in P?=NP could have implications for factorization.

> so integer factorization is in NP

I never said it wasn't.

> And a breakthrough in P?=NP could have implications for factorization.

Indeed, but what's implied in the article is that they might have made a breakthrough in factorization specifically, not in fundamental CS theory at large.

Prove it.

Reply on news.ycombinator.com