NSA may have secretly made major mathematics breakthrough

September 12, 2013 7:59 AM

If the NSA is able to break through banks' computer security, does that mean it solved the prime factorization problem? The New York Times reported recently that “the agency has circumvented or cracked much of the encryption, or digital scrambling, that guards global commerce and banking systems.” Since banks' encryption codes rely on the fact that nobody knows how to find the prime factors of really large numbers, it could mean that the NSA has found a way to do that. Or it could mean that the NSA has simply gotten lots of banks to give up their information, or found other ways around their encryption. But if they've cracked this long-standing math problem, might the secret leak? What would be the effects?
posted by Sleeper (60 comments total)

Betteridge's law of headlines is an adage that states, "Any headline which ends in a question mark can be answered by the word no."
posted by ethand at 8:02 AM on September 12, 2013 [29 favorites]

What would be the effects if this information leaked? The government would be able to spy on you.
posted by three blind mice at 8:04 AM on September 12, 2013

The government would be able to spy on you.

The government is currently spying on us. If the information leaked, third parties could break into our bank accounts.
posted by Admiral Haddock at 8:05 AM on September 12, 2013 [7 favorites]

There's a more prosaic explanation pointed out by a mathematician friend:
Are the NIST standard Elliptic curves back-doored?
posted by vacapinta at 8:07 AM on September 12, 2013 [13 favorites]

For those who are all TLDR about Vacapinta's link, I can factor any large product of two primes assuming those two primes came off a list I provided. One can only assume the NSA has at least my level of skill in operating a calculator.
posted by Kid Charlemagne at 8:11 AM on September 12, 2013 [7 favorites]

"the agency has circumvented or cracked much of the encryption"

is a somewhat sloppy interpretation of what the documents say, which is

"NSA/CSS has some capabilities against the encryption in ...".

Anyone who has looked at the sort of vulnerabilities that are public knows that there are a million possible ways to "have capabilities against" a cryptographic system without coming anywhere close to a total break on the underlying cryptographic primitives (e.g., prime factorization).
posted by kiltedtaco at 8:12 AM on September 12, 2013 [6 favorites]

This article is clickbait. The headline of this post itself is just a reiteration of one part of the body text of the articles in the FPP about the NSA's security breakthroughs.
posted by Going To Maine at 8:15 AM on September 12, 2013 [2 favorites]

If the information leaked, third parties could break into our bank accounts.

And if they gain access to the same backdoors that the NSA uses won't the result be the same? Whether RSA is cracked or not it would seem that a determined agent can already today get at the information they want. What good is encryption if there are backdoors all over the place? Solving the factorization problem would be an elegant solution, but breaking a window works pretty well too.
posted by three blind mice at 8:17 AM on September 12, 2013

I agree with the other commenters. It is much likely that the NSA has discovered or deliberately introduced an error into the methods for generating the large primes to make them less random.
posted by humanfont at 8:18 AM on September 12, 2013 [1 favorite]

I think the NSA (hi guys if you're reading) are more likely to introduce backdoors before the fact.
posted by GallonOfAlan at 8:21 AM on September 12, 2013

The answer is complex.

There are allegations that the NSA cannot break strong cryptography (if it can, this is a very closely held secret) but has recommended that banks use only strong-ish cryptography. Further, that for the secure connections that https provides, that the NSA has requested or can request the keys for a given institution's secure connections from that institution (I.e "Bank of America, here's a request for your keys"). Finally, there are allegations that the NSA bypasses secure connections by tapping into insecure "internal" data pipes that are physically external to the institution (I.e Google encrypts your connection to Gmail, but not the connection between a Google data center in San Francisco and another Google data center in Portland).
posted by zippy at 8:26 AM on September 12, 2013 [1 favorite]

While I have no doubt that the NSA is probably spending lots of money hoping to make the breakthroughs suggested by the article, it's much easier to break encryption by focusing on the implementation of encryption systems. For example, who needs to factor ridiculous primes when SSL relies upon certificate authorities?
posted by antonymous at 8:27 AM on September 12, 2013 [3 favorites]

Maybe they've just perfected quantum computing.

Or ESP.
posted by Segundus at 8:28 AM on September 12, 2013 [1 favorite]

This Daily Dot article is awful, pure uninformed speculation. Yes, it is possible that NSA has a major breakthrough that allows them to directly break RSA or other encryption algorithms. But Schneier's take on it is that the fundamental crypto math is strong and that these documents show NSA is attacking everything else around it. If there's anyone whose speculation I'd trust to be thoughtful and well informed, it's Schneier. (The Daily Dot article does admit that Schneier doesn't believe their position, but buries that at the end of a tedious explanation of how RSA works and fails to link Schneier's article.)

The big hook for the Daily Dot article is "banking systems", but it fails to quote enough context from the source NYT story to properly evaluate the statement. Here's the whole paragraph

The agency has circumvented or cracked much of the encryption, or digital scrambling, that guards global commerce and banking systems, protects sensitive data like trade secrets and medical records, and automatically secures the e-mails, Web searches, Internet chats and phone calls of Americans and others around the world, the documents show.

The NYT phrasing is stock journalism for trying to explain what crypto is to ordinary Americans. Banking is included in a laundry list of other things that readers understand are secrets that need to be protected. It seems odd to spin that into a whole theory about NSA's mathematics capabilities, unless your goal is to get clicks. In which case, mission accomplished.

Again, I'm not saying it's not possible NSA has broken RSA. They almost certainly can brute force RSA with small key sizes, and after all the Snowden leaks the entire community is deciding 1024 bit RSA keys really aren't good enough any more. But we have no evidence from Snowden's docs that there's been a fundamental math breakthrough that lets them break RSA entirely.

This ongoing NSA story is complex and enormous. Uninformed speculation hurts the public's understanding of it.
posted by Nelson at 8:33 AM on September 12, 2013 [6 favorites]

who needs to factor ridiculous primes

Factoring large prime numbers is actually really easy.
posted by ryanrs at 8:34 AM on September 12, 2013 [51 favorites]

If the information leaked, third parties could break into our bank accounts.

And there are parts of the government that aren't the NSA who use the same fundamental encryption as well, and if this supposed mathematical revelation were to leak (or even be discovered independently by someone else) they'd be just as vulnerable to third parties as the rest of us.

Assuming the military, the state department, CIA, FBI, etc, etc haven't quietly issued radical changes to their specs on securing data, I'd say it's unlikely that there's been any fundamental breakthrough.
posted by RonButNotStupid at 8:45 AM on September 12, 2013 [1 favorite]

Maybe they've just perfected quantum computing.

I Want To Believe!!!!!

(Actually, Schneier thinks that's not totally impossible, albeit highly unlikely. Can't think of very many possible breakthroughs as simultaneously exciting and terrifying as that.)
posted by graphnerd at 8:49 AM on September 12, 2013 [1 favorite]

Deployment of Flame malware included mathematical attacks on MD5 that was considered to be years ahead of what was known about the algorithm from university research. Who ever deployed Flame almost certainly understood the fact that they were giving away hints to a previously secret algorithm. Probably one factor in giving up that kind of secret is the slow transition to the SHA family, but why give up one weapon if you don't have a closet full of other weapons?

Of course, a downside to developing a magical break for RSA, AES, or SHA is holding on to that secret. More likely is the kind of break we saw with Flame, something that simplifies a problem from "impossible" to "within the scope of a multi-billion-dollar customized black-budget computing system."
posted by CBrachyrhynchos at 8:49 AM on September 12, 2013 [1 favorite]

I think the NSA (hi guys if you're reading) are more likely to introduce backdoors before the fact.

This has been the standard wisdom for the 25 years I've been keeping tabs on the crypto world. The only problem is that while the NSA may have a lock on American cryptographic talent, there are a number of large governments who could easily field teams of their own. The NSA would have to be awfully sure of their back door staying hidden...,
posted by Tell Me No Lies at 8:51 AM on September 12, 2013 [1 favorite]

Factoring large prime numbers is actually really easy.

Oh dear. I honestly can't believe I typed that.
posted by antonymous at 8:58 AM on September 12, 2013 [5 favorites]

The big hook for the Daily Dot article is "banking systems", but it fails to quote enough context from the source NYT story to properly evaluate the statement.

An earlier comment is entirely correct - "click bait". The Daily Dot is one of the worst non-UK tabloid tripe mongering hysteria portals I have seen in a long, long time. Some of the other gibberish they churn out beggars belief - like Storify triggering PTSD in people that habitually say stupid things.

I am sure they are so, like, totally, grateful to the person that linked them from here.
posted by felch at 8:58 AM on September 12, 2013

It's pretty hard to imagine that the NSA wouldn't brag about it if they'd solved prime factorization.
posted by maryr at 9:12 AM on September 12, 2013

Usually the RSA cipher is used to transmit a session key, to be used with a different cipher. If the latter cipher has been cracked, then you don't need to crack RSA (i.e. the factorization problem).

RSA is too compute-intensive for bulk data transmission.
posted by Chocolate Pickle at 9:21 AM on September 12, 2013 [1 favorite]

It's pretty hard to imagine that the NSA wouldn't brag about it if they'd solved prime factorization.

Huh? Could you point to previous examples of No Such Agency bragging about their technological breakthroughs?
posted by Nelson at 9:41 AM on September 12, 2013 [5 favorites]

It's pretty hard to imagine that the NSA wouldn't brag about it if they'd solved prime factorization.

The NSA suggested changes to the DES cipher that strengthened it against a form of attack that was not known until two decades later. Historically, they've been pretty good about not bragging.
posted by zippy at 10:21 AM on September 12, 2013 [2 favorites]

It's pretty hard to imagine that the NSA wouldn't brag about it if they'd solved prime factorization.

The purpose of the NSA is not to collect awards from the academic establishment. The whole point (the the cryptoanalytic side of the house) is to secretly break an encryption scheme and then rake in intelligence while others continue to use it. Announcing a break would be entirely counter to that mission.
posted by newdaddy at 10:25 AM on September 12, 2013

Kid Charlemagne: "I can factor any large product of two primes assuming those two primes came off a list I provided."

And the list is sufficiently small, although in the NSA's case "sufficiently small" would seem quite a large list to most of us.
posted by wierdo at 10:33 AM on September 12, 2013

We had another thread about this last week. Just how much more does the NSA know about factoring and elliptic curves? Did the NSA cook the elliptic curves used in cryptography? etc. No answers. Snowden never knew. In fact, maybe only people at IDA know, not actual NSA employees, well the NSA does subcontract out all research and development.
posted by jeffburdges at 10:48 AM on September 12, 2013 [1 favorite]

Flame uses undisclosed cryptographic techniques to precisely match the public state of the art against MD5, unveiled by Stevens and Sotirov at CCC 2008. Very different implementation, same result.

RSA1024 is known crackable if you can print wafers. The NSA can print wafers (a fact that people amusingly deny).

The mechanism that was supposed to show that the curves in the NIST ECC curves weren't backdoored, doesn't work, because it's a deterministic process across an undetermined seed. This wasn't an NSA "innovation", this apparently dates back to IEEE process from the 90's.
posted by effugas at 12:00 PM on September 12, 2013 [1 favorite]

I knew burying cash in mason jars was the way to go, but they all laughed at me....
posted by Redhush at 12:19 PM on September 12, 2013

I knew burying cash in mason jars was the way to go, but they all laughed at me...

Burying cash is ok for the short term, but for the longer term, you want to bury MONEY, not cash. Money holds its value, no matter what Central Bankers do.
posted by MikeWarot at 12:36 PM on September 12, 2013

I'd rather put this another way:

If some of the mathematicians working for the NSA have solved prime factorization, and they kept that advancement to themselves for the sole use of a national security agency rather than the good of mankind, then they would be traitors to humanity, would make their teachers and professors ashamed of them, and would be deserving of our collective contempt.
posted by JHarris at 12:45 PM on September 12, 2013 [3 favorites]

This deserves mention here, as it contends the NSA deliberately engineered weakness in the IPSEC standards while they were under development.
posted by panglos at 12:53 PM on September 12, 2013 [1 favorite]

RSA1024 is known crackable if you can print wafers. The NSA can print wafers (a fact that people amusingly deny).

What does this mean?
posted by Aizkolari at 12:58 PM on September 12, 2013

If some of the mathematicians working for the NSA have solved prime factorization, and they kept that advancement to themselves for the sole use of a national security agency rather than the good of mankind, then they would be traitors to humanity, would make their teachers and professors ashamed of them, and would be deserving of our collective contempt.

Unless of course they were only holding onto it until they could come up with a crypto scheme that it couldn't break.
posted by Tell Me No Lies at 1:01 PM on September 12, 2013 [1 favorite]

Is Betteridge's law of headlines an adage that states, "Any headline which ends in a question mark can be answered by the word no."?
posted by ersatz at 1:07 PM on September 12, 2013 [2 favorites]

RSA1024 is known crackable if you can print wafers. The NSA can print wafers (a fact that people amusingly deny).

What does this mean?

From Shamir and Tromer, On the cost of factoring RSA 1024 (pdf), RSA CryptoBytes, 2003. if you can make custom silicon wafers (chips) then you can take advantage of parallelism specific to the factoring task that reduces the cost of breaking RSA-1024 in a year from an estimated trillions of dollars to about $10m.
posted by zippy at 2:19 PM on September 12, 2013 [2 favorites]

Breaking encryption is like, what the NSA does, right? I mean, why are we even surprised? Dogs gonna bark, Quants gonna math.
posted by Annika Cicada at 2:34 PM on September 12, 2013

The "printing wafers" thing is interesting. Basically, what the NSA would do is design and fabricate their own chips instead of buying commodity. Large portions of each processor go to the ordinary housekeeping chores of being a processor, the circuitry for all the instructions, etc; if you have a chip that all it does is factor, then you don't need that other stuff.

I'm not sure about that $10M figure, if it were that cheap and easy we'd have seen other people making custom factorization hardware by now. But if you had a whole percent of the US GNP to throw behind such a project, it doesn't seem out of the question.
posted by JHarris at 2:41 PM on September 12, 2013

I'm not sure about that $10M figure, if it were that cheap and easy we'd have seen other people making custom factorization hardware by now. But if you had a whole percent of the US GNP to throw behind such a project, it doesn't seem out of the question.

There is a very strong economic (or strategic) incentive for anyone who can do this and apply it to just do it and say nothing. I believe Shamir also says there are economies of scale where you need to batch analyze multiple RSA-1024 keys that I presume not many organizations can take advantage of.

For an example of the distance from "my paper says this is possible" to "someone did this and published their achievement" there were discussions about the feasibility of cracking DES for twenty years before the EFF sponsored the construction of Deep Crack to actually do it (for about $200k in FPGA hardware).
posted by zippy at 3:15 PM on September 12, 2013

You know - we have more than enough fucking bullshit on our plate with the NSA fucking with our shit than to have stupid shits who know nothing of the technology and want to speculate about the math/science behind it bringing up all sorts of uninformed conspiracies.

It's the anti-vaxx/climate-change deniers of NSA-Crypto, and if we don't nip this shit in the bud, we're gonna have these fuckers driving people ever more to Alex Jones la-la land, when we have real concerns to actually be taking on instead. Sometimes you almost think this kind of thing is posted by the very people implementing these schemes to make the naysayers look stupid and ignorant. But then, wouldn't that start to turn me into a conspiracy theorist, then I'm turning into one who I am blaming and ripping on in the first place, which means, what, exactly?

Fuck.
Me.
posted by symbioid at 3:31 PM on September 12, 2013 [1 favorite]

If some of the mathematicians working for the NSA have solved prime factorization, and they kept that advancement to themselves for the sole use of a national security agency rather than the good of mankind, then they would be traitors to humanity, would make their teachers and professors ashamed of them, and would be deserving of our collective contempt.

Yeah, either that or they'd be doing the only even remotely responsible thing by not revealing and thus avoiding an economic, social and political calamity the likes of which the world has never seen.

You do realize the stakes involved in suddenly rendering the most common form of encryption entirely moot overnight, right?
posted by graphnerd at 3:53 PM on September 12, 2013

We know how to break the encryption it just takes a very long time or "special chips". It's been done on small examples. If you need to be more secure bump up the size of the key. But 1024 is the default on almost any program that generates keys, change that to 4096 and it's much less likely that it will be broken (this year/decade).

Now one rule of security is "Do Not write your own security software" basically because there will be bugs, WILL be bugs. Are the various encryption products bug free? Well better than most, they are generally very well checked (lots of geek mojo to the guy that finds a bug in a web server security stack) but is there a bug no one noticed? Now that I can see the NSA keeping quiet about. Well and the Chinese and Russians also.
posted by sammyo at 7:15 PM on September 12, 2013

Cryptographer Matthew Green not only quotes Schneier (the opinion of NYT counts for -nothing- in this) but goes on at some length on this, never suggesting that the math has been compromised (there is no evidence to support such speculation).

Questioning the math, in fact, is a diversion away from the evidence of attempts to subvert encryption by:

Tampering with national standards (NIST is specifically mentioned) to promote weak, or otherwise vulnerable cryptography.

Influencing standards committees to weaken protocols.

Working with hardware and software vendors to weaken encryption and random number generators.
posted by Twang at 1:09 AM on September 13, 2013 [2 favorites]

Yeah, either that or they'd be doing the only even remotely responsible thing by not revealing and thus avoiding an economic, social and political calamity the likes of which the world has never seen.

Oh please. What one person can discover, so might another. If the economy of the fucking world rests on the difficulty of solving a math problem, then the world had better choose a good one or it deserves what it gets. Anything else would asking everyone to agree not to look too hard at the man behind the curtain.

And in the twenty years since the internet hit it big, has so much really come to rely on this encryption? Shouldn't this possibility be a wakeup call that people shouldn't rely so much on it?
posted by JHarris at 2:03 AM on September 13, 2013 [1 favorite]

Schneier's blog today reports NSA Man in the Middle attacks, a way to achieve the same result without having had to make a historical mathematical breakthrough. It requires compromising a router, instead of just listening in. The NSA diverts traffic between the target and the service (whether that service is a bank or an email provider), and pretends to be the other person to each side, decrypting in between.

Right now, trust that you're actually talking to a Google server happens through a "trusted" third party, certificate authorities, who are only supposed to hand out certificates to people who really are who they say they are. But if the NSA can compromise any one of these certificate authorities, and we know of at least two such certificate authorities being compromised, then the MITM attack becomes easy.

Speculating about breaking RSA is kind of going out on the edge of plausibility; it is at the extreme realm of possibility, but unlikely, and not necessary at all to explain current revelations.
posted by Llama-Lime at 8:10 AM on September 13, 2013 [3 favorites]

And in the twenty years since the internet hit it big, has so much really come to rely on this encryption? Shouldn't this possibility be a wakeup call that people shouldn't rely so much on it?

Of course it should. But that has literally no bearing on the fact that making an insane breakthrough in prime factorization and immediately sharing the results would be inconceivably reckless.
posted by graphnerd at 12:27 PM on September 13, 2013

And to clarify: yeah, that much does rely prime factor integration being very expensive. Of that were to change, SSL would be totally meaningless (not compromised as it may currently be). By and large, that would mean that a huge portion of currently-encrypted communications would be opened up.

This would likely lead to a massive run on the banks. And absolute chaos in finance, since the concerns over corporate communications would drive people bananas. And then the cycle could spiral way out of control.

We've got plenty of reason to believe that the world has chosen an excellent math problem to maintain economic stability. But releasing a solution to that problem would (at least in the short-term) be much much more harmful than holding onto it for security purposes.
posted by graphnerd at 12:51 PM on September 13, 2013

There is probably no polynomial time algorithm for factoring, graphnerd, but..

If I encountered any algorithm that rendered existing public-key cryptography, like say a trick that handled 1024 bit RSA keys quickly, then I'd disclose it as widely and as publicly as possible. Just too much risk that governments might kill you to hush you up.

Any true "cryptographic emergency" could be resolved by News agencies all explaining the problem, temporary fixes, and announcing when longer term fixes came out.

Realistic scenario : Everyone must download a new browser that does Diffie–Hellman key exchange with 4096 bit keys, which requires like 5 seconds per connection.

Worse case scenario : All large organizations rush around trusted curriers transporting symmetric keys. Average people should stop using debit cards online. Credit card companies would become rather paranoid. We develop and deploy a symmetric key infrastructure based upon, air gapped login devices for a federated "online currier network" and Shamir's Secret Sharing. I dislike so much centralized trust, but the math is the math. Ain't catastrophic.

Would it crash the markets? Yes, but so what? Imagine all high finance stopped for six months while we deployed a symmetric key infrastructure. Ain't nearly as bad as say invading Iran.
posted by jeffburdges at 2:19 PM on September 13, 2013 [2 favorites]

But that has literally no bearing on the fact that making an insane breakthrough in prime factorization and immediately sharing the results would be inconceivably reckless.

Anything other than publicizing it would be security through obscurity.
posted by JHarris at 6:24 PM on September 13, 2013

Would it crash the markets? Yes, but so what? Imagine all high finance stopped for six months while we deployed a symmetric key infrastructure. Ain't nearly as bad as say invading Iran.

Eh, maybe I'm being super pessimistic here, but I think it would be much worse than invading Iran. I'm not a huge Wall Street defender, and I think as a whole financial services are way too large a part of the economy.

But six months without finance (or even a few weeks) would have catastrophic effects on commodities markets, which would decimate supply chains for pretty much everything. The food supply would have to revert to Victorian-era fluctuations. No one would know the price of oil, which of course means that it would both rise an insane amount and then have total price instability. And because transporting goods is such a major component of price, this would have a domino effect on all prices.

So I'm not even concerned here about stocks, bonds, derivatives, or other high-level financial instruments. Whether we like it or not, every interaction we have with the economy relies intimately upon having stable, well-functioning commodities markets. And although it seems extraordinarily unlikely that there's any end-run around the basic basic building blocks of encryption, publicizing any such discovery would cause a tremendous level of harm.

Eventually, we'd probably settle for slightly slower encryption and a noticeably less efficient Internet. But we saw a few years ago how bad the effects of a comparatively small fuckup in a single, non-commodity sector of the financial sector can be. And how long those effects can last. I wouldn't want to risk seeing the sequel.
posted by graphnerd at 8:14 AM on September 14, 2013

Anything other than publicizing it would be security through obscurity.

You're right, which would not be a tenable long-term solution. But in the short-term, it'd absolutely be preferable to the alternative.
posted by graphnerd at 8:15 AM on September 14, 2013

You're still discussing a dreamland scenario though, graphnerd. All communications amongst major financial institutions could migrate the symmetric keys extremely quickly by installing big VPN devices.

Also, physical locks remain quite effective at "keeping the honest people honest", despite being ineffective against prepared attackers. We could retask the FBI and DEA to "keep people honest" by prosecuting successful attacks on public-key connections, maybe place them under the SEC's control.

I suspect we'd lose only the encryption that protects stuff law enforcement doesn't care about, so maybe we'd lose debit cards and ATMs, credit card companies become paranoid, and maybe small stores lose their credit card processing.

Also, even your dreamland scenario, where the internet grows too dangerous for finance, still works out okay for anyone living in a nation that produces anything like what it must consume : We'd exchanges before the internet and public-key cryptography, which negotiated though high oil prices even. We've records from recent years too, so if an industry or financial sector starts screwing up badly enough, then just temporarily nationalize it, and emulate the past as best you can. American and Europe might not buy many cars, but people should not starve. I'll admit many poor nations import far too much of their food, and we'd never take their plight seriously enough to prevent starvation, which could easily outweigh the suffering from a war with Iran. In fact, if we're off in dreamlands, then Iran might take out one U.S. battle group with a nuclear warhead, forcing the U.S. to back off, meaning war causes relatively little suffering.
posted by jeffburdges at 9:53 AM on September 14, 2013 [1 favorite]

You're absolutely right that I'm talking about a total dreamland scenario. I was responding to JHarris' assertion that not revealing a hypothetical efficient solution to prime factorization would make one a "traitor to humanity".

And my point is that in the real world, things aren't as simple as "information wants to be free"-style sloganeering, and the actual effects of solving prime factorization and publicizing the results could potentially be disastrous in the short term.


(And although it's beside the point, I do find the questions of actual effects to be interesting. Obviously, I was painting the most pessimistic picture possible, I don't think that saying that we had pre-encryption markets means that we could just revert. We had societies before electricity, but that doesn't mean that the sudden loss of electricity wouldn't be catastrophic.

And I'm not all that familiar with ECC. Would solving prime factorization allow that to be cracked as well?)
posted by graphnerd at 10:35 AM on September 14, 2013

The "printing wafers" thing is interesting. Basically, what the NSA would do is design and fabricate their own chips instead of buying commodity. Large portions of each processor go to the ordinary housekeeping chores of being a processor, the circuitry for all the instructions, etc; if you have a chip that all it does is factor, then you don't need that other stuff.

I'm not sure about that $10M figure, if it were that cheap and easy we'd have seen other people making custom factorization hardware by now. But if you had a whole percent of the US GNP to throw behind such a project, it doesn't seem out of the question.

That $10M is ballpark correct if:

1. you are licensing most of the IP blocks -- for example CPU cores from ARM or MIPS (now Imagination); memory controllers etc from Synopsys etc -- rather than designing them yourself. VLSI design, integration, and verification is expensive work.

2. you are contracting out the wafer fabrication to a foundry rather than operating your own fab.

3. probably also you are contracting out wafer test and packaging to a test house, because handling unpackaged silicon is also expensive.

This "fabless" model is very typical of smaller-scale semiconductor companies; only the top tier (Intel etc) have the capital required to construct their own fabrication plants, or to generate all their own IP in-house.

Would the NSA entrust fabrication of its sooper-sekrit-RSA-factorizer wafer to the likes of (Taiwan's) TSMC? Seems unlikely, although TSMC are by far the biggest pure-play foundry by volume so most fabless semis are choosing to trust them. Seems more likely that the NSA would contract with a US-based foundry, of which there are only a few. (The conspiracy theorist in me notes that GlobalFoundries brought a plant in Saratoga, New York online last year...)

If you're building your own foundry, the ballpark is $1B.
posted by We had a deal, Kyle at 11:08 AM on September 14, 2013

You're right, which would not be a tenable long-term solution. But in the short-term, it'd absolutely be preferable to the alternative.

First, you didn't appear to be arguing short-term or long-term, but in favor of just not publishing, period, and contributing to the culture of secrecy many of us are decrying. I still disagree, but not as strongly.

Think of it this way. If you make an important but dangerous discovery, there is nothing to say that someone else, or indeed many people, have not already made it and are keeping it secret too. They could be doing this for the same reasons (in which case the only people missing out are the damn public who should know in the first place), or they could be doing it to take advantage of it, like the NSA would be, which is terrible.

Second, what are we, as a species, even here on earth for? Discovering things about the universe, and making them public for our fellow humans, that's a big thing. Why would we launch Voyager without telling anyone about it? These are major things, first-order priorities, they're axiomatic. A major math discovery would be similar; not telling it to people because of petty economic or security concerns is being a traitor to your race.

Third, math is an unusual field in that it requires little in the way of physical capital to contribute to. "Ordinary people," whoever they are, thinking on their own can still, potentially, contribute to it; they probably have to have a strong background in math, but still, all kinds of people can and do work on advancing it every day. Asking such a diverse population of people to all agree on your argument about keeping specific advances quiet is foolish; you're basically saying to be careful what you tell people about the contents of your own mind, because you might speak the world to destruction. Well, some of those people might not have such a vested interest in the status quo, so it's not a good idea to rely on the discretion of people who merely think.
posted by JHarris at 12:40 PM on September 14, 2013

Afaik, there are no expected complexity differences between ECC and RSA/DSA, graphnerd. In particular, "elliptic curve cryptography is vulnerable to a modified Shor's [quantum] algorithm for solving the discrete logarithm problem on elliptic curves." So, if you break RSA, then you'll likely break ECC soon after. Conversely, there are so many more parameters for ECC that all currently used curves could be broken without anyone expecting that RSA or even all curves for ECC are vulnerable.
posted by jeffburdges at 1:35 PM on September 14, 2013

Vaguely related : Security company says Nasdaq waited two weeks to fix XSS flaw
posted by jeffburdges at 4:41 PM on September 16, 2013

'Follow the Money': NSA Monitors Financial World. The NSA monitors banks and credit card transactions -- sometimes in apparent violation of national laws and global regulations. The European SWIFT financial transaction network is being tapped on different levels, internal documents from the US spy agency show.
posted by homunculus at 1:24 PM on September 18, 2013 [1 favorite]

Former Microsoft Privacy Chief Says He No Longer Trusts The Company

Silent Circle moving away from NIST ciphers in wake of NSA revelations
posted by jeffburdges at 9:20 AM on October 1, 2013 [1 favorite]