8

As far as I understood*, one of the major criteria when choosing a password / salt hashing algorithm is it's speed. To prevent brute force attacks, a slower algorithm is better (and also makes it more impractical to generate rainbow tables)

Assuming I understood correctly, is there any table that has machine independent relative benchmarks of those algorithms, sorted by speed?

e.g.

  • MD5
  • SHA-1
  • SHA-256
  • PBKDF2
  • bcrypt

e.g. if theoretically bcrypt is x times slower than SHA-1, then is repeating SHA-1 x iterations considered equivalent? (for brute force attack prevention related to hashed and salted passwords at least)

* I'm new to security, and to this site, please be gentle

Eran Medan
  • 851
  • 1
  • 10
  • 20

6 Answers6

12

To get an accurate measurement, you need to benchmark using your intended hardware with your intended software. Implementation makes a huge difference, plus some hardware can built-in acceleration for certain algorithms.

If you intend to use OpenSSL then you're in luck, because they have a built-in benchmarking suite.

$ openssl speed md5 sha1 sha256
Doing md5 for 3s on 16 size blocks: 4595381 md5's in 3.00s
Doing md5 for 3s on 64 size blocks: 3732906 md5's in 3.00s
....
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
md5              24508.70k    79635.33k   227390.21k   419190.78k   557154.30k
sha1             21918.90k    68573.48k   164350.12k   256347.14k   305924.78k
sha256           20979.09k    52742.04k   100939.52k   130634.07k   142630.91k
tylerl
  • 82,665
  • 26
  • 149
  • 230
  • Thanks @tylerl. so it seems that the "slowness" factor between sha256 and md5 is not mind blowing, and not even an order of magnitude apart. This starts to clear up for me the reason why bcrypt is popular then. But I still wonder, does simply iterating a large number of md5's / sha1s roughly equivalent to using bcrypt or PBKDF2? – Eran Medan Nov 21 '12 at 18:30
  • @Eran Medan - If you look at the implementation of Bcrypt, you will see, that in each iteration, the original key and the salt are mixed up with the result of the last iteration. So it's not exactly the same as just iterating a number of times, using the result as the input for the next iteration. – martinstoeckli Nov 21 '12 at 20:47
  • Curiously my numbers for sha1 were better than md5: The 'numbers' are in 1000s of bytes per second processed. type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes; md5 32526.28k 94598.98k 207205.21k 297106.77k 338960.38k; sha1 36823.75k 104859.48k 228837.80k 324861.43k 367695.19k; sha256 32061.67k 71195.82k 123225.51k 150144.34k 160303.79k; – Shubham Chaudhary Jan 04 '18 at 06:46
10

PBKDF2 and bcrypt are configured with an "iteration count", which means that they can be made as slow as you want. Therefore, there cannot be a table which shows how fast they go. What you need to do, instead, is to decide how much time you allocate to the function (e.g. you want it to take 0.05 seconds on your server) and then set the iteration count accordingly. This very much depends on the computing abilities of your server, so this is a matter of measure on your target hardware.

For the other functions, you can find an awful lot of data on this site for performance measures of many hash functions on a lot of platforms (although all these platforms tend to be servers, desktop systems, or at worst smartphones -- smaller embedded systems are not covered). The high-level picture is that:

  • Performance depends a lot on the hardware.
  • Performance depends a lot on the implementation.
  • All currently defined hash functions are way too fast to be adequate for password hashing by themselves; you need some kind of slowdown through thousands or millions of iterations.

While PBKDF2 adds iterations properly, it can still be made much faster in the context of a parallel attack, by using a GPU; therefore, you may prefer to use a function which is GPU-unfriendly, and, right now, this means bcrypt (scrypt being a nice candidate, when it becomes old enough to be trusted). See this answer for details.

Community
  • 1
Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955
4

Such a table would not help you, finding out which hash algorithm is best suited to hash passwords. The idea of key-derivation functions like Bcrypt and PBKDF2 is, that the needed time is configurable and adaptable.

That means, with a cost-factor you decide how many iterations are done to hash a password. You adjust this value, so your server is not slowed down too much, but that it can thwart brute force attacks.

Since you have to determine the allowed time yourself, it's not that important, which hash function you use (in regards of time). What can make a difference though is, how good the hash function can be implemented in a GPU. Here is a table of the Hashcat tool 2012. One algorithm which tries to be ineffective on GPU's is Scrypt, Bcrypt is surely a good choice too.

martinstoeckli
  • 5,189
  • 2
  • 27
  • 32
3

Yes, slower algorithms are needed for password hashing. Bcrypt and PBKDF2 are both great for this purpose. Here is a great comparison between the two

It's tough to answer a machine independent question but I'll assume you're mostly interested in hashing using a desktop/server application in Java. Some people have run some of the hashing algorithms you mentioned on dedicated GPU, FPGA, or ASIC hardware at a blistering speed. The fortunate case with Bcrypt and Scrypt is that it was designed to use slow memory and resists GPU style optimizations.

PBKDF2 is good too and the NIST has approved it for password hashing. Also the .NET implementation is FIPS compliant. So speed may not be the only thing you need to consider.

Although you probably don't need it for this current question, for future reference you may also be interested in the crypto.SE site to compare algorithms, since it really depends what hardware will be generating the hash. For example, here is a link that discusses scrypt.

Some of these questions have been asked before so it's a good idea to search for those questions, link to them, and ask a question based on what knowledge is missing. Then again Security.SE is a intelligent, welcoming group of people so I think you'll fit right in.

Community
  • 1
makerofthings7
  • 50,488
  • 54
  • 253
  • 542
  • Thanks, What I'm trying to understand is this: Is iterating 1000 times on SHA-1 / SHA-256 considered "safe" for password hashing? Or should I move to PBKDF2 / bcrypt? – Eran Medan Nov 21 '12 at 06:18
  • I don't have the credentials to answer that question. Based on what I've read in this site, the answer is almost always Bcrypt, Scrypt, or (with some reluctance by others) PBKDF2 – makerofthings7 Nov 21 '12 at 06:26
  • One reason to not use SHA based hashes: I can purchase a dedicated FPGA hashing machine that can probably crack that algorithm very quickly. The entire Bitcoin network is based on SHA so I'd advise against using that for one way hashing. – makerofthings7 Nov 21 '12 at 06:29
  • 3
    PBKDF2 is a key derivation function that uses a hash algorithm within it. Most implementations will select SHA1 or an SHA2-family algorithm. The important difference between you manually iterating through SHA1 a few thousand times and PBKDF2 is that PBKDF2 has been properly designed and scrutinized by cryptographers. – Polynomial Nov 21 '12 at 06:53
  • @Polynomial this is exactly the missing part of what I was looking for, thanks for clarifying, changed my code to use PBKDF2 instead of SHA-1 – Eran Medan Nov 21 '12 at 07:19
3

The following answer is only for the specific question "is there any table that has machine independent relative benchmarks of those algorithms, sorted by speed?".

Such a table can't possibly exist since the relative speed of the different algorithms are different depending on the machine used. Some algorithms (e.g. DES) were designed to be fast in hardware and slow in software. Other algorithms (e.g. AES) were designed to fast in software.

There are various kinds of machines that an attacker is likely to use. PCs are the simplest to use but generally give the lowest performance. Serious crackers are much more likely to use GPUs. Well funded organizations, like governments, will most likely use FPGA farms.

Even if we focus on crackers using GPUs (the most likely attackers) there are differences between GPUs in the relative performance of different hash functions. This is both because of the GPU type (CUDA or OpenCL) and because of varying memory sizes (some hash functions are more memory intensive than others). Ivan Golubev maintains a great table comparing the performance of pretty much every GPU on the market with a few hash functions (e.g. MD5, SHA1) though not bcrypt or scrypt.

David Wachtfogel
  • 5,522
  • 21
  • 35
3

Short answer:

  • SHA-1 is fundamentally broken, never use it.
  • MD5 is weak, marginally stronger with a salt.
  • SHA-256 is OK for password storage, still use a salt though.
  • There is a lot of arguing going on whether bcrypt or PBKDF2 is "the best".
    • bcrypt fans argue that PBKDF2 can be parallellized and therefore bruteforced faster.
    • PBKDF2 fans argue that bcrypt's use of blowfish 'weakens' it because blowfish hasn't been researched for vulnerability extensively enough and hasn't been 'officially' accepted by X security org of the week.
    • then it all descends into petty namecalling and 'your momma's so fat...' jokes.

The bottom line is that using either PBKDF2 or bcrypt puts you a mile ahead of anyone else that's not using a hash function with a work factor.

Sammitch
  • 233
  • 1
  • 7
  • Thanks :) that pretty much explains it. One thing I still don't get, if I do 10000s of SHA-1 iterations, is it still bad? isn't that the way PBKDF2 does the work factor? or am I completely mixing non-related things together? – Eran Medan Nov 21 '12 at 18:26
  • @EranMedan it's *less* bad, but it's still best to not use it at all. SHA-1 effectively has a "shortcut" that allows an attacker to reverse a hash [or generate hash collisions, I don't remember exactly] relatively easily, and generally faster than a regular bruteforce. – Sammitch Nov 21 '12 at 18:31
  • Thanks, and thinking that so many websites still store plain passwords, only a part of these hash them, and only a part of these also salt them, and a large part use MD5 or SHA-1, which all now seem from reading here - very easy to crack. I'm going to use a random password generator for every new website I sign up to, chances are that whoever wrote it, doesn't read this site. – Eran Medan Nov 21 '12 at 18:35
  • 1
    @EranMedan you'd *still* be shocked how bad it is. Fun fact: Plesk Panel for Windows *still stored all passwords as plain text* as of the current version last I looked at it about 4 months ago. Basic hashing was supposed to be implemented as an *option* "in the next version" but I have my doubts. – Sammitch Nov 21 '12 at 18:39
  • It's the other way round: MD5 is fundamentally broken. It has been broken already long before SHA-1. Never use MD5! SHA-1 is not fundamentally broken but it has been partially broken and thus is insecure as well for cryptographic tasks. However, for key derivation, both are used as HMAC and when used as HMAC, neither one has been broken yet. – Mecki Jan 11 '21 at 12:31