Thursday, April 30, 2020

How strong should Master Password be?

KeyReel has a distinct difference from most password manager apps. While other password managers require to enter master password regularly, KeyReel needs a password only to recover database from a backup on the new phone. The problem of selecting a good recovery password is similar to the problem of choosing a master password though. It is because an encryption key for a backup file is derived from the recovery password.

The key difference between a master and recovery passwords is the usage pattern: since recovery password is entered only as often as you change the phone, we don't really need to optimize it for memorization or typing. Instead, you should write it down and store it in a safe box at your home or bank (or in 4th volume of the "War and Piece" where it will never be looked for :)

So how strong should a password be?

You can find tons of advice on the Internet, like "strong password has at least 12 characters", "at least one capital and one lower-case letter and digit", "must include special symbols !@#$" etc. You can find number of articles saying that 8-character password can be cracked in seconds. However, these calculations do not apply to master passwords! These articles usually refer to SHA-256 and SHA-512 hashing algorithms, that should never be used for master passwords.

The password should be so strong that it would be too expensive to crack it. Would you call a password strong if it would cost billion dollars to crack? The cost of cracking depends a lot on password hashing algorithm chosen.

Spoiler: our low-bound estimate is that to crack KeyReel backup file protected with 12-character randomly generated password which consists of capital letters and digits costs at least 2 trillion US dollars. This is enough for any use!

Digging into details

(Warning: article contains a fair amount of math :)

Length of the password and character set used define how many combinations a cracker would need to try to guess the password. For example, if possible character set includes 26 capital letters, 26 lower case letter and 10 digits, then the character set is 26+26+10=62 characters. The total number of possible combinations for 8-character password is 628=~2.18*1014 or over 218 trillion combinations.

We estimate the total cost of a potential brute-force attack by calculating the number of combinations and estimating dollar amount of a single combination attempt.

KeyReel uses Argon2 hashing algorithm with 6 iterations, 128 MB RAM and 2 parallel threads. It takes ~1 second to run on 2 CPUs of Pixel 2 phone. We have specifically used this phone as a baseline, since it is not too old, not too new. A second spent on password hashing during installation or recovery would not affect user experience.

By our estimates the cost of trying 1 billion combinations is ~$1,700 (see details at the end of the post). Trying 218 trillion combinations would cost 218,000*$1,700=$370,000,000 (or 370 million dollars). And to try all the combinations within 1 year a cracker would need to run on over 28,000 of most powerful AWS compute-optimized instances.

For a comparison, here is a reference table of estimated brute-force cost for various password parameters.

Character set Approx.
Est. Cost
1062 (a-z, A-Z, 0-9)1018220,000,000$1.4 trillions
962 (a-z, A-Z, 0-9)10163,500,000$23 billions
862 (a-z, A-Z, 0-9)101457,600$370 millions
892 (a-z, A-Z, 0-9, !@#$%...)10151,300,000$8 billions
1236 (A-Z, 0-9)10181,250,000,000$8 trillions
1036 (A-Z, 0-9)1015900,000$6 billions
1232 (A-Z without I and O, 2-9)1018300,000,000$2 trillions

For KeyReel Restore Key generator we chose the configuration with 12 characters and 32 combinations each. We decided to avoid ambiguous characters, like digit 0 and letter O, or digit 1 and letter I). Dividing generated sequence into 3 groups, like "3LDB-W4F9-3JHX" makes it easier to read, write or type. It is still too expensive to crack to worry about it in next few decades.

Does using special symbols help?

As you can see from the table above special symbols do not help much. Even if we use an additional set of 30 special symbols available on US layout keyboards, total number of combinations for 8-character passwords is still smaller than for 9-character password that does not include special symbols. The effort of typing special characters on mobile devices is just not worth it.

What about using words and phrases in passwords?

This is quite a large topic on its own and we will cover it in a separate post.

What about other password managers?

There is no single standard and various password managers use different algorithms with various parameters. Nowadays most used algorithms are PBKDF2, Scrypt and Argon2. PBKDF2 is oldest and also the cheapest one to crack due to availability of specialized hardware. Argon2 is a winner of Password Hashing Competition in 2015 and most recommended by the community. You can learn more about various algorithms in this article on Medium

Below is the list of various password mangers and algorithms used. To compare the speed of hashing we ran benchmarks for each algorithm on the same test machine. Slower the hashing, more costly it is to crack it.
  • KeyReel uses Argon2d with 6 iterations, 2 threads, 128MB RAM (~0.8s)
  • Dashlane uses Argon2d by default with 3 iterations, 2 threads, 32 MB RAM (~0.1s)
    • also supports PBKDF2-SHA2 with 200,000 iterations (0.01s)
  • LastPass uses PBKDF2-SHA256 with 100,100 iterations (0.005s)
  • 1Password uses PBKDF2-SHA256 with 100,000 iterations (0.005s)
  • KeePass uses AES-KDF with 60,000 iterations by default - (0.002s)
    • can be configured automatically based on 1-second performance test (needs ~25,000,000 iterations to be secure)
    • also supports Argon2 with configurable parameters. Defaults are 2 iterations, 2 threads, 1MB RAM (0.003s)
Note, that SHA256/AES are much faster/cheaper to run on GPUs or specialized ASIC hardware. Argon2 is resistant to GPUs, which makes it a better choice for hashing passwords.

Estimation of a brute-force attack cost 

As it is mentioned above, KeyReel uses Argon2 password hashing algorithm, which takes ~1 second  when executed on 2 CPU cores in parallel on Pixel 2 or iPhone 7. It would take a bit more on the older phones and a bit less on the last generation of the phones ( up to~30% faster). For the sake of our calculations we will lower the number to 0.4 seconds on a single CPU, to account for advances in hardware and software optimizations.

To estimate the cost, we use a public price of a most powerful compute-optimized instance in AWS called "c5.metal". This instance has 96 vCPU and 190 GB of RAM. And the lowest price you can get it without a special deal with Amazon is $13,000 per year (calculated based on 3-year contract full-upfront price, North Virginia region, Linux OS).

Since we chose 128 MB as a parameter for hashing algorithm, this instance has enough RAM to run 1,900 hashes in parallel. However, there are enough CPU cores to run only 96 hashes in parallel. With one hash taking 0.4 seconds, such host can calculate 96/0.4=240 combinations per second. This is equivalent of 240*60*60*24*365=~7,600,000,000 combinations per year. Therefore, we assume that cost of testing 1 billion combinations is $13,000/7.6=~$1,700

No comments:

Post a Comment