Don't Store Passwords, Generate Them When Needed

What happens when the generated password doesn't meet the strength requirements for the site (too long/too short, not enough/too many numbers, not enough "special characters")? Or when I'm required to change my password periodically?

I'd like to verify it with my expectations for a passphrase:

- not-so-common (non-)words (think meme, Shakespeare style English, abbreviations/artifical words -> Jedi, Klingon, whatever) - I'd like to understand how to valuate punctuation: You don't just need to guess the passphrase, you might need to pepper it with commas, quotes, dots, question/exclamation marks at the right spots

    # generate our HMAC
    hash = generate HMAC-SHA1 (facebook.com, passphrase) (String)
    hash += SHA1(hash) # just need the extra length
    
    # transform hash into a Passy
    passy_chars = "ABCDEFGHabcdefgh23456789#$%*+=@?"
    passy = ""
    foreach octet in hash (starting with MSB)
      passy += passy_chars[octet % 32]

    # figure out the length of this passy
    for i in 16 to passy.length
      if passy.substr(0,i) is "good", return passy.substr(0,i)
        where good means includes at least one from each of [A-H], [a-h], [2-9], and [#$%*+=@?]

I have evolved this algorithm over the past decade. My requirements:

  1. minimum of 80 bits of entropy (16*32=80)
  2. must include at least one symbol, one uppercase, one lowercase, and one digit
  3. base it on cryptographically secure hash algorithms
  4. avoids confusing similar symbols O and 0, l and 1 and !, etc.

With any of these systems, your generates passwords are still only as good as a) the strength of your passphrase, and b) the secrecy of your passphrase. As well as the obvious (physical security, keyboard sniffers, etc.)

Better to use the age old technique found in "Unix System Administration" by Evi Nemeth: Choose a well known phrase or poem or song lyrics. Then pick a letter from each word, and interpolate some weird chars. E.g.

Yellow Submarine In the town where I was born, Lived a man who sailed to sea...

First letter of each word: IttwIwbLamwsts then interpolate stuff, e.g. "IttwIwb$beatles1968$Lamwsts"

Still a pain in the ass to type, but not nearly as painful as a SHA1 or base64 string.

I know this was a rough estimate, but I think it is way, way off. Passphrases are not usually generated by random choice of English words but are instead a particular, meaningful English sentence.

This means not only are you dealing with word distribution nonuniformity but word history correlations. Without doing any math in particular, let's pick a typical 4 word phrase (literally, I'm opening the book in front of me and looking for a 4 word sentence.)

   "This will be natural"

In comparison, four random words drawn from an English dictionary.

   "idiocy rammer stars cookshop"

So what does this mean? In all likelihood, if passphrases become more common, we'll see language model based cracking routines which generate billions of sensible English sentences to crack these passwords.

Length is no protection ("abcedfghijklmnopqrstuvwxyz1234567890"). Anything with genuinely high entropy is by definition difficult to remember.