Passphrases You Can Memorize That Even the NSA Can’t Guess | Hacker News Reader

Passphrases You Can Memorize That Even the NSA Can’t Guess

firstlook.org

70 pointsetiam55 comments

This doesn't stop the biggest threat against a government-sponsored entity: if they really want to break into your data, they'll just install a key logger into your bios or some other crazy shit like that.

All these nice pass-phrases do is protect you against people that get big user dumps of hashes like we saw with the recent Slack security breach.

The NSA doesn't need to guess your passphrase. The Chinese equivalent doesn't need to either. They'll just literally watch you type it in. Or use existing vulnerabilities to capture the traffic at your border router. And if you're REALLY a person of interest, they'll just use their CIA equivalent to capture you and torture the information out of you.

FreeBSD has an odd dictionary file (/usr/share/dict/web2a) which has short phrases. I use a script to randomly pull some entries from it and then I piece memorable ones together to make my passphrase. Sprinkle in some punctuation and character replacement and it makes great passwords that are easy to remember.

  % ./passphrase.pl 10
  coppice-topped
  belly-naked
  bastard locust tree
  diamond bort
  middle-aged
  self-mapped
  air level
  field gun
  machine rifle
  chock stone
  % ./passphrase.pl 10
  self-knowing
  soul-killing
  Magna charta
  fly-killing
  spring chicken
  blotting book
  finger-cone
  gauge glass
  Fort union
  assistant examiner
  % ./passphrase.pl 10
  soya-bean oil
  foxtail pine
  island-dotted
  four-way cock
  side-bar rule
  benzoyl hydride
  straight-fibered
  steel town
  stone bramble
  rag-boiling

Not that odd. All the words from Webster's are in web2, all the compound entries (not strictly "words") are in web2a.

That said, "straight-fibered four-way cock" is my new favorite passphrase.

So that explains where they were sourced from. Thanks!

Be careful that your "memorability" pruning doesn't reduce the entropy too much.

You just increase the entropy by adding characters, numbers, etc and keeping it reasonably long (20+ chars). The entropy of my passwords is quite high according to Keepass.

The thing is, you can't determine "entropy" of a password after the creation. It's the creating process that determines how "random" your password is. KeePass's measure is just an approximation, and I have no idea about how accurate it is.

Using web2a is a great idea. I'd written a Diceware-like password generator in Scheme. The word word list was derived from the web2 list (FreeBSD /usr/share/dict directory). Even after paring it down to ~151000 items, the resulting passwords often contained arcane terms limiting password usability.

With the web2a list slightly tweaked, I get many memorable passwords, e.g., "power-weaver-sand-screw-1081" or "cloud-ring-tea-fighting-1107". OTOH web2a is shorter (~76000 entries), giving 2 bits less entropy vs. using the filtered web2 list. Taking password readability into account, the higher rate of "keepers" with web2a probably evens out the difference.

BTW the web2a word list is here (https://svnweb.freebsd.org/base/head/share/dict) in case anyone doesn't have access to it.

I've tested the passphrase:

    password password password password

and most of the online entropy checkers[1] says it's really safe to use such .. is this true?

1. http://rumkin.com/tools/password/passchk.php

Entropy checkers are based on a faulty premise and are always at a disadvantage compared to the state of the art in password cracking. Online security would be in a better place if they had never been invented at all.

The only way to guarantee the entropy of a passphrase is to generate it from a source of high quality randomness (e.g. a CSPRNG or by actually rolling dice, hence the name "Diceware"). Diceware-style passphrases simply balance this requirement with usability by optimizing for things humans are typically good at memorizing (strings of words).

The entropy checker doesn't know about externalities like how common a word is or how likely it is to appear following some other word or how frequently it's used in passwords specifically. It's just measuring the length of the string, and probably the class from which its characters are drawn (in your case lowercase letters and spaces).

Relevant Dilbert:

http://dilbert.com/strip/2001-10-25

my point was using some common word on purpose, expecting it to produce a low entropy result

My thinking was that "Correct Horse Battery Staple" had more entropy than: "go go go go go go go go go go go go go"

.. which, apparently, is not

An online entropy checker is going to assume all the decisions that went into making the password, beyond the ones it's been programmed to understand, were die rolls. This is a false assumption unless, of course, those decisions actually were die rolls. It's generally going to tell you passwords are stronger than they are -- sometimes a LOT stronger.

A password from the space of "things users think up while staring at a dialog box for 5 seconds" has a much different probability distribution than "random strings". There are common passwords, and that's an exploitable pattern, but recognizing those patterns is difficult. All the typical entropy checker is going to tell you is how strong the password would be if it were a random string.

Any pattern is, in principle, exploitable. If I use ten digits of pi as a password, a programmed entropy checker isn't going to know that's easier to guess than ten random digits unless it has been told that, and including all possible exploitable patterns would require rather better software than can currently be written.

So don't trust the results too much.

What you really want to know with passwords is, "Is there outside information that would make this easy to guess?" Does it conform to some external, independent pattern, or are all the patterns in it things you made up after seeing the password itself?

That is why I am a big advocate of random generation as the only safe way to make passwords. Knowing the strength of a password is the same thing as knowing the size of the class of live probabilities from which it's drawn, and to do that you have to characterize the method used for generating it.

The problem is that it depends on your definition of the sample space. In particular if the sample space remains constant.

If your sample space is "all words in the english language, capitalized and uncapitalized", then the second one has more entropy than the first one. But if your sample space is "all characters or runs of characters that appear in the passphrase", the second one has a whole lot less entropy.

http://www.oxforddictionaries.com/us/words/the-oec-facts-abo...

Well assuming random guessing with 95% vocabulary coverage its about 50,000 words. A passphrase checker that doesn't start from there but rather works from the ascii tokens is likely not very helpful for checking the strength of a passphrase.

> ... should be 8 characters or longer, which forces you to use multiple words or extra symbols. > ... should have upper case, lower case, symbols, and numbers; or at least three of those four groups. > ... should not be a common word and should not be a common phrase. > ... should not contain a date, a name, or other things that can be associated with you. > ... should be created randomly or semi-randomly. > ... should not be a suggestion when you type in the first few characters into Google.

As for your cited tester, you seem to have ignored every single piece of advice on the page and it seems it doesn't test for it in an automated way. I'd say, in this case, the problem is a bug in the tester rather than the truth of that being "safe".

If you had followed the guidelines, yes, it'd likely be reasonably safe.

This is actually pretty cool.

From the article: Not too bad for a passphrase like “bolt vat frisky fob land hazy rigid,” which is entirely possible for most people to memorize. Compare that to “d07;oj7MgLz’%v,” a random password that contains slightly less entropy than the seven-word Diceware passphrase but is significantly more difficult to memorize.

At one trillion guesses per second — per Edward Snowden’s January 2013 warning — it would take an average of 27 million years to guess this passphrase.

The other advantage? It's generally faster /easier for someone to type something like "bolt vat frisky fob land hazy rigid" than "d07;oj7MgLz`%v,". At least it is for me.

It's easier on keyboards (since we spend most of our time typing lowercase letters as part of text) and also on mobile (since you don't need to do annoying and error-prone context switching for capital letters or symbols).

I think this is one of the greatest unspoken benefits of Diceware-style passphrases!

I actually can remember a password like the d07 one easier because of keyboard pattern matching. That's how I generate passwords is I draw patterns on the keyboard. It's so unpopular that nobody creates tables for keyboard patterns entries.

I created an account just for you....

https://github.com/Rich5/Keyboard-Walk-Generators

Is the one trillion guesses per second with or without the key-stretching (hashing the master password N number of times)?

I used this concept a while back to generate 7-word passphrases with 84 bits of entropy. I picked a list of popular words and filtered it down to 4270 that are reasonably short and memorable:

https://raw.githubusercontent.com/dbasch/clj-brainwallet/mas...

Here's a browser implementation. I wouldn't use it (do you trust your browser's prng? Do you trust my code?) but it's fun to see the passphrases it generates, and how easy it is to create a story to remember them.

http://diegobasch.com/passgen/

Same thing applied to generating bitcoin brainwallets. Once again, don't use this. It was just a fun experiment to see if I could keep money in my brain.

http://diegobasch.com/brainwallet/

A mechanism to implement XKCD's password recommendation: http://xkcd.com/936/

Sadly doesn't work ever because of internet enforced password length and character pattern requirements.

So much this.

You can think of a great passwords scheme for yourself, and then find yourself in a pool of shit where hotmail asks you to have maximum 12 characters in a password, facebook requires you use a number, but it can be up to 40 characters, amazon wants you to use a special character like an @ or a # and but has a max length of 15 so on and so on.

Passwords. Suck. Use a password manager that autogenerates and autostores it like lastpass.

A hat-tip to Arnold Reinhold, the guy behind Diceware, would have been nice. (I know the article links to the Diceware site, which gives Mr Reinhold's name at the bottom, but still ....)

Reading this, I just thought of another way to make passphrases that might be a bit more memorable. The idea is to come up with a sentence which will be grammatically correct, so it'll be easier to remember.

First, write down 36 words. Roll two dice, take six times the number on the first minus the number on the second plus one. That is the position in the list of the first word in the sentence.

Next, write a new list of 36 words, but only include words that make sense given what is already there. Roll again as before and pick as before. Reusing words between lists is fine, but don't include the same word in the same list multiple times.

Rinse and repeat until you have the desired amount of entropy. Each die thrown adds log_2 6 bits.

Edit, just tried this, 36 is a lot of words to come up with. Much easier to write down 6 at the cost of making it twice as long. Unless you have access to lists of nouns, verbs, etc.

Bored now, but came up with "Countries can slowly sit at my feet", 24 bits of entropy (some lists had 36 words others had 6. It's very low, but, if you did that 2 or 3 times, you'd be getting somewhere). Couldn't be easier to remember.

In practice this would take longer than the 27 million years stated assuming 2 things: that the computer doing the guessing doesn't try passphrases it has tried in the past and that the user changes their password at least 1 time (more likely multiple times) within the 27 million years. This is contingent upon somehow not changing your passphrase to a passphrase much much higher up on the list of what the computer will try to guess. What are the chances of this occurring and what are the chances of the opposite occurring where the user's correct passphrase is somehow next on the list yet at that time the user randomly changes it to the passphrase at the very end of the list? Would this then mean it is better to keep the same passphrase forever or to change it?

From a UDS password framework the Dicey password generator is pretty formidable.For one things its extremley user friendly: you can memorize it easily, and there are infrequent errors attached to its usage. Deployment wise it's non-propietary software which is a plus. Lastly for security, it's easy to see that there is a big resistance to machine guessing. I liken this in intensity with an grID password, while although has a big cognitive exertion to be able to input your password within a set of grids which change, the security is high not only for machine guessing but also from internal observation since malware would be able to deduce the hash based off a new random event each time and resilient to physical observation!

The diceware word list has a lot of words that aren't very memorable.

Here's my attempt at memorable password generation: http://rmmh.github.io/abbrase/

How many easy-to-remember words are there in English, does anyone happen to know? Does Diceware's list include almost all of them?

By 'easy-to-remember', I mean for 99% of the world's English speaking population (i.e., for a widely used application).

I'm trying to estimate the entropy of random, easy-to-remember words. I'm not trying to generate a list (which would vary by region and country).

I can't imagine doing this for the hundreds of passwords in my list, especially when I change some of them regularly.

It could be useful for a master password, though - such as the one that secures my password list. Isn't just remembering a line from a song a little easier? Then you get a password recovery mechanism too, as long as you remember the song, or at least the artist!

Some guy lost 4 Bitcoins that were encrypted with a line from some obscure afrikaans poem, because someone was crazy enough to brute-force all possible private keys that you can come up with using basically any phrase you can find on the internet [0]. So as someone else already said - if it's online, it's not safe.

[0] http://www.reddit.com/r/Bitcoin/comments/1ptuf3/brain_wallet...

The article mentions using this for your master password. Quote: "For logging in to websites and other servers, use a password database. [...] Then lock up all your passwords behind a master passphrase that you generate with Diceware."

A line from a song is far weaker entropy-wise due to grammar. I wonder by how much. Common songs/writings would be vulnerable to a dictionary type attack.

As for the hundreds of passwords in your list, I'm convinced a password manager with a master password/3rd party auth/dongle is the way to go. Otherwise it's impossible to have unique passwords for all sites, rotate them, and remember them. Of course the risk is of losing the dongle.

> A line from a song is far weaker entropy-wise due to grammar.

Interesting observation, the usual objection is due to the reduced Kolmogorov complexity which is difficult to quantify. Let's look at a modified diceware scheme of the form:

Article adjective noun adverb verb adjective noun

A (non-random) example might be: The young boy really likes video games.

I'm not going to go through the diceware word list and classify each word, but assuming it is (or could be made) 50% nouns, 25% adjectives, 14% verbs, 11% adverbs and four articles you'd get roughly: 2 bits + 11 bits + 12 bits + 10 bits + 10 bits + 11 bits + 12 bits = 68 bits, which is the equivalent to a 5.2 word normal diceware password. Most of that reduction comes from the article.

Here's a random example made with a diceware generator:

an straw scrim ne adorn drab sybil

I'm not sure that's any easier to memorize.

I wonder how many nouns, verbs, and adjectives we can dig up? Can we dig up 7776 each?

While I think the set of adverbs would be much smaller (and obviously the set of articles will be very small) you could easily approach the same entropy as the Diceware method with a longer phrase. So long as there are 7 words in the phrase with 7776 possibilities each, you're equivalent. The rest is mnemonic glue.

Since I think nouns are going to be the easiest set, shooting for something even more noun heavy could help.

Edit: though since you're now syntactically more likely to be used in the wild, you'd probably want to search to make sure the phrase wasn't used in some other source. Problem there is the search leaks your password...

Interesting, I really like your approach to this.

If we go back to the original 'song verse' idea, the space of all valid/written phrases is much smaller than the space of all possible word combinations. It's vulnerable to dictionary attacks based on commonly chosen phrases and frequency of phrase use in language/culture.

Wikipedia only has 2.4 billion words, out of an estimated billion English words [1]. Perhaps we could add project Gutenberg with it's 50,000 works, and all the song lyrics we could find on the internet. We may hit 5 billion words. Let's estimate we also get 5 billion 6-word phrases out of that set. We've lost a ton of entropy.

Ultimately, we suck at passwords. Machine capability will exceed what we can reliably, efficiently memorize.

[1] http://www.languagemonitor.com/number-of-words/number-of-wor...

This is the more usual objection that I was referring to with Kolmogorov complexity. Forty random digits has very decent entropy, 40 digits of PI, though they look very random, has much less. From that you can see how it's really hard to quantify exactly how much entropy there is an song verse that exists somewhere on the internet.

If you wanted an absolute ranking of password strength, you'd first want to construct a universal brute force dictionary of passwords. Clearly the password 'password' is going to be near the beginning of the list and a password consisting of 48 randomly picked characters from [a-zA-Z0-9!@#$%^&*()] is likely to be somewhere out beyond the number of particles in the universe. But where exactly is "When you ain't got nothing, you got nothing to lose" going to appear? The first 10 million? billion? 10 billion? trillion? I really have no idea.

We should be able to at least estimate an upper bound.

If wikipedia has 2.5B words, let's generously assume 10B words. Let's allow phrase lengths of 1-10 words and arrive at 100B combinations.

Optimistically we're at 37 bits, not even a 7 character [a-zA-Z0-9!@#$%^&()].

And unlike the [a-zA-Z0-9!@#$%^&*()], we could madly cut that down based on frequency and popularity.

Therefore existing phrase passwords are security through minority. If they are adopted, they provide at best an order of magnitude or two over simple dictionary words.

But we're kidding ourselves, most people still use 'password'.

If your pass phrase already exists online somewhere (song lyrics, quote, meme) it's much much less safe than seven random words.

The official website of Diceware does not have a certificate http://world.std.com/~reinhold/diceware.html Is it intentional ?

The word list is signed but for someone unfamiliar with crypto an electronic signature is useless while a lock in the address bar is reassuring.

while true, the nice thing about the diceware wordlists is you can scan them. The only thing that would lower the entropy is if there were duplicated words. The lists are in alphabetic and numeric order.

(shameless plug) https://github.com/leshow/rust_mnemonic

BIP0039 has been around for a while and generates passphrases strong enough to be the seed of every private key you will ever deterministically generate in a wallet.

Here's something I wrote a little while ago - an xkcd-style passgen script in ruby. Usage is just `./passgen.rb [number of words]`. Default word count is 5.

https://github.com/kurotetsuka/passgen

You can create your own dice word list by selecting 7776 words and indexing them with a base-6 ID.

From the article:

"Unfortunately there doesn’t appear to be user-friendly software available to help people generate Diceware passphrases"

This is silly. There are popular applications for every major phone OS that implement Diceware. Does anyone feel that they're untrustworthy?

These kinds of passwords remind me of gfycat URLs.

Interesting rewrite of the actual title :P

We're at the point where we're more worried about NSA then a random attacker, as we should be.

Really? You think the NSA is more interested in your bank password than random criminals in [country over there]?

You can't imply that these organizations would need to try and guess your passwords though. They have extensive profiles on everyone, "see" the entire internet traffic and can take the data from that password protected website at will.

hmm I guess we are worried about a smart attacker, and we know those guys are really smart

Their are two levels of security, Mossad and non-Mossad. Worrying about evading the NSA is premature optimization at best and a form of mental illness at worst.

Other than it not being tinfoil after the past 2-15 years of evidence that citizens are targeted, it's not unreasonable to assume that the public is "only" 10-20 years behind the NSA when it comes to technology. So unless you have lifecycle management on all your encrypted files, and plan on regular password rotation on everything on your hard drive that you keep encrypted, perhaps it's not unreasonable to use something secure and memorable NOW.

Reply on news.ycombinator.com