It's a MITM solution that injects fake certificates, i.e. nothing groundbreaking and equivalent to compromised/corrupt CAs (which, as we know, exist and are able and willing to hand out fake intermediate certs etc. to rogue entities). The Whole CA ecosystem is broken and basically snake oil and pretty much everyone knows it.
This is likely a minority view, but I have no problem with the NSA being able to break encryption, that's in fact part of their job. Decoding encryption has long been part of their mission. I also suspect they're not alone in terms of signals intelligence groups in having this capability.
The issue to me has always been how and what data they access and store, and how it is used.
Encryption is still useful. The NSA can read your messages - but not everyone. Encryption will still protect your bank transactions and wikipedia reading. No encryption will protect you from a goverment turned Evil, and I hope you realise this. If the US government is good or evil is all a matter of perspective. War is peace, Mr O wrote, and surely there has been a lot of that going on in US foreign policy the last few decades.
I guess I'm with you on the ability to crack. Any researcher should be able to try as hard as they want, and succeed.
I draw the line at collecting everything without specific warrants, regardless of what they do with it, against their charter and the Constitution.
I draw the line at hardware backdoors for equipment that I buy, and insertion of vulnerabilities into encryption standards that I take advantage of. Or I guess I should say that take advantage of me.
I'd agree with that. I've often been wondering if where we're headed is a some kind of reform compromise. Not that I think it's ideal or right, but for example I could see the NSA having a Chinese wall around data for Americans, such that FBI and other investigators could not use data collected by the NSA, but could open their own collections with a warrant.
I'm quite opposed to what the NSA has done - but I don't see anything happening that will change it. If the recent revelations haven't done anything to stir Congress to action I don't know what will. Additionally, until and/or unless the NSA ever uses data collected this way against an American citizen in a judicial/criminal way, the courts are quite likely to find that petitioners lack any standing.
Well I also assume that many other signals intelligence agencies are collecting data. Having worked at a time for a large global PR firm, I am sure many if not most of our communications were intercepted, especially with work once done for a Chinese based phone hardware maker. I think it would be a massive mistake to assume this is a United States only issue, so far the United States is the only country to have someone leak the information.
So - yes, my most immediate legal concern is how the US government could use the data collection against me contrary to protections given. That doesn't mean there are many more and larger concerns to be thought through, I was merely speaking to one of them.
The larger issue here is that they "covertly introduce weaknesses into the encryption standards". It's not that they cleverly and fairly break encryption, it's that they sabotage the standards.
I have a problem with encryption being breakable, regardless of who's doing the breaking. I want encryption to be mathematically solid with the only option being brute-force older-than-age-of-earth time. When we get to quantum computing, then I don't know what we'll do...
Quantom computing cannot break all of crypto. Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP
> Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP
Incorrect, well mostly. The deal is that there are problems that can be done in "polynomial time" (how long it takes is not exponential in the size of they key) for a normal computer (or person); the set of these is called "P", the ones that CANNOT be done on polynomial time is "NP". And there are problems that can be done in "polynomial time" (with reasonable limits on errors) by a quantum computer; the set of these is called "BQP". If P = BQP it would mean that quantum computers can (in reasonable time) solve all the same problems that classical computers can. But in fact, P is a subset of BQP: there are problems that are "hard" for classical computers but "easy" for quantum computers.
An example of this is factoring numbers. Shor's algorithm is a way to factor numbers using a quantum computer and it runs in polynomial time. Now it isn't practical today: the biggest quantum computers in existence are hard put to factor the number "10", much less some 40-digit monstrosity. But computers only get better.
Fortunately, there are problems which are NOT in BQP -- problems that are hard even for quantum computers. And these are the ones you want (not those in NP) if you want to stymie a quantum computer.
> the ones that CANNOT be done on polynomial time is "NP".
I see you've solved one of the great open problems!
NP is defined as problems that a nondeterministic turing machine can solve in polynomial time. Imagine, if you will, a turing machine that when it "branches" always chooses the right path (Or: chooses "both" without overhead)
However a quantum machine that would be capable of post-selection is described by the more powerful class PostBQP = PP, and we know that PP includes NP, so this justifies your analogy.
I don't know much about quantum physics or quantum computing, so I may be mistaken, but it seems to me that post-selection is more of a philosophical construct than something that is physically possible, though.
I've seen post-selection demonstrated in a laboratory. It definitely isn't just a philosophical construct, except inasmuch as what it says about time making people want it to be less than real, and logic doesn't work that way.
As for whether you could make a PostBQP-capable computer, though.. I don't think so, at least in the most general case. I don't understand this nearly well enough to be sure, but from what I've heard, tricking causality like that has the problem that you're increasing the chance of your circuitry failing right along with the chance of getting the right result, and quantum computers are already hard enough.
The latter of which is exactly what a quantom computer does. The problem is that when we make a measurement, we randomly select one of the execution paths and see its result. The problem is that once we make a measurement, we would have to repeat the experiment in order to make another measurement.
But we do know that BQP \ P is non-empty, which is what I was trying to say. In fact, factoring large integers lies in BQP \ P, and is also the basis of some commonly used encryption algorithms.
No, we don't know that either. For all we know, we could have BQP = P: today, we don't know any algorithm in P to factor integers, but that's not a proof that it doesn't exist. If we had such a proof, as mcpherrinm points out this would directly lead to a proof that P != NP (since we DO know that factoring is in NP).
Also, I don't mean to pile on, but this wasn't what you were trying to say in the paragraph I quoted: in that paragraph, you said that we just had to pick problems outside BQP to make cryptography work despite quantum computers. I don't know if that's what you had in mind, but for such an algorithm to be tractable, it should at least be in NP (nobody with a deterministic computer wants to spend an exponential amount of time establishing an SSL connection): so the mathematical statement is whether NP \ BQP is non-empty. Did I miss something?
Everyone focuses on the decrypting power of quantum computing, which is warranted as it will break _modern_ cryptography (in theory). However, think about the encrypting power a quantum computer will have; being able to generate completely random keys among other facets of crypto that seem implausible with modern computers. I think it will just open the door to a whole new science of crypto we haven't reached yet.
We've seen this phenomenon, just on a smaller scale. When an encryption standard is compromised, people either switch to something stronger or face the consequences of essentially leaving their data in the open.
DES was an acceptable standard until the late 90s, but you'd be foolish to use it now. RSA is the accepted standard now, but it is said to fall within 5 years or so. At that point, people will either start paying for a license to use Elliptic curve encryption algos or something new will be found. It's a vicious cycle, but I certainly don't think encryption ends with quantum computing, but maybe disrupts it quite a bit for some time.
If we get quantum cryptography out the door in a reasonable space of time, then we can do secure one time pad exchanges on there. Doesn't matter what you throw at that, since with the right keys you can derive any message of the same length from it.
> I have no problem with the NSA being able to break encryption, that's in fact part of their job.
Their "breaking" of encryption is a combination of purposefully introducing vulnerabilities into standards, surreptitiously altering software and hardware to give the NSA a backdoor, hacking into private systems and stealing keys, etc etc.
I'm cool with an NSA super computer trying to brute force my VPN traffic to YouTube, I'm not cool with the NSA planting an engineer at a chip fab and changing designs to add a backdoor (a backdoor that could also be exploited by other actors).
I will bet good money that the NSA has never bothered to try and plant backdoors in encryption standards.
If the NSA recommends AES to the US government, but knows there's a vulnerability, then they have to assume that any adversary may be as good as whoever designed it. Which means an adversary would be perfectly capable of discovering and exploiting the weakness. Which in turn means the NSA has just made the entire US government vulnerable to foreign or non-state actors.
The same applies to anything you might imagine doing to chipmakers. Not only is there the risk of being found out (how do you explain to a talented engineer spotting a flaw in a schematic, how high up do you have to go to try and stop that leaking?) but there's the more serious risk that you've just added a backdoor to hardware you yourself need to be secure. Which again, could be discovered by an adversary and used against you.
This whole line of argument has always been speculative fiction on the part of the internet: it's looking for unicorns because you heard hoofs.
> I will bet good money that the NSA has never bothered to try and plant backdoors in encryption standards.
Did you read the article?
> By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors or by surreptitiously exploiting existing security flaws, according to the documents.
"The leaked documents" is as much detail as the article goes into. Given the history of reporting on this matter and the walking back done on all the original leaks, color me skeptical its as dramatic as it sounds and not what I said: the NSA engages in a bunch of spycraft since encryption is based on trust, trust is easy to compromise, but again: I'll bet AES encryption has no easily exploitable weaknesses, and SSL is completely secure provided you don't need to use the root chain of trust associations which all ultimately wind up at "the government".
I was wondering about AES myself. When you look at the wikipedia entry for AES it says it was "approved" by the NSA, which doesn't exactly inspire me with confidence. I don't think they would approve something that they haven't already cracked or backdoored.
The problem isn't that they're working to break encryption. The problem is that they're maliciously inserting backdoors and subverting crypto-research and publication, which puts all of our security at risk. (Not to mention runs counter to their stated mission)
It's definitely great knowing that our government is willing and able to commit pretty serious industrial espionage, and if anyone tries to do anything about it, hey, we have nukes too. Don't worry everyone, we're the good guys! We promise to send you some foreign aid after you've come to terms with your subjugation. /s
There are a couple of other issues, even if one agreed with your view:
1. They obviously can't keep their own secrets, so it's unlikely that they will do any better than keeping yours. Eventually, your data will leak out to non-NSA people.
2. By adding backdoors, they weaken the encryption. This implies that anyone with sufficient skill who goes looking for backdoors may be able to exploit the hole that the NSA opened up. This is a big deal, especially if you have secrets that you need to protect.
We cannot rely on them to be always good so we have to also have the prior, encryption to protect us if the law or law makers are not working for our best interest.
"Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology, the United States’ encryption standards body, and later by the International Organization for Standardization, which has 163 countries as members."
Wonder if it is referring to the Dual_EC_DRBG RNG.
Well, it goes on to say "Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency." The Dual_EC_DRBG vulnerability was revealed by two Microsoft researchers in 2007: http://rump2007.cr.yp.to/15-shumow.pdf
So I'd say yes, it sounds like that's what they're talking about.
Speaking of which, I'm really quite frustrated how many of these recent reports about the NSA elide the technical details. You have to read between the lines to figure out what's really going on, what weaknesses there really are.
As a matter of security, it would be better to know specifically what vulnerabilities there really are. Merely the announcement of vulnerabilities can allow a dedicated black-hat to find and exploit it; but someone who's trying to secure their system, and isn't following cryptography incredibly closely, won't know what they need to do or change to make their systems more secure against these types of attacks.
There's a reason that the security community advocates for full disclosure (or at least responsible disclosure, if it's possible to selectively disclose to a few vendors so they can do a coordinated release that fixes the vulnerability before it becomes public), in which you completely disclose a vulnerability so people aren't left guessing about it.
> Speaking of which, I'm really quite frustrated how many of these recent reports about the NSA elide the technical details.
Are you? Well please sign up to work for the NSA, learn the technical details, then go public with them. The reason that the NYTimes isn't publishing the technical details is because they DON'T KNOW THEM. (They might not publish them if they did.) They don't know them because Edward Snowden was a system administrator not a cryptography expert and he's releasing memos about the process.
> "Intelligence officials asked The Times and ProPublica not to publish this article, saying that it might prompt foreign targets to switch to new forms of encryption or communications that would be harder to collect or read. The news organizations removed some specific facts but decided to publish the article because of the value of a public debate about government actions that weaken the most powerful tools for protecting the privacy of Americans and others."
NYT, the Guardian, etc do have access to these details, but chose not to publish them.
They say that they were asked not to publish at all, but did so anyway and chose to remove some specific facts. I don't understand how you get from that to concluding that they know (and are suppressing) the particular vulnerabilities that the NSA is exploiting.
I assumed it was that and that case is puzzling but benign as the algorithm is much too slow to be chosen compared to the alternatives[1]. As far as anyone can tell this wasn't their best work:
If this story leaves you confused, join the club. I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard. It makes no sense as a trap door: It's public, and rather obvious. It makes no sense from an engineering perspective: It's too slow for anyone to willingly use it. And it makes no sense from a backwards-compatibility perspective: Swapping one random-number generator for another is easy.
Normal people don't need 256-bit symmetric encryption. That's assault encryption and should only be used on the battlefield. 40-bits is enough and anything over that should be banned.
I'm only joking, but the same argument is used against other technologies that governments seek to control/dominate.
The funny thing is 56-bit encryption is still in use in the form of PPTP with MS-CHAPv2. I bet most of the decrypted VPN traffic mentioned in the article uses that.
People don't take a 256-bit cryptoalgorithm into a middle school and kill kids with it, so I don't think the analogy works exactly. Maybe if you print it out on paper, or use a floppy disk or CD, you could cut a few people.
I suppose most people who shoot schools have no partners helping them, but at some point they may need to find information to help them carry the attacks, and encryption would help them conceal the fact that they have this information, and how much information they have.
I just think that a politician moved by the desire to do something could construe non-backdoored encryption as something that "helps the enemy."
You're right. That's why I'm introducing a bill to make it illegal to have a conversation without a certified government agent (or authorized private contractor) present. To improve citizen's security, a rider on the bill will also make it illegal to talk about, write about, or represent in interpretive dance the existence of those agents.
Ever heard about presumption of innocence? Just because you have physical capability to do something, does not give right to spy on you. Now if there is clear evidence that you are predisposed to do something, then you go to the judge and get a warrant for surveillance. And no, expectation of privacy by using strong encryption is not any kind of evidence, it is matter of personal choice/preference.
It is used to aid in the creation and distribution of child pornography, so the analogy is exact - unless of course you don't view the molestation of those middle schoolers to be an attack on them (as the downvotes seem to indicate).
The ability to defend one's self is a basic function. Being dangerous can be useful. Encryption is a tool for guarding privacy, and weapons are tools for guarding against physical threats.
Not having widespread access to firearms in a society doesn't imply that its citizens are defenceless. I.e. some societies skew towards longer-term strategies like reducing desperation or increasing self-control.
There is a cost to having a society saturated with firearms. The vivid, individualistic, but rarely used benefit of personal defence has to be weighed against the boring, common case of excessive violence and escalation due to access to and glamorization of firearms.
In a sense, yes. In fact, it is good that they put the effort into breaking these systems, and good that Snowden let us know about it. Now we know that the vulnerabilities exist, we can go about fixing it.
Why are you surprised, or even disgusted? They've moved on from governments (http://www.bbc.co.uk/news/world-middle-east-23762970) to using technology to do it. I use the term "moved on" loosely, because it is still happening no doubt. The US has long used it might and influence around the world, esp Latin America, to do very questionable things and really no one has batted an eye lid apart from the little guys getting screwed over. Terrorism is the just the new guise they are using to justify their actions.
The N.S.A. hacked into target computers to snare messages before they were encrypted. And the agency used its influence as the world’s most experienced code maker to covertly introduce weaknesses into the encryption standards followed by hardware and software developers around the world.
This is mostly a confirmation of what has been supposed: No magic, mostly bribed and coerced cooperation from the people who should be keeping our communications secure.
And while it doesn't do anything for the credibility of US-based companies, N.B.: "hardware and software developers around the world."
I would assume the NSA has evaluated every plausible attack, and implemented them based on what they want to get out of it, and that they have global reach into chips, peripherals, and software.
If you are a foreign government, hostile or friendly, I don't see much of a case to made for "Naw, they wouldn't..." They would, they probably can, and the probably already did.
If you are a consumer, the main problem is the creepiness factor. Who wants to use incrementally more technology if along with it you get incrementally more surveillance?
If the source code/hardware diagrams are kept private you should assume backdoors, always, with everything. How is there any other way to know for sure otherwise?
These government agencies are obviously dug much deeper in private industry than many expected so I wouldn't put it past them
If you see the diagram, and someone else makes the chip, how do you know the diagram matches exactly with what's on the chip? Unless you can make your own chip from the diagram, you still cannot be sure.
Very valid point, and I you're right you really would have no idea. You could check on some devices if you knew enough about hardware to compare the internals and the diagram, but that is a select few people.
This is why customer-company relationships and company integrity is becoming increasingly important, and frankly not many US companies are doing well in that regard.
So does this means they have broken or fund a bug in RSA, fast enough computers to brute force or solved the P versus NP problem. In decreasing chances of possibility. I am also an encryption noob, so I gather that if they have broken a crypto then my 4096 bit files will be no more secure than 1024 bit ones. Right?
The best publicly known attacks on RSA reduce the attack time by a few orders of magnitude at best. A functional quantum CPU could reduce that by a few more orders. Your 4096-bit RSA key is still 2^3072 times harder to break, so even with reductions we're still talking about "heat death of the universe" amounts of time to brute force.
RSA has issues but as of yet hasn't yielded entirely to cryptanalysis.
As the article says, it's easier to attack the system and try to get the plaintext, or coerce you into giving up your key through legal means.
Edit: adding a link to Wikipedia's article on post-quantum crypto, it's a good place to start understanding how to answer these type of questions:
Are you sure about that? As far as I understand it, generic quantum computation would cut that '3072' in half, and using quantum computers specifically for factoring reduces problems to a low polynomial time.
Correct. Shor's algorithm renders any use of RSA... pointless.
And while there are limits to the applicability of Grover's algorithm, you're correct that it effectively cuts the number of bits in any cryptosystem it applies to in half. Which, to my nonexpert eyes, looks to be most of them.
Hmm, yes, I think I conflated the asymmetric vs symmetric cases.
Shor's algorithm is very tasty, but when the real world demonstrations at top research facilities are saying, "yes, we factored 21 into 7x3, but WITH ENTANGLEMENT"[1] it makes me think that scaling to RSA-size prime factors is still a good way off.
Listen, the US government is powerful, but building a full scale quantum crypto decoder ring in complete secrecy _decades_ ahead of everyone else? I just don't think so. Maybe I'm a sheep for not wanting to believe the government so powerful and corrupt, but the whole thing sounds like a tin foil fantasy.
I don't doubt they would if they could, though. And they've done as much as they can with present day tech: supercomputers, mass data collection, penetration of target systems, exploiting SSL's many weaknesses, tapping undersea lines, and legally strong-arming perceived threats into giving up their encryption keys. I just don't think we need to get science fiction involved.
Hey, I wasn't claiming practical quantum computers existed. Just that, at whatever point running Shor's algorithm becomes practical, RSA will be pointless.
"Your 4096-bit RSA key is still 2^3072 times harder to break,"
No, because the difficulty of breaking RSA keys doesn't scale in the same way as symmetric encryption. Integer factorisation is much easier than a brute force search of the keyspace. A 1024-bit RSA key is believed to be roughly equivalent to an 80-bit symmetric key. A 3072 bit key is about as hard to brute force as an 128-bit symmetric key.
Ah shoot, you're right. I'm an armchair crypto geek at best.
In any case, you can choose a public key exponent large enough to still make it a hard problem to crack in a reasonable amount of time. Barring some huge vulnerability in RSA that hasn't been discovered in 30 years of public scrutiny, of course.
Can someone who actually knows about encryption comment on whether it's actually physically feasible for the NSA to have actually broken, say, SSL 3.0 (which has 128 bits of entropy, IIRC) on a large scale (i.e., when you're sifting through petabytes of data on a daily basis)?
And if this were really an issue, couldn't you just use 4096-bit RSA (unless they have managed to surreptitiously insert a backdoor in it)?
Brute force is only required if there isn't a vulnerability (either in the algorithm or that the NSA has a key).
> Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”
> N.S.A. documents show that the agency maintains an internal database of encryption keys for specific commercial products, called a Key Provisioning Service, which can automatically decode many messages. If the necessary key is not in the collection, a request goes to the separate Key Recovery Service, which tries to obtain it.
It might be but it is highly dubious. However, they MIGHT have put some effort into "plugging" each implementation and planting a subtle bug in them. You never can tell.
It is not somuch the protocol what matters but the implementations.
Imagine they "rig" all those beatiful hardware RNG. Could you tell the difference?
Are you sure renowned developer X van Y is not an NSA mole?
SSL relies on a chain of trust, and it's prudent to assume that the NSA has the private keys necessary to produce valid certificates that will be accepted by the certificates that ship with Windows, OS X, Firefox, etc out of the box.
So man-in-the-middle attacks are certainly within their capability and fairly hard to detect. As to whether the NSA can passively intercept and decrypt SSL traffic, I don't know, but they may not need to.
Yes, certificate pinning would alert the user to a MITM attack, but it's not commonly used. By "hard to detect", I meant that it's impossible to see simply by examining the certificate if it's genuine, you can only detect when the certificate changes. And since SSL certs expire and are re-issued all the time, it makes it a fairly large headache to continually try and guess whether the other party changed their own cert or if you are experiencing a MITM attack.
You want to use something like TLSpool (http://www.tlspool.org) and DANE. For a browser something like Firefox's Certificate Patrol is a great solution.
It looks like there's no chance for even the slightest expectation of privacy. Even if the data is encrypted they can ask American companies to decrypt it, after all they store the encryption keys. Even if the encryption keys are stored on the client side, they can push fake updates through major browsers or straight out compel American companies to insert backdoors in their software (e.g. Google Chrome) and get access to those keys. Our reliance on these services is what most likely would need to be avoided in the pursuit of privacy, but could you live without Google Search, Google Maps, GMail, Outlook, and on and on?
The protocol itself would still seem to be safe (or rather, have safe combinations of key exchange and encryption).
But it is certainly feasible that if they manage to find cracks in popular-but-old communications protocols that they are able to automatically decrypt them, or use prior key recovery successes to bootstrap fast attacks on new communications from the same host.
What would be interesting is if NSA's own "Suite B" crypto recommendations are susceptible to these risks, as that would potentially represent a rather significant break in the U.S.'s own COMSEC, and COMSEC is one of the things NSA is very specifically tasked with ensuring are safe with no backdoors for anyone to jump through.
Backdoors in the NSA recommendations could be due to trapdoor functions that only NSA has the key for. Other parties would therefore be unable to utilize that backdoor (short of the secret being exfiltrated).
Inserting such a keyed backdoor is much more difficult to do undetected, and more limited in scope (has to be done separately for every crypto algorithm being backdoored), than introducing a flaw in a hardware or software RNG implementation.
Your self-signed 4096-bit key is probably fine. Even better, be your own CA.
People assume CAs should be trusted but it's a huge game of chicken: If the NSA can't break SSL, you have to assume that either SSL is opaque to them, which these revelations seem to contradict, or they have corrupted the CAs.
If I was in the NSA (which I am not) I would place a backdoor in the browser themselves, and since the browsers auto-update from the internet anyway, I would change the DNS provider for the machine being watched (remember the DNS settings generally default to that provided by your ISP) to point to the NSA-version of the browser, and then the user would be browsing securely, but after decryption and before display, the payload would be sent elsewhere to be collected.
I don't think this would be particulary hard either. For IE, the NSA can just get MSFT to do it. For Firefox, they can compile from source, and for Chrome, well, they can probably compile from source too, because they probably have access to the build source of Chrome, with or without GOOG mgmt knowledge.
Can anyone come up with a (technical) reason the NSA could not be doing this?
Very few people have any idea how many outbound connections their machine opens or which software is opening them. There seems to be just enough people paying attention to this that it would be caught but most people would never know.
But if they did that to everyone? Surely it would be noticed. Probably very quickly. There are a LOT of smart security researchers scouring browsers for bugs and running them in carefully controlled environments every day. Someone would also eventually notice that the production binary doesn't match the version built from source, especially for open-source browsers.
Well, it's not that simple, is it? Generally speaking, the public key algorithm used in SSL is used to protect the private key that is used to protect the data:
1) Site sends public key certificate to browser.
2) Browser verifies certificate against in-browser store.
3) Browser extracts public key from certificate.
4) Browser generates symmetric/private key.
5) Browser encrypts that symmetric key with the site's public key.
6) Browser sends encrypted symmetric key to site.
7) Site decrypts symmetric key with its private key (the one associated with its public key certificate)
8) Site and browser encrypt and decrypt data using the privately shared symmetric key.
If I break the public key algorithm(s) used in SSL, I break all of that. But we think that's tough (as in NP hard).
If I break SSL itself (find flaws in negotiation, etc.) I might be able to break all of that. That's been done a few times (SSL v1.0 is garbage; v2.0 is borked; v3.0 a little broken; only TLS 1.2 is borkless, so far. As far as we know.
If I break the symmetric algorithm(s), then I can get at the data without breaking SSL itself. But we think that's tough, too. As far as we know.
If any of the software used in any of the above is borked, then usable attack vectors may be exist. Or not. We don't know until we find them.
It's a complex box of moving parts with many potential attack vectors, many potential vulnerabilities, etc.
Who really knows if the NSA might have found a multi-vector, multi-vulnerability attack that allows them to get at a lot of encrypted data without having broken all of any one of those things.
It's purest speculation until someone with a sufficient clearance and sufficient need-to-know decides to speak out, and even then it would remain unconfirmed.
Can someone elaborate on how secure the underlying algorithms still are? Most of the NSA's "foiling" seems to be done via coercing corporations and side-channel attacks. Are TLS, AES, etc. still thought of as secure?
Can someone boil this down and tell me the same thing from the technical side? I.e. what technical barriers have they managed to break (RSA, DSA, AES, etc.) ?
So at this rate are there any encryption methods that we're pretty sure that the NSA cannot crack?
By introducing such back doors, the N.S.A. has
surreptitiously accomplished what it had failed
to do in the open. Two decades ago, officials
grew concerned about the spread of strong
encryption software like Pretty Good Privacy,
or P.G.P., designed by a programmer named Phil
Zimmermann. The Clinton administration fought
back by proposing the Clipper Chip, which
would have effectively neutered digital
encryption by ensuring that the N.S.A. always
had the key.
I feel like these kinds of articles are meant to induce a sense of hopelessness regarding the ability to push back against the NSA.
If it turns out one way functions actually don't exist, I'll give in and learn to love big brother. Withstanding that, I'll continue considering communications freedom (and all that it implies) as our manifest right and view these types of breaks as implementation errors.
You mean ability to push back _technologically_ against the NSA, right? This sort of article makes you think you can't beat the NSA tech, they will outsmart you.
What this sort of article does to me (unlike you, I make no claims to know what the article was 'meant' to do, other than report the news) is make it clear that we need to push back against the NSA _politically_ to win, make what they are doing illegal, change the gag order laws, etc. We aren't going to beat them technologically, but (for those of in the U.S.), it's theoretically a democracy, we can tell them to stop.
I've seen that argument made before, several times, in essays linked to on HN. It's a political problem, not a tech problem, that the NSA can force corporations to install back doors and give the NSA the keys.
The problem is technological, as deficiencies in relied-upon communication technologies is what have allowed surveillance to scale from human intelligence on prioritized targets to dragnet scrutiny of everybody. No matter how much effort is required, "law enforcement" will always be snooping on some suspects - what we'd like to prevent is an institutionalized fishing expedition.
You're signing up for a losing game. The myth of Democracy (tm) is another layer of control over individuals.
1. Most people will never have a problem with what the NSA is doing. They support the NSA's goals (tautology, since as you've mentioned, it is responsible to the majority), and if its methods end up causing harm to enough people, they will simply be adjusted to reduce aggregate harm (not to rule out any possible harm). The feedback loop of democracy works on specific actualities, not hypothetical corner cases.
2. The most memetically fit ideas are the simplest ones that elicit the strongest feelings (see: bikeshedding). Outrage peddlers swamp the political reception bandwidth with lowest common denominator controversy - usually judgments on other's lifestyles.
3. Even if there is a widespread preference to reduce the scope of the NSA, the people simply do not have the transmit bandwidth to make this preference clearly known. And they are easily led into squandering their input on the aforementioned manufactured controversy.
4. Elected figures don't actually run the government, the entrenched bureaucracy does at an imperceptible glacial pace. The elected figures run interference by making the majority believe they voted for this shit.
1) they have found/introduced a bug in encryption standards
2) they have solved a fiendishly hard math problem to which no known solution exists and on which solution there is a price of 1 mio $
working in dev i assume (1) is several orders of magnitude more likely.
Because strong encryption can be so effective, classified N.S.A. documents make clear, the agency’s success depends on working with Internet companies — by getting their voluntary collaboration, forcing their cooperation with court orders or surreptitiously stealing their encryption keys or altering their software or hardware.
That's the money quote there- the NSA hasn't cracked encryption. They've just put back doors in.
And we can't even be that angry at the (e.g.) Microsoft execs that authorise the back doors- they potentially face jail time if they resist NSA requests. All the while presumably not able to talk about the requests publicly.
That's the quote that jumped out at me too. The solution for those who want to stay out of NSA's reach is to use your own hardware, and use open source software (where it's hard to put a backdoor without being discovered) and strong encryption.
Remember when Microsoft would trash Linux because it was open source and "not secure." Well, this settles it. Using your own hardware and open source software helps but someone determined will still get in...
The following isn't directly applicable to your suggestion, but it's a reminder that an FPGA, just like a CPU, may not be doing exactly and only what you told it to do:
> Abstract. This paper is a short summary of the first real world detection of a backdoor in a military grade FPGA. [....] The backdoor was found to exist on the silicon itself, it was not present in any firmware loaded onto the chip. [....]
I don't agree with RMS on much, but this just goes to show that calling people "extremist" is a logical fallacy. There is only correct and incorrect, and the margin by which something deviates from a commonly accepted norm is irrelevant to judging that.
That's a false sense of security. You can inspect every line of code in SSL but unless you are a world-class cryptographer yourself, how will you spot a backdoor in the algorithm?
It's a bit harder to sneak in junk in open source projects. You can see the checkins. However, you are right, if the flaw is in the algorithm itself, it's hopeless.
Is it harder to sneak in junk in open source projects? I'm reminded of Ken Thompson's Turing Award lecture, "Reflections on Trusting Trust". http://cm.bell-labs.com/who/ken/trust.html
Could someone add a backdoor to git that hides backdoors from showing up in git? Could gcc be backdoored to add backdoors to arbitrary software? How likely is it that NSA has a few zero-days lying around they could use to hack into the servers that host git or gcc or any other tool you rely on? What if they had agents among the committers and maintainers of these projects?
Security against a well-armed, well-funded, well-organized, secretive adversary is hard.
I have given some thought to this kind of thing, and one thing I realized is that the limits of the trusting trust attack can be exploited as well. Let's support you only have one compiler. Now, it is going to try to insert the worm into any compiler it compiles, right? The problem is that it must be able to detect that it is actually compiling a compiler.
This, however, is not a decidable problem. It is possible to construct a program that will fool the worm and thus you can create a compiler that you know you can trust for this test. It will probably be a hard compiler to use, but you will need it at most twice -- once to check for an attack, and if there is an attack once more to bootstrap a clean compiler.
But in order to create a disguised compiler, you need to know what method a compromised system uses to decide whether something is a compiler.
i.e., you actually have to have an example of a compromised compiler, which pretty much solves the problem in the first place.
If you decidedly don't-trust the only compiler on your system, and don't trust outside sources, the only solution is to hand-assemble a new compiler on the system, and hope that at least the hardware is trustworthy. which it isn't, necessarily.
The strength of open source lies in the number of eyes with access to the code.
Perhaps I lack the wherewithal to identify security vulnerabilities in deployed code, but there's a good chance that there are others who are able to spot said vulns.
Actually, we don't know if there's a good chance or not. All the best cryptographers in the world, who aren't already working for intelligence agencies, are reliant on government funding (i.e. they're in academia). The fact that these have gone undiscovered so long suggests that finding them will not be trivial.
Can we combine multiple algorithms such that having any one of them be secure is safe? For example, instead of encrypting with just RSA, do one pass with RSA and then another pass with ECC. Instead of just using AES, do one pass with AES, another pass with Twofish, and a third pass with RC4. Does that actually help?
You can do this but it will probably make it less secure, not more.
Nobody seems to know if the NSA actually has practical attacks against primitives like AES or SHA-2. We do know for sure that they go after higher level implementation flaws. The more complex your encryption scheme is, the more likely it is that you'll introduce a grave flaw. It only takes one.
I'd suggest that our best bet already exists: NaCl[1]. It's by Daniel Fucking Bernstein, so the implementation is as flawless as it gets. Better yet, it doesn't use a single US-approved primitive (not even the NIST curves Schneier was warning against in his Guardian piece).
Funnily, before the leaks Bernstein's use of all his own primitives was seen as a bit wacky and concerning, but now it seems almost sensible.
DJB has always been laughed off as an eccentric paranoiac, and yet as the years go by he almost always ends up being proven right. It's been kind of a funny pattern over the past few decades.
Your statement reveals a real lack of understanding of opensource. Hint; it's open to all, all includes world-class cryptographers. Each contributes their ability for the greater good of all. WCC may not spend their time coding or packaging or whatever. Others will.
Plus (form the Guardian article) there are covert agents in all the companies, presumably lifting all the certs, which may well be unauthorised, but you can't prosecute.
Prosecuting would require contacting an authority that would be willing to take the case, and would also require going public with the fact that one of your "trusted" employees had invalidated your security systems, potentially opening you up to untold amounts of liability from customers who may believe their security has been compromised.
Go ahead, call the cops and media. I hope you have a ton of money on hand and some jewelry stashed away in various locations before you do so.
Why couldn't who prosecute? That's a function of the government; a prosecutor is not obliged to engage in a case (formally, get an indictment out of a grand jury) whenever they believe a crime to have been committed.
Undercover agents at all levels of law enforcement commit apparently criminal acts every day, with no fear of prosecution. There's no reason for this to be any different.
> That's the money quote there- the NSA hasn't cracked encryption. They've just put back doors in.
It's not like they've just gotten secret keys. They've specifically gotten chip manufacturers to add backdoors to hardware, as well as significantly influenced actual cryptography standards themselves:
> "The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”
> “Eventually, N.S.A. became the sole editor,” the memo says.
I'm guessing this is what tripped up Lavabit. Mr. Levison probably didn't have the back doors and balked at being complicit once he came onto the NSA's radar.
From the article: "Intelligence officials asked The Times and ProPublica not to publish this article, saying that it might prompt foreign targets to switch to new forms of encryption or communications that would be harder to collect or read."
Also: “Properly implemented strong crypto systems are one of the few things that you can rely on,” - Snowden
I would assume that because Snowden used Lavabit & they shut down that the NSA took issue with how secure Lavabit actually was.
Isn't this the fact that NSA has access to the internet companies private key for the SSL certificate? There by giving them the tools to decrypt the initial TLS handshake and then from there you can get the symmetric key and decrypt the rest? Or is there more to it, reading the article I didn't see any hard proof of this.
It always seemed likely to me that governments can generate fake trusted certs for browser TLS traffic and then man in the middle the traffic, but what are the likely modes of attack otherwise? I don't really see what they are from this article - do they have a database of keys they have acquired nefariously?
> The documents are among more than 50,000 shared with The New York Times and ProPublica, the nonprofit news organization, by The Guardian, which has published its own article. They focus primarily on GCHQ but include thousands either from or about the N.S.A.
Is this the first time we've seen a 5-digit number to describe the number of documents Snowden has? Of course, these are just the ones used for this story...
I noticed that number as well and don't recall seeing it before, but I do seem to recall reading something about "multiple laptops" of Snowden's. Obviously, one can store a helluva lot of documents on three or four laptops.
What's truly frightening is this line from the Guardian's article on the topic:
> The NSA describes strong decryption programs as the "price of admission for the US to maintain unrestricted access to and use of cyberspace".
What does that even mean? That statement is at the same time paranoid, arrogant, and subtly threatening. It's as if to say that without the ability to decrypt interesting traffic, the NSA would be forced to take stronger measures to curtail internet traffic.
That was what caught my eye also. It seems to imply that if they can't read our Internet traffic then they'll have to take the US off the Internet. That's a pretty drastic threat.
It means there are two choices for America's participation in the global internet: decryption capabilities or America's Great Firewall.
The statement implies that in the absence of "strong decryption programs" then there would be only restricted access to and use of cyberspace. I'm sure the intelligence leadership in the US Government look at China's Great Firewall with both trepidation and admiration.
I think the key to understanding this is to remember that it was written by the NSA for the understanding of the NSA, or other highly authorized eyeballs in the government.
In many government documents, use of the name "U.S." is shorthand for the U.S. national government, not the entirety of the nation. Sometimes it is even shorthand for the particular agency that authored the document (since, in theory, they represent and act on behalf of the entire nation).
So what this internal NSA document most likely means by "unrestricted access and use" is the NSA's unrestricted access to, and use of, whatever data they want.
Think of it like a budget justification (since that is the purpose of at least half of all internal government reports). "You need to keep spending a lot of money on this program if you want us to keep getting all that data you like so much."
Look at what's happening in the UK, in Australia, in France, in Italy, in Spain... the Chinese model is winning hearts and minds of politicians everywhere, and how could it not? If you're into politics, you likely want to reach a Platonic ideal of harmonic society, where nobody is offended, nobody is threatened, and all laws are perfectly respected and enacted. You can't have that on a fully-open network. How can you keep your people from enduring child porn and Islamic propaganda, without censorship?
So most states are slowly moving towards implementing their own little firewalls. The only notable absence? The US. Despite occasional campaigns from religious nutters of various sizes and shapes and continuous pressures from commercial telcos, subsequent US administrations repeatedly affirmed that fundamental Net freedoms would not be curtailed.
This document states that such a position is not coming from idealism or even commercial convenience: it's a way to persuade the rest of the world to do business over networks and protocols that the NSA can tap at will. Should this capability be forcefully contained, there wouldn't be a political incentive to keep the Net flowing freely through US routers.
It's a perfectly reasonable and plausible position, and that's why it's so terrifying.
Completely off-base. The US has, by longstanding tradition, had a more expansive attitude towards free speech than Europe. Consider blasphemy laws in the UK, which were only abolished in 2008 but would never have been constitutional in the US. Consider laws against Holocaust denial or displaying Nazi symbols in continental Europe that would be unconstitutional in the US. In Germany you can be arrested for displaying a swastika. In the United States, the courts (in National Socialist Party of America v. Village of Skokie) allowed a Nazi group to march through a neighborhood populated largely by Jewish Holocaust survivors. None of these have to do with controlling networks. They have to do with the first amendment and with both jurisprudence and attitudes towards freedom of speech that are different in the US than in many other countries.
Maybe. In practice, however, even in the US there are and there have been censorship instruments, from the FCC all the way to Sen. McCarthy and Hoover. Today, US military personnel and civil servants are "protected" from wikileaks material by blocks at the network level. Federal pornography filters have been proposed several times, and on occasions it looked like they would become a reality. The US Constitution might be more benevolent than average on freedom of expression, but it doesn't mention TCP/IP anywhere.
> The US has, by longstanding tradition, had a more expansive attitude towards free speech than Europe...Consider laws against Holocaust denial or displaying Nazi symbols in continental Europe that would be unconstitutional in the US. In Germany you can be arrested for displaying a swastika.
These laws were included in the German constitution following the "denazification" of Germany by the USA, where Nazi symbols were banned and literature burned.
The laws against Holocaust denial and Nazi symbols were pretty much forced by the USA. It's extremely ironic how often they're mentioned as an illustration of the USA's devotion to free speech.
As someone who has been following the NSA and government monitoring of online activity for close to 15 years the Snowden leaks just keep taking the wind out of me. It's like everything that we thought might be going on was actually going on. When Theo de Raadt wrote the above mail I, like many at the time, assumed it was tinfoil hat territory. I was clearly wrong.
In that particular instance you weren't wrong[1], but that's the problem when stories like this come out, is that it makes it much harder to know what's a crazy conspiracy theory and what's real.
[1] Those claims made by Greg are completely untrue. I ran the professional services group for that company and will happily attest to whomever asks that at no time did we insert a backdoor (or anything that could even be construed as such) into IPSEC.
>Those claims made by Greg are completely untrue. I ran the professional services group for that company and will happily attest to whomever asks that at no time did we insert a backdoor (or anything that could even be construed as such) into IPSEC.
Somehow I doubt if you did that you could tell us. You might even have to lie to be able to comment on that letter at all.
I'm still unclear on the government's ability to compel falsehoods (even the discussions around National Security Letters seem to indicate that they prevent disclosure, but can't require lying), but I don't think I can convince you of that.
When all the hullabaloo around the alleged IPSEC backdoor occurred, it was frustrating to not be able to be as open about it as I wanted (not because of any government/security issues, but because at the time I still worked for the company and we were advised against talking about it).
You are free to assume that even right now as I type this, a shadowy figure in an ill-fitting Brooks Brothers suit is standing over me dictating my responses, and then chastising me for spending my time on HackerNews.
The effect of all of this is mistrust and suspicion of nearly everything. Which, compared to the alternative of implicitly trusting nearly everything, may not be a bad thing.
I'm hoping open development models(open source, peer production, peer review) end up providing the correct institutional incentives for us to innovate away the mistrust.
To misquote Linus: “given enough eyeballs, all backdoors are shallow.”
394 comments
[ 3.1 ms ] story [ 298 ms ] threadhttp://rt.com/usa/allegations-nsa-tool-decrypts-https-085/
It's a MITM solution that injects fake certificates, i.e. nothing groundbreaking and equivalent to compromised/corrupt CAs (which, as we know, exist and are able and willing to hand out fake intermediate certs etc. to rogue entities). The Whole CA ecosystem is broken and basically snake oil and pretty much everyone knows it.
The issue to me has always been how and what data they access and store, and how it is used.
I draw the line at collecting everything without specific warrants, regardless of what they do with it, against their charter and the Constitution.
I draw the line at hardware backdoors for equipment that I buy, and insertion of vulnerabilities into encryption standards that I take advantage of. Or I guess I should say that take advantage of me.
I'm quite opposed to what the NSA has done - but I don't see anything happening that will change it. If the recent revelations haven't done anything to stir Congress to action I don't know what will. Additionally, until and/or unless the NSA ever uses data collected this way against an American citizen in a judicial/criminal way, the courts are quite likely to find that petitioners lack any standing.
So - yes, my most immediate legal concern is how the US government could use the data collection against me contrary to protections given. That doesn't mean there are many more and larger concerns to be thought through, I was merely speaking to one of them.
Correct (except for the spelling of "Quantum").
> Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP
Incorrect, well mostly. The deal is that there are problems that can be done in "polynomial time" (how long it takes is not exponential in the size of they key) for a normal computer (or person); the set of these is called "P", the ones that CANNOT be done on polynomial time is "NP". And there are problems that can be done in "polynomial time" (with reasonable limits on errors) by a quantum computer; the set of these is called "BQP". If P = BQP it would mean that quantum computers can (in reasonable time) solve all the same problems that classical computers can. But in fact, P is a subset of BQP: there are problems that are "hard" for classical computers but "easy" for quantum computers.
An example of this is factoring numbers. Shor's algorithm is a way to factor numbers using a quantum computer and it runs in polynomial time. Now it isn't practical today: the biggest quantum computers in existence are hard put to factor the number "10", much less some 40-digit monstrosity. But computers only get better.
Fortunately, there are problems which are NOT in BQP -- problems that are hard even for quantum computers. And these are the ones you want (not those in NP) if you want to stymie a quantum computer.
For more details, see http://www.scottaaronson.com/papers/bqpph.pdf or frankly ANYTHING written by Scott Aaronson (http://www.scottaaronson.com/blog/).
I see you've solved one of the great open problems!
NP is defined as problems that a nondeterministic turing machine can solve in polynomial time. Imagine, if you will, a turing machine that when it "branches" always chooses the right path (Or: chooses "both" without overhead)
How sure are we that BQP != NP?
However a quantum machine that would be capable of post-selection is described by the more powerful class PostBQP = PP, and we know that PP includes NP, so this justifies your analogy.
I don't know much about quantum physics or quantum computing, so I may be mistaken, but it seems to me that post-selection is more of a philosophical construct than something that is physically possible, though.
As for whether you could make a PostBQP-capable computer, though.. I don't think so, at least in the most general case. I don't understand this nearly well enough to be sure, but from what I've heard, tricking causality like that has the problem that you're increasing the chance of your circuitry failing right along with the chance of getting the right result, and quantum computers are already hard enough.
> Fortunately, there are problems which are NOT in BQP
We don't know yet if NP \ BQP is non-empty (and neither do we know if BQP \ NP is non-empty).
Also, I don't mean to pile on, but this wasn't what you were trying to say in the paragraph I quoted: in that paragraph, you said that we just had to pick problems outside BQP to make cryptography work despite quantum computers. I don't know if that's what you had in mind, but for such an algorithm to be tractable, it should at least be in NP (nobody with a deterministic computer wants to spend an exponential amount of time establishing an SSL connection): so the mathematical statement is whether NP \ BQP is non-empty. Did I miss something?
Either everything will fall apart or we'll have wised up before hand.
DES was an acceptable standard until the late 90s, but you'd be foolish to use it now. RSA is the accepted standard now, but it is said to fall within 5 years or so. At that point, people will either start paying for a license to use Elliptic curve encryption algos or something new will be found. It's a vicious cycle, but I certainly don't think encryption ends with quantum computing, but maybe disrupts it quite a bit for some time.
Their "breaking" of encryption is a combination of purposefully introducing vulnerabilities into standards, surreptitiously altering software and hardware to give the NSA a backdoor, hacking into private systems and stealing keys, etc etc.
I'm cool with an NSA super computer trying to brute force my VPN traffic to YouTube, I'm not cool with the NSA planting an engineer at a chip fab and changing designs to add a backdoor (a backdoor that could also be exploited by other actors).
If the NSA recommends AES to the US government, but knows there's a vulnerability, then they have to assume that any adversary may be as good as whoever designed it. Which means an adversary would be perfectly capable of discovering and exploiting the weakness. Which in turn means the NSA has just made the entire US government vulnerable to foreign or non-state actors.
The same applies to anything you might imagine doing to chipmakers. Not only is there the risk of being found out (how do you explain to a talented engineer spotting a flaw in a schematic, how high up do you have to go to try and stop that leaking?) but there's the more serious risk that you've just added a backdoor to hardware you yourself need to be secure. Which again, could be discovered by an adversary and used against you.
This whole line of argument has always been speculative fiction on the part of the internet: it's looking for unicorns because you heard hoofs.
Yes, and it says this in the article.
And it makes perfect sense too. If you were the NSA, wouldn't you want a heads up if someone was talking about budget cuts?
Did you read the article?
> By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors or by surreptitiously exploiting existing security flaws, according to the documents.
Seems pretty cut and dry.
The leaked documents confirm that this is exactly what happened.
1. They obviously can't keep their own secrets, so it's unlikely that they will do any better than keeping yours. Eventually, your data will leak out to non-NSA people.
2. By adding backdoors, they weaken the encryption. This implies that anyone with sufficient skill who goes looking for backdoors may be able to exploit the hole that the NSA opened up. This is a big deal, especially if you have secrets that you need to protect.
Wonder if it is referring to the Dual_EC_DRBG RNG.
So I'd say yes, it sounds like that's what they're talking about.
Speaking of which, I'm really quite frustrated how many of these recent reports about the NSA elide the technical details. You have to read between the lines to figure out what's really going on, what weaknesses there really are.
As a matter of security, it would be better to know specifically what vulnerabilities there really are. Merely the announcement of vulnerabilities can allow a dedicated black-hat to find and exploit it; but someone who's trying to secure their system, and isn't following cryptography incredibly closely, won't know what they need to do or change to make their systems more secure against these types of attacks.
There's a reason that the security community advocates for full disclosure (or at least responsible disclosure, if it's possible to selectively disclose to a few vendors so they can do a coordinated release that fixes the vulnerability before it becomes public), in which you completely disclose a vulnerability so people aren't left guessing about it.
Are you? Well please sign up to work for the NSA, learn the technical details, then go public with them. The reason that the NYTimes isn't publishing the technical details is because they DON'T KNOW THEM. (They might not publish them if they did.) They don't know them because Edward Snowden was a system administrator not a cryptography expert and he's releasing memos about the process.
> "Intelligence officials asked The Times and ProPublica not to publish this article, saying that it might prompt foreign targets to switch to new forms of encryption or communications that would be harder to collect or read. The news organizations removed some specific facts but decided to publish the article because of the value of a public debate about government actions that weaken the most powerful tools for protecting the privacy of Americans and others."
NYT, the Guardian, etc do have access to these details, but chose not to publish them.
If this story leaves you confused, join the club. I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard. It makes no sense as a trap door: It's public, and rather obvious. It makes no sense from an engineering perspective: It's too slow for anyone to willingly use it. And it makes no sense from a backwards-compatibility perspective: Swapping one random-number generator for another is easy.
[1] http://www.schneier.com/essay-198.html
I'm only joking, but the same argument is used against other technologies that governments seek to control/dominate.
Edit: Skipjack was 80-bits I think. It was used in Clipper Phones: http://en.wikipedia.org/wiki/Skipjack_(cipher)
Edit: Devil's advocate.
I just think that a politician moved by the desire to do something could construe non-backdoored encryption as something that "helps the enemy."
:-/
They occupy exactly opposite quadrants on the useful/dangerous axis.
There is a cost to having a society saturated with firearms. The vivid, individualistic, but rarely used benefit of personal defence has to be weighed against the boring, common case of excessive violence and escalation due to access to and glamorization of firearms.
This is the part that truly disgusts me.
This is mostly a confirmation of what has been supposed: No magic, mostly bribed and coerced cooperation from the people who should be keeping our communications secure.
And while it doesn't do anything for the credibility of US-based companies, N.B.: "hardware and software developers around the world."
If you are a foreign government, hostile or friendly, I don't see much of a case to made for "Naw, they wouldn't..." They would, they probably can, and the probably already did.
If you are a consumer, the main problem is the creepiness factor. Who wants to use incrementally more technology if along with it you get incrementally more surveillance?
These government agencies are obviously dug much deeper in private industry than many expected so I wouldn't put it past them
This is why customer-company relationships and company integrity is becoming increasingly important, and frankly not many US companies are doing well in that regard.
http://www.techspot.com/news/41643-intels-sandy-bridge-proce...
RSA has issues but as of yet hasn't yielded entirely to cryptanalysis.
As the article says, it's easier to attack the system and try to get the plaintext, or coerce you into giving up your key through legal means.
Edit: adding a link to Wikipedia's article on post-quantum crypto, it's a good place to start understanding how to answer these type of questions:
http://en.wikipedia.org/wiki/Post-quantum_cryptography
And while there are limits to the applicability of Grover's algorithm, you're correct that it effectively cuts the number of bits in any cryptosystem it applies to in half. Which, to my nonexpert eyes, looks to be most of them.
Shor's algorithm is very tasty, but when the real world demonstrations at top research facilities are saying, "yes, we factored 21 into 7x3, but WITH ENTANGLEMENT"[1] it makes me think that scaling to RSA-size prime factors is still a good way off.
Listen, the US government is powerful, but building a full scale quantum crypto decoder ring in complete secrecy _decades_ ahead of everyone else? I just don't think so. Maybe I'm a sheep for not wanting to believe the government so powerful and corrupt, but the whole thing sounds like a tin foil fantasy.
I don't doubt they would if they could, though. And they've done as much as they can with present day tech: supercomputers, mass data collection, penetration of target systems, exploiting SSL's many weaknesses, tapping undersea lines, and legally strong-arming perceived threats into giving up their encryption keys. I just don't think we need to get science fiction involved.
[1] http://www.nature.com/nphoton/journal/vaop/ncurrent/full/nph...
See http://en.m.wikipedia.org/wiki/Shor's_algorithm
No, because the difficulty of breaking RSA keys doesn't scale in the same way as symmetric encryption. Integer factorisation is much easier than a brute force search of the keyspace. A 1024-bit RSA key is believed to be roughly equivalent to an 80-bit symmetric key. A 3072 bit key is about as hard to brute force as an 128-bit symmetric key.
(Source: http://www.keylength.com/en/4/ )
In any case, you can choose a public key exponent large enough to still make it a hard problem to crack in a reasonable amount of time. Barring some huge vulnerability in RSA that hasn't been discovered in 30 years of public scrutiny, of course.
And if this were really an issue, couldn't you just use 4096-bit RSA (unless they have managed to surreptitiously insert a backdoor in it)?
> Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”
> N.S.A. documents show that the agency maintains an internal database of encryption keys for specific commercial products, called a Key Provisioning Service, which can automatically decode many messages. If the necessary key is not in the collection, a request goes to the separate Key Recovery Service, which tries to obtain it.
It is not somuch the protocol what matters but the implementations.
Imagine they "rig" all those beatiful hardware RNG. Could you tell the difference?
Are you sure renowned developer X van Y is not an NSA mole?
https://lwn.net/Articles/420858/
So man-in-the-middle attacks are certainly within their capability and fairly hard to detect. As to whether the NSA can passively intercept and decrypt SSL traffic, I don't know, but they may not need to.
But it is certainly feasible that if they manage to find cracks in popular-but-old communications protocols that they are able to automatically decrypt them, or use prior key recovery successes to bootstrap fast attacks on new communications from the same host.
What would be interesting is if NSA's own "Suite B" crypto recommendations are susceptible to these risks, as that would potentially represent a rather significant break in the U.S.'s own COMSEC, and COMSEC is one of the things NSA is very specifically tasked with ensuring are safe with no backdoors for anyone to jump through.
People assume CAs should be trusted but it's a huge game of chicken: If the NSA can't break SSL, you have to assume that either SSL is opaque to them, which these revelations seem to contradict, or they have corrupted the CAs.
I don't think this would be particulary hard either. For IE, the NSA can just get MSFT to do it. For Firefox, they can compile from source, and for Chrome, well, they can probably compile from source too, because they probably have access to the build source of Chrome, with or without GOOG mgmt knowledge.
Can anyone come up with a (technical) reason the NSA could not be doing this?
But if they did that to everyone? Surely it would be noticed. Probably very quickly. There are a LOT of smart security researchers scouring browsers for bugs and running them in carefully controlled environments every day. Someone would also eventually notice that the production binary doesn't match the version built from source, especially for open-source browsers.
1) Site sends public key certificate to browser. 2) Browser verifies certificate against in-browser store. 3) Browser extracts public key from certificate. 4) Browser generates symmetric/private key. 5) Browser encrypts that symmetric key with the site's public key. 6) Browser sends encrypted symmetric key to site. 7) Site decrypts symmetric key with its private key (the one associated with its public key certificate) 8) Site and browser encrypt and decrypt data using the privately shared symmetric key.
If I break the public key algorithm(s) used in SSL, I break all of that. But we think that's tough (as in NP hard).
If I break SSL itself (find flaws in negotiation, etc.) I might be able to break all of that. That's been done a few times (SSL v1.0 is garbage; v2.0 is borked; v3.0 a little broken; only TLS 1.2 is borkless, so far. As far as we know.
If I break the symmetric algorithm(s), then I can get at the data without breaking SSL itself. But we think that's tough, too. As far as we know.
If any of the software used in any of the above is borked, then usable attack vectors may be exist. Or not. We don't know until we find them.
It's a complex box of moving parts with many potential attack vectors, many potential vulnerabilities, etc.
Who really knows if the NSA might have found a multi-vector, multi-vulnerability attack that allows them to get at a lot of encrypted data without having broken all of any one of those things.
It's purest speculation until someone with a sufficient clearance and sufficient need-to-know decides to speak out, and even then it would remain unconfirmed.
Should I bother to read up on PGP?
If it turns out one way functions actually don't exist, I'll give in and learn to love big brother. Withstanding that, I'll continue considering communications freedom (and all that it implies) as our manifest right and view these types of breaks as implementation errors.
What this sort of article does to me (unlike you, I make no claims to know what the article was 'meant' to do, other than report the news) is make it clear that we need to push back against the NSA _politically_ to win, make what they are doing illegal, change the gag order laws, etc. We aren't going to beat them technologically, but (for those of in the U.S.), it's theoretically a democracy, we can tell them to stop.
I've seen that argument made before, several times, in essays linked to on HN. It's a political problem, not a tech problem, that the NSA can force corporations to install back doors and give the NSA the keys.
You're signing up for a losing game. The myth of Democracy (tm) is another layer of control over individuals.
1. Most people will never have a problem with what the NSA is doing. They support the NSA's goals (tautology, since as you've mentioned, it is responsible to the majority), and if its methods end up causing harm to enough people, they will simply be adjusted to reduce aggregate harm (not to rule out any possible harm). The feedback loop of democracy works on specific actualities, not hypothetical corner cases.
2. The most memetically fit ideas are the simplest ones that elicit the strongest feelings (see: bikeshedding). Outrage peddlers swamp the political reception bandwidth with lowest common denominator controversy - usually judgments on other's lifestyles.
3. Even if there is a widespread preference to reduce the scope of the NSA, the people simply do not have the transmit bandwidth to make this preference clearly known. And they are easily led into squandering their input on the aforementioned manufactured controversy.
4. Elected figures don't actually run the government, the entrenched bureaucracy does at an imperceptible glacial pace. The elected figures run interference by making the majority believe they voted for this shit.
1) they have found/introduced a bug in encryption standards 2) they have solved a fiendishly hard math problem to which no known solution exists and on which solution there is a price of 1 mio $
working in dev i assume (1) is several orders of magnitude more likely.
That's the money quote there- the NSA hasn't cracked encryption. They've just put back doors in.
And we can't even be that angry at the (e.g.) Microsoft execs that authorise the back doors- they potentially face jail time if they resist NSA requests. All the while presumably not able to talk about the requests publicly.
EDIT: and the really fun part - did you know the former head of the NSA serves on the board of directors for Motorola Solutions? http://en.wikipedia.org/wiki/Michael_Hayden_(general)
working with chipmakers to insert back doors
So you're going to need to make your own chips, too.
http://www.cl.cam.ac.uk/~sps32/sec_news.html#Backdoor
> Abstract. This paper is a short summary of the first real world detection of a backdoor in a military grade FPGA. [....] The backdoor was found to exist on the silicon itself, it was not present in any firmware loaded onto the chip. [....]
Could someone add a backdoor to git that hides backdoors from showing up in git? Could gcc be backdoored to add backdoors to arbitrary software? How likely is it that NSA has a few zero-days lying around they could use to hack into the servers that host git or gcc or any other tool you rely on? What if they had agents among the committers and maintainers of these projects?
Security against a well-armed, well-funded, well-organized, secretive adversary is hard.
This, however, is not a decidable problem. It is possible to construct a program that will fool the worm and thus you can create a compiler that you know you can trust for this test. It will probably be a hard compiler to use, but you will need it at most twice -- once to check for an attack, and if there is an attack once more to bootstrap a clean compiler.
i.e., you actually have to have an example of a compromised compiler, which pretty much solves the problem in the first place.
If you decidedly don't-trust the only compiler on your system, and don't trust outside sources, the only solution is to hand-assemble a new compiler on the system, and hope that at least the hardware is trustworthy. which it isn't, necessarily.
You can't rely on a backdoor looking like this:
Anything in the leaked docs on that particular incident?
Perhaps I lack the wherewithal to identify security vulnerabilities in deployed code, but there's a good chance that there are others who are able to spot said vulns.
I'm talking about vulnerabilities in crypto software no in email clients, browsers or office software (that probably they use too)
The reason we don't do that is, of course, CPU cost.
Nobody seems to know if the NSA actually has practical attacks against primitives like AES or SHA-2. We do know for sure that they go after higher level implementation flaws. The more complex your encryption scheme is, the more likely it is that you'll introduce a grave flaw. It only takes one.
I'd suggest that our best bet already exists: NaCl[1]. It's by Daniel Fucking Bernstein, so the implementation is as flawless as it gets. Better yet, it doesn't use a single US-approved primitive (not even the NIST curves Schneier was warning against in his Guardian piece).
Funnily, before the leaks Bernstein's use of all his own primitives was seen as a bit wacky and concerning, but now it seems almost sensible.
[1]: http://nacl.cr.yp.to
Do you know who your covert agents are?
Go ahead, call the cops and media. I hope you have a ton of money on hand and some jewelry stashed away in various locations before you do so.
Undercover agents at all levels of law enforcement commit apparently criminal acts every day, with no fear of prosecution. There's no reason for this to be any different.
It's not like they've just gotten secret keys. They've specifically gotten chip manufacturers to add backdoors to hardware, as well as significantly influenced actual cryptography standards themselves:
> "The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”
> “Eventually, N.S.A. became the sole editor,” the memo says.
[1] http://en.wikipedia.org/wiki/Dual_EC_DRBG
From the article: "Intelligence officials asked The Times and ProPublica not to publish this article, saying that it might prompt foreign targets to switch to new forms of encryption or communications that would be harder to collect or read."
Also: “Properly implemented strong crypto systems are one of the few things that you can rely on,” - Snowden
I would assume that because Snowden used Lavabit & they shut down that the NSA took issue with how secure Lavabit actually was.
I wonder which computer viruses belong to the NSA.
And maybe even ones you have compiled yourself "from scratch":
http://cm.bell-labs.com/who/ken/trust.html
Is this the first time we've seen a 5-digit number to describe the number of documents Snowden has? Of course, these are just the ones used for this story...
> The NSA describes strong decryption programs as the "price of admission for the US to maintain unrestricted access to and use of cyberspace".
What does that even mean? That statement is at the same time paranoid, arrogant, and subtly threatening. It's as if to say that without the ability to decrypt interesting traffic, the NSA would be forced to take stronger measures to curtail internet traffic.
The statement implies that in the absence of "strong decryption programs" then there would be only restricted access to and use of cyberspace. I'm sure the intelligence leadership in the US Government look at China's Great Firewall with both trepidation and admiration.
In many government documents, use of the name "U.S." is shorthand for the U.S. national government, not the entirety of the nation. Sometimes it is even shorthand for the particular agency that authored the document (since, in theory, they represent and act on behalf of the entire nation).
So what this internal NSA document most likely means by "unrestricted access and use" is the NSA's unrestricted access to, and use of, whatever data they want.
Think of it like a budget justification (since that is the purpose of at least half of all internal government reports). "You need to keep spending a lot of money on this program if you want us to keep getting all that data you like so much."
So most states are slowly moving towards implementing their own little firewalls. The only notable absence? The US. Despite occasional campaigns from religious nutters of various sizes and shapes and continuous pressures from commercial telcos, subsequent US administrations repeatedly affirmed that fundamental Net freedoms would not be curtailed.
This document states that such a position is not coming from idealism or even commercial convenience: it's a way to persuade the rest of the world to do business over networks and protocols that the NSA can tap at will. Should this capability be forcefully contained, there wouldn't be a political incentive to keep the Net flowing freely through US routers.
It's a perfectly reasonable and plausible position, and that's why it's so terrifying.
These laws were included in the German constitution following the "denazification" of Germany by the USA, where Nazi symbols were banned and literature burned.
The laws against Holocaust denial and Nazi symbols were pretty much forced by the USA. It's extremely ironic how often they're mentioned as an illustration of the USA's devotion to free speech.
So why doesn't German remove the laws now that they've served their wartime reconstruction purpose?
And that is why they were put in, the same reason that even in the U.S. free speech was curtailed in many areas during the American Civil War.
I think you know the answer to that one ;-)
As someone who has been following the NSA and government monitoring of online activity for close to 15 years the Snowden leaks just keep taking the wind out of me. It's like everything that we thought might be going on was actually going on. When Theo de Raadt wrote the above mail I, like many at the time, assumed it was tinfoil hat territory. I was clearly wrong.
[1] Those claims made by Greg are completely untrue. I ran the professional services group for that company and will happily attest to whomever asks that at no time did we insert a backdoor (or anything that could even be construed as such) into IPSEC.
Somehow I doubt if you did that you could tell us. You might even have to lie to be able to comment on that letter at all.
When all the hullabaloo around the alleged IPSEC backdoor occurred, it was frustrating to not be able to be as open about it as I wanted (not because of any government/security issues, but because at the time I still worked for the company and we were advised against talking about it).
You are free to assume that even right now as I type this, a shadowy figure in an ill-fitting Brooks Brothers suit is standing over me dictating my responses, and then chastising me for spending my time on HackerNews.
I'm hoping open development models(open source, peer production, peer review) end up providing the correct institutional incentives for us to innovate away the mistrust.
To misquote Linus: “given enough eyeballs, all backdoors are shallow.”