Creating multiple secure and easy to remember passwords

What exactly is the issue with a completely random password?

Auto generated passwords should be changed by your clients upon first login anyway, so there will not be an usability issue. It is not a good practice for your clients to retain the initial password, as it would have to be sent to them in a plaintext format. For that purpose - one time login tokens would be much more secure.

A password containing two dictionary words IS NOT secure. A simple dictionary attack trying out various combinations of words would easily crack your password.

Using several words instead of a single password is actually a good idea, but only because there are so many possible words available. You can calculate the possible combinations yourself:

Random characters:
26 characters in alphabet ^ 8 places = 2.0E11 combinations
52 case sensitive characters ^ 8 places = 5.3E13 combinations

Sentence with words:
135'000 words in dictionary ^ 4 places = 3.3E20 combinations

This leds to following important points:

1. You need a dictionary that is large enough ("apple", "orange" and "banana" is a joke of course)
2. Use enough words, 4 seems necessary to me, especially if your sentence should be readable (smaller groups with substantives / verbs).

If you create readable sentences, they can be a bit longer without loosing the advantage of easy remembering. "The dog jumps over the blue fence" is not harder to remember than "dog fence over blue".

Here is a type of password that is "reasonably" robust and yet "reasonably" easy to remember and type:

Select two random lowercase letters, then two random digits, then two random uppercase letters, then two random digits.

The lowercase/uppercase mix and the digits allow such passwords to be accepted by most "password rules". The entropy of such passwords is about 32 bits (because 26²*10²*26²*10² = 4569760000, which is slightly above 2³²). That's not a lot, but sufficient to thwart online dictionary attacks (when the attackers tries to log on your server by "guessing" the password, possibly with a script). They offer non-negligible resistance to offline dictionary attacks (e.g. for a password-encrypted file, or the storage of hashed password in a database) IF (and only if) they are employed with proper password-strengthening techniques, i.e. salts and slow hashing (bcrypt).

It turns out that I find such passwords easy to remember. There are relatively convincing indirect clues that I am a human being and that my brain works, at least qualitatively, along the same lines than any other human being, including "managers". Thus, it is plausible that your manager would find such passwords easy to remember as well.

Important: when I say random, I mean it. Appropriate randomness cannot be achieved in the privacy of a human brain. You shall:

1. use a computer to generate random digits and letters;
2. within that computer, rely on a cryptographically secure PRNG (e.g. /dev/urandom on Linux/FreeBSD/MacOS X or CryptGenRandom() on Windows);
3. accept the password. Don't generate a hundred passwords until you reach one which pleases you, because this reduces your entropy. Generate one password and learn it.

Ideally, we would not let users choose their own passwords; we would provide a tool which generates passwords for them. Depending on the situation, securely transmitting the computer-generated password to the human user could prove challenging, which is why we are not always in the ideal case.

It seems overly optimistic to expect average users to use and remember passwords with an entropy of more than 32 bits or so.

---

If your manager is not cooperative, there is an alternate plan: tell him to write down his password on a piece of paper, and keep that in his wallet. A wallet is relatively secure: at least, he takes care of it on a daily basis. This takes care of the "easy to remember" part, at least for the first days. Also, that's what the US president does for some of his nuclear launch codes (be sure to let your manager know that, too).

Do not enforce a rule of changing the password every month: such rules are irksome and they turn users into enemies (i.e. more or less voluntary accomplices for the attacker).

Make sure that users know that they should report loss of passwords promptly and that they will not be blamed. Realistically, once you have more than a dozen users, a password leak will occur (regardless of whether the password is stored in a wallet or in a brain). The only thing worse than a leaked password is a user concealing the leak out of fear of a sanction.