I recently had a conversion about how secure a 16-character password really is against a highly-financed attacker (e.g. the NSA). Getting a realistic answer turns out to be more complicated than just dividing passwords by tries/second. Let’s work through some ideas:
First, the choice of alphabet. People often assume that passwords are made of uppercase letters, lowercase letters, digits, and “special characters” from some list. This can certainly increase the password space for the same length of password (2616 is about 4.4×1022, while 9416 is about 3.7×1031), but it’s not necessarily a realistic expectation for the types of passwords people actually use. I’ll do the calculations with a few different choices and see how they come out.
Next, the choice of hashing algorithm makes a huge difference. For this post, I’ll assume we use scrypt, since that’s common and well-regarded.
All attackers, even the NSA, have a budget. Let’s suppose the NSA has a budget of $10 billion per year, and they’re willing to dedicate 1% of that to a machine to crack one password. Honestly, if your password is worth $100 million, they probably have other ways to get it, but let’s suppose they don’t.
Within that budget, they can only buy a certain amount of hardware. We’ll assume that they’ll buy the fastest thing available. As of March 2016, it looks like there’s a custom ASIC that will crack scrypt at ~150MH/s (that’s million hashes per second) using 250W of power. Prices haven’t been announced, but let’s assume they go for around $1000, since that’s what the previous model seemed to cost.
You also need electricity to run these ASICs. Electricity in New Mexico costs around $.08/kWh for large customers. Assuming these run around the clock, each one will cost 0.25kW * 24 h/day * 365 days/year * $.08/kWh = $175 in electricity for the first year. Other states will be higher or a little lower.
These chips also have to be cooled. Using a couple of conversion factors from watts to tons and an estimate of 13 EER, I’m assuming each one will need about 0.06kW of cooling. Since the cooling might only run half the time, let’s guess 0.06kW * 12 h/day * 365 days/year * $.08/kWh = $21 in cooling costs.
Adding that all up, the total cost of purchasing, operating, and cooling each ASIC for a year would be around $1200. If we assume the rest of the wiring, building, HVAC installation, etc. cost nothing, the NSA could use their $100 million to build a cluster of 83k such ASICs. If the work can be perfectly divided between them, this gives around 12.4TH/s (that’s trillion hashes/s).
So the NSA could build a cluster that cracked 12.4TH/s for a year for their $100 million. We know the NSA is full of smart people, so they may actually have an even faster ASIC. Let’s assume they’re twice as good as the unclassified stuff and round up to 25TH/s.
Putting this all together, we have 2616 passwords / 2.5×1013 tries/sec = 1.7×1010 seconds, or 56 years for a 16-character password using just lowercase letters. Since life expectancy in the US is around 78 years, that’s probably good enough to last the rest of your life if you’re at least 25-30 years old today. Protecting your personal data for longer than that has questionable value.
But wait! That was just the first year’s budget. The NSA can buy a whole new cluster each year. If these ASICs keep pace with Moore’s law, they’ll be about 1.4x faster than the previous year’s chips (to double in speed every two years). After the first year, the computer would have cracked r hashes, where r is the rate per second from above times the number of seconds in a year. After a second year, it would have cracked r + r*1.4. After the third year, r + r*1.4 + r*1.42. This continues until the sum is at least as large as the number of possible passwords. There should be an analytical solution to this, but it’s pretty easy to simulate with a quick Haskell program:
import Text.Printf -- Number of hashes cracked after n years. hashes_cracked :: Integer -> Double -> Integer -> Integer hashes_cracked rate increase years = floor $ sum $ map (\x -> fromIntegral rate * increase^x) [0..(years-1)] -- Sequence of annual hashes cracked. crack_sequence :: Integer -> Double -> [Integer] crack_sequence rate increase = map (hashes_cracked rate increase) [1..] -- Number of years to track a set of hashes. years_to_crack :: Integer -> Integer -> Double -> [Integer] years_to_crack hashes rate increase = takeWhileInclusive (< hashes) (crack_sequence rate increase) -- Same as takeWhile plus the sentinel value. takeWhileInclusive :: (a -> Bool) -> [a] -> [a] takeWhileInclusive p l = let (h, t) = span p l in h ++ [(head t)] -- Converts an annual hash cracked number into a string. printYear :: Integer -> (Int, Integer) -> String printYear t (y, h) = printf "After %d years, %d/%d (%0.2f%%) done." y h t (fromIntegral h * 100.0 / fromIntegral t :: Double) main = let alphabet = 26 length = 16 initial_rate = 25 * 10^12 annual_increase = 1.4 secs_per_day = 86400 annual_rate = floor $ initial_rate * secs_per_day * 365.25 num_hashes = alphabet ^ length crack_sequence = years_to_crack num_hashes annual_rate annual_increase in putStr $ unlines $ map (printYear num_hashes) (zip [1..] crack_sequence)
This produces output like this:
After 1 years, 788940000000000000000/43608742899428874059776 (1.81%) done. After 2 years, 1893456000000000000000/43608742899428874059776 (4.34%) done. After 3 years, 3439778399999999606784/43608742899428874059776 (7.89%) done. After 4 years, 5604629759999998951424/43608742899428874059776 (12.85%) done. After 5 years, 8635421663999998033920/43608742899428874059776 (19.80%) done. After 6 years, 12878530329599996329984/43608742899428874059776 (29.53%) done. After 7 years, 18818882461439992266752/43608742899428874059776 (43.15%) done. After 8 years, 27135375446015989514240/43608742899428874059776 (62.22%) done. After 9 years, 38778465624422382305280/43608742899428874059776 (88.92%) done. After 10 years, 55078791874191332212736/43608742899428874059776 (126.30%) done.
So you should worry about your 16-character all-lowercase password getting cracked if:
- It’s worth at least $1 billion to the NSA ($100 million per year).
- They’re willing to wait 10 years to get into that data.
- Custom ASICs to crack scrypt actually double in speed every two years.
- Your data being protected is still worth something in 10 years.
Most of us probably don’t need to worry. For even more years, you can add additional types of characters:
- 26 lowercase letters: 10 years
- 26 lowercase letters + 10 digits: 25 years
- 26 lowercase letters + 26 uppercase letters + 10 digits: 51 years
- All 94 characters on a standard US keyboard: 71 years
That’s the extreme case. But what about more realistic attackers? Suppose the attacker has a cluster of 20,000 of these ASICs (plausible for a large corporation or a more realistic government).
- 26 lowercase letters: 16 years
- 26 lowercase letters + 10 digits: 31 years
- 26 lowercase letters + 26 uppercase letters + 10 digits: 57 years
- All 94 characters on a standard US keyboard: 77 years
Or 1,000 ASICs (plausible for a mid-size corporation or organized crime)?
- 26 lowercase letters: 25 years
- 26 lowercase letters + 10 digits: 40 years
- 26 lowercase letters + 26 uppercase letters + 10 digits: 66 years
- All 94 characters on a standard US keyboard: 86 years
Or 10 ASICs (some skript kiddie who downloaded a password dump from the internet)?
- 26 lowercase letters: 39 years
- 26 lowercase letters + 10 digits: 54 years
- 26 lowercase letters + 26 uppercase letters + 10 digits: 80 years
- All 94 characters on a standard US keyboard: 100 years
So there you have it. Depending on who you think a realistic attacker is and how old you are, you can pick an alphabet that makes you comfortable with a 16-character password. Of course, if you’re at the lower end of the security concern spectrum, you can also choose a slightly shorter password with a larger alphabet to get similar security.