New Snowden Leak Reports 'Groundbreaking' NSA Crypto-Cracking

This could be little more than a way of making the purchase of a bunch of D-Wave boxes sound more compelling than it might really be at this time. The problem with secret organizations with no oversight is that we'll probably never know for sure.

After all, it would be fairly damning if the NSA were defending a high crypto budget by filling the document with hyperbole, just as it would be a trifle suspicious if they suddenly cut the department to a couple of well fed nerds and a years supply of sharp pencils and Mountain Dew.

The meagre sentences in this document seem to sit in the bureaucratic sweet spot of positive but vague.

Also, the proof-of-work is completed when you find a hash that begins with a specified number of zeros, and not when you reach a specific hash.

[1] http://cm.bell-labs.com/cm/cs/who/dmr/crypt.html

That source says nothing about the NSA. Is it believed the NSA invented it earlier and didn't share with GCHQ?

The "intelligence community" sponsors a lot of math and fundamental physics work in academia and the national labs. The grants are laundered through an intermediary, so you don't know who and in what agency is interested in the work. I think of that visible side as one way for them to keep their foot in the door, to check the pace of advances on the unclassified side.

But you're really asking about the classified "shadow" of that open work, which by definition is hard to measure. I think one easy yardstick is "how much a mathematician makes" versus the intelligence budget. This leads me to think that they can hire a lot of mathematicians.

And let's face it, the subject matter is really cool. There's a reason that mathematicians throughout history have been interested in coding. Now imagine someone paying them to do it.

A senior academic I knew (in the information theory area) consulted at the NSA for several summers. His work was done in a Faraday cage, and that's all he would say about it. He was top-notch in his field, and he wouldn't waste his summers with fools. I think that there are lots of similar stories.

My working belief is that, in certain areas, they are way, way ahead of the open state of the art. Like with Keyhole, or tapping fiber optic cables, etc. Not everywhere, but they don't have to be ahead everywhere, just in a few places.

Back in highschool one of my friends had an internship with the NSA. What he was doing is classified, but he is allowed to say that his work got published internally.

It's the thought that counts, right?

I think we put too much emphasis on the single data point of GCHQ inventing pgp early (IIRC)

"The NSA probably possesses cryptographic expertise many years ahead of public state of the art (in algorithms, but probably not in protocols) and can undoubtedly break many of the systems used in practise."

In 2010 former NSA technical director mentioned that they have been losing ground to their public counterparts during the last twenty years but that they would probably be still ahead of the public by "handful of years". [1]

[1] http://www.networkworld.com/news/2010/030410-rsa-cloud-secur...

I would not be surprised if the NSA had lost its advantage. In bureaucratic systems like this, where the target (advanced math) is best achieved by exorbitantly intelligent people getting lucky - the weight of a large number of mediocres can wind up becoming a drag instead of an asset.

Other interesting discussions about language usage on the AP blog - http://blog.ap.org/

You might be able to do better than that all told on the outside. You might not.

It's "don't have to worry about too much" money (though with inflation it's less that than it used to be), but not "I'm rich" money.

HTTPS, for example, depends on both crypto algorithm implementation, SSL/TLS, the responsible Certificate Authority[1], your random number generator, your OS, your hardware, and, of course, much the same list for the people at the remote end.

The other part of the problem is that, IIRC, the NSA is one of the largest employers of crypto/number-theoretic mathematicians, and from the article, this program with a 35k headcount probably has a bunch of them. Between them, and compute clusters not implausibly denominated in acres, a teeny tiny little flaw might be enough, if they think you deserve the effort.

[1] On a tangent, has anyone explored the implications of a "give us some valid certs/signing keys for $whoever and lie to everyone who asks" NSL to one of their domestic CAs? Apart from the EFF SSL-observatory or someone else maybe noticing, of course.

Absolutely not.

The algorithms rely on assumptions, and they're not at all future-proof.

One is about certain classes of mathematical problems being hard (in RSA, it's factoring numbers). We don't know whether they're hard (there's no proof; it's an "open problem").

Another is that random numbers selected in encryption are uniformly distributed and unpredictable. (In RSA, you pick two large prime numbers, p and q. If two people share a number, say my p is the same as your q, then we're both screwed. This particular assumption has been already been violated a bunch of times in the past twenty years; from the Debian OpenSSL thing, to the Android/Bitcoin thing.)

There are many other assumptions (Certificate Authorities can be trusted, etc.) that a paranoid person would have to worry about.

I think the new hotness is elliptic curve cryptography (e.g. ECDSA), but I don't understand it well enough to know if it's substantially better than the RSA implementations that are currently popular. I'd say what we have now is like a lock on the door -- it's enough to prevent the neighbour's kid from getting in, but not enough to stop a determined lockpick or the government.

But, speaking algorithmically, it is likely you can rely on a well-vetted symmetric algorithm like AES, used conservatively according to current best practices, to keep information secret during your lifetime.

Asymmetric algorithms are another matter. RSA relied on unproven assumptions that are turning out to be squishier than we might have hoped. ECC relies on assumptions that, for the moment, appear less squishy. I'm not a mathematician, so I can't have a truly informed judgement on how likely they are to remain unsquished, but the empirical history of public-key crypto means my confidence in ECC will remain well below my confidence in the likes of AES.

Which of the 2 possible breaches do you fear reprisal for more?

When we are able to attack, we must appear unable...

The amount of money you spend on one area of intelligence work versus some other area speaks volumes about your plans, priorities, capabilities, and so forth.

On the other hand, most modern encryption systems are based on the assumption that factoring is a difficult problem. Famously, quantum computers can factor numbers efficiently. So a large scale quantum computer could break current cryptosystems, but there are in fact cryptosystems (such as lattice cryptography) that are secure against quantum computers.