Now we're reaching the limits of my 1337 maths 5killz0rz

<takes a swig of b33r>

You don't need to brute force all possible MD5 output hashes. You just need to brute force all possible passwords. People still, by and large, use passwords like [0-9a-zA-Z]{6,8} even though longer, non-alphanumeric strings are allowed. That gives you a mere 218,340,000,000,000 permutations. I mean, that's definitely one metric buttload of work but a lot less than going the other way. And we want to be protected even when AMD's Palomino core is launched :-) so that's why we still need salts.

(incidentally, I think we can assume that since we're talking about stolen hashes, the cr4x0r doesn't need to keep trying the login prompt - he'll be running the crack on his own machinery and waiting for one good answer).

Storing two hashes. Hmm. That might well open you up to a sort of crib attack. It's possible that the two outputs could be solved simultaneously, I'm not sure. But the thing is, it's like Ovid's idea about storing the salt seperately- it's doesn't actually add anything that just using a stronger algorithm doesn't get you. You need twice as much processing horsepower to create hashes, so why not use a tougher algo in the first place? I'm going to mention bcrypt again. Bcrypt has a scaleable complexity, so that when you create passwords, you specify n, where n is the log₂ of the number of rounds to apply the algo. By default OpenBSD uses 2**6 rounds. You can make it twice as complicated by changing one number to '7'.

Round three (sorry to go on). The exact nature of the salt is immaterial. You could use everyone's first name, and post a story about your system on perlmonks*. The important thing is that it's different for each user. Salts make precompiled dictionary attacks hard. The reason for using a good random salt is (1) computers don't care whether the salt is 'HelloWorld' or 'a1dg763/gv'. (2) A random salt system maximises the number of possible hashes, making dictionary attacks hard.

Round four (don't worry, I'll go away soon). A cracker who's simply read your password hashes can't actually hurt you unless he can do something with them - like log in as admin, having cracked the password.

Round five - see the bit in parens above.

* But don't. B-)