Purpose And Scope Of This Post
When discussing password strength, money-to-crack calculations are far better than time-to-crack calculations. I propose a money-to-crack model that applies to dedicated password cracking rigs as well as cloud computing, and I make some calculations using recent (2020-Nov) data.
This blog post is focused on:
- Offline attacks (explained in Gentle Introduction)
- Computer-generated passwords, not human-generated passwords (more info in Background: Guesses-To-Crack)
The cracking costs tables are towards the bottom, feel free to check those out first if you want to see results, not methodology and commentary.
Gentle Introduction
When someone creates a password, sometimes they are concerned about how resistant the password is to being guessed by an attacker. For instance, a one-letter password for your bank account is probably unacceptably weak and a computer-generated 40-letter password is probably more than acceptably strong. These two example passwords are so extreme in weakness/strength, that we can make these judgments intuitively, but we will have to be more careful and systematic if we want to determine what sorts of passwords are acceptably strong and not excessively painful to type.
This blog post will focus on password strength in the context of offline
attacks, which is where an attacker has hacked some service, obtained hashes of passwords, and can very quickly check password guesses on their own machines. Offline attacks are a worst-case scenario for password strength, and it makes sense to have the worst-case decide what we consider acceptable password strength.
There are a few ways to think about how strong a password is: guesses-to-crack (GTC, basically entropy), time-to-crack (TTC), and money-to-crack (MTC). "Crack" simply means "correctly guess". Each way builds on the previous way. Discussions of password strength usually focus on GTC and TTC, and only rarely go into MTC. I think that MTC is far superior to TTC for most discussions about passwords, and I propose my own way of calculating MTC and plug in numbers for hardware available in 2020-Nov.
Interestingly, there's only a 15x-38x difference in costs between realistic upper bounds (AWS cloud computing) and unrealistic lower bounds (arbitrary number of GPUs with no overhead).
Background: Password Hashes
Feel free to skip this section if you know what a password hash is.
You can read Troy Hunt's password hash explanation.
An even shorter explanation and background:
- It is bad for services (ex: Facebook) to store your password. If someone is able to steal a service's user database, then they'd know the users' passwords. So, it is good practice for services to store password hashes (also called "hashed passwords").
- A hash function takes an input (like a password), and transforms it into a numerical output called a hash. A hash function cannot be "reversed"; there's no known way to take a hash and reverse it into the original input.
- If an attacker knows the hash of a password, the attacker can only figure out the password by making a password guess, hashing that guess, and comparing the guess's hash to the password's hash. If the two hashes are equal, then the attacker learns their guess was correct. If the two hashes are unequal, the attacker only learns his guess was incorrect; the attacker doesn't learn how close his guess was to the password.
- Some hash functions can be billions-or-more times slower than other hash functions. When an attacker is guessing passwords for stolen password hashes, the speed and cost of these guesses greatly depends on which hash function was used.
Background: Guesses-To-Crack (GTC)
The simplest and most foundational way to figure out a password's strength is how many guesses it would take an attacker to crack the password. For instance, a computer-generated 10-character password that uses only lowercase letters has 26^10 equal-probability possibilities, which is 1.4e14 in scientific notation. So, an attacker that knows they are dealing with a computer-generated 10-lowercase-letter password would have to make 1.4e14/2 = 7e13 guesses on average before cracking the password, and would have to make 1.4e14 guesses to guarantee cracking the password.
Remember there's a X% chance to crack a password while having covered only X% of the possibilities. Example: the attacker has a 1% chance to crack the password after 1.4e14*0.01 = 1.4e12 guesses.
Note: a human-generated password can not be evaluated so simply. If someone chooses their favorite sports team as their password (ex: "hurricanes"), an attacker will probably guess their password far sooner than 7e13 guesses, even though the password is 10 lowercase letters. This post will focus on computer-generated passwords that are uniformly chosen from the possibilities.
Background: Time-To-Crack (TTC)
A password that can take up to 1.4e14 guesses to crack might sound impressive. That's 140,000,000,000,000 or over a hundred trillion guesses. However, if the password was hashed with MD5, then a single NVIDIA RTX 3090 GPU ($1499 in the year 2020) can make and check 6.5e10 guesses per second, and will crack the password in 36 minutes or less. If the password was hashed using bcrypt with a cost factor of 10 (1024 rounds), then the GPU would take an average of ~753 years to crack such a password.
The usual TTC analysis is to assume a certain amount of password cracking hardware, and calculate how long it would take that hardware to crack that password. The natural and difficult question is "what is a reasonable amount of password cracking hardware that someone might use trying to crack this particular password?".
In my mind, the foremost type of attacker to worry about is organized crime groups, which crack passwords as a major business venture. I wouldn't be surprised if they had something like this Terahash rig ($204K, 60 GPUs, 2.3e12 MD5 hashes per second) or possibly much more guessing power, especially if they can effectively use botnets for password cracking.
Another notable type of attacker is governments. For instance, the NSA is very well funded, well staffed, and has an interest in cracking passwords far beyond their financial value. I recognize that governments/agencies can often do things to bypass the need for cracking passwords, but I think they find password cracking to be an often-useful tool. NSA's budget was estimated to be 10.8 billion dollars in 2013. I think it is reasonable to be worried about a scenario where NSA is willing to spend 5% of its annual budget on hardware that can be used for many things, including password cracking. Let's just say we're worried about hardware that can be purchased with 5% of their annual budget, or maybe 1% of 5 years of budget: $10.8e9*0.05 = $5.4e8 = $540 million. That's enough to buy 2647 of those 60-GPU Terahash rigs, meaning 6.1e15 MD5 hashes per second.
So, should TTC analysis include NSA-style attackers? Do organized crime groups have 60-GPU hardware or 600-GPU hardware at their disposal? The various plausible answers to these questions change TTC calculations by multiple orders of magnitude, which is not good.
Money-To-Crack (MTC) and Jacob's Model (JMTC1)
The MTC approach tries to estimate how much money it would take to crack the password. My particular model ("JMTC1"/"Jacob's MTC version 1") has several simplifications, but I think the model is still useful, especially for not overestimating password strength. My approach...
- JMTC1 tries to base calculations on the most cost-effective hardware, which is often recently-made GPUs.
- JMTC1 takes into account hardware lifetime. Currently MTC assumes hardware is 100% functional for the assumed lifetime, then needs to be replaced.
- JMTC1 takes into account both hardware-purchase costs and electricity costs. If a rig is used for 1 day, it makes sense to account for the electricity costs and that the rig is 1 day closer to needing to be replaced.
- JMTC1 assumes a single price for a kWh of electricity and a single purchase price for hardware.
- JMTC1 does not try to estimate labor costs.
- JMTC1's provides a crack cost for the average case (crack after trying 50% of possibilities) because average cost is what attackers would use for their cost-benefit analysis.
JMTC1 example for MD5-hashed passwords:
- Assume attacker is using some number of Terahash Inmanis rigs.
- $32K to purchase.
- 4e11 MD5-hash/s.
- 3.6 kW.
- Assume lifetime of 7 years.
- Assume $0.1/kWh.
- Calculate number of hashes and amount of electricity over the rig's lifetime
- 4e11 hash/s * (60*60*24*365.24) s/yr * 7 yr = 8.8e19 hashes
- 3.6 kW * (60*24*365.24) * 7 = 2.2e5 kWh
- Calculate lifetime costs...
- 2.2e5 kWh * $0.1/kWh = $22K of electricity
- $22K of electricity + $32K of hardware = $54K total cost over lifetime
- Final result is 8.8e19 hashes / $54K = 1.6e15 hashes/$
- Average costs to crack various types of passwords...
- 10 lowercase letters: 26^10 / 1.6e15 / 2 = $0.044 = ~4 cents
- 12 chars, unambiguous alphanumeric: (24+24+8)^12 / 1.6e15 / 2 = $297K
- Reminder: this is for computer-generated passwords selected uniformly from the space of possible passwords, not human-generated passwords.
If you want some combined equations...
GuessesPerDollar = 3.2e7*LifetimeYears*HashesPerSecond / (HardwarePurchaseDollars + 8.8e3*LifetimeYears*kilowatts*DollarsPerKilowattHour);
AvgDollarsToCrack = PasswordPossibilities / GuessesPerDollar / 2;
Also, it is easy to adapt the calculations to a different hash function, like bcrypt with default cost factor of 5. The Terahash Inmanis can do 2.5e5 of those hashes per second, which is 4e11/2.5e5 = 1.6e6 times slower than MD5. So a 10-lowercase-letter password hashed with default bcrypt would cost $0.044*1.6e6 = $70.6K.
Money-To-Crack (MTC) Vs Time-To-Crack (TTC)
I think MTC has some advantages over TTC, and these advantages are not specific to JMTC1:
- TTC requires an assumption/input of how much hardware various attackers going to use against you. How are you going to come up with a reasonable hardware quantity without resorting to money-based calculations anyway, especially with cloud computing? MTC makes the robust assumption that the attacker will bear a cost for the hardware used against you and sidesteps the entire question of attacker's amount of hardware or who the attacker even is.
- Attackers are constrained by money more than time, and thus their actions are better predicted by focusing on money. If the Russian mafia thinks that cracking your bank password is worth $100K to them, then they will not spend more than $100K to do it, regardless of whether it takes 1 day with a lot of hardware or 1 month with less hardware. Even though it's harder to estimate how much governments value cracking your password, governments will still weigh that value against the cost.
- MTC puts password strength in terms that make it easier to decide what types of password are "strong enough". Am I comfortable with a 100-year password (for a Terahash Inmanis) for my bank account? That question doesn't have good enough info to allow a good answer. Am I comfortable with a $771K password (for any amount of today's hardware) for my bank account? For a bank account that has less than $20K in it, that seems tolerable for now.
JMTC1 Caveats
JMTC1 has a few ways that it underestimates cost to crack a password, and thus underestimates password strength:
- JMTC1 doesn't try to model labor costs. Hardware requires labor for installation, maintenance, and operation. I'm okay with the model being best suited for attackers that are operating at such scale that hardware and electricity costs are far larger than labor costs.
- JMTC1 doesn't help you to model scaling costs. You can input costs and specs from Terahash rigs, which takes into account some of the cost of scaling up GPUs, but you could also input specs of a single GPU, completely ignoring the fact a password cracking rig is not just a GPU; you need power, CPU, RAM, networking, and so on. At some point, you also need to worry about these rigs at the room and building level.
- If you use AWS capabilities and prices (like g4dn.metal, see first table below), you've taken into account scaling costs and gotten rid of most of labor costs, but AWS is expensive and a notable attacker can probably be more cost effective with dedicated hardware.
- JMTC1 does not attempt to model increasing or decreasing prices as you buy more of something; I believe increasing prices to be more common than decreasing prices. It's possible to get bulk discounts, and it's very likely that after you buy all the RTX 30808 GPUs you can find for $699, you have to start buying them at higher prices.
- JMTC1 is for offline attacks only.
- JMTC1 tries to tell you cracking cost using today's hardware, not tomorrow's hardware. The trend of computing cost (it halves every 2 years, "Moore's Law") means that a password that takes $1M to crack today might only take $1K after waiting 20 years.
- I propose JMTC2, a simple extension of JMTC1 that predicts that cracking costs halve every 2 years, forever.
- Similarly, it's up to you to find and input the most cost effective hardware, which changes over time. JMTC2 is a partial solution to this; find the best hardware today, and extrapolate an exponential rise in hash/$.
JMTC2, Assume Cracking Costs Halve Every Two Years
JMTC1 gives you a GuessesPerDollar for the present. To predict a GuessesPerDollar for the future, it is reasonable to go with Moore's Law (the longstanding trend of computing cost halving every two years).
Formula that lets you choose your own YearsToHalveComputingCost:
GuessesPerDollarInFuture = GuessesPerDollarNow * 2^(YearsFromNow / YearsToHalveComputingCost)
The future of computing costs is highly uncertain. JMTC2 might yield a decent prediction for 2 years from now, but would yield an absurd prediction for 1000 years from now. As of writing this in 2020, I am extra hesitant to use JMTC2 for anything beyond the year 2035.
Robin Hanson's Age Of Em (chapter 6, Entropy section) estimates that at around the year 2035, further decreases in computing costs will require a shift to reversible computing, and that the time to halve computing costs may double. So, that prediction seems like a good reason to say "let's not forecast current computing cost trends beyond 2035".
An implication of the JMTC2 model is that after 15 years, a password
becomes ~181 times cheaper to crack. A $1M password in 2020 becomes a
$5.5K password in 2035. This implication motivates me to put further
safety margins on how strong to make my passwords. Right now I'm using a 32x
margin to handle cracking costs 10 years from now. I figure I can re-evaluate and possibly change my passwords any time along the way.
For almost all of my passwords, I use a password manager to automate generation and inputting of passwords, so most of the time, extra password length doesn't impact me. Very rarely, I will have to manually type a password, possibly on a smart phone, and I don't want that to be more painful than necessary. So, I'm not going to make 30-character passwords with mixed case, digits, and special characters. Looking at the cracking cost tables, a 15-alphanum password will plausibly cost at least $330M to crack in 2030 (and an acceptable $59M in 2035). 15-alphanum password seems good for passwords I don't have to remember and rarely have to type.
I have written an article on password creation suggestions.
Cracking Cost Tables (Originally Made In 2020-Nov)
There's a Google Sheet of mine that has various password calculations, including these password cracking cost calculations.
Here's an overall table that gives you hash/$ for various hardwares and hash functions:
I have more AWS instance types in my Google Sheet; g4dn.metal was the most cracking-cost-effective AWS EC2 instance type I could find. Under the assumptions of this model (ignoring labor and scaling costs), Terahash Inmanis is 5-8x as cost effective as g4dn.metal, and a bunch of purely hypothetical zero-overhead RTX 3080 GPUs are 15-38x as cost effective as g4dn.metal.
(Cloud-GPU-service vast.ai seems ~5x as cost effective as AWS g4dn.metal, but I'm not confident in how I interpreted their website, and I'm worried that renting a decent number of GPUs would quickly face increasing prices. Thus, I'm not going to focus on vast.ai for cloud stuff.)
JMTC1 hash/$ calcs for cloud stuff is a pretty realistic upper bound for money-to-crack. JMTC1 hash/$ calcs for zero-overhead RTX 3080 GPUs is a fairly unrealistic lower bound for money-to-crack. I think it's interesting that the difference between them is only a factor of 15 for some hash functions. A factor of 15 doesn't seem so big when adding an alphanum character to your computer-generated password increases strength by a factor of 62.
Terahash Inmanis Rig, 7yr Lifetime, $0.1/kWh
This table is for the Terahash Inmanis rig, and you see its specs from the JMTC1 example above and this Terahash page.
Each cell of the table below estimates average cracking cost for a computer-generated alphanumeric password for the combination of given length (row) and hash function (column). Remember that attackers have an X% chance to crack a password after trying X% of possibilities. A "$1B password" has a 50% chance of being cracked for $1B or less, a 5% chance of being cracked for $100M or less, etc.
NVIDIA RTX 3090 GPU, No Overhead, 7yr Lifetime, $0.1/kWh
The following table is for the NVIDIA RTX 3090 GPU, with these specs:
- Hashing performance is from this hashcat benchmark published by Chick3nman.
- $1499 purchase cost (as of 2020-Nov)
- 0.35 kW power consumption
This table is a bit silly in that it models the GPU and the GPU only, ignoring the necessity of actually needing to put the GPUs in a computer, which has hardware and electricity costs. If we assume that the NVIDIA RTX 3090 GPU is (currently) the most cost-effective GPU for password cracking, then this gives us a pretty safe lower-bound on cracking costs. Silly but useful.
NVIDIA RTX 4090 GPU, No Overhead, 7yr Lifetime, $0.1/kWh
The following table is for the NVIDIA RTX 4090 GPU, with these specs:
- Hashing performance is from this hashcat benchmark published by Chick3nman.
- $1600 purchase cost (as of 2022-Oct)
- 0.45 kW power consumption
TODO
Add increasingly cost-effective GPUs, dedicated rigs, and cloud stuff as I become aware of them. Suggestions by readers welcome.
You mentioned botnets in the intro. With that, the attacker would not need to aquire hw nor pay for runtime. I suppose each bot has a cost, but if not easily estimated the MTC is much less useful.
ReplyDeleteNevertheless, nice writeup and a reality check on what dedicated crackers can do.
JMTC1 definitely loses some accuracy/applicability for botnets. I'm not sure how effective botnets are for password cracking and thus not sure how much botnets are actually used for password cracking. Perhaps with botnets, time-to-crack is more useful than usual, though your calculations would still be at the mercy of whatever you estimate for the password-cracking power of the botnet. Botnets still have costs and if I understood the structure of those costs, I think a money-to-crack model other than JMTC1 would be better than time-to-crack.
Delete