http://qs321.pair.com?node_id=975703

andreas1234567 has asked for the wisdom of the Perl Monks concerning the following question:

Honorable Monks

While the news of the LinkedIn breach is still fresh, this (Krebs on Security) article recommends to distinguish between cryptographic hashes (which are designed to be fast) and password hashes (which are designed to be slow). Bcrypt is an interesting example of the latter.

I experiment with Digest::Bcrypt:

$ cat digest-bcrypt.pl use strict; use warnings; use Digest; use Time::HiRes qw(time); my $salt = "z" x 16; my $data = "super secret"; =pod Demonstrate B<bcrypt> time consumption with increasing value of I<cost> . =cut for (my $cost = 1; $cost <= 20; $cost++) { my $before = time(); # start timer my $bcrypt = Digest->new('Bcrypt'); $bcrypt->cost($cost); $bcrypt->salt($salt); $bcrypt->add($data); my $digest = $bcrypt->hexdigest; print $digest; printf( " Cost %02d took %.2fsec\n", $cost, time() - $before); } $ perl digest-bcrypt.pl 0cef6ce24cc4d3bdb553754f6ea95c765fd3a0bb23313b Cost 01 took 0.00sec 6444b8c9a0769c32a66e7eec17a4687d9491341fbaea1a Cost 02 took 0.00sec b574c9c72eece2b9b850684ec32c944ebbb7f23e913492 Cost 03 took 0.00sec 05d1da6d77aef3f839e1637ebfe86bfc9ce0f26e7adf10 Cost 04 took 0.00sec 1712b9f8a394fe2bdd87df4bccea1674603645f004b322 Cost 05 took 0.00sec 9b273724b2e0cd9a1261f5aa717ff1f3ca0706549729e0 Cost 06 took 0.01sec d613a9cb3373b3aaa2c3aa76eef452221ebfc54b6dc8fc Cost 07 took 0.01sec 4b5c602328abd9ebd98a624bbe31b60047782a659cf9c0 Cost 08 took 0.02sec 2eafabe1b068ce00a1a9d0b8a06063114e9b9cfcc72ce4 Cost 09 took 0.04sec 23d90b4016cc6ce3612fb6941a232bc463b3a4b49d7dd6 Cost 10 took 0.08sec 88f90f11bd655883543edd6858e724ce22fee202153026 Cost 11 took 0.17sec 3f36104c464b98678c2aa085dadca258699bd4c94c51bc Cost 12 took 0.34sec 3c739aa56523f1779bdbdd51a975efdb2f186cd2a52e09 Cost 13 took 0.68sec b004d1fce96e04be39bd1066f0ff8fba5281531387305c Cost 14 took 1.37sec 713abbcd3572169159f46ffabd9ca59421a827a847dade Cost 15 took 2.72sec 3f2cf30e4689c77934d60c47004d64868d98c40b5342ed Cost 16 took 5.42sec ba8d410333a168cd1f015f54e6b845a26d25b6701775a3 Cost 17 took 10.87sec 12d75ee1670461b46ebc8c102a90d4b66c479055a9a942 Cost 18 took 21.94sec 1322956f61ec11c58d3c58f3b910fbe09fe8885404769e Cost 19 took 43.27sec a66a7040d20b1cb1c259b23f9e63b443b69cb875920616 Cost 20 took 87.97sec
I observe that an increase of the cost value will slow down the process significantly. Also, the value of cost does have an impact of the output of the hash function. Ideally I would like to incrementally increase the cost over time (as CPU's get cheaper etc) to raise the bar and make it equally infeasible to brute force password hashes ten and twenty years from now as it is today. Imagine this being used in a web site for logging in and checking credentials.

Does it make sense to design the application for cost increase such that one can gradually phase out the fast ones and keep the process slow? E.g. For each user store the username, the bcrypt cost and the password hash. This would allow the application to increase the cost (at next login) and recompute the hash if the current cost is considered to low (e.g. if it takes less than 1 second to compute):

{ "comment" : "Cost 14 took 1.36s on on 2012-06-12T07:42:27", "password_hash" : "cab5a4e82eb3077b381d2cc882c99b13d51f706aedb7ff", "bcrypt_cost" : 14, "username" : "007" } # In 5 years from now we increase cost { "comment" : "Cost 15 took 1.72s on 2017-06-12T08:44:19", "password_hash" : "7f02d8b30b74b439cfafbe2f729c9daee3bb45a568dd1f", "bcrypt_cost" : 15, "username" : "007" }

--
No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]

Replies are listed 'Best First'.
Re: Adjust bcrypt cost to prevent future password hash attacks
by ikegami (Patriarch) on Jun 12, 2012 at 20:57 UTC

    Just store the cost along with the salt and the hash.

    Have the user change his password the next time he logs in after you increase the cost.

    sub set_passwd { my ($user, $passwd) = @_; my $cost = COST; my $salt = _get_random_salt(); _set_passwd($user, "$cost:$salt:$passwd); } sub check_passwd { my ($user, $submitted_passwd) = @_; my ($cost, $salt, $passwd) = split /:/, _get_passwd($user); return hash($submitted_passwd, $salt, $cost) ne $passwd; } sub is_passwd_expired { my ($user) = @_; my ($cost, $salt, $passwd) = split /:/, _get_passwd($user); return $cost != COST; }
Re: Adjust bcrypt cost to prevent future password hash attacks
by Anonymous Monk on Jun 12, 2012 at 10:38 UTC

    I'm using a different bcrypt module, Crypt::Eksblowfish::Bcrypt, and am observing that instead of a hex digest, it stores both the settings and the salt in the output hash:

    length = 11 $2a$11$WUHhXETkX0fnYkrqZU3ta.SjqJkrtBHwUGTHlTfGO1BINxczZnBJm length = 12 $2a$12$WUHhXETkX0fnYkrqZU3ta.D8cEIQdqzSrGG5wFTandtdP9Ypqzu0W

    Therefore, your JSON-like storage should not be needed. This is the code I was using:

    use Time::HiRes 'time'; use Crypt::Eksblowfish::Bcrypt qw(bcrypt en_base64); sub _salt() { return en_base64('abcdefghijklmnop'); } my $cost = sprintf("%02d", $ARGV[0]); my $settings = join( '$', '$2a', $cost, _salt() ); my $st = time(); print bcrypt("password", $settings), "\n"; printf "took %i milliseconds\n", (time() - $st) * 1000;

    I suspect a cost of 11-14 is good enough to deter brute force and even some dictionary attacks on today's hardware, while not bogging down your server -- depending of course on the security requirements and the amount and frequency of users needing to log in.

      I'm using a different bcrypt module, Crypt::Eksblowfish::Bcrypt,
      According to the documentation, Digest::Bcrypt is mostly a wrapper around Crypt::Eksblowfish::Bcrypt.
      .. it stores both the settings and the salt in the output hash
      Does that mean you can deduce the cost from the output hash alone? In order to adjust the cost over time, one either need to store the cost or be able to compute it (e.g. from the output hash).

      --
      No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]
        Does that mean you can deduce the cost from the output hash alone? In order to adjust the cost over time, one either need to store the cost or be able to compute it (e.g. from the output hash).

        I believe so. It's stored right after the $2a$. The output hash, by the looks of it, is similar to the way passwords are stored in Unixes -- and this is no surprise since bcrypt came from the OpenBSD guys.

        The format is: $cryptomethod$length$salt$password, although anything after $cryptomethod$ is roughly freeform and parsed by the method (i.e. bcrypt) itself.

        I'm not sure about what sort of hash Digest::Bcrypt is supposed to return, but it looks nothing like the raw Eksblowfish version. Personally, I would not trust this module if I cannot get an output similar to the crypt(3) C function from it.

Re: Adjust bcrypt cost to prevent future password hash attacks
by muba (Priest) on Jun 12, 2012 at 17:41 UTC

    If I read you correctly, your idea is to re-hash passwords every now and then as computers get faster, am I right? Assuming that I am, here's my question.

    Once the hash of a password gets stored, we really have no longer have an idea of what the actual password is. In an ideal world, even when the user tries to log in, a hash of his password is sent, and then the stored hash and the stored hash are compared to determine the successfulness of a login attempt.

    Given this, how do you propose the password is re-hashed without having the original password to work from?

      .. when the user tries to log in, a hash of his password is sent
      No. When the user tries to log in, the password is sent (encrypted in transit, then decrypted (in memory only) to clear text on the server).
      Given this, how do you propose the password is re-hashed without having the original password to work from?
      At next successful login. Add password expiry functionality (i.e. max 30 days), and we can ensure that all passwords are either
      • invalid, or
      • re-hashed with increased cost over the next 30 days.

      --
      No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]
Re: Adjust bcrypt cost to prevent future password hash attacks
by Anonymous Monk on Jun 12, 2012 at 08:12 UTC

    I'd say using Transport Layer Security (TLS) is more important as its easier to throttle login attempts on webservers, thus preventing brute-force attacks

      Data must be secured in transit and at rest. TLS protects data in transit only, and does not prevent offline attacks (e.g. recent Linkin breach).

      We need both TLS and bcrypt, not just the former.

      --
      No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]

        and does not prevent offline attacks

        of course not :) I wasn't suggesting switching away from bcrypt, merely that the cost is not as important for online attacks, those can be throttled effectively

        but, for offline, you should use encrypted harddisks and not rely on bcrypt alone

A reply falls below the community's threshold of quality. You may see it by logging in.