45

What is/are currently the most cryptographically secure hashing algorithm(s)? (available in PHP)

Speed is irrelevant, because I'm iterating the hash over a fixed time (rather than a fixed number of iterations). What I'm interested in is the mathematical strength.

My intuition tells me it's whirlpool, being the largest and slowest of the bunch. That or SHA-512. But where on the 'net can I see what the experts recommend?

nealmcb
  • 20,544
  • 6
  • 69
  • 116
Core Xii
  • 545
  • 1
  • 4
  • 5
  • 9
    How can you guarantee that the fixed time always leads to the same number of iterations from run to run? –  Jun 25 '11 at 17:29
  • 1
    By securest do you mean having the largest complexity? Sometimes an algorithm that can be considered strong have other flaws. –  Jun 25 '11 at 17:29
  • 1
    You really need to define "most secure". If you cannot give a more specific definition of "secure", then SHA-512 will do the job. –  Jun 25 '11 at 17:35
  • If you want the "most secure" hash, take any existing cryptographic hash function (not important which one) and replace the loop count with 1 million. –  Jun 25 '11 at 17:37
  • 1
    @Amber: By storing the iteration count with the hash. –  Jun 25 '11 at 17:56
  • 1
    "Secure" as in, based on a mathematical problem that has no known fast solution. "Most secure" as in, based on the most complex of such problems. A hashing algorithm is considered "strong" when breaking it would require a major contribution to cryptology/mathematics. –  Jun 25 '11 at 17:59
  • Hash algorithms are not designed to protect the confidentiality of passwords, which are short, but to quickly verify the integrity of medium to large chunks of data. Note that hashes are designed to protect integrity and not confidentiality. Encryption algorithms are designed to protect confidentiality of data. Hashes are used to protect password confidentiality because they are quick, easy, and do not require a separate key. The selection of slower hash function is an odd but understandable approach to avoiding the need for an encryption key. – this.josh Jun 26 '11 at 07:58
  • 2
    @Core So users who change their password at peak hours will have less securely hashed passwords than those who change them during off-hours? – Nick Johnson Jun 27 '11 at 00:04
  • @Nick Johnson: Yes, this does happen if they register/login during peak hours. But on every subsequent login, the system checks how long the password took to hash, and re-hashes it if it took less time than specified. Hence, low iteration counts will catch up automatically. – Core Xii Jun 27 '11 at 06:47
  • @this.josh: _Cryptographic_ hash algorithms _are_ designed to protect confidentiality such that the hash communicates as little information about the original input as possible. – Core Xii Jun 27 '11 at 06:49
  • 3
    No, cryptographic hash algorithms are _designed_ to be one-way functions that make it difficult for an attacker to modify a piece of data while keeping the hash value the same. The one-way function is _designed_ to make it difficult to determine how a change in input will impact the output hash value. Fundamentally cryptographic hashes are lossy compression functions. The information loss in compression makes it difficult to recover the input data. Design specs for MD5, SHA1, Whirlwind, etc, do not mention confidentiality, because is not a design goal. – this.josh Jun 27 '11 at 07:31
  • 2
    I think you are making a mistake: if you store the iteration count that was based on the minimal computation time in PHP, the attacker would likely choose a faster language (C for example), and thus could do the same amount of iterations in far less time. I take it you are familiar with the saying: "Don't roll your own crypto"? – Jacco Jun 27 '11 at 08:20
  • @Jacco: An attacker can _always_ hash faster than the web server running the service. But by iterating _for as long as is possible_, maximum security is gained. I know writing your own stuff is generally not a good idea, but there _are no_ implementations that adjust the cost automatically (and manual updates are out of the question). – Core Xii Jun 27 '11 at 12:22
  • 2
    I think the answers here are a little confus(ed|ing) because the time taken by a hashing algorithm is an upper bound on its security. So, except for broken or reduced algorithms, and adjusting for digest length; all hashing algorithms are of equal security if you're iterating for the same amount of time (and doing that in a way that introduces no new vulnerabilities). Except maybe scrypt, since it's memory-hard. – user502 Jun 27 '11 at 14:07
  • 3
    @Core Why is adjusting manually not an option? Having security depend on server load seems like a bad idea. – Nick Johnson Jun 28 '11 at 01:29
  • @Nick Johnson: Keeping tabs on clients' sites is outside the scope of my work, and I can't pass the responsibility of updating the parameter to them, either. Security depends on the lowest load the user logs in on. You have, however, motivated me to add another parameter, the minimum number of iterations, just in case. It suffers from not being increased periodically due to the same issues as above, but it's slightly more secure I suppose. – Core Xii Jun 28 '11 at 10:47

6 Answers6

34

Crypographers could point out that, when you read the fine print, there is no proof that secure hash functions actually exist at all. The only thing we have now are candidates for which no weakness has been found yet.

So the best you can hope for is a function which has survived scrutiny by many cryptographers for a long time. Also, you need it to have a wide enough output (256 bits are enough if you wish to achieve "128-bit security" and getting beyond that has little sense). Right now, as of summer 2011, this points to SHA-256 or SHA-512, not Whirlpool.

Basing the iteration count on the time it takes on a typical machine is a good idea -- but basing it on the time it really takes on your machine is not a good idea. Otherwise, you could end up with low iteration counts for some passwords because the machine was handling many requests at that instant (a situation which an attacker could force, by the way). Using many iterations is meant to thwart attackers by making password hashing slow on the attacker's computer -- that it also makes it slow on your system is an unfortunate byproduct; but the true target is whatever machine power the attacker could muster. Since you cannot really make benchmarks on the attacker's machine, you have to resort to rough estimates, hence a fixed count, as high as possible as long as the average burden is tolerable on your system (the important word here being "average", which disqualifies a dynamic measure as you intend to perform).

Also, the attacker's machine needs not look like yours; it may be, e.g., a GPU or a FPGA, which offers distinct computing abilities from what you can get on a typical server. You want a function for which an attacker will not be able to get huge performance boosts by using non-PC hardware. There again, this promotes SHA-256 or SHA-512, which are meant for CPU efficiency (with 32-bit or 64-bit arithmetic operations), not Whirlpool, which can benefit from hardware optimizations similar to those AES was designed for.

Finally, iterations are just part of the job; you also need a long enough, unique enough salt. Iterations and salting can be a bit tricky to do at the same time; you are warmly encouraged to use a standard construction such as PBKDF2 (although it was meant as a key derivation function, not a password hasher, PBKDF2 turns out to be reasonably good at that too).

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
20

From OP's comment:

"Secure" as in, based on a mathematical problem that has no known fast solution. "Most secure" as in, based on the most complex of such problems. A hashing algorithm is considered "strong" when breaking it would require a major contribution to cryptology/mathematics.

It sounds as if you have been reading Thomas Ptacek's "Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes", and now you're wondering which modern cryptographic hash optimized for password storage is considered 'the most secure'.

I don't think there is a clear-cut answer. As far as I know, some of the current favorites in the programming community (scrypt & bcrypt) haven't been rigorously peer-reviewed as password hashing functions. At least, they have not been peer-reviewed by a large number of cryptographers comparable to how the NIST hash function competition entries are vetted.

That said, the current Hacker News consensus is that the order is:

  1. scrypt. Because it is both memory-intensive and CPU-intensive, scrypt is thought to have the highest safety margin of current password hashes. You can see more about its design here.
  2. bcrypt was the previous champion, as mentioned in Thomas Ptacek's blog post above.
  3. PBKDF2 and multiple rounds of SHA2 (fx Unix Crypt with SHA256) are thought to be third-best (which one of these is 'best' depends largely on the number of iterations used).

(Note that "Hacker News" is mostly a programming community, and not as the name might imply to some a security specialist community (even though some of those hang out there too).)

If you look around on this site, under the cryptography passwords and hashing tags fx, then you will see that there usually isn't a single 'best' password hash mentioned. I guess that's in part because the real cryptographers have no clear-cut consensus on which one is 'strongest', due to the relatively limited peer-reviewing.

Here is a fairly even-handed and easily read comparison (which doesn't include scrypt, presumably because it's still too new).

Speed is irrelevant because I'm iterating the hash over a fixed time (rather than a fixed number of iterations).

With some of these hashes, you can't really do that. You supply a "work factor" when you call the library, and the library takes care of the rest.

Soufiane Tahiri
  • 2,667
  • 12
  • 27
  • _scrypt_ is not available for PHP. _bcrypt_ and _PBKDF2_ implement the adjustable cost as an iteration count, and requires fine-tuning for each point in time. I've already solved that by adjusting the cost by _time_ rather than a flat count. Now I'm just wondering what hashing algorithm to use. – Core Xii Jun 27 '11 at 06:54
  • 6
    @Core Xii: You seem bent on implementing your own novel solutions -- it is axiomatic that one shouldn't do that, "Don't roll your own crypto". In your case, I would suggest using PHP > 5.3.2 and use PHP's crypt() with Blowfish and default values (aka bcrypt). http://php.net/manual/en/function.crypt.php You can see the format description here (not PHP, but same format AFAIK) http://packages.python.org/passlib/lib/passlib.hash.bcrypt.html#passlib.hash.bcrypt –  Jun 27 '11 at 10:12
  • I can not fine-tune the cost parameter manually, that is out of the question. And there exist no implementations with dynamic adjustment, so I'm forced to roll my own. I did not ask what tool I should use to crypt my passwords, I asked for the most secure hashing algorithm. Blowfish is not a hashing algorithm. – Core Xii Jun 27 '11 at 12:36
  • 4
    @Core Xii: While "Blowfish" isn't a hashing algorithmn, there is a password hashing algorithm that is called "CRYPT_BLOWFISH" in some circles. That's already covered in @Allan Jude answer and in my links above. You seem to want to create your own password hashing scheme; and I'm not able to assist you further in doing so. –  Jun 27 '11 at 14:21
  • 2
    You could implement "pick #iters based on time taken" using a library-provided bcrypt -- just time the bcrypt call and if it's "too quick" increase the workload factor and re-try. But are you sure you want that? What if someone deploys your code onto a slow machine (e.g. a small VM) -- you don't want to get too-small work factors as a result. What if your system is left on a "2011" spec machine through to 2019 when all the attackers have 128-way 20GHz boxes? What if the attacker can use a DoS to increase the time your hashing takes? You will at least want a secure-for-now initial work factor. – Misha Sep 12 '11 at 12:15
  • @JesperMortensen The http://chargen.matasano.com/chargen/2007/9/7/enough-with-the-rainbow-tables-what-you-need-to-know-about-s.html URL seems to no longer exist and is redirecting to https://www.nccgroup.trust/us/about-us/newsroom-and-events/blog/ and is unsure if that website contains related information. Plus, http://packages.python.org/passlib/new_app_quickstart.html#choosing-a-hash seems to also be a non-existant page and attempts to redirect. Can you check all of the other hyperlinks and edit accordingly please? It's unsure if you're still active. – Funk Forty Niner Jun 11 '17 at 20:42
7

CRYPT_BLOWFISH (OpenBSD bcrypt, based on the blowfish symmetric cipher, but is an actual hashing algorithm, there seems to be a lot of confusion about this) and CRYPT_SHA512 are the best. Both of these provide the option to scale the number of 'rounds' used, allowing you to choose a security/performance tradeoff.

For example, the default number of rounds for blowfish is 7 (value range is 4-31). This value is logarithmic, so each increase results in the algorithm being run 10 times more. A value of 13, takes almost 1 minute per hash on a Core2Duo 2.4ghz

Tuning this as high as is tolerable performance wise, will result in the strongest security.

note: recently a bug was found in some implementations of bcrypt, and as such, you may wish to use SHA-512 instead.

Note: SHA-512 is faster to compute than SHA-256 on 64bit processors (especially if optimized w/ SSE2_64. Specifically, you should consider this and use additional rounds to ensure your hashes are strong enough for their purpose.

The open source application hashkill, published some performance benchmarks on how quickly modern GPUs could crack through modern hashing algorithms. Specifically, a Radeon HD 6990 can do: 11001 Megahashes/sec of straight MD5 (CRYPT_MD5 is salted, and the FreeBSD implementation uses 100 rounds). Straight SHA1 at 3444 Megahashes/s.

mgjk
  • 7,535
  • 2
  • 20
  • 34
Allan Jude
  • 208
  • 1
  • 3
  • Once again, I don't want to _tune_ the tradeoff; Hence I wrote a system that iterates automatically by _time_, thus remaining constant in its security over time. Now I'm just looking for the most secure hashing algorithm to use with it. The benchmark only compares MD5 and SHA-1 (both of which are broken), and so is completely useless. – Core Xii Jun 27 '11 at 07:00
  • @Allan - Both embedded URLs appear to time out, as per *"The connection has timed out"*. Can you edit accordingly please? I'm sure not if you're stil active though. – Funk Forty Niner Jun 11 '17 at 20:45
  • I edited out the hyperlinks and kept the text associated with them intact. – Funk Forty Niner Jun 12 '17 at 13:19
  • I noticed another edit using a web archived link. Thanks @mgjk – Funk Forty Niner Jun 12 '17 at 13:29
  • Glad it helped :-) I didn't want to see Allan Jude's reply lose the link, it adds some great background to his answer. – mgjk Jun 12 '17 at 14:07
  • @mgjk You're right. Btw, I only saw your comment when I revisited it *lol* you'd of had to use the @ as I did for you, in order for me to get a notification (ping) ;-) *Cheers* and thanks again. – Funk Forty Niner Jun 13 '17 at 09:59
0

I recommend you to use phpass

This is a portable public domain password hashing framework for use in PHP applications. It is meant to work with PHP 3 and above, and it has actually been tested with at least PHP 3.0.18 through 5.3.0 so far.

The preferred (most secure) hashing method supported by phpass is the OpenBSD-style Blowfish-based bcrypt, also supported with our public domain crypt_blowfish package (for C applications), and known in PHP as CRYPT_BLOWFISH, with a fallback to BSDI-style extended DES-based hashes, known in PHP as CRYPT_EXT_DES, and a last resort fallback to MD5-based salted and variable iteration count password hashes implemented in phpass itself (also referred to as portable hashes).

Like the website says Blowfish-based bcrypt is the most secure hashing. I believe this is true because it is "Moore's law proof" while most others are not.

  • It uses MD5 (a no-no). Also, read my question again. My system is Moore's law proof _automatically_, whereas PHPass requires manual fine-tuning of the iteration count for each point in time. – Core Xii Jun 27 '11 at 06:56
  • @Core Xii, it *can* use md5, for backward compatibility. But it does not by default and can be configured to only use BCrypt. – Jacco Jun 27 '11 at 12:32
  • @Jacco: I'm looking at the source _right now_ and there's a clear comment: "We're kind of forced to use MD5 here since it's the only cryptographic primitive available in all versions of PHP currently in use." – Core Xii Jun 27 '11 at 12:42
  • I know the source, if you set 'portable hashes' to false, it will not use md5. – Jacco Jun 27 '11 at 12:50
  • @Jacco: The execution path for `CheckPassword()` always goes through `crypt_private()` which always uses MD5. – Core Xii Jun 28 '11 at 10:53
  • @Core Xii, If you do not want to use it, that's ok. However, the library is good and reviewed by many people. It works. – Jacco Jun 28 '11 at 12:24
  • Old comment - but I do want to add that this library was brought up over in [this](http://security.stackexchange.com/questions/17111/php-crypt-or-phpass-for-storing-passwords) thread and people seem to speak highly/postively of it. I for one approve backwards compatibility as not every developer has access or ability to install later versions in their environment. – Natalie Adams May 28 '14 at 02:50
-2

If speed is not an issue, just add the outputs of multiple hash functions. (Whirlpool, sha-512, etc). Same principle as multiple encryption, any engineered or found weakness won't work through multiple hash functions. Basically, take string x, run it through n hashes separately (not chained, run each one separate on the same input), add the results into one new block. Repeat by doing the same thing to the new block. I assume you are doing this for secure password storage. Make sure you use a true random salt as well, and an independent one for each hash. (And please use a full length one).

Realanswer
  • 1
  • 1
-3

According to my personal experience, I consider Blowfish as one of the most secure encryption algorithm

Click Here to download the pdf documentation on Blowfish.

It is a symmetric block cipher that can be used as a drop-in replacement for DES or IDEA. It takes a variable-length key, from 32 bits to 448 bits, making it ideal for both domestic and exportable use. Apart from that, Blowfish is unpatented and license-free, and is available free for all uses.

  • Blowfish is a hash algorithm? –  Jun 25 '11 at 17:51
  • Blowfish is absolutely not a hash algorithm, and using it as if it were one will lead to tears. –  Jun 25 '11 at 17:53
  • 3
    Blowfish is not a _hashing_ algorithm, though. I don't know how exactly _bcrypt_ uses Blowfish but generally _encryption_ is a completely different thing from _hashing_. –  Jun 25 '11 at 17:55
  • 1
    If blowfish is not a hash algorithm, then I think people should make it clear and downvote it accordingly. – user774411 Jun 25 '11 at 18:15