I like using phrase passwords like this, but unfortunately a lot of sites have massive lists of ridiculous rules which disallow these sorts of passwords, despite their apparent security.

Google currently gets it right, but a lot of IT departments I've encountered are absolutely adamant about things like "must contain 1 number, 1 symbol, 1 uppercase, 1 lowercase" etc, essentially enforcing a completely non-memorable string of 8 random characters.

It's not super grammatical. I think the right way to do this is to invert a text compressor.

1) Take a state of the art text compressor like cmix (http://mattmahoney.net/dc/text.html#1243)

2) Compress a very large corpus of text with it.

3) Edit the compressed file, and add 16 random bytes to it.

4) Uncompress the text, and recover the part derived from the random bytes (for most compressors, the compression is sequential and it'll be at the end).

5) You now have a passphrase that sounds very natural and has 128 bits of entropy. It might be a short one with a rare word, or a longer one with more common words.

(P.S. I've tried to do it with cmix and got good results, though it didn't always work, so I suspect there is some redundant information in the compression to detect potential corruption).

You could alternatviely use my tech industry "Bullshit Generator 3.0" for this: http://bsgen30.com/

Every internet user has so many passwords that the age of trying to remember passwords is over. You pretty much either have to reuse passwords (dumb) or use a password manager. Given that any technically literate person will choose the latter option, grammatical passphrases provide no benefit over random characters.

What sort of attack is this assuming? Would a dictionary attack be more effective than the "centuries" estimate?

Here's a toy pseudo-random generator I threw together the other day in the course of doing something else:

https://www.exratione.com/2014/10/four-word-phrase-pseudoran...

How about this password scheme: [category] [words] [name of service] [optional: required characters]?

Examples:

email correct horse battery staple gmail

social correct horse battery staple facebook

dumb correct horse battery staple imgur

bank correct horse battery staple stupid-bank-inc 0!A

Don't you want to generate my SSH keys, while you're at it? ^^

I mean, I understand the idea but I would much rather a short script that I can run locally.

Edit: See answer below. Apparently this is possible. Sorry!

  > and/or thir reverified Erastatus
  > divers Clymenus unreconcilably iarovized