Password strength calculations given class, length and PBKDF2 iteration count with may assumptions made.

Random password classes

Word or phrase based passwords are much harder to analyse because there are different probabilities of characters being picked depending on language rules and other human factors. In general they will require longer lengths to be secure.

In this analysis we will look at password that use a set of character from which password is constructed by picking them at random, with no correlation between the picks.

Here are the password classes we will look at:

Alpha (single case): 26 characters to choose from or 4.7 bits of entropy per password character.
Alpha (single case) and numbers: 36 characters to choose from or 5.2 bits of entropy per password character.
Alpha mix of lower and upper case: 52 characters to choose from or 5.7 bits of entropy per password character.
Alpha mix of lower and upper case and numbers: 62 characters to choose from or 6.0 bits of entropy per password character.
All printable ASCII characters: 128 characters to choose from or 7.0 bits of entropy per password character.

Attacking passwords

I assume that the attacker gains full, off-line access to a password database. I assume that the database contains password hashes derived using PBKDF2 or that PBKDF2 was used to derive cryptographic key used to encrypt entries in the database in such a way that it is possible to tell if the attacker has guessed correct password to decrypt the contents in constant time using GPU or custom ASIC.

The process will involve generating a candidate password guess, running PBKDF2 algorithm involving a hash function like SHA1 one or more times and using the resulting derived key to verify if the guess was correct or not.

In this brute-force attack the structure of the password used and order of techniques used to generate the candidate password guesses will determine how long statistically the cracking process will take.

For language based password, attacker may choose many different approaches at generating candidate passwords.

The attacker will be forced to use brute-force methods of guessing password based on two main parameters:

Password length

Attacker will start with most common password length, and generally start from small lengths as they can be iterated quickly. Long passwords will be less likely tried as the search space increased exponentially with the password length.

Set of characters used

Because it is easier to remember password containing just numbers or just lower case character, the attacker may focus first on trying passwords with limited set of characters used.

Password strength

Because length of the password make it exponentially stronger compared to all other parameters that make them stronger linearly we will focus on password lengths.

Assuming strong password will take 1000 years in average of offline cracking (e.g. for leaked password vault or encrypted GPG private key).

This is 1.33491456e+23 password hashes calculated (for half of the search space) in 1000 years.

Password would need to have 76.8 bits of cracking resistance.

PBKDF2 iterations and cracking resistance

PBKDF2 is a method of deriving keys from passwords. The keys derived can be then used as key for encryption algorithms (like AES) to decrypt encryption keys or data directly.

PBKDF2 iterations can make cracking harder by requiring multiple hash calculations per password checked. This is equivalent of having that many times harder password to crack.

By “cracking resistance” I mean the entropy of the password in bits (length and character classes used) plus any extra hashing iterations needed to actually verify if a password has matched the given hash.

So for example with 4 iteration a password that has entropy of 14 bits (2 arbitrary printable ASCII characters) would have 16 bits of cracking resistance because the GPU would need to calculate 65536 (2^2*4) SHA1 hashes to check all password combinations.

Medium sized GPU cluster model

Assuming that attacker uses 200 GPU cards we can perform 4340000000000.0 giga SHA1 hashes per second.

Ref: GPU Accelerated Password Cracking in the Cloud: Speed and Cost-Effectiveness

Salted hashed passwords (1 KDF iteration)

Assuming that password is salted with a random value (to defeat rainbow tables attack) and is hashed once.

Maximum password length

Assuming 128 bit protection for password protected object (e.g. AES-128 symmetric key derived from password) as having stronger password makes the key the easier target instead.

Passwords lengths that are required for different character classes to reach 128 bits of cracking resistance:

Alpha (single case): 28
Alpha (single case) and numbers: 25
Alpha mix of lower and upper case: 23
Alpha mix of lower and upper case and numbers: 22
All printable ASCII characters: 19

Minimum password length for strong GPU cracking resistance

To reach 76.8 bits of cracking resistance:

Alpha (single case): 17 characters for 79.9 bits of cracking resistance
Alpha (single case) and numbers: 16 characters for 82.7 bits of cracking resistance
Alpha mix of lower and upper case: 14 characters for 79.8 bits of cracking resistance
Alpha mix of lower and upper case and numbers: 14 characters for 83.4 bits of cracking resistance
All printable ASCII characters: 12 characters for 84.0 bits of cracking resistance

Passwords hashed multiple times (iterations > 1)

Iterations add computational cost for both the user and the attacker as multiple passes of hashing algorithms has to be run per password check.

Adding characters to password makes them harder to remember but does not cost computation.
Iterations add constant number of bits of cracking resistance to bits of entropy of the password making them harder to crack.

Iterations needed to make password strong against GPU cracking

In order for password to reach required 76.8 bits of cracking resistance we may use KDF iterations to force the GPU to run more hash calculations per password guess tested.

Alpha (single case)

17 characters for 79.9 bits of entropy is enough to have only 1 iteration
16 characters for 75.2 bits of entropy, missing 2.6 bits: 8 iterations needed
15 characters for 70.5 bits of entropy, missing 7.3 bits: 256 iterations needed
14 characters for 65.8 bits of entropy, missing 12.0 bits: 8192 iterations needed
13 characters for 61.1 bits of entropy, missing 16.7 bits: 131072 iterations needed
12 characters for 56.4 bits of entropy, missing 21.4 bits: 4194304 iterations needed
11 characters for 51.7 bits of entropy, missing 26.1 bits: 134217728 iterations needed
10 characters for 47.0 bits of entropy, missing 30.8 bits: 2147483648 iterations needed
9 characters for 42.3 bits of entropy, missing 35.5 bits: 68719476736 iterations needed
8 characters for 37.6 bits of entropy, missing 40.2 bits: 2199023255552 iterations needed

Alpha (single case) and numbers

16 characters for 82.7 bits of entropy is enough to have only 1 iteration
15 characters for 77.5 bits of entropy, missing 0.3 bits: 2 iterations needed
14 characters for 72.4 bits of entropy, missing 5.4 bits: 64 iterations needed
13 characters for 67.2 bits of entropy, missing 10.6 bits: 2048 iterations needed
12 characters for 62.0 bits of entropy, missing 15.8 bits: 65536 iterations needed
11 characters for 56.9 bits of entropy, missing 21.0 bits: 2097152 iterations needed
10 characters for 51.7 bits of entropy, missing 26.1 bits: 134217728 iterations needed
9 characters for 46.5 bits of entropy, missing 31.3 bits: 4294967296 iterations needed
8 characters for 41.4 bits of entropy, missing 36.5 bits: 137438953472 iterations needed

Alpha mix of lower and upper case

14 characters for 79.8 bits of entropy is enough to have only 1 iteration
13 characters for 74.1 bits of entropy, missing 3.7 bits: 16 iterations needed
12 characters for 68.4 bits of entropy, missing 9.4 bits: 1024 iterations needed
11 characters for 62.7 bits of entropy, missing 15.1 bits: 65536 iterations needed
10 characters for 57.0 bits of entropy, missing 20.8 bits: 2097152 iterations needed
9 characters for 51.3 bits of entropy, missing 26.5 bits: 134217728 iterations needed
8 characters for 45.6 bits of entropy, missing 32.2 bits: 8589934592 iterations needed

Alpha mix of lower and upper case and numbers

14 characters for 83.4 bits of entropy is enough to have only 1 iteration
13 characters for 77.4 bits of entropy, missing 0.4 bits: 2 iterations needed
12 characters for 71.5 bits of entropy, missing 6.4 bits: 128 iterations needed
11 characters for 65.5 bits of entropy, missing 12.3 bits: 8192 iterations needed
10 characters for 59.5 bits of entropy, missing 18.3 bits: 524288 iterations needed
9 characters for 53.6 bits of entropy, missing 24.2 bits: 33554432 iterations needed
8 characters for 47.6 bits of entropy, missing 30.2 bits: 2147483648 iterations needed

All printable ASCII characters

12 characters for 84.0 bits of entropy is enough to have only 1 iteration
11 characters for 77.0 bits of entropy, missing 0.8 bits: 2 iterations needed
10 characters for 70.0 bits of entropy, missing 7.8 bits: 256 iterations needed
9 characters for 63.0 bits of entropy, missing 14.8 bits: 32768 iterations needed
8 characters for 56.0 bits of entropy, missing 21.8 bits: 4194304 iterations needed

GPG example

For GPG exported private key I get this information on my system:

iter+salt S2K, algo: 7, SHA1 protection, hash: 2, salt: D8AD57FB46799088
protect count: 65011712 (255)

Looks like KDF hashing algorithm used is SHA1, password is salted and the iteration count for 65011712. According to documentation GPG agent will calculate the number iterations based on hashing speed of your machine so that it takes about 100ms to run all iterations for single password.

This gives us 26.0 bits of extra cracking resistance as each passwords guess has to be hashed 65011712 times before next one can be tried.

Maximum password length

Passwords lengths that are required for different character classes to reach 128 bits of cracking resistance:

Alpha (single case): 22
Alpha (single case) and numbers: 20
Alpha mix of lower and upper case: 18
Alpha mix of lower and upper case and numbers: 18
All printable ASCII characters: 15

Minimum password length for strong GPU cracking resistance

To reach 76.8 bits of cracking resistance:

Alpha (single case): 12 characters for 56.4 bits of entropy for total 82.4 bits of entropy
Alpha (single case) and numbers: 11 characters for 56.9 bits of entropy for total 82.9 bits of entropy
Alpha mix of lower and upper case: 10 characters for 57.0 bits of entropy for total 83.0 bits of entropy
Alpha mix of lower and upper case and numbers: 9 characters for 53.6 bits of entropy for total 79.6 bits of entropy
All printable ASCII characters: 8 characters for 56.0 bits of entropy for total 82.0 bits of entropy

Dictionary based passwords

Password based on language construct will have lower entropy than equivalent length and character class passwords where each character is chosen at random independently. Crackers will use statistical techniques to generate password candidates based on real life passwords used, dictionary word or phrases. It is hard to estimate entropy of such passwords as there are many ways generate such candidates.

Other KDF algorithms

Today there are much better ways to derive keys from passwords that make use of GPU (or custom ASIC) based cracking less practical. These are based on hashing functions requiring relatively large amounts of RAM to run.

In any case if you can use algorithms like Argon2 over PBKDF2, please do so.

Conclusion

For GPG you need at least 9 character mixed case with numbers password.
To be iteration safe (1 iteration) you need at least 14 characters mixed case with numbers password.
Passwords stored in password manager should aim for 128 bits entropy and therefore should be 22 characters or longer mixed case with numbers passwords.
When you need to type your password on a phone or TV often you could use 16 lower case and number characters.

Appendix

The above text was generated with this Ruby script:

#!/usr/bin/ruby
require 'erb'
puts ERB.new(DATA.read, trim_mode: '-').result
__END__
<%-
def entropy(search_space)
  Math.log2(search_space)
end

hash_speed = 21.7 * 200 * 1_000_000_000
years = 1000
year_sec = years * 3600 * 24 * 356

pw_class = {
  "Alpha (single case)" => ('a'..'z').to_a.length,
  "Alpha (single case) and numbers" => ('a'..'z').to_a.length + 10,
  "Alpha mix of lower and upper case" => ('a'..'z').to_a.length * 2,
  "Alpha mix of lower and upper case and numbers" => ('a'..'z').to_a.length * 2 + 10,
  "All printable ASCII characters" => 2**7,
}
-%>
# Random password classes

Word or phrase based passwords are much harder to analyse because there are different probabilities of
characters being picked depending on language rules and other human factors. In general they will require
longer lengths to be secure.

In this analysis we will look at password that use a set of character from which password is constructed by
picking them at random, with no correlation between the picks.

Here are the password classes we will look at:

<%-pw_class.each { |c, n|-%>
  1. <%= c %>: `<%= n %>` characters to choose from or `<%= entropy(n).round(1) %>` bits of entropy per password character.
<%-}-%>

# Attacking passwords

I assume that the attacker gains full, off-line access to a password database.
I assume that the database contains password hashes derived using PBKDF2 or that PBKDF2 was used to derive
cryptographic key used to encrypt entries in the database in such a way that it is possible to tell if the
attacker has guessed correct password to decrypt the contents in constant time using GPU or custom ASIC.

The process will involve generating a candidate password guess, running PBKDF2 algorithm involving a hash function
like SHA1 one or more times and using the resulting derived key to verify if the guess was correct or not.

In this brute-force attack the structure of the password used and order of techniques used to generate the
candidate password guesses will determine how long statistically the cracking process will take.

For language based password, attacker may choose many different approaches at generating candidate passwords.

The attacker will be forced to use brute-force methods of guessing password based on two main parameters:

## Password length

Attacker will start with most common password length, and generally start from small lengths as they can be iterated quickly.
Long passwords will be less likely tried as the search space increased exponentially with the password length.

## Set of characters used

Because it is easier to remember password containing just numbers or just lower case character, the attacker may focus first on trying passwords with limited set of characters used.

## Password strength

Because length of the password make it exponentially stronger compared to all other parameters that make them stronger linearly we will focus on password lengths.

Assuming strong password will take 1000 years in average of offline cracking (e.g. for leaked password vault
or encrypted GPG private key).

This is `<%= hash_speed * year_sec %>` password hashes calculated (for half of the search space) in `<%= years %>` years.

Password would need to have `<%= entropy(hash_speed * year_sec).round(1) %>` bits of cracking resistance.

# PBKDF2 iterations and cracking resistance

PBKDF2 is a method of deriving keys from passwords. The keys derived can be then used as key for encryption
algorithms (like AES) to decrypt encryption keys or data directly.

PBKDF2 iterations can make cracking harder by requiring multiple hash calculations per password checked.
This is equivalent of having that many times harder password to crack.

By "cracking resistance" I mean the entropy of the password in bits (length and character classes used) plus any
extra hashing iterations needed to actually verify if a password has matched the given hash.

So for example with 4 iteration a password that has entropy of 14 bits (2 arbitrary printable ASCII characters)
would have 16 bits of cracking resistance because the GPU would need to calculate 65536 (2^2*4) SHA1 hashes to
check all password combinations.

# Medium sized GPU cluster model

Assuming that attacker uses 200 GPU cards we can perform <%= hash_speed.round(1) %> giga SHA1 hashes per second.

* Ref: [GPU Accelerated Password Cracking in the Cloud: Speed and Cost-Effectiveness](https://systemoverlord.com/2021/06/05/gpu-accelerated-password-cracking-in-the-cloud.html)

# Salted hashed passwords (1 KDF iteration)

Assuming that password is salted with a random value (to defeat rainbow tables attack) and is hashed once.

## Maximum password length

Assuming 128 bit protection for password protected object (e.g. AES-128 symmetric key derived from password)
as having stronger password makes the key the easier target instead.

Passwords lengths that are required for different character classes to reach `128` bits of cracking resistance:

<%- pw_class.each { |c, n| -%>
  1. <%= c %>: `<%= Math.log(2**128, n).ceil %>`
<%- } -%>

## Minimum password length for strong GPU cracking resistance

To reach `<%= entropy(hash_speed * year_sec).round(1) %>` bits of cracking resistance:

<%- pw_class.each { |c, n| -%>
  <%- pw_len = Math.log(hash_speed * year_sec * 2, n).ceil -%>
  1. <%= c%>: `<%= pw_len %>` characters for `<%= entropy(n**pw_len).round(1) %>` bits of cracking resistance
<%- } -%>

# Passwords hashed multiple times (iterations > 1)

Iterations add computational cost for both the user and the attacker as multiple passes of hashing algorithms has to be run per password check.

* Adding characters to password makes them harder to remember but does not cost computation.
* Iterations add constant number of bits of cracking resistance to bits of entropy of the password making them harder to crack.

## Iterations needed to make password strong against GPU cracking

In order for password to reach required `<%= entropy(hash_speed * year_sec).round(1) %>` bits of cracking resistance
we may use KDF iterations to force the GPU to run more hash calculations per password guess tested.

<%- pw_class.each { |c, n|
  gpu_entropy = entropy(hash_speed * year_sec * 2)
  pw_len = Math.log(hash_speed * year_sec * 2, n).ceil -%>

### <%= c %>

1. `<%= pw_len %>` characters for `<%= entropy(n**pw_len).round(1) %>` bits of entropy is enough to have only `1` iteration
  <%- (pw_len - 1).downto(8).each { |pw_len|
    pw_entropy = entropy(n**pw_len)
    iter_entropy = gpu_entropy - pw_entropy -%>
1. `<%= pw_len %>` characters for `<%= pw_entropy.round(1) %>` bits of entropy, missing `<%= iter_entropy.round(1) %>` bits: `<%= 2**iter_entropy.ceil %>` iterations needed
<%-  } -%>
<%- } -%>

## GPG example

For GPG exported private key I get this information on my system:

```
iter+salt S2K, algo: 7, SHA1 protection, hash: 2, salt: D8AD57FB46799088
protect count: 65011712 (255)
```
<%- gpg_iter = 65011712 -%>

Looks like KDF hashing algorithm used is SHA1, password is salted and the iteration count for <%= gpg_iter %>.
According to documentation GPG agent will calculate the number iterations based on hashing speed of your machine
so that it takes about 100ms to run all iterations for single password.

<%- gpg_entropy = entropy(gpg_iter) -%>
This gives us `<%= gpg_entropy.round(1) %>` bits of extra cracking resistance as each passwords guess
has to be hashed `<%= gpg_iter %>` times before next one can be tried.

## Maximum password length

Passwords lengths that are required for different character classes to reach `128` bits of cracking resistance:

<%- pw_class.each { |c, n| -%>
  1. <%= c %>: `<%= Math.log(2**(128 - gpg_entropy), n).ceil %>`
<%- } -%>

## Minimum password length for strong GPU cracking resistance

To reach `<%= entropy(hash_speed * year_sec).round(1) %>` bits of cracking resistance:

<%- pw_class.each { |c, n|
  pw_len = Math.log(2**(entropy(hash_speed * year_sec * 2) - gpg_entropy), n).ceil -%>
  1. <%= c %>: `<%= pw_len %>` characters for `<%= entropy(n**pw_len).round(1) %>` bits of entropy for total `<%= (entropy(n**pw_len).round(1) + gpg_entropy).round(1) %>` bits of entropy
<%- } -%>

# Dictionary based passwords

Password based on language construct will have lower entropy than equivalent length and character class passwords
where each character is chosen at random independently. Crackers will use statistical techniques to generate
password candidates based on real life passwords used, dictionary word or phrases. It is hard to estimate entropy
of such passwords as there are many ways generate such candidates.

# Other KDF algorithms

Today there are much better ways to derive keys from passwords that make use of GPU (or custom ASIC) based cracking less practical.
These are based on hashing functions requiring relatively large amounts of RAM to run.

In any case if you can use algorithms like Argon2 over PBKDF2, please do so.

# Conclusion

* For GPG you need at least `9` character mixed case with numbers password.
* To be iteration safe (1 iteration) you need at least `14` characters mixed case with numbers password.
* Passwords stored in password manager should aim for `128` bits entropy and therefore should be `22` characters or longer mixed case with numbers passwords.
* When you need to type your password on a phone or TV often you could use `16` lower case and number characters.

Password lengths and KDF

Random password classes

Attacking passwords

Password length

Set of characters used

Password strength

PBKDF2 iterations and cracking resistance

Medium sized GPU cluster model

Salted hashed passwords (1 KDF iteration)

Maximum password length

Minimum password length for strong GPU cracking resistance

Passwords hashed multiple times (iterations > 1)

Iterations needed to make password strong against GPU cracking

Alpha (single case)

Alpha (single case) and numbers

Alpha mix of lower and upper case

Alpha mix of lower and upper case and numbers

All printable ASCII characters

GPG example

Maximum password length

Minimum password length for strong GPU cracking resistance

Dictionary based passwords

Other KDF algorithms

Conclusion

Appendix

Navigation