0

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?

  • 4
    MD5 is severely broken. If you're asking this for any reason other than pure curiosity, then answers will likely give you false confidence in whatever you're trying to do. – Joseph Sible-Reinstate Monica Mar 11 '19 at 1:50
  • 2
    1) Iterations mean multiple runs. And of course it will take N times as much time if you run it N times. 2) The amount MD5 takes depends on the amount of input not if the input is salted or not, i.e. 1000 bytes with no salted takes more time than 100 bytes with a 100 byte salt (i.e. 200 bytes input). - Anyway, it is not clear what this question has to do with security since you don't provide any context. If you ask about password hashing please don't use a simple hash like MD5, see How to securely hash passwords? instead. – Steffen Ullrich Mar 11 '19 at 6:04
  • 1
    @JosephSible: MD5 is not broken in general the same way as CRC is not broken in general. These are just algorithms which are unsuitable for specific use cases. It is not fully clear what exact use case this is but it looks like password storage. In this use case a simple MD5 was never suitable but sufficient rounds of MD5 (to be slow enough) with proper salting (to be resistent against rainbow tables) would still be sufficient (although there are much better solutions - don't roll your own) since the collision resistance problem of MD5 does not matter here. – Steffen Ullrich Mar 11 '19 at 6:11
  • MD5 time depends of the amount of data that is being MD5'ed. To MD5 a small document it's an instant procedure, to do it for a movie, you actually have to read the whole file which takes a lot more. – Overmind Mar 11 '19 at 6:34
  • It would be helpful if you provide some context. Are you using MD5 for passwords? Are you worried about performance? Do you want a fast or slow hash function? – Sjoerd Mar 11 '19 at 9:25
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.

  • "create a function that takes tens of milliseconds" tens is insufficient; hundreds is a much better ballpark. – Polynomial Mar 11 '19 at 11:43
  • 2
    "..multiple iterations can sometimes be parallelized" - how can you parallize iterations of MD5 where the output of iteration n is the input to iteration n+1? – Steffen Ullrich Mar 11 '19 at 21:55
0

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.

  • Just a heads up, your info is a bit out of date. The current industry standard recommendation for password hashing is Argon2. – Polynomial Mar 14 '19 at 0:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.