Password Durability

TL;DR: The computing power of computers is growing exponentially, and it has a huge impact on the strength of passwords. On the other hand, passwords with 192 bits of entropy are impossible to crack. Examples of such passwords could be 28b3043325104886db6e3c9f7c75f8b1712c1e422314225e (hexadecimal, 48 characters) and UAEOWtKlFdpMw5QzVBj5wrSEkh/BFueu (base64, 32 characters).

I recently gave a short presentation at our Friday “pöhinät” (internal tech sessions) about password strength.

What is a good enough password? And is the same password still secure ten or twenty years from now?

The recommended password length has grown over the years: at least six characters, then eight, ten, thirteen… Will this continue forever? What is the logic behind this?

What if a password had to last forever? Finding an answer to this question is fairly easy. But first, it’s good to figure out how to measure password strength.

The measure of password strength is its entropy. Slightly simplified, it tells you how many cracking attempts are required to guarantee the password is broken. For example, a password with 42 bits of entropy requires 2^42 cracking attempts to go through all combinations. A numeric-only password contains 3.322 bits of entropy per digit. A byte-based password contains 8 bits of entropy per byte. The assumption is that the password is randomly generated. The entropy of self-created passwords is significantly lower.

Bruce Schneier, in his book Applied Cryptography, investigated how much entropy a password should have to be theoretically impossible to crack. He quotes his book on his blog:

If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192.

Brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

Passwords with 192 bits of entropy are slightly impractical due to their length if they had to be remembered or typed at all.

What would be an appropriately secure amount of entropy for a password? For most of us, passwords that last less than 100 years against a persistent superpower’s continuous full-power attack are sufficient.

Edward Snowden stated in 2013 that the NSA has the capability to perform a trillion (10^12) cracking attempts per second.

We can compare this to the development pace of supercomputers and develop an algorithm based on this to calculate the required amount of entropy.

The development of computers is quite staggering. For comparison: the performance of the GeForce RTX 3090 graphics card released in September 2020 was 29.3 TFlop/s. Roughly the same amount of computing power (35.9 TFlop/s) was in the world’s fastest supercomputer in 2002. So what is the world’s fastest computer today will likely be within reach of consumers for a couple of thousand euros in 20 years.

In 2013, the world’s fastest supercomputer was capable of calculating 33.9 PFlop/s (33.9*10^15 flop/s). If you compare this to Snowden’s reported trillion cracking attempts per second, you could make a quick conclusion that one cracking attempt requires approx. 33,900 flops. But because we cannot be completely sure, I decided to use the flop/s development of the world’s fastest supercomputers as a measure, in an perhaps overly conservative estimate.

Calculation

Let’s dive in! If math and theory don’t tickle your fancy, feel free to jump straight down to the summary.

Let’s find the flop/s for the desired period.

• Extract the statistics of the fastest supercomputer from the source code of the page https://www.top500.org/statistics/perfdevel/.
• Convert the data to csv format (gflops.csv) such that the first column is unix epoch seconds and the second is GFlop/s.
• Perform a regression analysis so we can calculate how flop/s will develop.
• The equation is of the form y = a * b^x where x is time in unix epoch seconds and y is GFlop/s.
• When the equation is integrated integrate a*b^x dx from x=i to j, we get (a * (-b^i + b^j)) / log(b).
• Now we can calculate how many gigaflops accumulate over a period.

Regression analysis can be handled, for example, using R:

data <- read.csv("gflops.csv", header=FALSE)
x <- data[,1]
y <- data[,2]
model <- lm(log(y) ~ x)
a <- exp(unname(model$coefficients[1]))
b <- exp(unname(model$coefficients[2]))
sprintf("a = %s", a)
sprintf("b = %s", b)

Regression coefficients:

a = 6.80261320890583e-05
b = 1.00000001886219

For example, in 50 years, gigaflops accumulate as follows starting from 1994 and 2020:

i = 757382400 # 1994-01-01T00:00:00Z
j = 2335219200 # 2044-01-01T00:00:00Z
gflops = (a * (-b^i + b^j)) / log(b) = 4.859636690149365E22
i = 1577836800 # 2020-01-01T00:00:00Z
j = 3155760000 # 2070-01-01T00:00:00Z
gflops = (a * (-b^i + b^j)) / log(b) = 2.5601462397922633E29

If we assume that one flop corresponds to one cracking attempt, the amount of entropy required for a password to have a 50% probability of being cracked:

• convert gigaflops => flops
• take the log2 of the number to get the required number of bits to go through all combinations
• add 1 to reach 50% probability

For example:

log2(2.5601462397922633E29 * 1000000000) + 1 = 128.589493827428332
# or if we assume that one cracking attempt requires 33,900 flops:
log2(2.5601462397922633E29 * 1000000000 / 33900) + 1 = 112.540496174517264

Finally, we calculate the required password length:

L = ceil(H/(log2(N)))

Where L is the password length, H is the amount of entropy, N is the number of symbols, and ceil rounds up.

Some examples:

ceil(128.59/(log2(10)))   = 39 # digits
ceil(128.59/(log2(16)))   = 33 # hex
ceil(128.59/(log2(62)))   = 22 # alphanumeric
ceil(128.59/(log2(64)))   = 22 # base64
ceil(128.59/(log2(95)))   = 20 # printable ascii
ceil(128.59/(log2(256)))  = 17 # bytes
ceil(128.59/(log2(7776))) = 10 # diceware

Summary

We reviewed how password strength is determined using entropy, what the maximum required amount of entropy is, and how the development of computers will affect password durability. Next, we went through how password entropy is calculated for a desired period and how password length is calculated from entropy.

What should be the takeaway from all this? The computing power of computers evolves exponentially, and it has a huge impact on the strength of passwords. A password that might be secure with current recommendations may be quite insecure in 20 years.

But does a good password ultimately matter that much?

Algorithms may break over time, people may break, or be scammed, and there are many ways to obtain a password. The point is that passwords that are computationally unbreakable can still be broken as a result of human error.

Despite these, it’s always worth choosing a password that is strong enough for each purpose.

But before rushing to change all passwords, it’s better to consider if other practices are in order, such as password management.