What is password strength considered enough for use with password_hash function?

Question

As far as I understand, one of the most important features of the new PHP password hashing extension (or bcrypt in general) is algorithm's speed, which slows brute-force attack method a lot.

But still it runs at some speed, surely enough for the dictionary attack and to brute-force weak passwords, [supposedly] shorter than six alphanumeric characters.

So I want to know, how it's certainly slow, and, particularly - which password strength considered safe to be used with. "As strong as you can imagine" is not an answer, as password strength is always a trade-off between security and usability - so, I am looking for the minimal strength that can be considered safe and even some future-proof.

Please note that I am a man of practice - so, certain answer based on concrete numbers is way more preferable than long and windy theoretical reasoning with uncertain conclusion.

To clarify a bit more, worst scenario supposed: users database is stolen, and someone would try to decipher passwords. Rainbow tables are not an option thanks to strong salt. So, the only vectors left are dictionary attack and brute-force. Assuming we are supplying users with pre-generated passwords, eliminating dictionary attack. This is why password strength is my only concern.

Update:
It seems I weren't understood well. The question, to me, is quite practical, and fairly answerable. And of great importance.

Without determining enough password strength, the use of this new algorithm can be questioned. Why bother with good algorithm if passwords are still left unsafe? So - it is my strong belief - that along with recommendation for using new hashing algorithm, there should be always a recommendation for the minimum password strength. Which I want to know.

In other words, if there exists particular certainty about one part - algorithm ("use this one, not other!") - there apparently should be certainty about another part - password strength, which can be spoken with same level of authority. Otherwise the weakest part will spoil the strongest one.

Answer 1

Am not sure if i understand your question clearly but i would just focus on password strength and how it affects brute-force attack.

But still it runs at some speed, surely enough for the dictionary attack and to brute-force weak passwords, [supposedly] shorter than six alphanumeric characters.

Introduction

For a moment forget about hash algorithm (md5, sha , pbkdf2 bcrypt , scrypt , etc) and lest focus on Password Strength first

Password Strength Wiki

This is a measure of the effectiveness of a password in resisting guessing and brute-force attacks. In its usual form, it estimates how many trials an attacker who does not have direct access to the password would need, on average, to guess it correctly.

It can simply be calculated as :

The entropy is given by H=Llog2N where L is the length of the password and N is the size of the alphabet, and it is usually measured in bits.

Hash Function

password_hash uses [bcrypt][4] by default with is sufficient for a password but there are better alternatives such as PBKDF2 or scrypt for more information on what i mean see How To Safely Store A Password

Using oclHashcat , lets estimate the following

+--------+-----------+----------------+
|  HASH  | ESTIMATE  |     BITS/S     |
+--------+-----------+----------------+
| MD5    | 10742M    | 90110427136    |
| BCRYPT | 31M       | 260046848      |
+--------+-----------+----------------+

Please note that is is an estimate and can vary based on hardware capacity

With this information we can safely calculate how long it would take us to brute force different password

Calculate Entropy in PHP

$passwords = array(
        "1234",
        "F2A1CC",
        "password",
        "PaSSworD",
        "P4ssw0Rd97",
        "p#aSS*Word14",
        "Dance With Me Tonight" 
);

print("PASSWORD\tLENGTH\tENTROPY\tTIME MD5\tTIME BCRYPT\n");

foreach($passwords as $password ){

    printf("%s\t%s\t%s\t%s\t%s\n", 
        $password, 
        strlen($password), 
        $entropy = calculateEntropy($password), 
        totalTime($entropy, "90110427136"),     // Check with MD5
        totalTime($entropy, "260046848")        // Check with BCrypt
    );
}

Output

+-----------------------+--------+---------+------------+----------------+
|       PASSWORD        | LENGTH | ENTROPY |  TIME MD5  |  TIME BCRYPT   |
+-----------------------+--------+---------+------------+----------------+
| 1234                  |      4 |  13.29  | 1min       | 1min           |
| F2A1CC                |      6 |  24.00  | 1min       | 1min           |
| password              |      8 |  37.60  | 1min       | 1min           |
| PaSSworD              |      8 |  45.60  | 1min       | 1day+          |
| P4ssw0Rd97            |     10 |  59.54  | 2mo+       | 71yr+          |
| p#aSS*Word14          |     12 |  75.86  | 13,479yr+  | 4yr+           |
| Dance With Me Tonight |     21 |  120.29 | 474,250yr+ | 164,335,595yr+ |
+-----------------------+--------+---------+------------+----------------+

Output Converted using csv2table

CUDA/OpenCL implementations of password crackers can leverage the massive amount of parallelism available in GPUs, peaking at billions of candidate passwords a second.

Lets Estimate With we can do 921600M c/s on in parallel on very fast system

T = 966367641600 * 8   
T = 7,730,941,132,800  // bits/sec

Using

foreach($passwords as $password ){  
    printf("%s\t%s\t%s\t%s\n", 
        $password, 
        strlen($password), 
        $entropy = calculateEntropy($password), 
        totalTime($entropy, "7730941132800")        // Check with Hash
    );
}

Output

+-----------------------+---------+---------+----------+
|       PASSWORD        | LENGTH  | ENTROPY |   TIME   |
+-----------------------+---------+---------+----------+
| 1234                  |       4 | 13.29   | 1min     |
| F2A1CC                |       6 | 24.00   | 1min     |
| password              |       8 | 37.60   | 1min     |
| PaSSworD              |       8 | 45.60   | 1min     |
| P4ssw0Rd97            |      10 | 59.54   | 20hr+    |
| p#aSS*Word14          |      12 | 75.86   | 157yr+   |
| Dance With Me Tonight |      21 | 120.29  | 5,527yr+ |
+-----------------------+---------+---------+----------+

As you can see it still takes a while for a decent 12 digit to be broken.

Function Used

// Calculate Password entropy
// Uses H = L Log2 N
// where L is the length of the password and
// N is the size of the alphabet, and it is usually measured in bits
function calculateEntropy($password) {

    // See http://en.wikipedia.org/wiki/Password_strength
    // Entropy per symbol for different symbol sets
    // Missing All extended ASCII printable characters
    // Missing Diceware word list

    // TODO
    // Larger Character Set
    // '/[\!"#$%&\'\(\)\*\+,\-.\/:;<\=>\?\@\[\]^_`\{|\}~]+/' => 32,
    $cases = array(
            "/\s+/" => 1, // Arabic numerals (0–9) (e.g. PIN)
            "/[0-9]+/" => 10, // Arabic numerals (0–9) (e.g. PIN)
            "/[a-z]+/" => 26, // Case insensitive Latin alphabet (a-z)
            "/[A-Z]+/" => 26, // Case insensitive Latin alphabet (A-Z)
            '/[\!\@#$%\?\&\*\(\)_\-\+=~:;.]+/i' => 18  // Other Character
        );

    $L = strlen($password); // Length of password
    $N = 0; // Character Set

    foreach($cases as $regex => $value ){
        if (preg_match($regex, $password)){
            $N += $value;
        }
    }

    // Don't confuse hexadecimal for alpha numeric characters
    // hexadecimal numerals (0–9, A-F) (e.g. WEP keys)
    if (ctype_xdigit($password)){
        $N = 16;
    }

    // Fix pure number cases that might have been changed by hexadecimal
    // Arabic numerals (0–9) (e.g. PIN)
    if (ctype_digit($password)){
        $N = 10;
    }

    // Using H = L Log2N
    // See http://en.wikipedia.org/wiki/Password_strength
    // Random passwords entropy
    $H = $L * log($N, 2);
    return number_format($H, 2);
}

// Claculate Total time it would take
// Using Entropy & froce / s
function totalTime($entropy, $force) {
    bcscale(0);

    // Total Base on entorpy 2^H
    $total = bcpow(2, $entropy);

    // Time Taken per sec on Force
    $ss = bcdiv($total, $force);

    $time = "";
    $parts = [];

    $parts['yr'] = bcdiv($ss, "31104000");
    $parts['mo'] = bcdiv(bcmod($ss, 31104000), 2592000);
    $parts['day'] = bcdiv(bcmod($ss, 2592000), 86400);
    $parts['hr'] = bcdiv(bcmod($ss, 86400), 3600);

    // Clean Year
    // Can really generate large numbers

    $suffix = "";
    $yr = $parts['yr'];
    if (!empty($yr)){
        if (bccomp($yr, "1000000") > 0){
            $parts['yr'] = bcdiv($yr, "1000000"); // Million
            $year = " million ";
        }

        if (bccomp($yr, "1000000000") > 0){
            $parts['yr'] = bcdiv($yr, "1000000000"); // Billion
            $year = " billion ";
        }

        if (bccomp($yr, "1000000000000") > 0){
            $parts['yr'] = bcdiv($yr, "1000000000000"); // Trillion
            $year = " trillion ";
        }
    }

    foreach($parts as $t => $v ){
        if (empty($v)){
            continue;
        }
        $time .= number_format($v, 0) . $suffix . $t . "+";
        break;
    }

    return empty($time) ? "1min" : $time;
}

Misunderstanding

You are right password length is important so as the entropy of the password. Most recommendations advice users to use use bcrypt , password complexity, etc. without understanding of password strength

But the fact is the simplest passwords can often be the strongest.

Source | Related blog post

So I want to know, how it's certainly slow, and, particularly - which password strength considered safe to be used with.

Source

Definitely not 6 letters :)

• < 28 bits = Very Weak; might keep out family members
• 28 - 35 bits = Weak; should keep out most people, often good for desktop login passwords
• 36 - 59 bits = Reasonable; fairly secure passwords for network and company passwords
• 60 - 127 bits = Strong; can be good for guarding financial information
• 128+ bits = Very Strong; often overkill

Conclusion

Here are some good references you might what to look at

• The Rainbow Table Is Dead
• oclHashcat
• How To Safely Store A Password
• Don't use bcrypt
• Password Entropy
• Password Strength/Entropy: Characters vs. Words
• HOW MUCH ENTROPY IN THAT PASSWORD?
• Kolmogorov complexity

Answer 2

It is an interesting question, though it is very unlikely that anybody will be able to give a final answer.

As you know, BCrypt (and other key-derivation functions) have a cost factor. Normally you tune this cost factor, until your server needs a certain time for hashing a password, for example 1 millisecond. An attacker with the same hardware could therefore calculate 1'000 hashes/s.

If you compare the speed of oclHashcat (GPU) with its CPU version you see a factor 100 for MD5, so we can guess that an attacker can bruteforce about 1'000'000 hashes/s (BCrypt is not GPU friendly, but to be on the safe side...). That's ways from the 8'000'000'000 MD5 hashes/s and depends on the cost factor.

The second problem is the strongness of the password. If it is part of a common dictionary, it can be found quickly even if it is long, so a minimum length is no guarantee for a strong password. If it is "random" enough, the only way to crack it, is brute-forcing (the best case for us). For this case we can try some math:

Password alphabet: 62 characters (a-z A-Z 0-9)
Combinations to try: half of all possible combinations
Password length 7: 3E12 combinations → 20 days
Password length 8: 2E14 combinations → 3-4 years

Of course this is based on a lot of assumptions, maybe the attacker can brute-force much faster, or the password is not this strong. I myself demand a minimum of 8 characters, but recommend to use a passphrase.

EDIT: One more note about password strength:

The strength of a password cannot be realistically calculated, surely not by a formula. Every serious password cracker tool will support hybrid attacks and rule based attacks. Passwords looking strong can be very weak, if they are part of a dictionary or are coped by a rule, so it depends on the imagination of the attacker, how fast a password can be cracked.

The only thing we can tell is, that long and random passwords are strong, because there is no easier way to crack them than brute-forcing. But this doesn't help here, because the users will choose their passwords, not the developer who built a website, and they do not choose ideal passwords.

Answer 3

Per your latest comment, you wish to construct a password scheme that would be acceptable to major governments. This information is readily available.

• FIPS 112, the standards required by the US government.
• EU Password Guidelines