Which hashing & salting algorithm should be used ?

Gentlemen, as this has been a big topic, and there's still no real answer to this, I would like to introduce this wiki page. Feel free to post/change whatever you like, the goal is to find an answer to the question:

Which hashing & sorting algorithm should be used in the script ?

A little keynote: As this project gets more attention than i ever thought, there's some kind of responsibility NOT TO DELIVER insecure stuff.

According to the PHP's crypt() doc page CRYPT_BLOWFISH uses 22 char salt and generates a 60 char hash, and CRYPT_SHA512 uses a 16 char salt and generates a 118 char hash. Both algorithms have changeable cost factors (that allow to change to "intensity" of the hashing/salting function, useful when technology becomes stronger and servers/crackers have more power), so at first view, SHA512 looks stronger (because longer).

I have asked this on stackoverflow - but as usually - the question has been closed, because of "off topic". Yeah, sure. link. A reopening of the same question on stackoverflow's partner site security.stackexchange.com can be found here.

A similar question, with 90+ upvotes and answers with nearly 150 upvotes here, has also been closed due to "not constructive".

##Benchmark: All crypt() hash/salt algorithms##

All of those loops use "rasmuslerdorf" as the password. I'm not sure if it's fair to compare them like this, but we'll see. This benchmark has been made on a i3 2120 CPU with 8GB of 1066 RAM [might be important, as crypt relies quite much on RAM speed].

BLOWFISH: uses a cost factor from 04 to 31 (the two digit cost parameter is the base-2 logarithm of the iteration count for the underlying Blowfish-based hashing algorithmeter).

SHA256/SHA512: uses a cost factor in form of how many times the hashing loop will be executed. The default number of rounds is 5000, there is a minimum of 1000 and a maximum of 999,999,999.

Runtime for 100 runs with CRYPT_STD_DES, which has a 2 character salt	0.029006004333496 seconds
Runtime for 100 runs with CRYPT_EXT_DES, which has a 9 character salt	0.062263965606689 seconds
Runtime for 100 runs with CRYPT_MD5, which has a 12 character salt	0.27028179168701 seconds
Runtime for 100 runs with CRYPT_BLOWFISH with $2a [before PHP 5.3.7], which has a 22 character salt and standard cost factor of 7	1.8341250419617 seconds
Runtime for 100 runs with CRYPT_BLOWFISH with $2y [from PHP 5.3.7], which has a 22 character salt and standard cost factor of 7	1.8966331481934 seconds
Runtime for 100 runs with CRYPT_SHA256, which has a 16 character salt and standard cost round factor of 5000	0.97224402427673 seconds
Runtime for 100 runs with CRYPT_SHA512, which has a 16 character salt and standard cost round factor of 5000	1.3613569736481 seconds

BLOWFISH wins (because it's the slowest). As this is just a comparison with the given standard parameters, this benchmark might be not accurate or even totally wrong.

##Benchmark: BLOWFISH with different cost factors##

Not really a benchmark, but a little guide on how the cost factor in blowfish performs. Blowfish uses a cost factor from 04 to 31 (the two digit cost parameter is the base-2 logarithm of the iteration count for the underlying Blowfish-based hashing algorithmeter), that will slow down the calculation (which is good) to keep the hashing secure for upcoming generations of much stronger server/cracker hardware. [TODO] It would be great of somebody could provide excellent information/benchmarks on blowfish/sha512 cracking in an "professional" cracker environment (stack of GPUs / EC2 / FPGA).

This benchmark has been made on a i3 2120 CPU with 8GB of 1066 RAM [might be important, as crypt relies quite much on RAM speed].

Runtime for 10 runs with CRYPT_BLOWFISH (which has a 22 character salt) and cost factor of 04 (minimum possible)	0.03049111366272 seconds
Runtime for 10 runs with CRYPT_BLOWFISH (which has a 22 character salt) and cost factor of 10	1.4444839954376 seconds
Runtime for 10 runs with CRYPT_BLOWFISH (which has a 22 character salt) and cost factor of 11	2.3012299537659 seconds
Runtime for 10 runs with CRYPT_BLOWFISH (which has a 22 character salt) and cost factor of 12	5.7425429821014 seconds
Runtime for 10 runs with CRYPT_BLOWFISH (which has a 22 character salt) and cost factor of 13	7.3200581073761 seconds

##Trying to max out the cost factors of BLOWFISH and SHA512##

First: We are testing ONE run of the crypt() function with the given cost factor here. This test simply wants to show the relations between the different cost factors. On a real server you will have quite different numbers, and a professional hacker will use high-end GPU powered equipment that will be much much faster.

PHP's manual uses 7 (of 4 to 31) as the standard cost factor in BLOWFISH, 5000 (1000 to 999,999,999) in SHA512. The official PHP 5.5 password functions use BLOWFISH and a cost factor of 10 as standard.

####SHA512####

Runtime for 1 run with CRYPT_SHA512, which has a 16 character salt and cost round factor of 999.999	3.2299280166626 seconds
Runtime for 1 run with CRYPT_SHA512, which has a 16 character salt and cost round factor of 9.999.999	20.304142951965 seconds
Runtime for 1 run with CRYPT_SHA512, which has a 16 character salt and cost round factor of 99.999.999	206.54775309563 seconds
Runtime for 1 run with CRYPT_SHA512, which has a 16 character salt and cost round factor of 999.999.999 (maxed out)	2119.8040719032 seconds

####BLOWFISH####

Runtime for 1 run with CRYPT_BLOWFISH with $2y [from PHP 5.3.7], which has a 22 character salt and cost factor of 10 (min 4, max 31)	0.17402386665344 seconds
Runtime for 1 run with CRYPT_BLOWFISH with $2y [from PHP 5.3.7], which has a 22 character salt and cost factor of 15 (min 4, max 31)	3.9221420288086 seconds
Runtime for 1 run with CRYPT_BLOWFISH with $2y [from PHP 5.3.7], which has a 22 character salt and cost factor of 20 (min 4, max 31)	93.527085781097 seconds
Runtime for 1 run with CRYPT_BLOWFISH with $2y [from PHP 5.3.7], which has a 22 character salt and cost factor of 25 (min 4, max 31)	2984.5868999958 seconds
Runtime for 1 run with CRYPT_BLOWFISH with $2y [from PHP 5.3.7], which has a 22 character salt and cost factor of 31 (maxed out)	(theoretically) ???.??? seconds

##Other hash/salt techniques, stuff for future investigation

1. Maybe we should clarify the term "bcrypt", as it's often used in threads and always described in a very strange way. From my understanding, what we are doing there, is bcrypt. A cost factor variable hashing and salting, with the possibility to rehash.

2. Also interesting: PBKDF2, but a total killer anti-argument is this: The official PHP documentation clearly says: Don't use this, use crypt() and BLOWFISH instead: The PBKDF2 method can be used for hashing passwords for storage (it is NIST approved for that use). However, it should be noted that CRYPT_BLOWFISH is better suited for password storage and should be used instead via crypt(). found here

3. All other techniques, like scrypt, are soooo small, experimental, unmaintained and usually just available in non-mass-tested libraries. All of them are probably quite good [i don't have the knowledge to judge this in any way], but usually very small, made/hosted by one (!) developer and of course there's no documentation, guideline etc.!

##Conclusions (so far)##

1. BLOWFISH seems to be the slowest alorithm (but those benchmarks may not be accurate, as cracking relies on RAM speed, CPUs, GPUs, GPU architecture, setups of clever cracking algorithm sharing etc).

2. BLOWFISH is the one preferred by the guys that build the official PHP 5.5. password functions.

3. According to the max-out-benchmark BLOWFISH's cost factor can be stretched much more than SHA512's.

4. BLOWFISH is the only algorithm supported by the PHP password compatibility library so far.