Most Tor Keys May Be Vulnerable To NSA Cracking

Ars Technica reports that security researcher Rob Graham of Errata Security, after analyzing nearly 23,000 Tor connections through an exit node that Graham controls, believes that the encryption used by a majority of Tor users could be vulnerable to NSA decryption: "About 76 percent of the 22,920 connections he polled used some form of 1024-bit Diffie-Hellman key," rather than stronger elliptic curve encryption. More from the article: "'Everyone seems to agree that if anything, the NSA can break 1024 RSA/DH keys,' Graham wrote in a blog post published Friday. 'Assuming no "breakthroughs," the NSA can spend $1 billion on custom chips that can break such a key in a few hours. We know the NSA builds custom chips, they've got fairly public deals with IBM foundries to build chips.' He went on to cite official Tor statistics to observe that only 10 percent of Tor servers are using version 2.4 of the software. That's the only Tor release that implements elliptical curve Diffie-Hellman crypto, which cryptographers believe is much harder to break. The remaining versions use keys that are presumed to be weaker."

Comments

Re:well

[Jeremiah Cornelius]

Just use bigger DH, with better cipher. AES-256? Maybe. Twofish? OK.

Bruce Schneier himself advises avoiding elliptic-curve, as being intellectually tainted by the spooks.

Re:well

[Black Parrot]

I recommend a "zero time pad" : if you want it secret, don't put it on a computer.

a few hours for one key would be good

[raymorris]

If that speculation is right, that a billion dollars will buy hardware that takes a few hours to break one key, great. That would mean nobody is going to break MY key, and that al Qaeda's keys were broken soon after they started using them. Works for me.

Re:a few hours for one key would be good

[girlintraining]

If that speculation is right, that a billion dollars will buy hardware that takes a few hours to break one key, great. That would mean nobody is going to break MY key, and that al Qaeda's keys were broken soon after they started using them. Works for me.

I think you're looking at this backwards; They won't spend any money to break your key because you're worth zero dollars. What could you possibly be doing that would warrant the NSA's interest? You need to understand the organization; They primarily do signals intelligence, and they operate in a support role to other agencies, principally the CIA, FBI, and DHS.

The NSA simply logs the data and holds on to it until and unless something happens that makes analyzing that data a priority. They may record all cell phone calls, but they don't listen to them all. They may record all internet traffic, but they don't review all of it. In order for them to expend resources, there needs to be a reason. You could be using '1 bit' encryption and it would be as interesting to them as '1 million bit' encryption.

In security, your defenses need to be harder to break than the value of the thing being protected. Although Tor's encryption may be insufficient against a government, it is plenty strong for most everyday uses -- getting around corporate proxies, location-locked services (like shows the BBC offers, Netflix, etc.), and for proxying to Facebook. Yes, I use Tor to connect to Facebook... because I don't want them knowing where I am, and my IP address provides a wealth of marketing information to them. I also don't use my real name, but really, the main reason is just to piss in their data collection cheerios, not because I'm doing it to be 'anonymous' or 'super secure'. And this is what most people use Tor for; along with browsing bittorrent sites (though downloading is still direct...), and other things that they may feel uncomfortable with having a readily-accessible record of at their ISP's office (gay porn anyone?).

The NSA cares not for these activities. It's logged all the same, but until they say that, say, "the alias raymorris on slashdot indicated he may be in possession of classified materials" all that data just sits on a harddrive somewhere, waiting to expire. The NSA just waits for the phone call.

That said, a few hours to break one key is pretty petty for accessing your internet traffic or mine, but if Al Quaeda has a hidden service inside Tor they're using to communicate with, a secret website if you will... now those few hours' worth of electricity seem very, very worth it.

You've gotta understand that security is not an absolute; There is no "secure" versus "insecure". There is only no security, and then varying degrees of more security; And good security is when it costs more to break it than the value of the thing being protected. Great security is when that's true and the computer functions the way you expect.

Re:a few hours for one key would be good

[Yvanhoe]

This is good only if you work under the assumption that you will not disturb any entrenched interests. As a European who works for European companies with US competitors, I can not assume that no one will ever spend a few hours to know what is inside the mails I sent to my boss.

This is not an hypothetical case. In my last job we were in direct competition with IBM and were exchanging crucial pricing information through email. There has been precedents of ECHELON being used to gain economic intelligence (google "echelon airbus boeing" to learn about that)

Re:a few hours for one key would be good

[girlintraining]

This is not an hypothetical case. In my last job we were in direct competition with IBM and were exchanging crucial pricing information through email. There has been precedents of ECHELON being used to gain economic intelligence (google "echelon airbus boeing" to learn about that)

Oh please. Every government engages in industrial espionage. The French are so well known for it that CEOs for pharmaceuticals that check-in to local hotels are told not to use the fax machine or internet there, and to keep their laptops in their room, and to bring their own locks to secure it and not use the hotel safe or in-room safe as the cleaning crew often isn't the usual maid service. I mean, this is SOP. Not that I'm picking on the French -- they're only guilty of being particularly bad at doing it covertly, but everyone does it.

One does not need ECHELON to spy on a company. Hell, showing up to replace a printer in slacks and an official-looking work order is usually enough to get into a building... and having a rigged printer that records all the jobs sent to it is a nice opener. Following up with a power strip with its own wifi, mini computer, and cat5 pass-thru is a good follow-on. Why do people assume you need satellites and taps on hundreds of internet routers all over the world to do this?

And don't underestimate blackmail, human stupidity, or the CEO's penchant for keeping a post-it note with his password on his computer, trusting that his secretary and security staff would neeeeever let anyone in who wasn't supposed to be there.... and of course, nobody ever takes bathroom breaks while watching the CEO's office over lunch time.... -_-

And as a bonus... most corporations record all e-mails to monitor their employees. Amusingly... these systems are usually less secure than the ones they're tapped into. So if you don't have the money to bring your own equipment... they're usually nice enough to provide it for you.

Re:a few hours for one key would be good

[j-turkey]

I disagree with your assertion that since you're not a terrorist, the NSA has no interest in you and/or what you do. Law enforcement tools are always used to their fullest extent. I mean, it makes sense; law enforcement is a bit hamstrung by rights guaranteed under the constitution - they will use whatever tool is at their disposal to get their job done.

Whether or not you were investigated when the system was new is irrelevant to what law enforcement has started (or will start) using these systems. Also, to obtain a FISA warrant for an investigation related to terrorism is quite trivial and open to interpretation. Any evidence discovered of other crimes in that warrant is usable in court. I have seen it first-hand while siting on a federal jury last summer. A US khat-selling ring's sending money overseas was investigated by DHS due to concerns about possibly funding terrorism. It wasn't, but the multi-million dollar investigation had to net something - so I sat on a jury for 5 weeks and sifted through mountains of wiretap transcripts so the federal government could incarcerate a bunch of taxi cab drivers who wanted to chew some khat so they could work a little later and make a little bit more money.

I hate to be the slippery slope guy...but this is typical. It's only a matter of time until these law enforcement tools are used on a wholesale basis (if they aren't being already). After reading about the extremes that the Soviets would go to under Stalin (if you were being investigated, you must be guilty of something), I feel like I have a fair understanding for how far things can go. I'm not suggesting that America is going that way...but why give her the chance, especially when we can do something now? Why not start setting some limits on this stuff? I think that the risks of what's going on outweigh the benefits. Is it unreasonable to do an honest analysis of the real risks of terrorism against the security measures that our government is putting in place?

Re:a few hours for one key would be good

[nbauman]

I disagree with your assertion that since you're not a terrorist, the NSA has no interest in you and/or what you do. Law enforcement tools are always used to their fullest extent.

National security agencies will use their tools not only against criminals, but against their political enemies who are engaging in Constitutionally-protected activities. For example, J. Edgar Hoover used to tap Martin Luther King's telephones, and then spread personal information about King's sex life to try to harm the integration movement.

Or a recent example. Eliot Spitzer was the Democratic governor of New York, and he was an effective governor who was aggressive about shaking things up. Banks have to report every transaction by every customer of $10,000 or over to federal authorities, and every transaction under $10,000 that looks "suspicious." So the feds get this huge flow of reports. One of the reports was on Spitzer. They investigated and found out as the result of this fishing expedition that he had used an escort service, which was probably legal and almost never prosecuted. Nonetheless, the Republican Attorney General decided to prosecute Spitzer for this, and leaked his name to the press. The Republican AG offered Spitzer a "deal" -- if the effective Democratic governor resigned, the Republican AG wouldn't prosecute him. Spitzer resigned, and was replaced by David Patterson, who didn't want the job and nobody, including Patterson, thought was qualified.

So there you have a partisan use of confidential information that a federal agency got through its financial monitoring process, that a Republican AG used to get rid of an effective Democratic governor.

The more electronic monitoring we have, the more it will be used improperly by politicians to damage their enemies.

Re:Question: multi-layer encryption

[dantotheman]

Depending on the encryption method, doing it twice might make it easier to crack...

**This message has been encrypted twice with the ROT13 method**

Re:well

[Jeremiah Cornelius]

Wrong Guardian Schneier link. :-)
http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance

From Item 5:
"Prefer symmetric cryptography over public-key cryptography. Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can."

Guess who is funding Tor?

[hypnosec]

According to consolidated financial statements and reports of the Tor Project for the year ending December 2012, US Federal agencies are responsible for nearly sixty percent of funds received by the project. Tor has taken a defensive stand against this, but who knows?

Re:Guess who is funding Tor?

[girlintraining]

According to consolidated financial statements and reports of the Tor Project for the year ending December 2012, US Federal agencies are responsible for nearly sixty percent of funds received by the project. Tor has taken a defensive stand against this, but who knows?

Tor was created by the US Air Force. Surprise, surprise, they still want to fund it. Sooo, why did they create Tor? Well, as it turns out, we've got this massive high speed satellite and ground network we use for military purposes, which basically amounts to a compartmentalized version of the internet. And within that, because soldiers are away from home for months or years at a time, they decided to offer internet access to them. Often they're on board carriers, or deployed in places where a direct hookup isn't really feasible. And they want to make sure that all that traffic isn't pouring out at locations that can be easily monitored... because as much as operational security is drilled into soldiers, loose lips sink ships and all, they're still human. They can screw up.

So they needed some way of giving them internet access without making it pathetically easy for foreign powers to simply tap a couple key routers and see everything any soldier browses (Facebook anyone?)... Enter Tor.

Tor has over 13,000 exit nodes all over the world. And it's expensive to monitor every node. Not only that, but you have no idea where in the Tor network the traffic originated from -- is this J. Random Soldier, or Closet Gay Guy Looking At Porn? Noooobody knows. It wasn't meant to be high security. It's not meant to be totally anonymous; It's meant to make it difficult for small-time players like, say, Iran, to spy on our soldier's personal communications. Because this has happened, and it has killed people; A cell phone left on in a soldier's pocket during an operation led to the death of a half dozen marines when enemy combatants used the signal to figure out when they were leaving base... and they planned an ambush.

So Tor will be funded by our government for the conceivable future, and they have a vested interest in maintaining the security of the network to the point that it would cost an adversary more to 'break' the network than the intelligence value of the soldiers' personal internet browsing.

Does this worry me? Nope. Tin foil hat time? Not a chance. Don't use Tor for high value communications. But then... that goes for the public internet as well. If you want to secure high value communications, you build your own VPN, and then add code to have it transmit/receive at a constant rate to deter traffic analysis. Which, coincidentally, is what most financial institutions these days do.

Re:Guess who is funding Tor?

[ShawnA.Miller]

Tor was not created by the Air Force. Initial work was funded by the Office of Naval Research via the Naval Research Laboratory. See: http://www.onion-router.net/History.html. You can also see a list of funders here: https://www.torproject.org/about/sponsors.html.en.

Re:Other than a few uber nerds

[black3d]

What's this "have to hide" bullshit? What if you want to hide? A large percentage of the population are introverts, and a significant proportion of both those (among others) don't have any desire to share anything personal with anyone, at least aside from those they choose to. Some people like privacy, like anonymity, like not being seen by others. Hell - I get a serious case of anxiety if someone is merely standing behind me, no matter how innocuous my activities.

Please, don't start with this "if you have nothing to hide, you have nothing to worry about" utter crap. The next step to that is "if you have anything to hide, you're probably a pedophile" which you're already alluding to. No, we just don't like oxygen-wasting cretins sticking their nose into our lives. Considering such a vast number of people value their privacy in exactly the same way, this behavior is *natural*.

I make very little effort to hide my presence online. But if I did choose to, then by no means does anyone have any justification to suggest that there's something wrong with wanting to hide. It's part of the human condition - some people like being seen, being known, being pored over - some people prefer the exact opposite.

You might suggest this is an over-reaction, that you're merely pointing out that the internet isn't for people who want to hide. But the point is, it should be. You should be directing your energies to fixing the problem - not just throwing your hands up and saying 'don't bother trying to hide even if you want to'.

Re:Other than a few uber nerds

[djdanlib]

Exactly. Some activities need to stay hidden. For example:

* I don't want someone's Christmas gift to be spoiled for them.

* My neighbors don't need to know how much my electric bill was, or what tier of service I have hooked up to that wireless router.

* I have a very dedicated stalker, whose information is limited because that person can't dig into my email or other accounts to find out what I'm up to.

* If I post on a forum for people who own a particular product, I don't need people to be able to find my house so they can steal it.

* A friend who's hurting after a disastrous breakup might email me something in confidence. That should stay confidential.

* Employment and tax documents, with pay grade information and SSNs and all kinds of other PII.

* Online banking, anyone?

* I may compose some music that isn't ready for release yet, and that needs to stay private until it's been polished.

* Medical records about who has what rash on their what now?

There's just some information that doesn't need to be free. No nefarious intent, just things that shouldn't be public.

Re:Getting tired here

[AHuxley]

We have had 30 years of whispers, books, magazines and talks by past experts. We seem to have a generation of experts who seemed to allow their allowed hardware and software encryption to fail on a global scale.
So every new story adds to work mentioned in the past. In 30 years this would have been amazing news.
Getting all this crypto and telco news now is going to allow some very creative people to release some new software and hardware.

About Tor versions

[ShawnA.Miller]

The original blog post by Rob Graham that Arstechnica reports on has created some confusion about Tor versions. The current recommended stable version of Tor is 0.2.3.25-12. The current alpha release is Tor 0.2.4.17-rc, and people running relays are being encouraged to use this version on the mailing lists. So the repositories, by recommending Tor 0.2.3.x, aren't out of date. However, the Tor website does advise against using the Ubuntu repositories because they aren't "reliably updated" (https://www.torproject.org/docs/debian#ubuntu), which I don't think is the fault of Tor developers. Also, the most up to date version of Tor can be found at the following repository: deb http://deb.torproject.org/torproject.org/ tor-nightly-0.2.4.x-wheezy main.

Re:Getting tired here

[QRDeNameland]

I just want to read about science and technology, interesting shit.

I feel your pain, but unfortunately, if the NSA/intelligence complex truly can not be reined in (and I'm not optimistic that it can be), I think you're looking at the dark ages for any science or tech that doesn't serve their purposes.

Someone posted the following citation at the New York Times yesterday, which really struck a nerve with me:

"The man who is compelled to live every minute of his life among others and whose every need, thought, desire, fancy or gratification is subject to public scrutiny, has been deprived of his individuality and human dignity. Such an individual merges with the mass. His opinions, being public, tend never to be different; his aspirations, being known, tend always to be conventionally accepted ones; his feelings, being openly exhibited, tend to lose their quality of unique personal warmth and to become the feelings of every man. Such a being, although sentient, is fungible; he is not an individual." Bloustein, Privacy as an Aspect of Human Dignity: An Answer to Dean Prosser, 39 N. Y. U. L. Rev. 962, 1003 (1964).

Don't think for one second that this is an intangible threat. The people who blissfully ignore or accept it are exactly the people who won't be doing the paradigm shifting science or creating disruptive technologies. The people who would do those things are stuck with the same choice you state: acknowledge a really sucky situation and face being miserable, or ignore it as 'intangible' and go about their day, and just focus on uncontroversial science and tech that won't get them in any trouble. Can that possibly be a good thing?

Re:Getting tired here

[sharklasers]

I think their point is that Slashdot (and presumably most tech sites at the time) focused more on tech, developments, hard science and whatnot. Now it's basically more about the politics that goes on in tech, such as data mining, surveillance and patent wars. Sure, the stuff being talked about is serious and worth covering, but it dominates coverage these days and the balance doesn't seem to be there anymore.

Also, if you are a fan of a site, you SHOULD piss and moan about the quality of the articles and discussion. The only reason you'd bother is if it was once great and has devolved, and you're not pleased by it. There seems to be this impression that making noise and complaints about something is a BAD thing. No wonder things are getting worse.

Re:Getting tired here

[Artifakt]

I'm going to take a stab at empowering you.
We're in a long term fight for human freedom. Long term means you may have to influence people now who can just possibly help us, or at least you, ten or twenty years down the road. Pick people who are running for minor or local offices, and need a little help, whether it's contributions or getting out the vote or going door to door. You don't have to spend a fortune or put in fifty hours a week on top of your day job to be remembered as one of those people who helped congressman X get his start in politics.
Write letters - you'ld be surprised how many seemingly major pieces of legislation draw two or three letters as they are up for debate, and how getting letters from as few as 10 or 20 people may make a congressman suddenly vote the way he now thinks the vast majority of his constituents want him to vote. Senators and Representitives may see 10,000 e-signatures on a stock electronic petition, but don't usually see even 10 actual letters. A letter thanking them for having done the right thing after it's over is even rarer.
Focus on the persons who seem like they have a good chance of making it to higher office eventually. Find out what a Farley file is, and make sure you end up in a few, in a positive way. Work on your spelling and grammer - An eloquent nutcase may be able to pass as a mainstream voter, but a mainstream voter who writes in all caps and spews sentence fragments, can definitely say something eminently sensible and still be labled a nutcase.

Here's a link for Farley Files. Politicians who make it to high office just about invariably use these, so it's always helpful to know about them. Learning to watch for signs a candidate uses the system is a way of spotting the ones who will go high enough they may someday be able to address issues like the NSA programs. It's also useful to consider in judging what a politician truly considers important rather than what he says in prepared speeches - that is, if he or she is using a file, what do they focus on.

http://en.wikipedia.org/wiki/Farley_file

Re:well

[Anonymous Coward]

We certainly need more research, but it looks like an RC4 complete break (that would be the big, recent breakthrough - would love to see the details, now we know about it) and 1024-bit RSA keys are the meat and potatoes of BULLRUN. And since PCI Compliance for a while advised everyone to use RC4 as a workaround to the BEAST attack... yeah. NSA. Bastards.

They set the constants for all of the NIST curves, however. And if they have a SHA-1 preimage (and it's their algorithm they no longer even recommend, so they might) then they could set them any way they wanted. Or just try repeated phrases until they got bit patterns they were after. prime256v1/secp256r1 and all that jazz? We can't trust them anymore. They're NSA-derived - and the way it turns out they've been behaving, we therefore assume that they ARE backdoored, even if they use them themselves.

The curve Tor uses is curve25519. That is not NIST-derived, NSA didn't pick parameters out of a hat for that one: DJB made it independently. It's been designed, and the reasons for the choices thoroughly explained. It's extremely fast due to its structure, it's good even through the twist, the implementation is so careful that it's constant-time to avoid timing attacks, and we have a rough idea how strong it probably is (around 2^110-ish). Ed25519 is also similarly good and makes a great signature scheme (and you could do DH with it better as well), although you probably don't want to use SHA-512 with it anymore, because NSA - Skein-512-512 is probably the way to go. I don't trust NIST's choices anymore. They are ALL NSA, and thus ALL potentially-tainted.

Unless elliptic curves in general are crackable, which would be quite a wheeze, and of course a possibility. Certicom (NSA) have been doing those for a long time: but the 25519 curves are the product entirely of civilian mathematical research, at least. For now, Schneier is spooked and notes RSA still works fine, if slowly, and maybe bigger keys... 3072-bit? 4096-bit? Against an adversary like this - and it's clear that they consider EVERYONE an adversary - we need the margin.

I note DSA and ECDSA really need strong random numbers for every signature (see fail0verflow's Sony crack for a practical exploit), and GCM fails quicker than it should with non-random keys. Reasonable conclusion: subtle RNG backdoors. We should keep a special look-out for those. Other choices exist which aren't similarly affected (particularly, Ed25519 does not need random numbers per-signature, neither does RSA, although RSA blinding does).

What next? AES-128-CCM use in TLS, perhaps, or OCB-AES-128? (Note I'm specifically NOT recommending AES-256/192 because of the meet-in-the-middle attack - I'd rather move to TWOFISH-256.) Ed25519 DH in TLS? All commercial CAs are toast, the model has been so thoroughly subverted that it can't possibly continue to work. What about DNSSEC? Could do the job. But we can't trust the US to manage the internet anymore. We're meeting in November to see what we have to do: maybe if we remake it used good RSA or Ed25519 keys and take the hands of the root out of ICANN, because ICANN is the US and the US has spectacularly demonstrated it cannot be trusted to manage anything, probably no country can... which means, perhaps, it's time to dig the root KSK revocation key out of mothballs: if there's no trust, there's no point. We're going to need a treaty, a .INT. This isn't a quick-fix.

Schneiers most recent comment....

[ssimpson]

Bruce Schneier http://www.wired.com/opinion/2013/09/black-budget-what-exactly-are-the-nsas-cryptanalytic-capabilities/ stated that "Breakthroughs in factoring have occurred regularly over the past several decades, allowing us to break ever-larger public keys. Much of the public-key cryptography we use today involves elliptic curves, something that is even more ripe for mathematical breakthroughs. It is not unreasonable to assume that the NSA has some techniques in this area that we in the academic world do not. Certainly the fact that the NSA is pushing elliptic-curve cryptography is some indication that it can break them more easily."

I'd not rush from DH to ECC but would strongly recommend a move to 2048-bit or above keys

And have just realised that I haven't posted to Slashdot for many years...And yet somehow my .sig is still relevant. NSA may have dropped their plans for mandatory Escrow 15 years ago after the quote was made...but they didn't change the fundamental goal: to read everything.