(Summary is in the last paragraph.)
How long will it take to crack 1 password? Is the time to crack 1 billion, just
1e9 * t?
Imagine I have this hashing algorithm:
hash = 0
foreach character in password:
hash = hash + toNumber(character)
If you call
hash("ab") it might return 3, since the first character's numeric value could be 1 and the second could be 2, and it adds them up, resulting in 3.
Now if you have a database full of numbers, like 583, 140, 8582, etc., how long would that take to crack?
In this example,
hash("ab") would result in 3 as well as
hash("ba"), which is called a collision (two inputs mapping to the same output). In md5 this does not happen so easily. The order matters and you cannot derive any information about the input given the output. Not even the length.
So you have to resort to just trying all possibilities until you find one that gives you the right output. If someone has a strong, random, 20-character password, it could take centuries. But most people use passwords like "horselover49", "letmein" or "penis" (though the latter might be too short), which are much easier to crack.
The reason everyone's complaining about using md5 is because it's fast. But hashing algorithms are made to be fast. MD5 might be broken for other purposes, but it isn't for password hashing. You just shouldn't use a single pass of any hashing algorithm, be it md5 or sha1 or sha512.
Better algorithms, like bcrypt/scrypt/pbkdf2/etc. use a hashing algorithm a million times (among other things). Now instead of being able to run the algorithm once for every guess, you need to run it a million times for each guess. That takes a lot longer, allowing you to try fewer passwords, which better protects weak passwords.
So yeah, the same is going to happen as with other breaches that used MD5: lots of passwords will be cracked. But they won't all be cracked and definitely not in linear time. The stronger ones will take exponentially more time.