Don't memorize passwords, Memorize an algorithm

The 1995 Turing Award winner, Manuel Blum, has come up with a clever way to remove the necessity to memorize cryptic passwords. The gist of his approach is that you no longer have to memorize cryptic passwords, you just need a matrix of letters/numbers, and then an algorithm for creating a password based on the name of the web site. All you need to memorize is your personal algorithm of navigating through the 6x6 square of letters and numbers.

As clever as this sounds, his approach is not without flaws.

Because his approach only traverses the matrix for each letter of the site you're registering on (ie, "amazon" is 6-characters long) you end up with very short passwords since most sites want short domain names. And with shorter passwords, computers can brute-force find your password quite quickly.

Another alternative, according to the XKCD web comic.

For a while I started generating long passwords like in the cartoon, but as I memorized them I started chaining them together to make them longer and longer. Unfortunately there are still some web sites out there which require relatively short passwords. They'll limit you to 20 characters or 32 characters. I've only found a few that let me set super-long (50 to 100 characters) passwords.

My biggest suggestion: use a tool like LastPass ... it has great browser plugins, and you only need one really long hard-to-guess password, and it'll store all of your passwords for free, encrypted on their side. (granted, if you forget your master password you're out of luck) But it has tools which can generate and cycle through really long passwords and store them automatically for you.

A security researcher a while back wrote an article on how the best password tool is to never remember any password at all. Open a text editor, type in a long string of gibberish, copy it to your clipboard, paste it in a password field, and then close your text editor without saving the text. Instead of trying to memorize that gibberish password, use the site's "forgotten password" function to issue you a new token that they'll usually send via Email whenever you need to log in to that site. This also helps authenticate you because (hopefully) you're the only one to have access to your Email account. Simply reset your password every time you need to log in. It adds an extra few seconds, but is actually a great way to never worry about stored passwords.

UPDATE 2016: LastPass has made its tooling free to use across multiple devces (you used to have to pay $12/yr for mobile access for example)