Relevant portion of the transcript from Security Now! E313
TOM: All right. Let's move into the security news. And I was really excited when I saw this xkcd cartoon yesterday. Randall Munroe, who does xkcd, is really smart, really funny, and it's absolutely worth reading this every day. But as soon as I saw his cartoon for today, Password Strength, I immediately thought of you, Steve, and the Haystacks, because he's talking about exactly what you were talking about, which is you make these really complicated passwords that you can't remember, and they're actually less secure than an easy-to-remember password.
Steve: Well, yes. So it's a great cartoon. I know that I'm involved in social networking when thousands of people are sending me this cartoon. It really filled up my Twitter feed. And I was glad for it because I appreciated knowing about it. So just for those who don't, you can just go to xkcd.com today. Or, if you're not listening to the podcast today, it's #936. So xkcd.com/936, which will get you to this fun cartoon.
I have to imagine, Tom, that this was inspired, in fact, by the Haystacks page because the second frame of the cartoon talks about how 2^28 bits of entropy, or 28 bits of entropy is 2^28 combinations, which takes three days - and he's correct about that, it's like 72 hours or something - at 1,000 guesses per second. Which is exactly the number I use on the Haystacks page. And then he says, "(Plausible attack on a weak remote web service. Yes, cracking a stolen hash is faster, but it's not what the average user should worry about.)" Which is exactly the language, or a version of exactly the language I have on that page. So I'm delighted that Randall Munroe picked up on that and probably knew about it.
The only problem I have is that his math is wrong. In the first frame he talks about - he uses little squares. I mean, I love how graphical and xkcd-ish this is. It's typical for the work he does. But he's not assigning bits for entropy correctly. And he's doing it in a way that benefits the point he's trying to make, so I'm not criticizing him. Just for the sake of our listeners, if you put his example into the Password Haystacks page, it shows that you've got - where he says his example has 28 bits of entropy, I calculate it at 72.3. And so rather than it being three days at a thousand guesses per second, it's actually 1.83 billion centuries at a thousand guesses per second.
But that really wasn't the point he was trying to make. He was trying to make the point, and the cartoon does beautifully, that what we've done in trying to create bizarre passwords that are impossible to memorize is we've actually, in some cases, not come up with something that has substantially more strength than, in his case, he suggests taking four easily memorized random words from the dictionary and concatenating them. So he computes them as each having 11 bits of entropy, so he's assuming that we had a dictionary of 2,048 words because that's 11 bits, and that we randomly chose them from the dictionary to assemble a four-word sentence which is easy to remember. So 11 bits of entropy each, times four words, is 44 bits of entropy. And then he says 2^44 is 550 years at a thousand guesses per second. So that's clearly long enough, since none of us are going to live that long.
TOM: And on Haystacks it says 78.3 billion trillion centuries. So it's an order of magnitude more secure than the first password still, even when you're comparing it through Haystacks.
Steve: Now, the problem with this is that he ends up with seven - so his example is "correct horse battery staple." And that's a total of 25 characters. It's surprising how many websites won't let you use a 25-character password.
TOM: Yeah. We've talked about this before. It's so frustrating.
Steve: Yeah, yeah. So some require, like, between eight and 16. So you'd have to drop a word or two or something. So really, if you end up with a website that has a ridiculously small or a worrisomely small maximum password length, then you're really forced to expand the size of the character set. He's using all lowercase. So I would say yes, that's a good password. But we also know there are other ways to create strength.
And in fact explainxkcd.com, which apparently follows xkcd.com's cartoons one for one, like daily, he explains this and has a link to the Haystacks page at GRC, explaining that this really comes from an understanding of what it takes to make passwords strong. And of course I take the point or the position that as soon as you're forced to do brute-force cracking, length matters more than entropy, which was the theme of the Haystacks page. So just sort of a fun little coincidence on the day that we're recording the podcast. Go ahead.
TOM: I was just going to ask, if I use "correct horse battery staple," I don't have to - my immediate reaction is, well, those are four dictionary words. Wouldn't a dictionary attack find them? But the fact that there are four concatenated random words makes it so that it's harder for that dictionary attack to work?
Steve: Well, okay. So here's one of the things that's hardest to get your head around, and this is the reason that first frame in the cartoon is a little misleading, is, for example, he appends a number "3" on the end, and he gives that three bits of entropy because that could be any one of 10 digits. But the key is the attacker doesn't know that you put a digit on the end. If you said to the attacker, oh, and by the way, while you're trying to guess my password, I ended it with a digit, well, then the attacker would go, oh, thank you very much. Now I don't have to try all the lowercase alpha, all the uppercase alpha, and special characters. I'll just try zero through nine. And so in that case he's right. That would be about, actually less than, three bits of entropy. No, it would be a little bit more, actually because three bits would be eight combinations.
But the point, the key of the concept is the bad guy has no idea what you've done. And if they did have an idea, if the bad guy knew that, for example, a password was four dictionary words, then, yes, then you've restricted the domain of experimentation. But the bad guy has no idea what you've done. So the fact is, it is much easier to make a much stronger password of a certain length by adding, changing the case, and salting it with some special characters. I mean, even, for example, if you took "correct horse battery staple," and you just stuck dashes in between, or your own special joiner character that you didn't tell anyone about, that makes it radically stronger because the bad guy doesn't know what you - if you make any change to it. Because, and that was the real insight that the Haystacks page tries to bring across is that anything that you do that is going to sort of take it off the map, all the feedback the attacker gets is it either matches or it doesn't. They don't get - it's not horseshoes and hand grenades. They don't get, ooh, that was a close one.
TOM: Yeah, yeah, yeah. I think that's what our minds do.
Steve: It's getting warmer. It's getting warmer.
TOM: Yeah, yeah. We think that. We're like, oh, well, we'll get close, and then we'll start to figure it out. But I think the only weakness that I can think of in this is if somebody cracks a password in some SQL injection attack at a site that was not properly salted, and they get your format, and they want to go after you. And so they go, okay, it looks like he takes the last two letters of the domain name, and then always has the word "d0g" spelled with a zero. If they get that little extra bit of information, it would undermine this.
But otherwise, this is definitely the way to go. Cory Doctorow on Boing Boing pointed out there's a study done at the University of London showing the cost of having these complicated passwords because people can't remember them. And then they rely on the less secure questions that allow you to recover passwords and all that stuff. So easy-to-remember secure passwords would save us time, money, hassle, and all kinds of things.
Steve: Or maybe passwords that you don't need to remember.
TOM: Yeah, now, that's - I'm really interested in that.