Go to Making Light's front page.
Forward to next post: Ann Crispin
Subscribe (via RSS) to this post's comment thread. (What does this mean? Here's a quick introduction.)
Because the NSA has been breaking most encryption on the net, as it turns out. The story is being jointly reported by the Guardian and the New York Times.
Two responses by Bruce Schneier, who has been to Rio to work with Glenn Greenwald and has seen many of the Snowden documents:
How to remain secure against NSA surveillance
The US government has betrayed the internet. We need to take it back
None of this is entirely surprising, but to have it so thoroughly confirmed is to move permanently into a different world.
There's something wrong with the New York Times link. At the moment, it just points back to whichever page of this site you're seeing it from.
When I took a class in cryptography in college, we talked a bit about the Data Encryption Standard and the algorithm it used. There were rumors even then that NSA either had a back door or a way to break it, especially since they were involved in its development.
a link for the NYT story
oh, yeah: the class I was in was in the early 80s.
It's really hard to exaggerate how big a deal this is. And I've been working on this stuff for 15+ years.
New York Times link fixed. Sorry about that.
Mitchell, #5: Yeah. And I liked your post on the subject. If "liked" is the word in circumstances such as this.
I do want to say in advance that I would be very grateful if nobody posts comments about surprised they are that this is news to anyone.
As I said, it's not entirely a surprise, but it's different to have it completely confirmed. More to the point, though, this. (Thanks to @iucounu on Twitter for reminding me of it.)
One of the most worrisome things about this is that we can't assume that only the NSA knows about these weaknesses. Oh, probably the whole panoply is only available to the NSA. But something this big cannot be kept entirely secret and some--many?--of the individual cracks have probably leaked. There's plenty of criminals who can figure out things to do with them, as well as power-mad security forces. Are bank deposits secure? Medical records? What else is at risk?
I find it interesting that Schneier's "How to Remain Secure" essay reiterates the importance of the "end-to-end" principle, from a different perspective. In the past, there was a battle between the "phone people", who wanted an intelligent network with dumb edge nodes, and the "internet people", who wanted a dumb network with intelligent edge nodes. The "end-to-end" principle was the internet approach, where you keep the intermediate parts of the network relatively simple, and do most of the interesting algorithms at the edge, in the "end nodes". Back in the day, this was seen as a way to best allocate computing power.
Today, we have so much computing power dripping from our fingers (well, at least from our wrists, ears, and pockets) that it's possible to say "the heck with the end-to-end principle, let's make everything intelligent, and spread complex behavior through the whole network."
Schneier's article points out that from a security point of view, we're better off doing our encryption at the edges, in the computers we have physical access to, and trusting less of our unencrypted data to the network in between.
PJ:
The weird thing is, the backdoor appears to have been right out in the open. There were attacks found on DES, but they were entirely impractical (like "collect 2^{43} plaintexts and their corresponding ciphertexts" impractical). But the damned thing had a 56 bit key, which was breakable with a sufficiently big budget within a few years of its adoption.
BTW, I have long suspected the sexist Google Plus "real names" policy was one result of NSA influence.
11
Computers now are very much not computers then. (I was really happy that I didn't have to use the mainframe system at the school for most of my homework. (It had an editor that was @#$%^&*() to use with a bouncy keyboard. And getting a program to run was difficult. Punchcards were easier....)
PJ: There was a fair bit of suspicion about the NSA's involvement with DES, especially since IBM asked them to review it and they said, "You should make this set of changes," without explaining why. Later, when private-sector cryptography advanced and new methods for attacking encryption were developed, it was discovered that the NSA's changes made DES particularly resistant to the newly-developed attacks, so the NSA was deliberately strengthening DES against attacks that weren't public knowledge at the time. All the evidence indicates that the NSA's involvement with DES was entirely in good faith. (I've also read things that indicate the people who reviewed DES at the NSA didn't entirely understand how public the algorithm was going to be.)
Albatross @#11: DES when standardized reduced the key length from IBM's original 128 bit to 56; the response to that was triple-DES, which is still reasonable to rely on. I couldn't quickly find the paper but at Bell-Northern Research, there was an analysis of the pricing of a dedicated hardware machine for breaking DES. Back in the 90's, I think, it was expensive but easily within government budgets. Today, any interested party with moderate resources can afford the equivalent. I expect that a pure software solution would be quite reasonable, using "cloud" resources if you only need it now and then.
I've assumed this sort of thing for quite a while, but it is certainly different to have it confirmed. That's assuming the confirmations are true. At least one day a week, I assume something very different: That quite a few of the NSA's supposed abilities are lies and bluffs designed to call attention away from other, more traditional methods of intelligence gathering. I just don't know. I'm not sure we can know and that's creepy. What I do know is: Spying is lying.
While the NSA didn't tell us why they encouraged IBM to change DES from 128 bits down to 56, eventually somebody in the academic world discovered Differential Cryptanalysis, which provided an attack that weakened DES to about 57 bits. Assuming the NSA had already discovered that, it meant that they hadn't actually weakened the algorithm, and they might have cleaned up some other problems in the process. But 56 was still too weak by the mid-90s; there's an ASIC chip on my office wall that was one of the rejects from John Gilmore's $250,000 custom machine that could break DES in a day or two, and there was a distributed-processing project that could also cracked DES in about the same time using a large number of volunteer PCs doing background work.
AES probably doesn't have any backdoors, but the academic community could have missed something, even though they have a lot more mathematicians than the NSA these days. But it doesn't really matter how good your encryption algorithm is if the operating system lets the Bad Guys steal your keystrokes when you're typing the password.
Bill @#17: AES has some implementation gotchas that might or might not be intentional.
The biggest example is that it's notoriously difficult to implement AES on a general-purpose CPU in a way that it will run quickly, but also always run in constant time no matter what its inputs are. The most obvious ways to make AES go fast involve the use of table lookups -- but these table lookups introduce a timing side-channel. This fact was known at the time that AES got standardized, but for whatever reason (not necessarily conspiracy) people thought it wasn't a big deal.
There's a pretty good explanation of how bad things can get and how hard it is to fix them in this 2005 paper, which is surprisingly readable as cryptography papers go.
That doesn't mean that AES itself is broken, mind you -- only that it's quite difficult in practice to write a fast non-broken AES implementation. Other finalists in the AES contest had some similar issues, which makes me think this is likelier to be a flaw in how people were designing codes back in the late 1990s.
While NSA's involvement with DES seems to be well explained by differential crypto, the same can't be said for some of NSA's more recent contributions to cryptographic standards. In particular, a random number generation algorithm they put in a 2006-era standard is widely suspected of having a back door.
What makes this doubly suspicious is that the back doors that NSA is reported to have paid for in commercial software might well involve the use of weak random number generators. The advantage of this, from the NSA's perspective, is that bias in random number generators can have devastating effects on the security of a system, without being obvious to anyone looking at it.
The important quote in all this is from Schneier: "Remember this: The math is good, but math has no agency. Code has agency, and the code has been subverted." If he is correct, it is still technically possible to keep the NSA out of your stuff. You'd have to start with a clean system with no NSA-touched code, interpret nothing from the Internet as code, and store everything with encryption the first time. A quick search turns up several possible bases for such a system. If you're a well-funded terrorist organization or a hostile foreign government, you have hope.
We can assume that any conspiracy which uses email is now known to the NSA.
If it's a conspiracy which controls the NSA they only have to worry about another Snowden.
What do you do if, for instance, you are a British MP who voted against the Government on Syria? This week a report came out on the number of attempts to access porn sites which were made from the British Parliament's network.
This isn't like accidentally mistaking the Washington D.C. dialling code for a foreign country. This is the NSA attacking the security of the whole United States.
This is my surprised face.
Nope?
Okay: This is my ironic face.
(Same face. I don't gamble, otherwise it would be my poker face, too.)
I am having enourmous trouble resisting the urge to say "v gbyq lbh fb", so, er, v gbyq lbh fb, only you mistook it for pulp/genre fiction. And by you, I don't mean you, I mean everyone who had the opportunity to read "Applied Cryptography" or "The Puzzle Palace" back in the day, and didn't.
Ah, what's the use? We did this to ourselves, or by negligence allowed it to happen. This is the emergent consequence of the west lacking a moral spine to stiffen its utilitarian guts in the wake of the collapse of the ideological rival that was the only thing that kept the Owners straight for so many decades.
And now we're screwed. Welcome to the Panopticon, it's been nice being able to live in ignorance of your innermost secrets for so long.
Charlie Stross @22 in the wake of the collapse of the ideological rival that was the only thing that kept the Owners straight for so many decades
I hate to argue with you, truly I do, but I think the presence of that ideological rival served as justification to the Owners, in their own eyes, for all sorts of crookedness, and that this is just a continuation of the same. The collection of creepy-crawly things revealed when the Church Committee started turning over rocks back in the 1970s here, as well as all the revelations about the things J. Edgar Hoover felt were necessary to keep America safe from people who didn't see the world just the way J. Edgar Hoover did, bear a close taxonomic resemblence to these revelations. If Hoover had been confronted by these issues of cyber-security, he'd have done exactly the same as the NSA, or tried to, and so would the people at the CIA and NSA in his day. This is not a new thing, this is an old thing applied to new technology.
Because having secrets from them is just wrong, whatever you may want to hide from your mother or your spouse or your business competitors or anyone else in your life. After all, if you don't have anything to hide, why are you worried? /venom
re 21: I wouldn't assume that's true, actually. A reasonably competent conspiracy is going to use code instead of or as well as encryption; or it will encode encrypted material somewhere that isn't out in the open, e.g. inside of a JPEG or other noisy data. After all, the security of email is in one sense no better than the security of ordinary envelopes, which the government can read upon showing cause.
The biggest worry in this is that there's plenty of reason to suspect that the NSA isn't the only one able to do this. Even if they are, one must assume that private concerns (meaning criminals, but potentially any corporation of sufficiently weak ethics counts as such) will be able to do it too, soon enough; until we run off the end of Moore's Law it will ever be so. If encryption is the only form of network security, then network traffic will always be a short few years from insecurity.
OK, I'm just going to say this. A couple-eight years ago, I was terrified of Bush co. They were tossing civil liberties out the window like it was confetti on war parade day. I'm queer as hell, and the rollbacks on that scared me shitless. I still blame Bush and his cronies' moves for making it possible for a nice dyke couple in my neighborhood to be attacked by a guy who leaped out of his truck with a bat and beat them to death. Why'd he do it? They were holding hands. Authority-approval of fag hatred makes a difference. Because authority-approval of ALL these small hatreds makes a difference.
I'd like to say to Charlie Stross, look, man. Each American is one person. I looked around for someone who could beat Bush's even crazier successors, and I found Obama. One of the few senators who voted *against* the Iraq war in the midst of jingoism my nonagenarian gram hadn't seen since the *forties*. I campaigned hard, and we won. Yay.
It's not like my entire fucking country didn't go tits up. I spend my workday helping adults whose jobs got sent overseas learn new work so they can feed their families. I spend time trying to campaign for legislation that doesn't make it legal to fire myself. I vote against wars, crazy ass gun laws, crazier religious whacko legistlation, and abortion laws that my eyes wheel so fast I look like a rabid pony. I try to work hard to vote FOR food stamps, for legislation to prevent fracking, for fucking health care.
But oh wait! I'm just spineless. I should have OBVIOUSLY been prescient enough to ALSO become an expert on 'net cryptography! TOTALLY! In my spare time, absolutely, right. I did all this to my own self. Right. Because I just don't care. Right.
Yeah. You're really motivating me to think of you as anything other than one more specialist who thinks he's extra clever and ironic.
Look, I voted for a man who I hoped would get in that oval office and make a significant improvement to the apparently endless river of shit our politicians have been pouring out around them. I was wrong, but you know what? I still would have voted for him. Hell, I still campaigned for the bastard last time. Because my other options were worse. Do I feel like a chump? No shit, Sherlock. Of course I feel like a chump. The guy drone-striked a kid for being in the wrong place in the wrong time, sent out assassins, and is apparently spying on every damn last one of us. Well congratulations, Charlie, I feel lousy. Happy now? I'm sure you'll tell me that I should have voted for Mittens. Oh wait.
That's right. Life is complicated. Time is limited. Most of us are not net crypograph experts, most of lack the skills to work on that side of things. We work on the parts we *do* understand. And we accept that we cannot influence or control everything--and neither can anyone else.
Of course the downside is, recognizing our limited influence means we don't get to crow so much about how 'if only people weren't spineless we wouldn't be here'. We know in our hearts that despite the hard work of a lot of people, evil sometimes triumphs.
It did today. Evil has triumphed. It fucking sucks.
All I can do about it is cry, figure out what *is* within my power to roll it back (not much, but some), and then move on to the other pile of evil in front of me. Foodstamps getting cancelled. A friend whose unemployment runs out. Another friend whose illness is not covered by health insurance and who will go homeless soon. My friend having to take a different train because of angry racist tirades. Upcoming abortion fights. Going to war with a YET ANOTHER COUNTRY. There is PLENTY OF EVIL TO FIX. Are you going to smug about figuring out all of it, Charlie, or can I turn around and ask you what you did, YESTERDAY, to prevent my friend from going homeless? Because I personally don't find that shit all that helpful.
I'd rather say, Look, if you're an expert on some evil, then work on THAT. Pick an evil, ANY evil, and focus hard on it. Do your best. It's more effective. And let go of blaming others when they're working beside you, but on a different evil. There is enough damn evil right now to keep us all busy into our graves. You're an expert on crypto-internet whatever? Great. You work on that. I'm not. The best I can do is write a damn letter, figure my email will therefore be fucked, and cry. But I'm an expert on getting people to work again, so I'll spend the rest of my time on that. Maybe, if we focus on the damn evil instead of calling each other spineless, we'll have some hope of turning this fucking behemouth of hell around.
Charlie @22: Here's the thing: I did read "Applied Cryptography", "The Code Breakers", etc Back In The Day. And then last year I took the "Cryptography I" course on coursera and found out how little of what those books talked about mattered. The first week of the course the instructor described a basic property any good cryptosystem should have, and I immediately applied that test to DES, AES, etc. They immediately, trivially, obviously, failed.
What I got out of the more modern course on cryptography is that AES, etc are good building blocks for good crypto, but it's the protocols that use those building blocks that are truly important. This is not stressed enough in "Applied Crypto", etc.
A poem on the subject. I think it's wishful thinking, but it's a very sweet poem and has some good stuff in it.
Buddah:
There's a huge range from the primitives (AES, RSA, SHA2) to the modes of operation (AES-CBC, RSA-OAEP, HMAC-SHA2) to the protocol (TLS 1.2 with some specific ciphersuite) to the implementation. Every step of the way, there can be weaknesses, and having all but one part be secure can easily mean no security.
If there is a general weakness that's being exploited to break a lot of crypto, it's almost certainly either key generation or some flawed implementation that's in widespread use. My bet is on bad seeding for the RNG--most OSes provide entropy via some dev/random like thing, but often they do a lousy job making sure they actually have any entropy. That's what led to the stunning result a couple years ago about all those RSA keys with shared prime factors.
There is a rather simple thing you can do for your ordinary passwords to all those site-accounts.
1: Get an ordinary six-sided dice.
2: Draw up a 6 x 6 grid.
3: Fill that grid with the alphabet, and the digits 0 to 9. There's no need to jumble it up.
4: The next time a site asks you for a new password, roll the dice. Once for the row, once for the column. Whatever method you use for keeping your passwords, whether it's a notebook in your desk drawer or some hopefully secure program on your computer, the result, 8 or 10 characters long, is random.
Nobody will get at that account with a dictionary attack.
It probably won't stop the NSA, there are so many ways they can bypass crypto, but it's a start.
Don't give up. Don't make it easy for them. Don't use encryption only for the important things.
You don't even have to use the internet...
27
Probably the RNG, because it's very hard to tell if you're getting truly random numbers generated. There are some algorithms that are supposed to be good, but the devil is in the implementation.
(most of a BS in computer science here, even if it isn't actively in use.)
Academic @25: I'd like to say to Charlie Stross, look, man. Each American is one person. I looked around for someone who could beat Bush's even crazier successors, and I found Obama.
Yeah, I had exactly the same happy fun experience in 2010. Voted Liberal Democrat in the UK general election, expecting the party of civil liberties to go into coalition with New Labour and apply the brakes to their worst authoritarian tendencies. (Look how well that worked. Yes, they scrapped the National Identity Register. They also enabled a Tory reign of misrule, hideous abuse of the disabled, and all the time GCHQ was doing this stuff in the background.)
(Best I, personally can do is write extremely cynical novels in the hope that people will find them thought-or-rage-inducing, and maybe try for a magazine column somewhere that will make a difference. Being another warm body on a march ... not such a useful contribution. But trying to raise awareness feels like an uphill battle. And I'm getting very tired these days.)
Dave @29, I have bad news for you. Hint: the long password cracking at that link isn't the NSA, it's J. Random Hacker with a farm made of cheap graphics processors.
Charlie Dodgson 19: that example appears to be precisely confirmed by the NYT article, though not by name (2006 NIST standard, backdoor found by 2 MS people in 2007).
@27 @30
best current knowledge suggests we don't have any RNGs, only PRNGs (pseudo-random number generators). The problem even has its own many-worlds theory,
http://cstheory.stackexchange.com/questions/1026/status-of-impagliazzos-worlds
(RNGs are a form of one-way function).
The theory is beautiful but as Bruce Schneier says, math is not proof against human subversion, the beautiful model does not survive its implementation in code..
34
True, they're all PRNGs, but some are better at randomness than others.
Nancy Lebovitz #27: Taken literally, it would be wishful thinking. But... Isn't that where Snowden and Assad came from?
What made me laugh, and then feel sad, when I clicked the very first link in this post, was:
Another program, codenamed Cheesy Name, was aimed at singling out encryption keys, known as 'certificates', that might be vulnerable to being cracked by GCHQ supercomputers.
Codenamed Cheesy Name! Oh, British humour. Could almost be a nod to the waggish Ship names of the Culture. The Cheltenham Panopticon is surely staffed to a considerable extent with managers, Oracle DBAs, algorithmists, linguists who are absolutely Our Kind Of Fannish People: geeky quoters of Monty Python and Spaced and Adventure Time, voice impersonators of Julian and Sandy, devotees of I'm Sorry I Haven't A Clue. They probably read this blog and Charles Stross's and Boing Boing with genuine pleasure, tinged only slightly with pro interest. They're nice people just like you and me. God help us.
Hey, @Patrick, a small but important correction to your lede: "the NSA has been breaking most encryption on the net."
From all appearances, the NSA has broken nothing, or very little. Rather, they have spent $250M/year sabotaging security software, deliberately introducing vulnerabilities in it.
The difference is significant in many ways, but here is the most important one:
* A break that only the NSA knows about may take a long time to replicate, while a backdoor is likely to be discovered by other parties (criminals, spies, etc)
The reporting on this has been pretty ambiguous, but recall that ProPublica's report -- based on the full docs, including the sections redacted at Obama administration request -- quoted Snowden's Guardian interview: "Properly implemented strong crypto systems are one of the few things that you can rely on."
The difference between a break and sabotage then, is that if we use open, auditable tools that are well-made, the NSA can't spy on us. If there had been a break, there would be no hope at all.
It seldom makes sense to try to attack crypto, at least assuming the crypto isn't terribly weak. (But GSM encryption and WEP encryption are examples where terribly weak crypto was fielded widely, so it can happen.) Otherwise, the best places to attack crypto are usually in the key management (especially random number generation) and the implementations.
And this is why I never ever put anything on my computer or on the internet that I don't want everyone and their dog knowing/finding. I'm not afraid to admit that the internet scares me.
academic @ 25 :::
I don't think Charlie was aiming his barbs at you. I think he probably meant to aim more toward people like me, only in my specific case, I did read Applied Cryptography and other similar texts— for all the good it did.
Short shameful confession time: I was the technical editor and primary contributing author to Recommended Simple Security Capabilities in Customer Premises Equipment (CPE) for Providing Residential IPv6 Internet Service [RFC 6092]. A fairly reasonable summary would be: "Hey kids, let's make sure IPv6, which doesn't need NAT gateways, breaks the end-to-end principle just as thoroughly as IPv4 does!"
I'm not terribly happy that this RFC needed to be written, and on balance, I think the Internet Architecture Board (IAB) should not have endorsed the need for this RFC to be written. Nevertheless, it did, and I have to live with the credit for having written and edited the damned thing.
I mention this now, because I am consumed with guilt these days. You see, during the development of the RFC, I fought tooth and nail within the IETF for an exception to the "block all unsolicited inbound flows" policy to be carved out for IPsec, c.f. the Bruce Schneier article about how to secure your systems. At the last minute, while the draft was in the RFC Editor queue, I had to add the following paragraph to the Security Considerations section. Some of you here might find it quite interesting:
Also worth noting explicitly, a practical side-effect of the recommendations in Section 3.2.4, to allow inbound IPsec and IKE flows from exterior to interior, is to facilitate more transparent communication by the use of an unauthenticated mode of IPsec, as described in "Better-Than-Nothing-Security: An Unauthenticated Mode of IPsec" [RFC5386], and this may be a departure from expectations of transparency set by traditional IPv4/NAT residential gateways.It was my hope when this RFC was published that implementers would conform to the recommendations, and residential network hosts would then be able to use RFC 5386 optimistically to establish IPsec transport associations when communicating peer-to-peer over the Internet. I was really hoping BitTorrent, in particular, would start doing that, but there are lots of other reasons why retaining the utility of IPsec P2P for home users would be a net win for the public interest.
Alas, none of that happened. Could I have pressed harder for endpoint implementations to take advantage of this mechanism? Yes and no. I would have certainly met with vigorous disapproval (at least) from my employers, who don't much like to see their engineers speaking in public. I could have evangelized harder, but I probably would have had to quit my job to do it. I didn't do that.
Moreover, it turns out that adding the admission I quoted above from the Security Considerations section seems to have been enough to make some implementors decide that blocking IPsec and IKE anyway is a very good idea. In my probing of the Internet to see how well implementers have conformed to the RFC, I'm finding less than cheery results. Maybe I should have pushed back about adding this admission to the Security Considerations section.
So yeah, IPsec is broken for home Internet users— even on IPv6— and I'm partly to blame for that. I was a coward, and placed my own family's well-being above that of all of yours, and I'm ashamed of it. Maybe the rest of you can feel like none of this is really your fault, but as for me? Let me say this: I have an awful pain in my stomach nearly all the time these days.
What really bothers me about the whole sordid set of events is the collateral damage from the revelations and allegations of misuse.
Case-in-point: Pamela Jones (PJ at groklaw.net) shut down her entire operation because she felt that she could no longer encourage people to expose themselves or their secrets to being exploited by one or more secret (or secretive) organizations. How many other groups or individuals are going to be intimidated or self-censor to avoid this (real or perceived) risk? How many of the good ideas and conversations from that forum and others will we now miss out on?
It is not just the immediate cultural smog that irritates our eyes from disasters like this that matters. It is the downstream pollution from the toxic effects of governmental and organizational misbehavior (like culteral dioxins) that will persist in our society for years to come.
Reading that "ways to keep yourself secure from the NSA" link -- goddammit, are people really still recommending TOR? (Not the publisher, the anonymizing network.) It's funded by the US government, fer chrissakes.
This is the latest edition of "fundamental vulnerabilities in the TOR network as deployed". I would be surprised if it's the only problem or the worst problem, and it's pretty damning as-is.
Cory Doctorow @38: From all appearances, the NSA has broken nothing, or very little. Rather, they have spent $250M/year sabotaging security software, deliberately introducing vulnerabilities in it.
As a software security friend of mine puts it, that seems like a lot of unnecessary work given our proven track record of introducing vulnerabilities without help.
"After all, if I got quoted sounding too much like an NSA conspiracy nut, my colleagues would laugh at me. Then I might not get invited to the cool security parties. All of this is a long way of saying that I was totally unprepared for today's bombshell revelations describing the NSA's efforts to defeat encryption. Not only does the worst possible hypothetical I discussed appear to be true, but it's true on a scale I couldn't even imagine. I'm no longer the crank. I wasn't even close to cranky enough." — cryptographer Matthew Green
Charlie Stross @32, maybe I’ve misunderstood it, but isn’t the password cracker in that article a very sophisticated form of dictionary attack? It mentions cracking a Lovecraft quote by finding the passage quoted online.
I’d think random clumps of alphanumerics would survive a dictionary attack, though they might have to be clumped more than 8–10 long.
A 10 character random alphanumeric string has around 3.65 * 1015 possible combinations.
Even a dictionary has a lot of words to check.
These guys aren't attacking just by trying passwords at the target site. They are somehow getting hold of the site's encrypted account data, usernames and passwords. That site encryption is by some sort of one-way function, which takes the data submitted on login, encrypts it, and compares it to the already-encrypted file data.
It's maybe a hash code. Nobody needs to decrypt the file to check for a match. Unless the NSA have cracked the math or suborned the process—what if the registration just sends a plaintext copy to the NSA—they still need to try a set of possible passwords. Maybe, by now, they've already worked out most of the hash codes and can just do a reverse look-up.
But why leave yourself open to a dictionary attack?
Is anyone else bothered by the code-names for the US and UK versions of these projects (“Manassas,” “Bullrun,” and “Edgehill”) being taken from major battles in the US and UK civil wars?
Avram @48: That, and the clear categorization of anyone who uses encryption as an adversary, without consideration of any other characteristic.
Also, the NSA is supposed to have 2 missions: intercepting the communications of potential adversaries, and protecting the communications of Americans. It bothers me immensely that they decided to over-do the first half of their mission at the expense of completely undermining the second half.
There's still Freenet, which is open source and believed to be fairly secure. However, the potential vulnerabilities that I recall, do involve massive computing efforts, which is of course an NSA speciality.
48
It was pointed out at emptywheel (not by me) that Manassas an Bull Run are the same battle. (I added that there are two battles of Manassas/Bull Run, and the Union lost both of them.)
Manassas was the name used by the Confederates. I think the Confederates used settlement names while the Union used geographical features, mostly. So Antietam Creek and Sharpsburg. But sometimes both sides used the same name.
Random one-time non-repeating key, with all the calculations done non-electronically. It's the only way to be sure.
Interesting column by Henry Porter here wondering why this isn't dominating the news to the exclusion of all else.
The Ars Technica article is a must read. The takeaway is that you have to assume that (a) the hacker knows the scheme you used to create your password, (b) has an unlimited number of tries at cracking it, and (c) regardless of anything else may get it anyway, so you can't reuse it or any variation of it anywhere else.
(a) is what really gets people. Even the Ars Technica article has a bunch of people posting their clever, never-before-thought-of scheme. And a lot have responses from the cracking crews that say, yeah, we thought of that. For example, attacks tailored to a site. If they're working on Example.com, they'll throw in variations of "example" as prefixes, suffixes, alternating letters, etc. That's why decorating a single password for each site doesn't work.
(b) and (c) are simply out of your hands. You don't know the security of the sites you're using. Even if they encrypt them properly, you still don't know if their web server has been hacked to record entered passwords.
Passwords that are very hard to crack are easy to generate -- just use a different 20 random ASCII characters on every site. The problem is remembering all of them. Schemes using keyboard patterns, first letters of sentences, or other patterns aren't very secure because they follow patterns, and computers are very good at patterns.
Diceware is probably the best compromise. It gives you truly random words out of a list of 7776. As long as you throw out anything it generates that's too short (in theory you could get all single-letter words), it's very secure, and you can come up with some mnemonic to remember it. You can also write it down, so at least they have to physically break into your house to get it. This is essentially XKCD's "correct horse battery staple" scheme.
I'm using a Diceware passphrase along with the Lastpass vault, using it to generate individual random passwords for each site. Unfortunately some sites do limit the complexity, but I can at least make them as complex as the sites allow.
So I've told you exactly how my passwords are generated, and I've even given you the list of words that the passphrase for the vault is using. But it's still going to be very very hard to break, and that's the advantage of this system. If any site gives up my password, it's useless anywhere else.
Like anything, it's not foolproof. If there's a flaw in Lastpass's encryption and someone gets a copy of my password vault, that's bad. Or someone could put a keystroke logger on my computer. I can take precautions, but I can't rule it out 100%.
As for SSL, you don't have to pick the lock if you can get a copy of the key. If the NSA can get copies of the top-level signing authority certificates, forging their own and doing man-in-the-middle attacks is pretty simple.
This could be done either by secret order, or just breaking into their systems.
People have long suspected that the cryptography libraries from major operating systems have backdoors, though nothing's been revealed publicly.
Open source may at least be reviewable, though you're you still have to trust someone at some point. A classic Unix exploit modified the C compiler to recognize it was compiling the "login" program, and insert a back door. And it also recognized if it was compiling itself, inserting the backdoor into the compiler executable too.
So it depends on how far down the rabbit hole you want to go. Exploits could be in the encryption code, in the compiler, in the operating system, or even in the CPU microcode. Once you use any binary created by someone else, you don't really know.
Alan Hamilton @ #56:
As per 'Reflections on trusting trust'. Thankfully, we can now defend (or at least detect) this attack, via a technique called diverse double-compilation.
Secret-court-order cryptanalysis is SO cheating.
Alan #56:
The libraries inevitably have many flaws. Whether some were put there intentionally is unclear, but it's plausible. And that's true whether or not NSA had anything to do about it. NSA's actions are getting a whole lot of press attention right now, but it would be really dumb to assume they're the only ones doing this stuff, or the ones doing it in the most reckless or destructive ways.
The thing is, crypto is pretty hard to get right, so there's a lot of opportunity for accidental weaknesses, for intentional weaknesses, and for accidental weaknesses that someone notices and starts exploiting.
Alan #55:
The fundamental problem here is that having human beings remember and type in passwords hard enough to resist offline brute force attacks is almost hopeless. That's the kind of attack you get if you steal a password file (a file full of userids, salts, and password hashes), or if you're trying to crack an encrypted file whose key was derived from a password.
There are technical measures that can help a little. You can make each operation that hashes a password more computationally expensive (aka, use a high iteration count). You can use a hash function that requires a huge memory to compute to make it harder to use lots of graphics processors in parallel to crack passwords (aka memory-bound functions). You can do some pre-checking of the users' passwords and reject the obviously-bad ones, if you don't mind really irritating the users. But in the end, you're fighting a losing battle--the complexity of the password needed to get a given level of security doubles every 18 months.
It is interesting to understand how password crackers work, and doing so helps you understand how to choose good passwords. But this isn't something you can expect most people to do, for the same reason you can't really expect most patients with a sinus infection to go read up on the mechanism of action of the different antibiotics they've been prescribed.
You have entered a password, which has been hashed down to some hash value H. It costs me X (time, memory, dollars, whatever) to check each guessed password.
I have a set of generation rules. Each one is basically a program to generate a sequence of guesses about your password. I can run these in parallel, or in sequence with a time limit--try rule #1 for 5 minutes, then move on to rule #2, etc.
A generation rule might be something like this:
Rule #1: For each word in dictionary D, try the word with every possible capitalization.
Rule #2: For each word in dictionary D, try every possible 3-digit prefix and suffix, so that word "apple" gets "123apple" and "123apple999" and "apple000".
Rule #3: For each word in dictionary D, try the word with each common substitution (e->3, t->+, etc.)
Rule #4: Choose two words from the dictionary, and combine them with a symbol between them.
Rule #5: Generate every possible date between (whenever) and (whenever), in each common date format.
and so on.
Some of the rules will be more-or-less random--try every random sequence of up to (say) 7 printable characters.
Others will be more subtle: using a 4th order Markov model of English text, generate passwords in descending order of expected probability.
Still others will use other available information, like name, userID, date of birth, etc. Anything you have.
Computing power is *cheap*. Thanks to graphics processors and the rise of Bitcoin, there has been a huge amount of effort in building up very efficient massively parallel brute forcing machines. Attackers can throw a *huge* number of cycles at cracking your password.
You should not assume you get any security from the rule you use to generate passwords. First, because it's liable to be in the attack tools somewhere (attackers learn from compromised passwords that are leaked, and write new generation rules), and second, because your password is very likely to be close to some other rule even if yours isn't guessed.
Instead, assume your technique for making up passwords is known. How hard are the passwords to guess then?
If you choose five words from a reasonably large vocabulary, you've got a pretty good password. (Assume a 2^{13} = 8192 entry dictionary, if you chose five words at random you'd get 65 bits of entropy, which is not enough for a strong encryption key, but is better than probably 99.99% of all the passwords in use.) There are techniques for choosing these at random using dice, or by starting a long phrase in your mind and selecting every 10th word. None are especially user friendly, and five-word passwords are probably easier to remember than the monstrosities a lot of systems demand ("W183#aona[$ef"), but they still aren't easy to remember, and they're a pain to type. (Though you can shorten them to three or four letters, or disemvowel them, without losing all that much entropy--maybe add another word.)
But all this is ultimately an unworkable kind of security mechanism. We keep using it because it's there and everyone expects it, but it doesn't really make any sense. Even with a password encryption program, this is just barely workable.
albatross: So, okay. What would be a method of generating easy-to-remember passwords?
passphrases are good. Especially if you xkcd it. But you need a different one for everything, because even if nobody can crack it in reasonable time, who knows if that new site you made an account for today isn't the one that either the NSA (or worse) has control of, or stores their passwords in the clear, or has an unindexed debug page that allows password->stored value runs without checks or notifications, or...and as soon as I have one of your passwords, now I have a much higher chance of guessing the rest, if they're identical or related.
I bet at least one in a hundred games available for "play, make an account" is 0wned by somebody, and on some of them, the game itself was written as a way to get your passwords.
Get a cloud drive of some sort, get a password locker of some reputation that creates strongly encrypted databases, pick *a* strong passphrase (that you change on your birthday, say), and let it randomly create 16-character passwords you just copy-and-paste into the application (or that do auto-population). Change those passwords regularly (use the locker program to remind you to do it, and follow its orders). Keep the program on all your devices, and the database locally and auto-synced (but not auto-deleted) on the cloud drive.
If you're perfectly paranoid, that doesn't help - they could have subsumed the password locker, or the cloud service, or they've installed a clipboard stealer or a keylogger, or a TEMPEST reader, or a Lacey-keypad wear scanner, or...and it does require you to be especially careful of prying eyes/CCTVs when you put in your master. But it's significantly better than any system that relies on your own memory.
Hash/rainbow tables: one comment on that is that remember, they don't need to guess your *password*; they just have to find a collision (a password that hashes to the same value as your hash). Using hash tables as one-way functions is exploiting a side-effect; hash tables were designed to massively reduce search length by minimizing collisions and spreading out the search. By hashing one hopes that the randomness of the search space is massively increased (for English, for instance, individual consonant-vowel starts to words are much more likely than individual consonant-consonant, so the dictionary space "clumps" around ca*, ce*, ci*, as opposed to cb*, cf*, cj*. So a hash (into a prime somewhere around 10 000 buckets, say) tries to bring the search space (say 1 000 000 words) into collections of 90-110 each, rather than the 0-40 000 a flat bucketing would do). The good news is that (as a side-effect), good hash functions are irreversable, and "near misses" hash to totally different values. This makes hash tables very good for storing password verification data. If, however, you create fewer buckets than search space (which is almost always done), then you will get collisions. They won't be reasonable to humans ("password1" might collide with "Si2%9f,EO10dNgieLdwIThGSLEmjgpoelDkqw1"), but you just run your hash generator on random strings, populating your rainbow table until you get one for each, and you're good. NT's rainbow table is a function of this "search space too small for Moore's Law" (both in terms of computing power, and in terms of storage space for the results) problem.
I have some passwords in this text, which look, I'm sure, like spam-padding crap. Sorry. Limited-release Unibroue Lager, anygnome (warning, 10% abv)?
I use a very long password to maintain my password safe. I usually have my password safe program generate random passwords for new accounts (or required password changes), which I then modify to fit the site rules (include a digit and a special character and capitalize something), or how I'm going to be entering it (stuff you have to enter via an iPhone should not have lots of switching between different soft keyboards, for example), or whatever.
Whenever possible, I also use two-factor authentication. For Gmail/Google Drive, that means that whenever I log into my email account, I get a text message to my phone with a six-digit code, which has to be entered into the login screen. You can set this up to only be required when you try to log in from new machines--your laptop or phone can keep logging in with only a password. You can (and should) also generate some one-time passwords to use when you can't get text messages, but then you need to store them somewhere. If you have a password safe program, that works pretty well.
The really critical place to use this is for the email account that you used to register for all your other online accounts, because when some bad person gets access to that email account, he will go to each of your other accounts and click the "I forgot my password" button, and will end up having a new password emailed to him for each of your online accounts.
re: #65 Albatross
What's available outside of gmail/Google Drive for the secure code, anyone?
So, one thing I've been muling over over all the latest sets of revelations.
All the documents or explanations talk about "exceptional cases" where the law was accidentally broken (now, granted, the number of exceptional cases is in the same frame as the number of "exceptional deaths" in the year, and you don't see the police saying that first-degree murder doesn't happen often enough to be a problem). But here's the issue:
You can stop a system fault in three places: you can say you won't do it; you can tell people via policy not to do it; or you can stop it from happening in the system. The first is the "societal agreement" or "gentleman's agreement", and bypassing that can gain if you don't get caught or shamed. The second gives cover for management: "we *can*, but we have policies and procedures that say we won't, so anybody who did was either an accident or a malefactor we got rid of." But our newspaper just reported on a commercial vehicles highway stop the police did last week. By law, you must do a daily inspection, have that report, and present it as demanded; and if there are defects that make the vehicle undrivable, you don't drive it. Out of 1000ish vehicles they stopped, 40% had undrivable defects; another 30% had drivable ones (the story didn't say how many were on the inspection report). People slack off; whether it be "I don't care", "I don't see why we should", "I don't see this is a problem", or "the cost of following procedure is higher than the cost of not", it will happen.
If it's important enough, once you identify the fault, you build the system to make it impossible to do it accidentally, and requiring procedure be followed to do it deliberately. It costs - in time and in money, and in reduced functionality (code spent doing this is code not spent doing "real work"), but if it's actually important, you do it.
It's clear that this didn't happen. Therefore, it's clear that following the law, and protecting Americans from their government, wasn't a high enough priority to actually matter. Whether the ability to have "accidents" was actually desired is not proven; but surely disinterest in the law - what little law there actually is, and who knows what the secret laws say - is definitely a sign of contempt for the their official customers. So the question becomes "are the American People their customers in reality, or just in law and on their slogan?"
My guess is that a lot of the overreach and massive overcollection come from the same source as the stuff in the Top Secret America stories from a couple years back. Great massive gobs of money flowed into NSA, and from there into their well-connected contractors, along with authorization to do a lot of new stuff.
Empires were built. Budgets were justified. Minions were promoted to subordinate evil overlords of their own domains. Everything was done fast, not because of a huge threat (the threat wasn't actually any bigger on 9/12/01 than on 9/10/01, and within a few years it was much smaller for a bunch of reasons), but rather because the rich years when the words "homeland security" or "9/11" were magic words that brought limitless funds were only going to go on for so long. Along with those funds came almost limitless deference to spies and soldiers about what was necessary to fight the war on terror, and almost limitless willingness to pardon oversteps and violations of the law, if they seemed to be done broadly in service of the goal of fighting terrorism.
I suspect this explains the cavalier attitude toward privacy and laws, as well as the clearly slipshod attention to security and compartmentalization of data that must have been behind Snowden having access to the stuff he has leaked. I suspect that this is also behind the apparent decision to intentionally insert weaknesses into crypto and security products and standards. (If that allegation is true, a number of people should lose their jobs and some should likely go to jail for it. That was a spectacular own-goal.) Empire building, a gold rush, the Peter principle, and the iron law of institutions can probably explain a great deal of it.
My other guess is that every step of these programs started out with something most of us would recognize as genuine good intentions. And that by now, a great deal of the programs have probably been subverted for all kinds of bad uses, only a small fraction of which will ever have been leaked. (If nobody made a slide presentation or wrote a formal document about some misuse, it doesn't look like Snowden's going to be able to leak it.)
It's my understanding that, before November 2008, Snowden was very much in favor of what he now decries.
Serge:
I seem to recall reading a statement from him saying that he was upset by this stuff before 2008, but hoped that electing Obama would put a stop to the worst abuses. But who knows what's really in his heart, or was?
69/70
He may not have realized, before he worked there, how much they were actually collecting.
I wish I still had the link to where I read this about Snowden. If I remember correctly, he knew exactly what was going on and was quite gleeful about it. If I'm wrong, I'll eat crow, but I'm not making this Libertarian gent into a saint.
I guess I don't see the relevance of Snowden's good or bad moral characteristics. Whether he is a good or bad man, what our government is doing in our name, here and abroad, seems about a million times more important.
Indeed this does not excuse the govt's actions, past or present, but his timing takes a lot of the purity out of his actions and motives. For me anyway. Let's see if the GOP will use that in 2016 to undermine the next Democratic presidential candidate.
I'm not sure I would wholly trust anyone, not even Snowden himself, on his motives. But I recall a lot of people being hopeful about Obama when he was elected, who are now sorely disillusioned.
"Secret laws."
Every time I see that phrase used about the US, my blood boils a little hotter.
Dave Bell @ 75: Hell, I recently disagreed, sincerely, with a musician I greatly respect about what one of his songs means, so I get your skepticism about Snowden's insight into his own motivations.
But I wasn't that disappointed by Obama. I expected him to be about what he was, except better on civil liberties. That was a shock. But he saved lives already with the Affordable Care Act, which is more than anyone but Monica got from Bill Clinton.
I don't know what Snowden's actual motives were, but I would think that his idealism wore off pretty fast after he started working at NSA and discovered what they really do. I've never thought of him as either a hero or a saint.
Mycroft W. @#63
My password locker is on my password protected smartphone. The backups I make of the phone are on my laptop. I am trading off some recoverability for at least illusions of being hard to harvest.
My phone's a BlackBerry, which will wipe itself on the tenth bad password attempt. And the recovery software's good enough that a wipe and restore doesn’t lose anything, I have needed to a couple of times.
Still vulnerable to the rubber-hose attack, of course.
Carol:
I know some other providers are using two-factor authentication with IMs to phones. Also, many banks set a cookie on your local machine, and then give you extra validation questions if you try to access your account from a different machine.
My workplace also provides us with SecureID tokens, which give a new 6-digit code every minute.
Thanks, albatross.
Unfortunately I have a DumbPhone, and my employer is moi.
I use Password Safe on my desktop, but if someone got into that I'd be sunk.
Its password is in my noggin, and in a sealed envelope at a friend's house.
I supposed I should put a copy in my Safety Deposit Box so that if both Friend and I buy it my data would be accessible to my heirs.