Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Adjust bcrypt cost to prevent future password hash attacks

by andreas1234567 (Vicar)
on Jun 12, 2012 at 07:15 UTC ( #975703=perlquestion: print w/ replies, xml ) Need Help??
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]

Comment on Adjust bcrypt cost to prevent future password hash attacks
Select or Download Code
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

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 sundialsvc4 (Abbot) on Jun 12, 2012 at 13:21 UTC

    Although I am not a crypto expert, my intuition is that this is a mis-application of the cost function.   Instead of this, I suggest that the password should be stored as a salted hash-value.   As you know, “salt” is a randomly-generated plaintext value, known to everyone because it is transmitted and stored with the hashed value, which has been in some way “mixed in” to the secret (the password) before the hash is computed.   A four-digit salt provides 10,000 entirely different hash-values, all of which translate to the same unknown password.   The odds are now 1 in 10,000 that Eve will even see the same hash twice if she taps into the communication circuit.

    A successful attack on LinkedIn (or whomever) would depend upon that service storing the user passwords in the clear, so that they could be stolen as cleartext from the purloined database.   But there is no plausible reason for storing a password “in the clear,” and it rather defies me why LinkedIn would actually have done so ... if indeed they did.   (I frankly take news-stories that promise “total penetration and the recovery of plaintext card-numbers or passwords” with a grain of, ummm, salt.)

    Hashing is useful simply for the validation of a secret, such that the secret remains unknown to the party who is validating it.   The entire exchange over which the secret is transmitted should as a matter of course be encrypted, using a well-known and peer-reviewed “soup to nuts” protocol.   I have no reason to believe that the usual suspects (SSL/TLS/VPN) would not be acceptable for any commercial-grade purpose.   I am not a crypto expert.   Your Mileage May Vary.™

      The OP is using salted hashes and also assumes that LinkedIn was doing the same. The use of cost here would be to prevent many attacks per second against the hashes since an attack would take additional time. The hope is that this time is long enough to deter attackers who already have the ability to see your salted hashes, or have the ability to query the login server repeatedly. TLS has the ability to filter out login requests over the network, and this addition of bcrypt will help against physical attacks where data has already been compromised.

      Linkedin practically stored the user passwords in the clear. They stored them as unsalted SHA1 hashes. The vast majority of them can be cracked by having a rainbow table, i.e. a precomputed table of SHA1 hashes of common and less common passwords.

      I believe the OP is worried that the attacker might gain access to the password database (or even a single password hash) and then start cracking that offline. This is where attacks are their most potent.

      Having a costly crypto function is meant to thwart password-guessing attacks, especially brute force ones. Pretty much every OS uses these for password checking. Bcrypt takes the cost idea a bit further and gives adaptable cost, doubling in computation length for every step, to cover for future increases in CPU speed.

      Oh, and I'm not a crypto expert either.

      Although I am not a crypto expert, my intuition is...

      That would have been a good place to stop writing. The rest of your post is mostly irrelevant to the OP's question.

      sundialsvc4,

      I regret to write that most of your three paragraphs make no sense at all. I mean no offense.

      --
      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 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 ikegami (Pope) 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; }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://975703]
Approved by Ratazong
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (10)
As of 2014-09-19 17:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (143 votes), past polls