How to securely generate memorable passwords?

Question

TL;DR: how secure are memorable password generators, given the fact that `memorable' passwords are a subset of total password space? How big is the entropy in memorable passwords compared to random passwords?

Whenever I need new passwords I use some tools to generate those, preferable memorable passwords, but I've been wondering how secure this might actually be.

Using The xkcd random number generator is probably pretty bad, cat /dev/random is probably pretty good, but generating memorable passwords seems a bit more tricky.

Whenever a program generates a memorable password, it only uses a subset of the total password space available, and it is not clear to me how big this space is. Of course a long password should help in this case, but if the `memorable' part of the program is too predictable, your passwords are not very good in the end.

Some tools I know of:

• pwgen -- seems ok, but passwords are not too memorable
• Mac Password Assistant - generates memorable passwords but it is unclear to me how this works.

Update: Thanks for the insight on theoretical password entropy and memorability, but I was also looking for the practical aspect of generating these passwords.

How do I choose such a password in practice, and specifically: what is the entropy of pwgen or Mac Password Assistant (MPA)? For example: what if the MPA has a very small database of words and generates passwords predictably? Perhaps this is a bit pedantic on my part, but I was curious if anyone could shed some light on this.

Update II: Although this question received a plethora of answers on password generation, none go into the question how secure these are. The question is still open and waiting for an answer.

Answer 1

Forget any "clever scheme" of composing passwords. The hackers know all the tricks (leetspeak, concatenating words, adding numbers etc) by analyzing lists of stolen passwords. Extended info in Security Now episode 366 "Password Cracking Update: The Death of 'Clever'" (or read its transcript).

I suggest you use a good password generator like LastPass (also entensively discussed in Security Now episode 256) to generate random passwords for you. Humans are bad at random (either generating it or detecting it)

If you really want memorable passwords, you might want to use the password haystacks technique as an alternative to hard to remember random combinations. Here you append a repetitive string (123 123 123) to a short string containing maximum entropy (D0g!).

Whatever method you choose, make your passwords at least 12 characters. All 8 character passwords can now be cracked in 13 hours on a build-it-yourself machine that costs $12000 (mainly for the GPUs)

Answer 2

How secure are memorable password generators?

Its easy to give a personal and qualitative opinion on this, I think it's better to seek some quantitative answers that in some way objectively measure the degree of security.

See Wikipedia

Considering that the entropy of written English is less than 1.1 bits per character,[2] passphrases can be relatively weak. NIST has estimated that the 23 character pass phrase "IamtheCapitanofthePina4" contains a 45 bit-strength. The equation employed here is:[3]

4 bits (1st character) + 14 bits (characters 2–8) + 18 bits (characters 9–20) + 3 bits (characters 21–23) + 6 bits (bonus for upper case, lower case, and alphanumeric) = 45 bits

Using this guideline, to achieve the 80-bit strength recommended for high security (non-military) by NIST, a passphrase would need to be 58 characters long, assuming a composition that includes uppercase and alphanumeric. There is room for debate regarding the applicability of this equation, depending on the number of bits of entropy assigned. For example, the characters in five-letter words each contain 2.3 bits of entropy, which would mean only a 35-character passphrase is necessary to achieve 80 bit strength.[4]

...

Passphrases differ from passwords. A password is usually short—six to ten characters. Such passwords may be adequate for various applications (if frequently changed, if chosen using an appropriate policy, if not found in dictionaries, if sufficiently random, and/or if the system prevents online guessing, etc.) such as:

• Logging onto computer systems
• Negotiating keys in an interactive setting (e.g. using password-authenticated key agreement)
• Enabling a smart-card or PIN for an ATM card (e.g. where the password data (hopefully) cannot be extracted)

But passwords are typically not safe to use as keys for standalone security systems (e.g., encryption systems) that expose data to enable offline password guessing by an attacker.[citation needed] Passphrases are generally stronger, and a clearly better choice in these cases. First, they usually are (and always should be) much longer—20 to 30 characters or more is typical—making some kinds of brute force attacks entirely impractical. Second, if well chosen, they will not be found in any phrase or quote dictionary, so such dictionary attacks will be almost impossible. Third, they can be structured to be more easily memorable than passwords without being written down, reducing the risk of hardcopy theft.[citation needed]. However, if a passphrase is not protected appropriately by the authenticator and the clear-text passphrase is revealed its use is no better than other passwords. For this reason it is recommended that passphrases not be reused across different or unique sites and services.

Also Jeff Atwood of this parish has published his thoughts on this subject, concluding with

Passphrases are clearly more usable than traditional "secure" passwords. They are also highly likely to be more secure. Even naive worst-case passphrases like "this is my password" aren't all that hackable, at least when compared to their single word equivalents, eg, "password".

Easier on the user, harder for hackers: that's a total no-brainer. I've adopted passphrases across the board on all the systems I use.

---

Update:

Since several people refer to XKCD and XKCD explicitly provides a URL for image embedding ...

Answer 3

There's two ways to break a password - brute force and dictionary attacks (there's a third - whick would be to grabbed the hashed password and crack that but lets ignore that for now). Length generally makes brute force attacks harder, though a dedicated hardware cracker, or a GPU based cracker would speed things up significantly.

Dictionary attacks rely on people using words. However 2 words would make it harder (since they'd have to iterate through 2 word combinations as well, and three words... Substitution also increases the possibilities that you'd need to go through).

I personally use a long multiword passphrase, with modifications per website and different substitutions. I also often remember passwords as a phone number, using 8 digits, and remembering them in pairs, then converting them back. People remember phone numbers, and are hidden easily. Pair that with having a personal ruleset and it gets easier.

I'd note most large password hacks occur on the server end, and having a secure password wouldn't help there - having a site unique password would.

Answer 4

Is it really necessary for all passwords to be memorable? I'd recommend having only two different memorable long passphrases at most: one for master-key to some cross-platform password keeping tool and one for primary e-mail account, which nowadays works as another master key too with most services sending details and recovery letters to it.

With only two passphrases to remember you can use some lengthy passphrases, guaranteeing that they're practically impossible to bruteforce and the rest of your password will be strong thanks to true randomization to full extent allowed by target site.

Answer 5

Personally i think you should apply your own logic into creating memorable passwords. Say you can add two words plus numbers together. Then you make variations of this which are dependent on something you know or if certain condition is met.

P.S. If it's memorable to you it doesn't mean it's easy to crack.

Answer 6

I made a free tool called Pafwert that combines randomness with a number of techniques to make strong, easy-to-remember passwords. Not every password it generates is SUPER strong, but most are and it is a great way to stimulate your creativity.

Here are some examples of some passwords it generated and why it chose them:

www.cold-as-ice.gov (uses a familiar pattern, slang phrase) TittyCupcakes3 (uses offensive words to make it more memorable) 5barde*barde5 (uses repetition) lots of lizard Meat..2 (alliteration) D:\another\48\hours.txt (familiar pattern, familiar movie name) Eight volunteer state= (rhyming)

Overall there about 150 patterns it uses with many variations of each. You can even tweak the patterns yourself, there is a fairly robust pattern language syntax.

Answer 7

For an organisation then a password policy is both a good and bad idea. Any system of generating passwords will cause a smaller set than a truly randomly generated password. To help with that things like the XKCD story system work quite well as they avoid personal items about the user which could be known or discovered.

As an example suggesting that users use their name, with voles substituted for numbers (a=1,b=2,etc) will generate something that looks random to the average person but is easy to break. Incorporating another word like job title, department or mothers maiden name will add to the abstration but you still basically have something that a disctionary attack should pick up. All be it that now you have increased the dictionary attack time from Proper Nouns in (western?) culture + Proper Nouns with vowel subs.

ThomasSoftwareEngineer becomes Th4m1sS4ftw1r22g3n22r

Looks random but is not very random to a software program. Certainly not to one that know the user is a Software Engineer called Thomas.

If you add to the above a collection of stores that people could incorporate, some memorable but obscure things might be: - Childhood memories - Secret crushes - Nemesis - First Cars - Car number plates - Narratives from a book they like This could create something a little more lengthy and for passwords longer is almost always better. Thomas had a Astra as his first car and he drove it into a ford in a river.

ThomasAstrafordriver

Again that is is only 4 dictionary words but it starts to be memorable. I could increase the entropy by including the year I got the car or that I broke it.

ThomasAstra2005fordriver2006

I could further up the entropy by choosing some symbol to use as a space, _ and - are well known but they are better than nothing and anything that is permitted could be chosen.

Thomas#Astra#2005#for#driver#2006

Now that is memorable, has a high entropy and should take someone a little time to guess. As with all good passwords it will take me some time to learn to type it fast but if you can easily type a password it is probably not a good one.

Now I would not recommend you use or type a password you really care about into any browser so you might want to use similar ones rather than actual one but... https://www.grc.com/haystack.htm The above website provides a nice was to see the size of the search space for a password. It does not measure strength but it gives you an idea that length is important as is using caps, numbers & symbols:

Password                           Search Space Size
ThomasSoftwareEngineer             5.76 x 10^37
Th4m1sS4ftw1r22g3n22r              4.44 x 10^37
ThomasAstrafordriver               2.13 x 10^34
ThomasAstra2005fordriver2006       1.56 x 10^50
Thomas#Astra#2005#for#driver#2006  1.86 x 10^65

Other things I have heard recommended is that you take users passwords and run them through a local, secure, powerful server with a password cracking tool doing dictionary and brute force attacks. If you can crack the password in a week then so can someone else. When you crack it expire the password and ask the user to make a new one, possibly providing them hits.

--endit to answer the question or "How much less secure than truly random"--- I had put this as a comment but it fits better as an addition to the answr. Carrying on from my above examples:

How secure these multiple word passwords are compared to truly random character passwords depends how you want to treat dictionary words. If we use entropy calcs as explained here: [http://blog.shay.co/password-entropy][1]

H=Llog2N where L is the length of the password and N is the size of the alphabet

We can do things in two ways. If we chose to treat each dictionary word as one symbol in the alphabet then ThomasSoftwareEngineer is only L = 3 but what is N? Well Google and OED say there are about 200,000 words in the English language so we get: H = 3*log[base2]*200,000 = 52.83 Which is Similar to a 9-alpha-numeric char password. If you then allow the substitution of some vowels with numbers you double your alphabet size to about 400,000 so it becomes H = 3*log[base2]*400,000 = 55.83 The XKCD comic uses 4 dictionary words instead of 3, these takes us from an Entropy of 52.8 for 3 words (no numerics) to: H = 4*log[base2]*200,000 = 70.44 70.4 is about the same entropy as a 12 character Alphanumeric password ( H = 12*log[base2]*62 = 71.45) so the question is can you remember 12 random numbers and letters as well as you can remember 4 non-related English words? Obviously a longer password (more words) is always going to be better and you should avoid short words (as 4 * 3-letter words is only 12 alpha characters which is an entropy of 68.4).

So here is the entropies you get for each style of password: Numeric Passwords (N = 10) Entropy (H) Length (L) Alphabet Size (N) 9.965784285 3 10 13.28771238 4 10 16.60964047 5 10

Case Insensitive Alphabetic Passwords (N = 24)
13.7548875  3   24
18.33985    4   24
22.9248125  5   24

Case Sensitive Alphabetic Passwords (N = 52)
17.10131915 3   52
22.80175887 4   52
28.50219859 5   52

Case Sensitive Alpha-Numeric Passwords (N = 62) 
17.86258893 3   62
23.81678524 4   62
29.77098155 5   62

Case Sensitive Alpha-Numeric Passwords with symbols on a QWERTY keyboard (N = 94)   
19.66376656 3   94
26.21835541 4   94
32.77294426 5   94

Passwords formed using a random selection of 200,000 words from the English Language (N=200000)     
52.82892142 3   200000
70.4385619  4   200000
88.04820237 5   200000

As above but assuming you know 20,000 words (N=20,000)
42.86313714 3   20000
57.15084952 4   20000
71.4385619  5   20000

Note: 20,000 words is the estimated number an educated English user will know so it is perhaps a better choice as a guess of what people will chose. Still it shows that 3 common words makes a password that is better than a 5-char totally random password from a QWERTY keyboard.

Answer 8

Since you haven't selected an answer, here's my two cents worth:

Strategies to share passwords for multiple users such as husband wife?

Select an account name that you will always use.

The password is built like this:

Pick a "root" password for the first 8 characters. Three characters are lower case letters. Two characters are upper case letters. The remaining characters are numbers and symbols on the keyboard.

These 8 characters are always used in the password. Next, you decide where you are going to put three additional characters. Either at the beginning or the end of the eight you originally came up with. Once you know if they are going to be a prefix, or a postfix, you have to decide what they are.

This is based on the website or service you are connecting to. If you were connecting to AT&T's website, you would add att or ATT to your original 8 character password.

I've been doing this for 15 years and NEVER had a security failure because of it. You can check my profile for my credentials if you're worried.

You can modify the system as needed. Always use a 3 instead of E (simple substitution). Always do the location based portion (the three letter prefix/postfix) backwards, or of varying capitalization.

I have over 200 accounts, NO PASSWORDS WRITTEN OR STORED ANYWHERE, and I have never forgotten one.