How quickly can these password schemes really be beaten?

Assume you have no rainbow table (or other precomputed list of hashes), and would actually need to do a brute-force or dictionary attack.

This program IGHASHGPU v0.90 asserts to be able to do about 1300 millions of SHA-1 hashes (i.e. more than 2^30) in each second on a single ATI HD5870 GPU.

Assume a password of 40 bits of entropy, this needs 2^10 seconds, which is about 17 minutes.

A password of 44 bits of entropy (like the one in the famous XKCD comic) takes 68 minutes (worst case, average case is half of this).

Running on multiple GPUs in parallel speeds this up proportionally.

So, brute-forcing with fast hashes is a real danger, not a theoretical one. And many passwords have a much lower entropy, making brute-forcing even faster.

If I use a truly random salt for each user, on what order of magnitude will this affect the length of time to crack my password?

The salt itself is assumed to be known to the attacker, and it by itself doesn't much increase the cracking time for a single password (it might increase it a bit, because the hashed data becomes one block longer, but that at most doubles the work).

The real benefit of a (independent random) salt is that an attacker can't use the same work to attack the passwords of multiple users at the same time. When the attacker wants just any user's password (or "as many as possible"), and you have some millions of users, not having a salt would could down the attack time proportionally, even if all users would have strong passwords. And certainly not all will have.

As a bonus, which hashing algorithms are safest to use?

The current standard is to use a slow hashing algorithm. PBKDF2, bcrypt or scrypt all take both a password and a salt as input and a configurable work factor - set this work factor as high as your users just accept on login time with your server's hardware.

• PBKDF2 is simply an iterated fast hash (i.e. still efficiently parallelizable). (It is a scheme which can be used with different base algorithms. Use whatever algorithm you are using anyways in your system.)
• Bcrypt needs some (4KB) working memory, and thus is less efficiently implementable on a GPU with less than 4KB of per-processor cache.
• Scrypt uses a (configurable) large amount of memory additionally to processing time, which makes it extremely costly to parallelize on GPUs or custom hardware, while "normal" computers usually have enough RAM available.

All these functions have a salt input, and you should use it.

If you don't use salts, the hacker can simply type them into Google and likely find it. MD5 encrypt your password, then Google the result, and you'll see what I mean.

If you've chosen a sufficiently complex password, then it probably won't be on Google, but it will still be in pre-computed tables called "rainbow tables" (the full tables would take too much space, so the "rainbow" technique is used to compress them).

If no tables are being used, then it doesn't matter if the password is salted or not. Of course, tables are always used, so yes, you should salt the passwords.

A desktop machine, with a gaming card (which can also be used to accelerate password cracking), and calculate a billion hashes/second. How fast this cracks your password depends. It can calculate all combinations for short passwords within a few minutes. But the, the problem is exponential, so that it cannot calculate all possible combinations for long passwords, even if you used a billion computers over a billion years.

Instead, what hacker do is a "mutated dictionary" crack. They start with a list of well-known words. It's called a "dictionary", but such lists contain a lot of words that you wouldn't find in a real dictionary, like "ncc1701", the designation for the Star Trek Enterprise. For each word, it does a number of mutations, such as capitalizing some letters, changing some letters to numbers, like "p4ssw0rd", or appending characters, like "password1234". How fast this works depends upon the skill of the hacker choosing just the right dictionary and just the right mutations. This can also change depending upon the hacker's knowledge of you. For example, if you are Hispanic, the hacker will add Spanish words and names to the dictionary.

You can expect that if your password database is stolen, the hacker will be able to crack about half of the salted passwords with a couple day's worth of work.

Well if you're just using MD5 or SHA-1 with no salt, just download a rainbow table and have it cracked in no time.

A subject on rainbow tables can be found here and how they leverage a bit better efficiency than just brute forcing one password in the case of a fixed salt.

how long does it take to actually generate rainbow tables?

On top of the first two, which applies to any hash without salt or with a fixed salt, MD5 has a lot of security vulnerabilities (reducing the time to crack the password).

http://en.wikipedia.org/wiki/MD5