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:
26 characters to choose from or 4.7 bits of entropy per password character.36 characters to choose from or 5.2 bits of entropy per password character.52 characters to choose from or 5.7 bits of entropy per password character.62 characters to choose from or 6.0 bits of entropy per password character.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:
2825232219To reach 76.8 bits of cracking resistance:
17 characters for 79.9 bits of cracking resistance16 characters for 82.7 bits of cracking resistance14 characters for 79.8 bits of cracking resistance14 characters for 83.4 bits of cracking resistance12 characters for 84.0 bits of cracking resistanceIterations add computational cost for both the user and the attacker as multiple passes of hashing algorithms has to be run per password check.
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 iteration16 characters for 75.2 bits of entropy, missing 2.6 bits: 8 iterations needed15 characters for 70.5 bits of entropy, missing 7.3 bits: 256 iterations needed14 characters for 65.8 bits of entropy, missing 12.0 bits: 8192 iterations needed13 characters for 61.1 bits of entropy, missing 16.7 bits: 131072 iterations needed12 characters for 56.4 bits of entropy, missing 21.4 bits: 4194304 iterations needed11 characters for 51.7 bits of entropy, missing 26.1 bits: 134217728 iterations needed10 characters for 47.0 bits of entropy, missing 30.8 bits: 2147483648 iterations needed9 characters for 42.3 bits of entropy, missing 35.5 bits: 68719476736 iterations needed8 characters for 37.6 bits of entropy, missing 40.2 bits: 2199023255552 iterations needed16 characters for 82.7 bits of entropy is enough to have only 1 iteration15 characters for 77.5 bits of entropy, missing 0.3 bits: 2 iterations needed14 characters for 72.4 bits of entropy, missing 5.4 bits: 64 iterations needed13 characters for 67.2 bits of entropy, missing 10.6 bits: 2048 iterations needed12 characters for 62.0 bits of entropy, missing 15.8 bits: 65536 iterations needed11 characters for 56.9 bits of entropy, missing 21.0 bits: 2097152 iterations needed10 characters for 51.7 bits of entropy, missing 26.1 bits: 134217728 iterations needed9 characters for 46.5 bits of entropy, missing 31.3 bits: 4294967296 iterations needed8 characters for 41.4 bits of entropy, missing 36.5 bits: 137438953472 iterations needed14 characters for 79.8 bits of entropy is enough to have only 1 iteration13 characters for 74.1 bits of entropy, missing 3.7 bits: 16 iterations needed12 characters for 68.4 bits of entropy, missing 9.4 bits: 1024 iterations needed11 characters for 62.7 bits of entropy, missing 15.1 bits: 65536 iterations needed10 characters for 57.0 bits of entropy, missing 20.8 bits: 2097152 iterations needed9 characters for 51.3 bits of entropy, missing 26.5 bits: 134217728 iterations needed8 characters for 45.6 bits of entropy, missing 32.2 bits: 8589934592 iterations needed14 characters for 83.4 bits of entropy is enough to have only 1 iteration13 characters for 77.4 bits of entropy, missing 0.4 bits: 2 iterations needed12 characters for 71.5 bits of entropy, missing 6.4 bits: 128 iterations needed11 characters for 65.5 bits of entropy, missing 12.3 bits: 8192 iterations needed10 characters for 59.5 bits of entropy, missing 18.3 bits: 524288 iterations needed9 characters for 53.6 bits of entropy, missing 24.2 bits: 33554432 iterations needed8 characters for 47.6 bits of entropy, missing 30.2 bits: 2147483648 iterations needed12 characters for 84.0 bits of entropy is enough to have only 1 iteration11 characters for 77.0 bits of entropy, missing 0.8 bits: 2 iterations needed10 characters for 70.0 bits of entropy, missing 7.8 bits: 256 iterations needed9 characters for 63.0 bits of entropy, missing 14.8 bits: 32768 iterations needed8 characters for 56.0 bits of entropy, missing 21.8 bits: 4194304 iterations neededFor 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:
2220181815To reach 76.8 bits of cracking resistance:
12 characters for 56.4 bits of entropy for total 82.4 bits of entropy11 characters for 56.9 bits of entropy for total 82.9 bits of entropy10 characters for 57.0 bits of entropy for total 83.0 bits of entropy9 characters for 53.6 bits of entropy for total 79.6 bits of entropy8 characters for 56.0 bits of entropy for total 82.0 bits of entropyPassword 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.
9 character mixed case with numbers password.14 characters mixed case with numbers password.128 bits entropy and therefore should be 22 characters or longer mixed case with numbers passwords.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.