The documents says they are "...investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic." Not that they have achieved groundbreaking cryptanalytic capabilities.
It's common for people to suggest that the NSA is 20 years ahead of the private sector, but it's not clear how true this is. That number is commonly cited as a result of changes the NSA made to DES, which later suggested (and Don Coppersmith openly confirmed) they knew about differential cryptanalysis 20 years before Shamir published anything about it.
However, that was long before cryptography became as popular a research topic outside of government circles. There are now many other places to go to do that type of research, and based on the public payscale data available, almost all of them pay better than the NSA. Recent developments, such as their Dual Counter Mode proposal in 2001, suggest that they might not be as far ahead as they once were.
> "...investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic."
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.
It seems unlikely that a document produced to justify funding would ever offer up anything which could give anyone a moments pause before the nodding gesture sought.
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.
What if the "groundbreaking" crypto-cracking was that the NSA discovered you could trick people into cracking "bountied" SHA-256 hashes in a massively parallel operation?
It doesn't work like that. The information being hashed is the hash of the merkle tree root of all the transaction in a block, and a nonce. They are hashing data in a very specific format, not every possible bytes sequence.
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.
NSA could purchase more GPUs, FPGAs and custom designed ASICs than all the world's bitcoin miners combined for a small fraction of its $11 billion annual budget.
NSA could have its own fabs for that kind of budget. Some people believe that they do, or at one time did. My guess is that they'd probably just prefer to book a midnight run on US industry fabs these days.
Never heard of it before, here are the results of my google search for anyone interested:
The Trusted Foundry Program (TFP) was established as a joint effort between Department of Defense and National Security Agency ... in response to Deputy Secretary of Defense Paul Wolfowitz’s 2003 Defense Trusted IC Strategy memo
- Program is administered by NSA’s Trusted Access Program Office (TAPO)
- DoD component resides in the Office of the Secretary of Defense, ASD R&E and is managed by Defense Microelectronics Activity (DMEA)
By the end of the program in FY2013, DoD will have invested >$700M to ensure access to microelectronics services and manufacturing for a wide array of devices with feature sizes down to 32nm on 300 mm wafers Program Provides National Security And Defense Programs With Access To Semiconductor Integrated Circuits From Secure Sources
Besides Forte Meade, the NSA recently purchased the Sony chip fabrication plant in San Antonio (94,000-square-foot) and has business connections with many manufacturers including National Semiconductor/Texas Instruments.
So they may have built a plant in 1989 when they were 60,000 ft2 and $85M, unless that was misdirection simply to mess with the Soviets. (Notice the conveniently placed infographic right underneath the article).
Twenty-five years of Moore's law later the price and complexity of an operational chip foundry has doubled similar to transistor count. The former Sony plant is 633,000 ft2, reportedly valued as $72M and being leased at $35/ft2.
I don't see any evidence they're using it for anything other than datacenter and office space.
This is as good a thread as any to perhaps start a discussion on something that's been on my mind ever since I learnt about the NSA's penchant for hiring mathematicians and cryptographers.
How would you reasonably estimate the NSA's academic prowess when it comes to crypto/codebreaking? How does this compare to the state-of-the-art in academia?
I am less interested (but definitely so) in knowing or estimating more about how such a budget helps in deploying and building systems to collect/store intelligence information. I also wouldn't be surprised if they are fairly ahead of the curve in terms of zero-day exploits and the like.
The thing that most makes me curious is in terms of pure mathematics (like better factoring algorithms, better predictors of pseudorandomness, weaknesses in commonly used parameters or poor choice of certain elliptic curves, say).
There are few interesting pieces of information that would help
-- a rough headcount of people in positions comparable to post-docs and professors in the worldwide crypto/math community. I find it incredibly hard to imagine a mathematical breakthrough without significant training and continuous involvement in the research community. Do they get a fair share of the best mathematicians out there? Does the pay make it a fairly attractive destination?
-- whether or not they have an active "collaboration" and "internal publication" environment, once again, comparable to the dozen or so reputable conferences occurring yearly that allows for exchange of several interesting ideas across 100s of people with the express incentive in attending these conferences being discussion and collaboration.
-- how much we can extrapolate from just 2 instances (from what I know) of the NSA being a decade or more ahead of the curve (the DES S-box and public-key cryptosystem examples). What's a reasonable way, as outsiders, of starting to get a legitimate guess? Do we have more examples or at least hints of such possible examples?
(ps: I see after posting this that several other people have raised similar points in the thread. I'd love to learn more about why Bruce Schneier thought that the NSA was decades ahead in 1996 and whether he holds the same opinion in 2013)
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.
>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.
lets not forget that having friends in government intelligence (people in the shadow with strong soft powers) may be just helpful ...
>whether or not they have an active "collaboration" and "internal publication" environment.
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.
The scope of this internal publishing system and the volumes contained in it, really is one of those details I wish would leak out. The open secret is 'the NSA has a LOT more UberMaths, PolyMaths, CryptoWizards, and sundry than any other organisation' ... the unanswered question is 'Just how much work do they do advancing the classified state of the art?'
But information on the NSA's efforts to crack the encrypted portion of that traffic — which would include much of the email bouncing around the net — has remained absent
What Wired.com? Much of the email bouncing around the net and even internal networks, save for traversals like gmail-to-gmail, are NOT a portion of the encrypted traffic. It's important you report this correctly, because "the masses" are otherwise made unaware or unconcerned about the implications. "Oh, I'll just email you my passwords; I heard 'those guys' can read SMS."
A lot of SMTP server-to-server traffic is encrypted. But a lot of it isn't, and it only takes one exposed hop. So as a general rule email isn't effectively or reliably encrypted. There's probably also a lot of email traffic being carried over crackable VPN links such as PPTP.
You're certainly right. By "much" and especially in cases involving security, I don't think we can be happy with or report on the system's security with just a "majority" being all that's need to feel safe. In fact, I'd go as far to say that unless approaching 100% and without considering circumstances like those that involve an NSL, all bets are off. Circumstances concerning an NSL are another matter, and that's where we should eliminate the on-the-wire concerns and opt for PGP-like communication.
:( up until just a few years ago, I always looked at the NSA organization with a sense of awe and pride ... that we (the US) were so advanced. Now it's just a source of shame that such powerful knowledge is being directed at us, rather than used as a tool for our benefit.
To my knowledge Al Qaeda and the Boston marathon bombers didn't have an extensive domestic data gathering program, a billion-dollar data center in Bluffdale, a network of secret courts and so on.
I think observers have long assumed NSA is some number of years ahead – say, 2-30 years ahead – of openly published results in cryptanalysis and cryptosystem vulnerabilities.
Bruce Schneier wrote in Applied Cryptography, Second Edition (around 1996):
"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]
But it's really hard to assume that - that's assuming true mathematical leaps and invention. Admittedly if you put enough cryptographers on the payroll they may form their own university, but they still need the air of their peers on the outside. Imagine a cosmologist today transported 30 years back and asked to attend conferences - they would gain no inspiration.
I think we put too much emphasis on the single data point of GCHQ inventing pgp early (IIRC)
But what if there are quantitatively and qualitatively more full-time, well-funded cryptographers inside the NSA (and its collaborating sibling organizations in its close allies) than outside? They may have an internal system, with geographically-distributed schools of thought, specialties, and long-running debates, as rich and open as the outside world - just completely segregated.
At least, that's how I'd do it, if I found myself a global superpower after WW2, thanks in large part to superior signals/crypto work, and didn't want any other emergent groups to surprise me from a "higher perch" of signals omniscience.
If you keep it secret, you're well-paid for cutting-edge work that's impossible to do anywhere else. And the general mission – keeping your home country's defense and political institutions the best-informed in the world – can be quite appealing. Inside, I'm sure you hear plenty about feel-good successes: lives saved and national interests protected.
On the other hand, if you reveal the programs, you lose your job, get cut off from your professional colleagues, and likely go to jail.
There are multiple data points suggesting the NSA is/was ahead of public researchers. There's the sbox changes to DES in the 70's when differential cryptanalysis wasn't publicly discovered till the 80's. The revisions between SHA-0 and SHA-1 (the attack the changes prevent weren't found for at least 5 years). The Dual EC DRBG random number generator they supplied to NIST that many people suspect of being compromisable by NSA etc.
I would count it's development and publication as another example of the NSA being a bit ahead as it very much looks like they developed an algorithm in secret with a backdoor. I would count the fact that the public found it (after a few years) a point for public crypto research.
Well, we have at least twice as many data points as that. IBM discovered differential cryptanalysis in the early 70s, and the NSA apparently knew about it before then, and nobody else found out until the late 80s.
I don't know what organization spends the most money on cryptanalysis every year, but the NSA's gotta be near the top. It's reasonable to assume they've found important results that the public won't know of for several years.
You may be thinking of the Ellis/Cocks/Williamson[1] invention of the RSA encryption and Diffie-Hellman key-exchange algorithms several years prior to their open publication.
I remember someone here commenting that the NSA over time is becoming like any other gov't org - beholden to "other factors", i.e. political correctness, which basically amount to making their number theory recruits mediocre.
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.
Truth is that we don't know whether they are that good or just a money-eating machine. They are the largest Mathematicians contractor for sure, but that doesn't mean anything if the bureaucracy in between is humongous (as expected in most of these organizations).
Hmm, this makes sense, but I think they need to find a new neutral word - leaker seems to have moved significantly closer to "traitor" than to "whistle-blower" amongst most of the people I talk to.
Well, he admitted to as much. I think the only reason they don't call him a 'mole' in the U.S. is that he isn't still there and that is identity is known.
> The Post's article [1] doesn't detail the "groundbreaking cryptanalytic capabilities" Clapper mentions, and there's no elaboration in the portion of the document published by the paper.
Nothing really new, just a breif line mentioning groundbreaking capabilities with no explanation.
Mostly I'm surprised at the pay distribution on page 9 of the included document.
GS pay tops out around $117k. Is that how much we're paying for top level cryptography research? Do contractors like Snowden get to make $200k because that's just what their consulting firm bills for?
My understanding is that huge pay increases are in fact the primary motivation behind the shift to these quasi-private sector contracting arrangements. It's basically an accounting scheme to either "retain the brightest", or to defraud the taxpayers, depending on how you look at it.
I think it's important to remember the original motive for leaking.
The NSA was conducting operations which many people feel are out of line with the way the American government should operate. Hence, Snowden is generally viewed as a hero rather than a villain.
Even if it was morally justified to leak PRISM and XKeyScore, leaking a detailed breakdown of the budget for the entire intelligence arm of the American government seems dubious. Now every other country knows the lower bound of how much money America invests into intelligence. This document could very well be used as a justification in other countries to convince their politicians to dramatically increase their budget devoted to cyber ops / intelligence.
If you feel the PRISM and XKeyscore leaks were a good thing, you may want to consider whether this latest leak shares the same merits. It seems a difference in kind.
Compared to the rest of the HN crowd, my knowledge of crypto is very light, so I could be incorrect... But aren't most widely adopted algorithms decently future proof? To where you would sort of have to break math in order for them to be crackable, if used with a very strong password? Sure, flaws were found in RSA, etc. But does something like that have a decent chance of happening again?
> But aren't most widely adopted algorithms decently future proof?
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.
The problem is partly that you personally aren't using just a widely adopted algorithm, you're using a specific implementation layered on some monster protocol stack with weird legacy support for "Look the other way and ROT13" mode as well as AES-$Whatever.
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.
If CAs gave up valid certs/signing keys for google.com, would the fingerprint be different? And if so, would it be possible to verify the fingerprint if Google hosted it at like pki.google.com?
I've been wondering if there's a public registry of certificate fingerprints somewhere to verify you're getting the cert the domain owner knows about.
Having thought about it a little bit more, I remember there are actually a few things being done about it.
Certificate Pinning[1] (bundle your cert with Chrome/$browser)
HSTS[2] (cache the cert you receive on this connection for $num days, bitch vocally if it changes)
Convergence (Dead?) / TACK[3] (add an independent site-specific key to cross-sign the CA-provided certs, like pinning but more flexible)
And the more passive detection approach I mentioned like the SSL Observatory[4] which looks for "unexpected" changes in certs.
To finally answer your question, no, I don't think there is any sort of list. Doing essentially that without any centralised bookkeeping (I mean, why trust those guys any more than the CAs? Not to mention it'd be hard to scale) is the plan.
DNSSec might have some sort of role in there, but I'm sufficiently hazy on how it works, and you're back to trusting your registrars/registries again anyway (see recent excitement at the NYTimes for why that's not such a great idea)
They could then generate a new key for site.com, trusted by browsers that don't support cert pinning, but yes, that new key for site.com would have a different fingerprint. The only way to keep the same cert fingerprint is to get site.com's cert's private key, either by demanding it with a NSL or FISA order, or by breaking RSA (2048bit, in most cases) if the site uses RSA as almost all of them do.
Generating a new cert from a trusted CA would be caught by EFF's SSL observatory (an optional feature in the HTTPS everywhere extension) and similar efforts.
It would fail if used against a site that has its certificate's CA pinned in the browser, unless the NSA gets the CA private key for the right CA.
Therefore, if they do have CA root key(s), they wouldn't MITM all the ssl connections they can. They would use that capability sparingly.
An encryption algorithm's security is boolean - it either leaks data to third parties or it doesn't. The algorithms we use are currently not known to be compromised, but lack of proof of compromise is not proof of lack of compromise. If the NSA has found a vulnerability in AES-256 or some mathematical breakthrough that makes it possible to decrypt AES-256-encrypted data in polynomial time, or even just a side-channel attack in $POPULAR_SSL_LIBRARY, all bets are off.
Given the fact that we still following Moore's law, no crypto is future proof even if full blown quantum computation never happens. Moreover advances in Math do happen quite often, recent one is about uniformity of data after encryption functions are applied. http://news.ycombinator.com/item?id=6210852 . There was another page that showed lifetime of common ciphers, in terms of ok, partially broken, and broken, but I can't find it.
To get the regular mantra out of the way: Humans are always the weakest link.
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.
Theoretically, yes. But it's far more likely that there are bugs in the implementation (both in software and hardware.) It's just a matter of time and resources to find them.
> The Post said it withheld the rest, and kept some information out of its reporting, in consultation with the Obama administration to protect U.S. intelligence sources and methods.
Weird. Why now? They (admin) refused to do that with WikiLeaks.
Nothing that wikileaks released was even remotely as damaging as what might be in the Snowden docs. The wikileaks leaks were all Secret, Snowden is releasing Top Secret stuff. The difference is quite severe.
"Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it."
Edward Snowden, in Q&A session at The Guardian's homepage, 17 June 2013
I interpret that to mean that the NSA are not able to bring into plaintext communications that are protected by strong cryptography, unless there were exploitable mistakes in the handling of the cryptosystem.
The NSA /are/ however very capable of, for instance, gaining access to and control of a persons computer. That could be used to inspect the communications before they are encrypted or to reverse the encryption by using the keys the same way the legitimate receiver would.
Great, thanks Wired, I just had SECRET/NOFORN material open on a government unclas computer and "I have a dream..." [1].
Both from the front page of Hacker News. Both apparently potentially a violation of law (intel and copyright). This makes the third open post, "Spy Kids" [2], also on the front page, all the more premoniscient.
Who needs Kafka. Or Orwell. Or Huxley. It's all here.
It's one thing to leak documents about the NSA being in a grey area in regards to US citizens rights. But this last month or so all the articles I see here are about Snowden trying to actively 1) attempt to hurt the USA and 2) attempt to embarrass the USA.
What makes you think Snowden is doing anything at this point? What makes you think he is still in contact with reporters? He probably hastily sent them a bunch of documents when he was worried that he would be sent back the USA, and now the journalists are deciding what will be published.
>He probably hastily sent them a bunch of documents when he was worried that he would be sent back the USA
Really!? You think that's probably what he did? You believe that it's more likely than not that he got all flustered with the USA's response, and sent a bunch of documents to Greenwald that he didn't want released?
You know what's crazy about Snowden? Every time the guy releases something, people freak out.
Why? Because nobody knows exactly what he stole. The even crazier thing is, this could all be a huge misinformation campaign and nobody would notice because we're all
Snowden takes documents, gives them to press, and they release them. How do they verify their validity? Oh yeah, they can't since it's all top secret. What a grand one-way street this guy just built for a bullet proof story of his own liking.
I think it's strange nobody is questioning the veracity of the documents he's releasing. They just accept them as de facto truth.
If you have specific articles which verify the documents he released were real, I'm pretty sure the NSA would like to see those. As far as I know, the only thing that's been verified is he took a LOT of documents. Even the NSA says they have no idea what he took:
The only verification is people saying, "leaked documents confirm XYZ." There's no way to verify the documents he's releasing are in fact - REAL. It's just people saying, "Oh yeah, we thought that was true, is now confirmed with these documents." Even though all the stuff he's releasing could be total fakes and no one would be the wiser.
Wonder what exactly? For one, all official responces confirmed that the documents were real, only correcting and trying to save face on minus BS points. And the language they used (e.g using "collect" as meaning "actually checked out by humans") made it clear that they are bullshiting.
Read the wikipedia article on the prism thing. It has lots of pointers to statements by officials that confirm the existance and scope of the program. Including officials that have lied before.
I wonder what is top secret there? Those things look quite mundane to me and I don't really understand how revealing, for example, that $1 bn is spent on "mission ground stations" would hurt national security. Revealing more deep details - maybe, I can see it, but on this level it doesn't look like it should be secret at the first place.
Intelligence is like this. You piece together seemingly random information from several sources. A tells he ate pasta on Wednesday and you know he had dinner with B because B withdrew money from an ATM next to an Italian restaurant before B's partner phoned B, who, after two hours, bought a bag of diapers on a convenience store on the route between the said restaurant and B's home.
What you're talking about are details. What I'm talking about is very coarse statistics. If you knew I spent $1000 on restaurants last year, what would it tell you about my meeting with B? Probably nothing.
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.
This makes me think that it might be good to have a "security by obscurity" layer on top of the existing security layer. A big weakness of a public security protocol is that a huge government might privately crack it and tell nobody.
Not advocating non standard crypto, but if the system is at least somewhat good ( that is, not susceptible to automatic attacks), it would keep a actual human busy. And you don't loose security, assuming that the cyphertext of the obscure system is again encrypted by a well established cypher.
It's not bullet-proof, but if you are the only person evaluating the system, then you've only protected it against the attacks that you can think up, and not against the attacks the other people can think up.
Is there a reason why the groundbreaking crypto-cracking could not be a quantum computer that tries all possible passwords/keys simultaneously? (I'm no expert on this subject.)
Yes, because this is not how quantum computers work. That is, they don't perform all computation paths non deterministically and then give you the 'right' answer. The answer that you get is a composition of all paths; it is not known how to use this to solve NP-complete problems.
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.
It's common for people to suggest that the NSA is 20 years ahead of the private sector, but it's not clear how true this is. That number is commonly cited as a result of changes the NSA made to DES, which later suggested (and Don Coppersmith openly confirmed) they knew about differential cryptanalysis 20 years before Shamir published anything about it.
However, that was long before cryptography became as popular a research topic outside of government circles. There are now many other places to go to do that type of research, and based on the public payscale data available, almost all of them pay better than the NSA. Recent developments, such as their Dual Counter Mode proposal in 2001, suggest that they might not be as far ahead as they once were.