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

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.

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:

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.

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.

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 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.

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

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

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`

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

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.

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.

`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

`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

`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

`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

`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

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.

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`

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

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.

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.

- 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.

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.