1. 26

Today I saw a disturbing Gizmodo article claiming that it would take 550 years to guess the XKCD “correcthorsebatterystaple” password.

While researching this subject, I noticed this blog post from Dropbox on their zxcvbn “password strength” meter library, which included this incredible sentence:

For example, even knowing the word-word-word-word structure of correcthorsebatterystaple, an attacker would need to spend centuries cracking it.

That is completely incorrect, and I’m disturbed how much confusion the XKCD comic has generated, that it has resulted in statements like that. The linked twitter thread explains why this is wrong. At heart, there are two critical mistakes in the XKCD comic:

  1. The idea that a password’s entropy is easily and accurately calculated. In reality, calculating a password’s entropy is somewhat of a red herring, as there is often information outside of the password that can be used to guess at the password’s structure (e.g. how long it took someone to type in their password)
  2. That password guesses happen at a rate anywhere near 1000 guesses/second. The true rate depends entirely on how the hash from the password is generated. For raw SHA256, it is somewhere on the order of 1197962070743187 guesses/second.
  1.  

  2. 32

    I’m assuming the NIST guy and Munroe are assuming the passwords are not stored as SHA256 hashes…

    The 4 words from a dictionary provides plenty of entropy (even with your “how long they typed” caveat) to foil any brute force approach with a password hashing algorithm implemented by a responsible engineer (bcrypt, scrypt, pbkdf2, etc).

    1. 10

      The thing that gets overlooked a lot, though, is that mass cracks of things like some website’s breached accounts table almost never use brute force, or even brute-force-with-dictionary, as their first tactic. They try big lists of common passwords and password patterns first, and enjoy a high degree of success from doing so.

      And if you got people to move en masse to the diceware/XKCD-style password scheme, every cracking tool would update to try stuff like

      heres-my-new-password
      this-is-my-password
      my-password-for-2019
      

      etc. because that’s what people would actually choose as their passphrases. The only way to avoid this is to force people to use a tool that selects random passwords for them, and even then they’d fight against having to remember one of these for every site or service they use. At which point you need the tool to remember the passwords for them, and then you’ve arrived at “just use a password manager”.

      1. 7

        That’s not how these passwords work. There’s way too much entropy to pre-calculate tables (and more entropy from the salting). And it’s too much entropy to crack for a reasonable price if any sensible KDF is used.

        4 words randomly selected from a large dictionary, say (200,000 words) yields 70 bits of entropy. That on it’s own is way too costly to precompute tables for, and salting typically adds at least another 32 bits (often lots more than 32 bits).

        See the working in my own password generation script here, which generates passwords with entropy of at least X and has another function for approximating the cost to crack a password:

        https://github.com/cmcaine/cli/blob/master/examples/token

        1. 1

          There’s way too much entropy

          My point is that “entropy” is a red herring.

          If you let the user choose their own diceware-style passphrase, you’re going to get things that are cracked within a fraction of a second, because they’ll be choosing things like “my-password-for-2019”, “my-password-for-ebay”, and so on. The alleged entropy of a passphrase of n dictionary words strung together is pointless in that situation, because nobody will be using a brute-force scan of every combination of n dictionary words as a way to crack these.

          Consider an analogy: it’s like saying you’ve developed a lock that’s unpickable because it has a million pins in it, and look how long it would take to pick a million pins! But somebody comes along with an under-door tool and yanks the handle from the other side without even trying to pick the lock. So sure, that was a million-pin lock, but it’s irrelevant how many pins it had because the door’s still open in a couple seconds via a simpler attack method.

          And since you presumably want to disallow reuse of a password across sites/services, if you’re not letting users choose their own, you haven’t really demonstrated an advantage over a password manager that just generates long random strings, because the only real thing the diceware system has going for it is memorability and users aren’t going to commit that many distinct passwords to memory (or recall them correctly later on even if they do try to memorize).

          1. 2

            Neither XKCD or Diceware recommend creating passphrases like that. Of course if you don’t pick your words randomly then your entropy is lower, that doesn’t make entropy a red herring. Entropy remains the key point.

            XKCD passwords are useful for passwords that you need to remember or transmit to other people. Like the passwords for your password managers or wifi networks or whatever.

      2. 1

        The whole idea behind these password hashers is that you aim to make the work take a fixed amount of time (say 5ms). That leaves 200 verifications a second on a single core. This is more than enough for a legitimate use case for authentication but is completely a showstopper against brute forcing with a good password.

        1. 1

          For scrypt, we only have Litecoin to go by as far as estimates go, and it has a weak choice of parameters. With Litecoin, we have around ~300TH/sec, which means a known 4-word structure password out of XKCD’s 2048 dict is cracked in under 0.05 seconds.

        2. 26

          If you’re targeted by a brute-forcing adversary, and the service doesn’t have rate limiting or their db is compromised, and they don’t use hard salted hashing like scrypt/argon, and you don’t have 2FA, and they don’t exploit you in some other way, your password is toast. Surprise! /s

          The point of the xkcd was to highlight the relative difficulty of pass phrases vs strings in light of the former’s increased memorability. Of course the real answer (for passwords) is long random strings in a password manager, or (otherwise) PAKEs or whatever.

          This tweet feels like it’s saying things that are already known to the technical security community, but perhaps not by Gizmodo authors, and simply saying them slightly more aggressively. As such, it belongs as a tweet but not as a lobsters article IMO.

          1. 19

            First, I think there probably needs to be a little grace extended on hash rate calculations to both the XKCD comic, and the Dropbox article considering they’re 8 and 7 years old respectively.

            Secondly, if you dislike the correcthorsebatterystaple advice you should say what you think is a better alternative so we can compare. From the screenshotted lobste.rs thread on this assuming the MacOS word dictionary and four words it has a search space of 235886^4 or roughly 10^21 possibilities. If instead your advice is for a user to pick a completely random password, then assuming they’re picking from the more or less 100 easily typable characters on a keyboard, they’ll need between a 10 and 11 character long random string to match the search space.

            I think if you ask most people if they’d rather memorize correcthorsebatterystaple or ]S7DX)|{”^ they’ll choose the former.

            1. 11

              i.e. how long it took someone to type in their password

              Mathematician pet peeve: confusion of existential and universal quantifier. You mean “e.g.” not “i.e.”

              As to the actual argument, is this saying that if you get the entire bitcoin network cracking your password, they’ll do it quickly? And how would you convince them to do that?

              1. 1

                is this saying that if you get the entire bitcoin network cracking your password, they’ll do it quickly? And how would you convince them to do that?

                Not from the Bitcoin network. The Bitcoin network is used in order to figure out an estimate of how much an organization (like the NSA) would have to spend to crack SHA256 passwords. See the text and corresponding paper in the link:

                Even assuming a centralized effort could be an order of magnitude more efficient, this still leaves us with an estimate of US$1M to perform a 2⁷⁰ SHA-256 evaluations and around US$1B for 2⁸⁰ evaluations. (source)

                1. 4

                  Meh. I doubt anyone’s gonna pay 1 million dollars to figure out my Mastodon password.

                  1. 3

                    Heh, I agree with you there. Also fixed the “e.g.”/“i.e.” thing, thanks for pointing that out. :)

                    1. 4

                      I always remember by replacing “e.g.” with “example given” and “i.e.” with “that is”.

                      1. 4

                        I think in essence.

                  2. 4

                    So if you’re using diceware w/ 7,776 words (13bits/ea), cracking 5 words (64b) costs <$1M, 6 words (77b) $1M-$1B, 7 words (90b) >$1B?

                  3. 1

                    As to the actual argument, is this saying that if you get the entire bitcoin network cracking your password, they’ll do it quickly? And how would you convince them to do that?

                    Have it be in the Mt. Gox leak and show signs of life on other bitcoin wallet sites.

                  4. 7

                    I should point out that XKCD was popularizing a technique called diceware, repeating a proposal from 1995. He was also doing it wrong: in diceware, you were supposed to have a delimiter between words, in order to increase the difficulty for a cracker that used dictionaries as input (since, without a delimiter, the same string can be interpreted as multiple different combinations of words, multiplying the number of opportunities for the cracker to get a hit).

                    As of 2014, the original diceware author specifically recommended moving to six words. Nothing in particular happened between 2012 and 2014 other than XKCD’s popularization of this nearly-twenty-year-old technique, so odds are that doing it with four words was not terribly secure in 2012 either.

                    (I don’t really blame Munroe for this problem. He probably didn’t remember where he got the technique himself – just part of ambient internet security lore. His popularization probably led to marginally better passwords and less password reuse, up until registries for auto-generated passwords started becoming common features of browsers.)

                    1. 2

                      without a delimiter, the same string can be interpreted as multiple different combinations of words, multiplying the number of opportunities for the cracker to get a hit

                      I’ve thought about this a little bit and I’m not seeing how the delimiter makes a difference. Can you provide an example?

                      1. 13

                        makedicespacespare could mean “make-dice-space-spare”, or “make-dices-paces-pare”, or a few other options. This reduces the number of possible passwords that you could have generated, reducing the entropy of your password slightly.

                        1. 1

                          Makes perfect sense. I was thinking of compound words not borrowing a letter or two from a neighboring word.

                        2. 3

                          Let’s say that somebody builds a password cracker specifically to hit diceware passwords. (Such a cracker probably exists – diceware was pretty common in the late 90s, and dictionary-based crackers like john the ripper are more elaborate versions of the same thing.) Such a cracker, if naively written, will brute force passwords the same way we generate them: pick four words, try them with a variety of delimiters and cases, & see if the thing hashes the same. With delimiters, every time it tries this, it will match if and only if all the words it chose are the same as the ones you chose – the basis for the entropy calculation. Without delimiters, there’s the possibility that two selections of words, when concatenated, will produce the same string (ex., “godisnowhere” can be read as “god is now here” or “god is nowhere”). Every such collision is an extra opportunity for the cracker to select a matching combination of words.

                          Let’s say you’ve got a dictionary of 2048 words, and you are using four words to produce the password, and you have no delimiters, and the cracker knows this. If there are no collisions, the cracker has a 1 in 2048 chance to pick each right word, for a 1 in 2048^4 chance to get all four right. If there are four collisions, you have a 4 in 2048^4 chance to get all four right.

                          Increasing that numerator enough to bring the ratio down to a reasonable number is hard for english, but if your password is in romanized japanese or korean (where all combinations of a relatively small set of sounds are more or less equally likely to be real words because of sound starvation & the transliteration of weird loan words into the syllablry) or in a language like german (where compound words are often composed of large sets of regular words strung together in an arbitrary order, rather than having distinct set of prefixes and suffixes), collisions become a lot more likely.

                          This matters a lot for a naive/brute force dictionary cracker. I don’t think such crude tools are used much anymore, though, & somebody more familiar with modern crypto & modern security techniques can tell you whether or not it matters for rainbow tables & other more esoteric things. My knowledge of cryptography is decidedly limited & casual.

                      2. 7

                        It seems to go against most tech security narratives, but IMO, having a hard-to-crack password is of little to no real value. What’s actually valuable and important is to have a unique password for every site, no matter how trivial.

                        It seems to me that if any attacker gets either a system interface where they can try a huge number of passwords without getting locked out, or retrieve the hash of the password to crack at their leisure, then that system is essentially already compromised beyond the hope of protecting anything on it. There’s no point in worrying whether cracking your password would take a millisecond or a month, on a Raspberry Pi or a ten thousand dollar AWS cluster.

                        1. 2

                          It’s not that unusual. It’s literally another xkcd comic

                        2. 2

                          One of the beauties of passphrases - and the way we should be educating people to use them - is that it doesn’t just have to be random words squished together, but could instead be a complete sentence, spaces, punctuation, capitalization, and all.

                          Now, of course, with standard rules you can guess those too. But it still introduces a lot more natural variation that is still simple for the individual to remember.

                          “This password is actually pretty bad, but has never been cracked.” is hard to guess, even if you have a word list and whittle down options based on standard rules of grammar.

                          Of course, it isn’t as good as some auto-generated sequence of pure randomness of the same length, but it is better than “correcthorsebatterystaple” (why wouldn’t you use spaces there?!).

                          1. 5

                            You can also mix words from every language you know, which is what my password generator script does.

                            % for i in {1..10}; do ./pwgen.sh 4; done
                            hover-seafarer-snigl-hare
                            transitory-nautheimskur-valhaj-affekt
                            pappaumbúðum-thimbleful-afbrotamála-stykkjatölu
                            áðurnefnds-dye-storpart-vestaver
                            hraðfrysting-afkastavexti-larkspur-levitate
                            vältrampad-trollrukkone-ward-boðorða
                            polymorfi-trosvittne-tenestemerke-trough
                            dukkardrakti-tungbruka-millipede-lineal
                            peremptorily-úrsúlu-fotbadi-seigliva
                            strollan-provision-fágætast-snuggle
                            
                            1. 8

                              Even though it’s 2019 and this this should not need to be said, but yet it is: be careful with characters outside of the ascii space because that will bring you into contact with many opportunities for whoever takes and stores your password to run into character encoding bugs.

                              If they don’t have specific support and just blindly hash bytes, you might still run into issues due to different Unicode normalization on different platforms you are typing your password on.

                              And if they do have specific support for Unicode, you can be nearly 100% sure they will have bugs in it anyways.

                              If you want Unicode in your passwords, make sure they do work on all the platforms you intend to log in from. Don’t be the person who can’t log in during an emergency when they are on their phone and it’s sending the ü in the password as “LATIN SMALL LETTER U” followed by a “COMBINING DIARESIS” rather than the “LATIN SMALL LETTER U WITH DIARESIS” that the site has seen when it was hashing your password (and that assuming both times correct UTF8 was used)

                          2. 1

                            Authentication as a whole is broken.

                            As a developer, your first and foremost priority should be integrating with a third-party identity provider wherever possible; they probably know better than you about how to secure user authentication. Alternatively, go for something that supports U2F, e.g. ed25519-sk (currently in OpenBSD-current), WebAuthn. Hardware tokens give you much better guarantees than anything else, and with Windows Hello and the general shift towards smartphones (which have their own built-in hardware), this is becoming an increasingly realistic options. Failing that, password (with ideally a PAKE, else a CPU/memory/cache-hard hash; rate limit with exponential backoff in any case) + TOTP is the bare minimum you need to have; the phishing protection is still lessened, but at least you’re better off in the situation of a server database compromise.

                            As a user, you should be using a password manager. Yes, it’s a single point of failure, but that’s why you can make backups of your password manager database. Ultimately, you’ll only need five passwords (the firmware password to boot a device, the encryption passphrase for the volume encryption, the user authentication password when logging in and unlocking the screen, the password manager master passphrase and the passphrase for the backup volumes that contains your password manager database and other backups).

                            1. 1

                              For a dictionary of 235886 words, the four-word “correcthorsebatterystaple” requires (235886^4)/(2^70) ~ 2.6 million US dollars. So what? Just make it six words.

                              By the way, where does this 1197962070743187 number come from?

                              1. 1

                                For a dictionary of 235886 words

                                Indeed, this also goes to point 1, that the entropy is hard to figure out. The XKCD comic indicated that it was using a 2048 (2^11) word dictionary, which apparently is about the size of the dictionary some cryptocurrency wallets use.

                                where does this 1197962070743187 number come from?

                                From this article: 2^75/(365*24*60*60)

                              2. 1

                                Personally I think diceware+password manager is the ideal approach:

                                • The password to unlock your password manager has to be memorable, since you don’t have access to your password manager’s passwords without it.
                                • For everything else, even with diceware I’m not going to remember unique passwords for each site/app I use, so I’d rather just use long, completely random strings.

                                Hopefully your password manager isn’t using SHA256.

                                I also use diceware for laptop/desktop logins (with disk encryption ofc), since a password manager is awkward to use to log in — you have to carefully transcribe from a second device — and I have few enough personal machines that I can remember diceware passwords for all of them.

                                1. 0

                                  I used a similar password strategy for a while and eventually stopped because typing long passwords is surprisingly inconvenient.

                                  When you use a short password, even if it is random, you can type it pretty quickly after a while. Long passwords always take longer.

                                  What’s worse, the probability of typos goes up quite a bit (somehow this seemed non-linear to me – oh, wait. it is non-linear. I’m a doofus.). Sure, you are using a dictionary and you could fuzzy match on the words, or do something like the auto-completion of magicwormhole. It just doesn’t exist in practice, so I gave up on this approach.

                                  1. 1

                                    I use a numeric password for one account and I can type out its 13 digits in about a second and a half (with a numpad at least)… but my fingers are only so proficient on that /one/ pattern, and reusing it risks that being revealed. So the longer sentences still win out on average since I’m pretty consistent with a lot of different ones rather than needing specific practice do type it well.

                                    1. 3

                                      Interesting. I found it really much harder to type longer passwords. Maybe I was too impatient.

                                      I also don’t actually memorize that many passwords. Most are in my password manager. The ones I have to remember are basically: masterpassword for the manager, login password for the machine, decryption password for the drive.

                                    2. 1

                                      I just got used to needing to re-enter my password every now and again. I do not endorse my approach. It’s pretty frustrating, especially on a mobile device, which has a password on the order of 30 characters long with digits, symbols, and multiple cases. On the plus side the phone is less distracting than it might be.