Late Meditations on XKCD 936 | Hacker News Reader

Late Meditations on XKCD 936

insideofthebox.tumblr.com

43 pointsgambler56 comments

I had a talk in 2005 and the person was saying passwords belonged to the past. 2014 and we're still there: Why?

- We have browserside certificates. Granted they're not sexy.

- We have logins by email tokens. After all, that's how to do password recovery anyway, so why not promoting password recovery to the normal login?

- We could have thousand kinds of SIM or USB passwords, such as YubiKey, which would have features like, you only auth while it's in the slot.

Instead the last gov website I've used to declare my payroll employees takes the birth date as the default password. And so many others accept my mother's maiden name as an authentifying proof.

How did we get there?

Browser side certificates only work in the browsers you install them in; the average computer user will need tech support to help them copy a key/cert pair to a new browser. The key is also probably not encrypted on disk (by default).

Emailing a login token to a user every time they want to log in requires that their email is working and that they can get to their email, and would slow down the login process. It would waste everyone's time. I think it only makes sense as an additional authentication measure for high security applications where logging in at a moment's notice is not a necessity.

Yubikey is okay for one or two sites if you have one[1]. They cost money, and serve no purpose other than improving security of logins. Compare to a smartphone running a TOTP app. Most people already have a handheld device, and a TOTP app and setup for a website is a free one-time install with one-time setup and no ongoing overhead. It also doesn't require working email or even working internet, which doesn't matter in the typical case but matters a lot in edge cases. Email might be down. SMS might be down. You might not have cell coverage at all.

[1] Yubikey only has two slots, and so you can't store unique OATH seeds for more than two sites, right? How many yubikeys do you expect people to carry around? How many sites even implement HOTP rather than TOTP? If every site implementing 2FA implemented challenge/response for yubikey, then yubikey would be great. However, TOTP is the dominant form of 2FA, and that limits the usefulness of yubikey.

Gregarious device use should sort of be on the decline. To the extent security matters, any ol' device is less and less of a good idea.

Still, I'd like devices to be able to ask my cell phone for authorizations (maybe with a complicated enough UI that the cell phone can limit the valid time of the auth).

Have a look at Yubico Authenticator ;-)

> browser-side certificates (...) the average computer user will need tech support

That's an example of good security with a bad UI. It's an order of magnitude better than passwords. But history didn't make them sexy and it's too late to start.

Sadly, portability trumps everything. The thing is, most people will never experience a identity theft. But most people will want to lock in to some service from a friends computer at some point. So immediate experience, as opposed to analysis, favors passwords over your suggestions.

"I agree but" ;) With a little head scratching, there are excellent solutions.

In Luxembourg, I had a little hard-printed card with 52 letters. At each login to my bank, I would be asked for 3 of them, plus my password. With this kind of extremely-cheap-and-portable token, I would dare to login even from an untrusted country. Because I never have to type the full 52 letters.

That's only for email. Every other service relies on email security.

The problem is, it's the provider (fb, gmail, ...) who chooses how their authenticate you. I wish a system like Mozilla Persona would gain traction (looking at you Gmail), because it would trigger innovation. There are a lot of better alternatives to passwords and SMS for 2FAs.

"I had a talk in 2005 and the person was saying passwords belonged to the past. 2014 and we're still there: Why?"

Because passwords qua passwords are not the problem. The security skill of the median person is. I honestly don't know how to secure people in general, even making the blindingly optimistic assumption of perfectly secure authentication code.

2FA has the problem that to work properly, you must also print off one-time-use reset tokens and properly keep them. (If you can just reset via an email, well, you've just returned back to auth-by-email-account and the second factor is of dubious utility.) Specialized hardware is problematic because it really ought to be open to be secure, but if it's open, it's hard to make the profit enough to make it work... and users would still have to do something to properly prepare for losing their token which is going to be nontrivial.

(Login by email tokens, BTW, is not a great idea in general; obtaining an email account fraudulently should not grant you access to everything the user has. That's a problem with the current system, not the solution.)

> Because passwords qua passwords are not the problem. The security skill of the median person is.

Not possible to blame the people, here's why:

- You can't remember 50 different passwords for each site you're on,

- You can't use password templates because hackers have pattern-matching attacks,

- You can't rely on password managers. Imagine one piece of software that a million people have, which provides access to all their banks and mail and websites? How much is the bug bounty for 1Password? I'll give you the formula: risk occurrence x cost of a leak per user x number of users. That's a hell lot of 0's. Should the bug bounty be under that, it's worth selling your bug to the pirates.

Passwords should have been thrown away in 2005.

"Not possible to blame the people"

It's not blaming the people. That's an entirely different mindset. This mindset is, we have to solve the problem that actually exists, with people that actually exist, with technologies that actually exist.

Further, you read something other than what I wrote. I said that I don't know how to secure people, at all. Explaining why passwords don't work is evidence in my favor, not a reason why I'm wrong. The problem is, it's not as simple as just "throwing away passwords", you have to actually have a solution. After year of people chewing on the problem online and various solutions actually being deployed, I'm not convinced one exists.

It's easy to snipe at deployed technologies and talk about how much better the ones that exist only in your head work. However, the track record on manifesting them is pretty dubious. Those of us with enough technology skills to use things like 2FA are sitting prettier than ever, but frankly we were already the ones that tended to be secure. The evidence that we've successfully pushed this out into the real world is pretty lacking. We can't even get website developers to stop requiring us to use 4-digit pins as passwords on our banking sites.

Thanks for clarifying.

At least now we have Mozilla Persona.

Oh, and a shining example of good mobile fingerprint reader UX. Soon...

How did we get there?

By ignoring human nature and geeking out about the technical side of things? It doesn't matter how technically advanced and theoretically secure an auth solution is. If it has certain kinds of usability problems it will never be willingly adopted by large number of common people. I think to move forward with security we (engineers) need to simply accept this as a fact, and stop bitching about supposed user stupidity.

I've actually seen people use that XKCD comic as an excuse for designing products that prevent the use of password managers.

Pass phrases do nothing to help you manage unique passwords for every site and then expire them when necessary.

Sure pass phrases are great for encrypting your password database, but they are not a substitute for password management.

> I've actually seen people use that XKCD comic as an excuse for designing products that prevent the use of password managers.

These people need to be publicly named and shamed, they're deliberately putting their users at risk.

I agree, but haphazardly shaming products/developers is not a way I want to do it. I don't know how long such a statement is going to hold true once I have made it. Also glass houses and all.

If someone maintained a database of products and how they interfered with the use of a password manager or good password hygiene and there was a way to get off the naughty list then that would be great, but that is a lot more work.

I wish you'd raised that idea like, three days ago. I would have had time to work on it. :)

I'm curious, how can you design a product that prevents the use of password managers?

I'll just pop this here:

  $ cat `which xkcdpass`
  #!/bin/sh
  perl -MCrypt::XkcdPassword -E 'say Crypt::XkcdPassword->make_password for 1 .. 10'

For the chumps (like me) who don't know how to get the perl mcrypt module:

    sort -R /usr/share/dict/words | head -n 4

Even shorter: (and much faster!)

    shuf -n 4 /usr/share/dict/words

Somewhat more seriously, Diceware works pretty well too as a low-tech, high-quality password generation method:

    http://world.std.com/~reinhold/diceware.html

(My only complaint is that a lot of words in the standard wordlist are pretty obscure.)

https://www.fusionbox.com/mouseware/

we wrote this one at my company. It uses your mouse movements as a seed for the random number generator.

Most people who quote XKCD #936 miss the point. It has a decent message, but taking it literally is a grave mistake.

This style of concocting passphrases (chain dictionary words together) as a whole has a low Kolmogorov complexity, and can easily be imported by attackers through wordlist mangling or using some advanced software features, such as Hashcat's combinator attack.

Finally, humans are fallible. They'll always go for certain predictable combinations, and certain permutations will be more widespread among those.

If an attacker has any suspicion you're using the XKCD algorithm literally, it's trivial for them to make a move.

I think the comic is suggesting that the words are selected at random, and not by a human so the distribution is even. That is how you end up with the expected entropy.

The comic makes no expectation or assumption about how the words are selected.

The expected entropy is derived from "correct horse battery staple", including the spaces, using NIST SP 800-63.

When the comic first came out there was a bunch of analysis http://www.explainxkcd.com/wiki/index.php/936:_Password_Stre... "xkcd's entropy estimate of 11 bits per word assumes that the password is being brute-forced with a dictionary attack, and that the words are being chosen from a dictionary of 2000 words (log2(2000) ≈ 11). (For comparison, the entropy offered by Diceware's 7776 word dictionary is 13 bits per word.) If a dictionary attack were not used, the "common words" password would take even longer to crack than depicted. (25 random lowercase characters would have 117 bits of entropy, vs 44 bits for the dictionary words.)"

So yeah maybe it is implicit in the comic, but the math is backed by a specific set of assumption on how the words were selected. Or I could be wrong, I haven't verified it personally.

I've validated it myself for an argument when the comic was published for the phrase "correct horse battery staple".

First character is 4 bits: c = 4

The next 7 chars are 2 bits/each: "orrect " = 14

Characters 9-20 are 1.5 bit/each: "horse batter" = 18

Charactes 21-n are 1 bit/each: "y staple" = 8

No bonus for including both upper and non-alpha chars.

No bonus for passwords of length less than 20 chars, not containing dictionary words, because the password is longer than 20 characters.

Total entropy: 4 + 14 + 18 + 8 = 44 bits of entropy.

There's a little box for each bit of entropy (this is consistent throughout the comic). There are 11 little boxes by each word.

I think it is cool that both estimates of entropy come to the same number, but that still seems like the wrong way to look at the approach even if Randall didn't intend it that way.

The NIST entropy estimation is based off of characters that aren't chosen at random (I think?) and it is a heuristic.

For the approach I think Randall intended to describe they aren't really words, just glyphs chosen randomly from a set of glyphs. That these glyphs are easy to memorize and drop right into existing password interfaces is orthogonal.

While it's true that NIST SP 800-63 gives 44 bits of entropy for the comic's password, this is purely a coincidence. The comic certainly isn't using using NIST SP 800-63 to calculate the entropy. The "xkcd" method extended to, say, 10 words would give 110 bits per xkcd's calculations, but I think it's safe to say that very few of these passwords would qualify as 110 bits under NIST SP 800-63.

The comic says "four random common words". It must take some creative reading to interpret that as "four non-random common words".

Can anyone explain to me why he assings only 2^11 bits of entropy to a word? Doesn't that correspond to choosing from only about 2000 words? If we choose from the more typical adult vocabulary of 100,000 words, isn't that log2(100,000) = 17 bits? Or am I doing it wrong?

I think he did this to show how even with a very restricted dictionary you could still build a relatively secure login system. Having a restricted dictionary could also help with the issues other people are discussing with humans being socially programmed to select certain word orders as their password under this scheme.

He's not assigning entropy per word. He's using NIST SP 800-63, based on the character-length of the phrase, to assign the entropy value.

Proof: https://news.ycombinator.com/item?id=7163362

Typical vocabulary is smaller than that.

And pass phrases will tend away from words like perspicacious.

ok... so what's the message?

Maybe the author just didn't think of Kolmogorov complexity and thought it was a good idea.

The message is pretty much the punchline of the comic.

The other message is: stop posting XKCD #936 for the bazillionth time, you assholes.

The Kolmogorov complexity is almost identical to the entropy (Kolmogorov complexity is applied to a given string, entropy applies to the thing producing it). The entropy estimates in the comic, if you prefer to think of it this way, assume a "wordlist attack" (they actually assume the most efficient attack possible, though in this case I guess you could say that's a "wordlist attack"). It's also assumed that the words are chosen randomly (from the comic: "four random common words"), not "off the top of my head," so no, human fallibility is not an issue with the scheme itself, so much as the way many people interpret the word "random," when in respect to entropy, it has a very specific meaning. It's therefore an undeniable fact that attacking those passwords would require trying an average of half the possible combinations, or 2^(entropy-1). These passwords are just as strong as fully random character strings, so long as you ascribe the correct entropy values.

If it helps, don't think of the words as words, but instead as random numbers. It just so happens that these random numbers are presented in a form that's easier to remember. And 4 random numbers between 0 and 2048 cannot be easily guessed.

I never bought into the XKCD 936 concept. Imagine using 20 web pages regularly, and having to remember 20 unique word combinations of 4 words.

What I do is the following:

I have a function that reliably converts the name of a service -> some string, easy to compute in the brain

passwords are salt + f(service)

where salt is a strong string of characters for critical services (financial, personal info, etc)

and a weak string of characters for stuff i don't care about.

That's effectively security through obscurity. If someone got one of your passwords, he could try to figure out f()^-1 and reverse your funciton, supossing its inversible; that would grant him all of your passwords with the same salt. Specially since you just now published an outline of your scheme.

All passwords are effectively security through obscurity, with varying sizes of trapdoors. If someone got a hold of your piece of paper that has all of your passwords written down on it, then you're hosed as well. If you're being targetted, you're basically in trouble no matter what. Sometimes security just has to be good enough, for most users, good enough is such that having one password compromised by a trawling operation is sufficiently firewalled against having the other passwords compromised by an automated agent.

Even so, you can bet that for things I really care about that are difficult to reverse (such as, like, say a bitcoin wallet) I'm not going to use this scheme.

Can you programmatically enforce your password generation scheme? No. Can you at least encourage it via system design? Unlikely. So essentially you're just saying "users, you should do it my way". This is what most developers have been saying for decades, and it simply does not help.

but that's exactly what the xkcd article did. I'm just pointing out a deficiency in the xkcd scheme, and offering an alternative. Some people may have a better arbitrary associative memory than I have, and for them, the xkcd scheme is a better choice.

Edit: Although the original xkcd was specifically complaining about silly practices that arbitrarily restrict the xkcd scheme.

You can use phrases which link into the service name:

Face book

    a common occurance with narcolepsy

Twitter

    said the robin, from the obnoxious flock

Hacker News

    Read all about it - people angry at programming feature

I like this!

Pass phrases are more memorable and at least appear more resistant to password cracking attempts, but as Mat Honan's experience and this recent post here on HN (https://news.ycombinator.com/item?id=7142916) both show, your account security can come down to a successful social engineering hack on a minimum-wage customer service employee who has the power to reset your account password.

This is true however a close read of the article you site would show that part of the reason that that hack is possible is because in our current paradigm the idea that someone would have completely forgotten their password. If pass phrases became more common then perhaps customer service reps would be able to be more skeptical of the social engineering ploy that was put to use in this scenario

Perhaps. Unfortunately, that's probably a pretty big "if".

True but it would be interesting to see some data on how many over the phone password resets big service providers do on a day to day basis. That kind of data would at least be a litmus to invalidate the current paradigm.

I would like to see some numbers on that. Is it as pervasive as it seems, or are the ones that get through just dramatic enough to set people on edge?

Maybe what we really need to do to prevent identity theft is increase the minimum-wage. :)

It couldn't hurt. At least the general populace's purchasing power would increase.

I dislike the idea of allowing permutations in word order. Remembering a strong passphrase involves muscle memory and finger typing, so having random order for words in a pass phrase would not help most people.

Passwords are horrible. I can't wait for the day when we have 2FA with something like a Yubikey (but better) and a short password.

Muscle memory works well for commonly used password, but what about rarely used ones?

Words can be blended into a single impression or narrative for easy memorization, and giving the user the ability to order them to support that narrative will greatly improve usability. (Besides, if you're consistent, your muscle memory will work just fine.)

"The golden goose crows from the cliff."

I don't know if this is the answer, but I like where the author is going. I like the way PG approaches these things: will we be remembering ridiculous combinations like r@bb1t24 in 50 years? Somehow I doubt it.

I remember my amazon password from ~15 years ago.

Reply on news.ycombinator.com