md5 is dead. long live crypt() ?

sneakyimp

So I understand that in order to prevent password cracks, hashing should be an expensive operation and salting should be used. At least php.net says so. In particular:

The suggested algorithm to use when hashing passwords is Blowfish, as it is significantly more computationally expensive than MD5 or SHA1, while still being scalable.

I was wondering a) what the kids are using these days for hashing and salting (code welcome!) and b) How does one use the [man]crypt[man] function and be sure that it's using blow fish. I am kinda confused by the manual (which leaves a lot to be desired) and it would appear that the 'salt' parameter that you specify is more than just a salt but also specifies which cryptographic has you use? The example from the docs for blowfish:

if (CRYPT_BLOWFISH == 1) {
    echo 'Blowfish:     ' . crypt('rasmuslerdorf', '$2a$07$usesomesillystringforsalt$') . "\n";
}

Seems to me the salt is some kind of hybrid parameter -- which is kinda lame IMHO.

Also, I'm wondering what happens if you don't specify a salt. Does the system just pick some default hash routine? Seems like that would not bode well for code (or data) portability.

NogDog

Whatever they're using, the NSA has probably already hacked it. :rolleyes:

Weedpacket

Well, MD5 was never intended for password hashing, but became popular because - paradoxically - it was fast and in the minds of many "fast=good". It needed to be fast because it was intended for generating checksums for authenticating the integrity of arbitrarily large documents/files. With the success of collision attacks it's obsolete in that role.

sneakyimp wrote:
How does one use the [man]crypt[man] function and be sure that it's using blow fish. I am kinda confused by the manual

Use a salt that is

as follows: "$2a$", "$2x$" or "$2y$", a two digit cost parameter, "$", and 22 characters from the alphabet "./0-9A-Za-z".

. To see if it's available, see the value of CRYPT_BLOWFISH (PHP>=5.3 uses its own implementation if the underlying platform doesn't supply one).

The slowness of the password hash function is to throttle brute-force attacks (the delay is miniscule compared to - for example - the amount of time it would take a user to type a good password; for a random password made up of eight characters from the base64 alphabet, a hash that takes a microsecond to process would take on average four years to brute force - and someone is bound to notice the attack going on during that time. To put it another way, building up a dictionary of all possible such passwords and their hashes would take at least eight years of CPU time - (un)fortunately the job is embarrassingly parallel up to the point where you build an index on the hash), and the salt is to deal with the fact that humans aren't good at passwords.

NogDog wrote:

Whatever they're using, the NSA has probably already hacked it.

Keccak (aka SHA-3). I'd post the link but NIST is a U.S. Government department... Oh, it'll be up again eventually: http://www.nist.gov/itl/csd/sha-100212.cfm
In the meantime I'll also link the home page: http://keccak.noekeon.org/

traq

tangent: are you aware of 5.5's password hashing functions?

There is a backwards-compatible implementation, as well. The default (as of now, "only") hashing algorithm is bcrypt.

Bonesnap

Was going to bring up what traq mentioned.

Regarding passwords, I've begun adding what is apparently known as a "pepper" (in addition to the traditional salt) to the passwords before hashing. The pepper is similar to the salt in that it's appended (or otherwise "added") to the password in some fashion before the hashing; however, unlike the salt, it is not unique to each password, and unlike the salt, it does not lie in the database. Instead it's a constant that sits in your source code. The reason for this is in the event that your database is compromised, cracking the passwords are that much more difficult since the attacker does not have the pepper. Since most breaches are database-related and not source code-related, this adds some additional security.

sneakyimp

OK the first thing that occurs to me is that both [man]crypt[/man] and [man]password_hash[/man] both have a mode where they use some unspecified "default" algorithm to hash passwords -- and there are no guarantees that this so-called "default" hash will remain the same. In fact:

The default algorithm to use for hashing if no algorithm is provided. This may change in newer PHP releases when newer, stronger hashing algorithms are supported.

Given that these are one-way hash functions, doesn't this seem like an absolutely terrible idea? I'm imagining updating my version of PHP to the latest only to find that my database with over a million hashed passwords are useless because they went and changed the "default" hash algorithm on me.

traq, thanks for that link. I believe I like how they have standardized the hashing thing with a very clear name. So very much in the philosophy of PHP to shield us dummies from the particulars. It sounds to me like it's probably just an alias to the crypt function which I had been asking about.

Weedpacket, I understand that one should check whether CRYPT_BLOWFISH==1 to see if it's available. It's the badly-named and abused $salt parameter that rankles me first. It's not really just a salt if you are also specifying the hash algorithm now is it? Seems like they could have added one more parameter for $algorithm rather than abusing $salt.

Secondly, the docs are not exactly clear. Is anyone else confused by this?

Blowfish hashing with a salt as follows: "$2a$", "$2x$" or "$2y$", a two digit cost parameter, "$", and 22 characters from the alphabet "./0-9A-Za-z". Using characters outside of this range in the salt will cause crypt() to return a zero-length string. The two digit cost parameter is the base-2 logarithm of the iteration count for the underlying Blowfish-based hashing algorithmeter and must be in range 04-31, values outside this range will cause crypt() to fail. Versions of PHP before 5.3.7 only support "$2a$" as the salt prefix: PHP 5.3.7 introduced the new prefixes to fix a security weakness in the Blowfish implementation. Please refer to » this document for full details of the security fix, but to summarise, developers targeting only PHP 5.3.7 and later should use "$2y$" in preference to "$2a$".

I'm confused in a variety of ways:
What's the damn difference between "$2a$", "$2x$" and "$2y$" ? What, exactly are we specifying here? I believe I understand that prefixing my salt with one of these values will tell crypt() to use blowfish as hashing algorithm but don't understand what each means?
"base-2 logarithm of the iteration count for the underlying Blowfish-based hashing algorithmeter and must be in range 04-31" -- LOLWUT? Do we just pick one? Is there any additional information about what they mean and the possible implications of choosing one over the oether?
Does the alphabet include periods and slashes or is something escaped there? Looks base-64ish but with a period instead of a plus, which is kind of odd.
am I correct in understanding that the example uses "usesomesillystringforsalt" as a salt (which is 25 chars instead of the specified 22 chars) and that the crypt algorithm just truncated the salt?

Having looked at the examples more, I think I now see that the resulting hash string includes both a specifier for the algorithm used and also the salt used. I guess this answers my first concern, right?

sneakyimp

Bonesnap;11034287 wrote:
Was going to bring up what traq mentioned.

Regarding passwords, I've begun adding what is apparently known as a "pepper" (in addition to the traditional salt) to the passwords before hashing. The pepper is similar to the salt in that it's appended (or otherwise "added") to the password in some fashion before the hashing; however, unlike the salt, it is not unique to each password, and unlike the salt, it does not lie in the database. Instead it's a constant that sits in your source code. The reason for this is in the event that your database is compromised, cracking the passwords are that much more difficult since the attacker does not have the pepper. Since most breaches are database-related and not source code-related, this adds some additional security.

I have seen projects (can't remember which ones off-hand) where one specifies salt on a project-wide basis. It sounds like you are double-salting each password both with its own salt (which I assume you store in the DB along with the password with some kind of delimiter or something) and also with a site-wide salt. I think I would agree that this might help protect your info if someone were to acquire your data but not your source, but if they get both I don't expect it helps much? I'm fond of paraphrasing Kerckhoff's Principle, "the enemy knows the system."

I found a popular article on how to hash passwords which goes into some detail. I'll be reading that when I have a moment.

laserlight

sneakyimp wrote:
Given that these are one-way hash functions, doesn't this seem like an absolutely terrible idea? I'm imagining updating my version of PHP to the latest only to find that my database with over a million hashed passwords are useless because they went and changed the "default" hash algorithm on me.

It isn't really a problem as long as the old algorithms are not removed. For checking, you do need to parse the resulting hash in order to determine the algorithm and cost, but for generating new hashes, using the default means that the result will follow what the PHP developers regard as reasonable. Still, it is usually better to just specify then update it yourself for full control.

sneakyimp wrote:
if they get both I don't expect it helps much?

It wouldn't help at all. However, since it is possible that an attacker might not have your source code, there is no harm in also having this fixed salt value.

traq

sneakyimp;11034289 wrote:
OK the first thing that occurs to me is that both [man]crypt[/man] and [man]password_hash[/man] both have a mode where they use some unspecified "default" algorithm to hash passwords -- and there are no guarantees that this so-called "default" hash will remain the same.

right, in fact, the default salt implementation goes out of its way to be psuedo-random. This is as it should be; and it doesn't create any problems because the salt is returned along with the hashed password (you don't need separate fields in your DB anymore).

Also, yes, the "backport" uses crypt (the native function uses C's crypt functions, obviously).

sneakyimp;11034289 wrote:
Secondly, the docs are not exactly clear. Is anyone else confused by this?

I'm confused in a variety of ways:
What's the damn difference between "$2a$", "$2x$" and "$2y$" ? What, exactly are we specifying here? I believe I understand that prefixing my salt with one of these values will tell crypt() to use blowfish as hashing algorithm but don't understand what each means?
"base-2 logarithm of the iteration count for the underlying Blowfish-based hashing algorithmeter and must be in range 04-31" -- LOLWUT? Do we just pick one? Is there any additional information about what they mean and the possible implications of choosing one over the oether?
Does the alphabet include periods and slashes or is something escaped there? Looks base-64ish but with a period instead of a plus, which is kind of odd.
am I correct in understanding that the example uses "usesomesillystringforsalt" as a salt (which is 25 chars instead of the specified 22 chars) and that the crypt algorithm just truncated the salt?

You're not alone. This is why, when I learned about [man]password_hash[/man], I grabbed it and never looked back. [man]crypt[/man] is just flat-out confusing, and, therefore, often error-prone.

NogDog

traq;11034295 wrote:
... This is why, when I learned about [man]password_hash[/man], I grabbed it and never looked back. [man]crypt[/man] is just flat-out confusing, and, therefore, often error-prone.

I'm confused. The [man]password_hash/man page says you should let it automatically generate the random salt. Don't I need to know what the salt is, though, for when I validate future log-in attempts? Or am I missing something obvious (or subtle)?

Weedpacket

NogDog wrote:
Don't I need to know what the salt is, though, for when I validate future log-in attempts? Or am I missing something obvious (or subtle)?

It's built into the returned string as is the algorithm identifier; it's part of [man]password_verify[/man]'s job to parse the string into algorithm/password/salt components.

Incidentally, that manual page also links to a PHP implementation of the password_* functions for versions of PHP prior to 5.5.

sneakyimp wrote:
* "base-2 logarithm of the iteration count for the underlying Blowfish-based hashing algorithmeter and must be in range 04-31" -- LOLWUT? Do we just pick one? Is there any additional information about what they mean and the possible implications of choosing one over the oether?

I thought it was pretty self-explanatory: the Blowfish hash function can be run between 2⁴⁼¹⁶ and 2^{31=2147483648} times, depending on how fast or slow you want it to run. Example 4 on [man]password_hash[/man] is a demo for trying various costs.

What's the damn difference between "$2a$", "$2x$" and "$2y$" ? What, exactly are we specifying here?

The exact version of the Blowfish algorithm to use: [font=monospace]a[/font] - whatever is installed, [font=monospace]x[/font] - the older and broken version, [font=monospace]y[/font] - the corrected version (see the page linked in the paragraph you quoted).

am I correct in understanding that the example uses "usesomesillystringforsalt" as a salt (which is 25 chars instead of the specified 22 chars) and that the crypt algorithm just truncated the salt?

Let's see:

$salt = 'usesomesillystringforsalt';
for($i = strlen($salt); $i >= 0; --$i)
{
	$fullsalt = '$2y$06$' . substr($salt, 0, $i);
	echo sprintf('%-32s', $fullsalt), "\t", crypt('password', $fullsalt), "\n";
}

echo "-------\n";

for($i = 4; $i <= 31; ++$i)
{
	$start = microtime(true);
	crypt('password', sprintf('$2y$%02d$abcdefghijklmnopqrstuv', $i));
	$end = microtime(true);
	echo $i, "\t", $end - $start, "\t(", log($end - $start, 2), ")\n";
}

traq

the password_hash function returns something like: [font=monospace]$thisisthesalt$thisisthehashedandsaltedpassword[/font]

You would implement it like so:

<?php
# user creates a password
$pass = "user's awesome password";

# hash the password
$hash = password_hash( $pass );
unset( $pass );

# store the hash (e.g., in your DB)

<?php
# now user is logging in
$login = "user's awesome password";

$hash = # get user's stored hash

# verify login is correct
print  password_verify( $login,$hash )?
    "you're awesome!":
    "you suck";

[man]password_verify[/man] knows the salt to use because it is stored along with the hash.

Edit

not fast enough! 🙂

NogDog

Ah, thanks. I didn't pick up on the fact that you use a separate function for the verify portion. Of course, we're still on 5.3.x at work, so... 🙁

dalecosp

Weedpacket;11034299 wrote:

Let's see:

$salt = 'usesomesillystringforsalt';
for($i = strlen($salt); $i >= 0; --$i)
{
	$fullsalt = '$2y$06$' . substr($salt, 0, $i);
	echo sprintf('%-32s', $fullsalt), "\t", crypt('password', $fullsalt), "\n";
}

echo "-------\n";

for($i = 4; $i <= 31; ++$i)
{
	$start = microtime(true);
	crypt('password', sprintf('$2y$%02d$abcdefghijklmnopqrstuv', $i));
	$end = microtime(true);
	echo $i, "\t", $end - $start, "\t(", log($end - $start, 2), ")\n";
}

I just ran this on 5.2 and it completed almost instantly, and then on a 5.4 and it's been 10 minutes and still hasn't returned (good thing it's a dual-CPU box).

Probably serves me right 😉

How can I tell which algorithm crypt() is using? (I don't see anything on the manual page....) The 5.4 box does have a lot more ciphers available ... so I assume it's using a very expensive one right now....

traq

NogDog;11034303 wrote:
Ah, thanks. I didn't pick up on the fact that you use a separate function for the verify portion. Of course, we're still on 5.3.x at work, so... 🙁

backport. backport!

dalecosp;11034307 wrote:
I just ran this on 5.2 and it completed almost instantly, and then on a 5.4 and it's been 10 minutes and still hasn't returned (good thing it's a dual-CPU box).

Probably serves me right 😉

doesn't sound right. I'd kill it

dalecosp;11034307 wrote:
How can I tell which algorithm crypt() is using? (I don't see anything on the manual page....) The 5.4 box does have a lot more ciphers available ... so I assume it's using a very expensive one right now....

It's determined by the salt prefix (the [font=monospace]$2y$06$[/font] part). [font=monospace]$2y$[/font] specifies blowfish (06 is the cost parameter).

dalecosp

traq;11034309 wrote:
doesn't sound right. I'd kill it

I did kill it ... after two hours, twenty minutes :o . It appeared to have been exercising the hardware somewhat normally (variations in CPU load on CPU0 ranged from 60% to 100%, continuously, for that time period). As I implied but maybe didn't mention, the server's not mission-critical for much of anyone (one insurance agency does get mail from it, I guess), and it's a 2CPU box on FreeBSD, so no services were impacted except, maybe, one daemon that died for lack of swapspace (another died when I noticed that the box was 9 minutes ahead of GMT, reason unknown, but NTPD wasn't peered properly, and I reset the time (POP service doesn't like that much)).

I'd actually like to hear Weed chime in on that.... the fast box didn't have any advanced ciphers available, while the "slow" box had them all. I figure that the fast box did MD5 or something and the slow one was doing a heckuva job trying to blowfish the script....

the cost parameter

Yeah ... it did seem pretty darned expensive. I might have to see if I can leverage some old hardware to make a Beowulf cluster! :p (Of course, wifey through about 24 old computers out in the rain a couple weeks ago....)

Weedpacket

dalecosp wrote:
I'd actually like to hear Weed chime in on that....

Depends how you were running it; it's a command-line script that will take a very long time to complete, but it outputs results on an ongoing basis (the explanation for which I left to the source code).

The first part completes quickly - it just illustrates the effect of a too-long/too-short manually-provided salt (in particular, it truncates excessively long salts, answering sneakyimp's question).

The second part is the slow one, showing the effect of the cost parameter as it ranges from 4 to 31 (i.e., as the number of Blowfish rounds doubles from sixteen to two billion). Like with a cost of 11, it might take 0.1 seconds to produce a hash; a cost of 12 would then take 0.2 seconds; 13 would take 0.4 seconds; eight grains of rice on the next square of the chessboard.... It shouldn't be very parallelisable.

dalecosp

I ran it in CLI ... never got any output in 2 hours plus. I read "top" the whole time, but didn't pay attention to RAM & Swap ... it's a VM without much of either and it may have just filled that up and caused it to more/less lock up...

dalecosp

Tried it on another VM with only one CPU, but 8x the RAM and it worked fine. Hmm....

Weedpacket

Memory won't be an issue (unless there is a leak further down); I've been running it for couple of hours now and while it has been maxing out its CPU core the process still only has 6MB committed to it with no swapping at all (and it's currently generating a cost-27 hash).