How long does it take to compute hashes using the MD5 hash algorithm?

Question

1) If one iteration of MD5 takes x seconds, is it safe to assume that n iterations of MD5 takes n * x seconds?

2) Will salted and unsalted versions of md5 hash algorithms take approximately the same amount of time to compute?

Answer 1

1) If one iteration of MD5 takes x seconds, is it safe to assume that n iterations of MD5 takes n * x seconds?

Yes, except that multiple iterations can sometimes be parallelized. So while it takes the same computing time, it may take less wall clock time because more computers can be put to the task.

The key derivation function PBKDF2 relies on this slowdown. It does several iterations of a hash in order to make the whole function slow.

2) Will salted and unsalted versions of md5 hash algorithms take approximately the same amount of time to compute?

Yes. A typical way to add a salt is to concatenate it to the password, so hashing it will take just a little bit longer to add the extra bytes to the hash.

In case of a password hashing function, you want it to be slow in order to slow down brute force attacks. So a password hashing function such as PBKDF2, bcrypt, scrypt or Argon2 should be used to create a function that takes tens of milliseconds. These slow functions are often made up of fast functions such as SHA1.

Answer 2

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.

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.