### Minimum Password Entropy

Categories: [ IT ]

What is the minimum entropy for my home computer's password?

In recent (post-2007) Debian (and probably other) Linux distributions, the
passwords are stored in `/etc/shadow`

using the `sha512crypt`

algorithm.
According to Per Thorsheim,
with 2012 hardware, a single Nvidia GTX 580 could make 11,400 attempts at
brute-force cracking such a password. This means that a
log_{2} 11,400 = 13.5 bit password could be cracked in 1 second.

To have a password that would resist a year to such a brute-force attack, one must multiply the password complexity by 86,400×365 (seconds per year) i.e., add 24.5 bits to the password for a total of 38 bits.

But this password is guaranteed to be cracked in a year. To make the probability of cracking such a password much lower, let's say less than 0.01, one must increase the password's complexity by a hundred times i.e., add 6.7 bits. We now have a minimum of 44.7 bits.

If one does not want to change the password for the next 10 years (because one is lazy), one must again increase the complexity tenfold (that's another 3.3 bits for a total of 48 bits) and account for the increase in processing power in the coming years. Between 2002 and 2011, CPU and GPU computing power has been multiplied by 10 and 100 respectively i.e., +0.37 and +0.74 bits/year. That means that the password's complexity must be increased by 0.74 ×10 = 7.4 bits. We have now reached 55.4 bits.

Now we need to guess who are the password crackers. How many such GPU will they put together? Titan has 18,688 GPUs (add another 14.2 bits to stay ahead of it), and the (more affordable) machine that cracked LinkedIn leaked passwords had 25 GPUs (requiring to add only extra 4.6 bits).

Assuming the crackers have a 25-GPU setup and not a gigantic cluster, 60 bits should be perfectly safe. If they are a government agency with huge resources and your data is worth spending the entirety of that cluster's energy for 10 years, 70 bits is still enough.

The same article also mentions an Intel i7, 6-core CPU would make 1,800 attempts per second i.e., 10.8 bits. For a password that must resist for 10 years, that would mean 49 bits. Titan has 300,000 CPU cores (50,000 times more than the i7), so that makes an extra 15.6 bits for a total of 64.6 bits. The Tianhe-2 has 3,120,000 cores, adding 19 bits to the original 49 bits, leading to 68 bits total.

In summary, 70 bits is enough. If you are lazy and not paranoid, 60 bits are still enough. If you think the crackers will not use more than 32 i7 CPUs for a month to try and break your password (adding 2.4 + 21.3 bits to the original 10.2 bits), 48.5 bits are still enough.