4

I often see people refer to arguments like: A (hashed) password will be cracked in 1.000 years if you use a normal desktop computer, but if you use 100.000 computers (botnet) it will be cracked in under 4 days. The "1.000 years" password seems fine, but the 4 days not. I think the "time" model is misleading.

Shouldn't we find a better model for how strong passwords are? We could estimate the cost in dollars?

What is a good metric for password security?

  • How are dollars better than time? If you would like a proper value you should use something like operations. But since most people already do not understand time why switch? I also believe this is based on a wrong assumption. namely that cracking a password scales perfectly horizontal. And that the "cracker" has both the password hash and the authentication mechanism used to check if he's correct. (or brute-force checks would flag him as a cracker) – LvB Mar 14 '16 at 14:48
  • 1
    Dollars would eleminate the number of computation nodes used. Hash cracking should scale in a good manner. If you use n nodes, every node could crack every nth combination. I refer only to offline cracking, online cracking scales bad. – honze Mar 14 '16 at 14:57
  • are you cracking the hash or finding a collision? (a.k.a. calculation a rainbow table) – LvB Mar 14 '16 at 15:03
  • I'm sure you'll like this: crypto.stackexchange.com/questions/1145/… – TTT Mar 14 '16 at 15:45
  • This is very nice. I look into it. Maybe this is a way! Thank you! – honze Mar 14 '16 at 16:16
4

The technical definition of password strength already exists in terms of bits of entropy. Essentially, it's the number of guesses required to arrive at a given password. A password that is 4 digits long has 10,000 possible values, so only 10,000 guesses or less would be required to guess it. These are expressed in powers of 2; 10,000 is approximately 2^14, so we would say it has 14 bits of entropy.

14 bits of entropy isn't a lot; a password that short can be brute forced in javascript in a browser in just a few moments. It's generally true that attacks up to 2^48 are easily achievable by a modern desktop computer; more if the attacker has customized hardware. In 2012 someone housed 25 graphics cards in a PC and was able to sustain 348 billion hash computations per second. For safety, we must assume the attackers get better over time as their hardware improves.

But computing hashes isn't the whole story. Beyond that, there are ways system owners improve security by using a better hashing algorithm, a better protocol such as PBDKF2 or bcrypt, applying salt, throttling guesses, custom hardware, etc. Rate limiting is very effective if you control the hardware: an iPhone passcode has only 2^14 bits of strength, but the custom chip built inside the machine will destroy its secret embedded encryption keys if the wrong passcode is entered 10 times.

On the other end of the scale, 2^80 bits of entropy are approaching the limits of imaginable attacks. It seems unlikely today that anyone could brute force crack an 80 bit password at home; it seems almost unthinkable that any entity ever could brute force crack a 128 bit key. The iPhone being studied by the FBI uses encryption keys that have 256 bits of entropy, and at this we know of no way to brute force those. Yet advances in mathematics and cryptographic research, and advances in hardware (such as quantum computing), have proven time and again that nothing should be declared uncrackable.

And defense is only half the picture. There are ways attackers can improve their attacks besides the custom parallelization mentioned above: they can use wordlists and tools like John the Ripper to prioritize guessing passwords based on the language of the user, rainbow tables are easily downloaded, collisions, malware, research on the target, zombies in a captive botnet, and other techniques can all reduce the search space. These all depend on the capabilities and dedication of your envisioned adversary.

Given that both offense and defense are not statically defined, each combination of implementation and threat model are specific, and are not really comparable to any other installation. That makes it hard to assign a fixed estimate of cost or time on a basis that is comparable between different password implementations. The most accurate things we can say are "this algorithm has x bits of strength", "this implementation multiplies attacker effort by 60,000", etc.

  • I think entropy is fitting most. Thank you for your great answer. – honze Mar 14 '16 at 21:19
3

Time and dollars are both very variable based on computer performance. In 1995, buying a computer which could perform as many MD5 hashing calculations as an average 2016 computer would have cost thousands. Even buying a device with the same power as a Raspberry Pi 3 would have cost thousands. Even nowadays, you can choose how to spend money to get the best return for your investment - some hashs will crack faster if you build a dedicated GPU based cracking rig, whereas others will work better if you scale out over multiple lower speed machines.

Similarly, it's easy to rent time on AWS or other cloud providers, which can provide vast amounts of computing power, but they don't have fixed costs. If you pay up-front for a load of server time, you'll pay a lot less than if you build up credit over a month and pay it off then. Which method should a calculation use?

For large scale calculations, it's sometimes better to forget about the real world implementation, and work on an abstraction. One that seems to work fairly well is assuming that every hash trial takes a fixed length of time (e.g. 1 per microsecond gives 1 million hashes tried in every second, 1 per nanosecond gives 1 billion hashes per second), then calculating the time it would take to cover the whole keyspace of the hash - for SHA-256, that is several times the age of the universe (doesn't matter which definition used - it's a big keyspace!). Don't forget that the average time will be less - this is the worst case scenario. This avoids the link to computer power, and scales as expected, while remaining independent of variable pricing or speed changes.

  • 1
    I would like to have a spreadsheet. Enter the complexity of the password, choose a hash and then it calculates the pricing for AWS, single computer, botnet, FPGA and the corresponding time it would take. Never seen this on the internet. – honze Mar 14 '16 at 15:33
  • 1
    Well, it would need constant updating, so seems unlikely to be worth creating, and, if you've entered the complexity of the password, so are expecting the average time to find it, you would have to take into account the order that hashes are tried. Most cracking tools try things like "Password1" well before "cni4ooeiH" - but they are equally as complex in pure character terms. – Matthew Mar 14 '16 at 15:39
2

I think your suggestion is an excellent one, and in fact has already been applied by real-world security researchers. The recent DROWN attack calculated it would only take $440 worth of Amazon EC2 time to perform the mathematical analsyis.

Mathew brings up an interesting question. How do we calculate the costs, since they're variable? Thankfully this has an easy answer, whatever is cheapest.

Costs generally go down with these sorts of attacks. This is also relevant to the situation, and should be factored in. 20 years ago the DROWN attack would have been far more costly. A rough estimate using Moore's law would suggest 20 years/18 months = 13 doublings, or 8,192*440=3.6 million dollars. (At the time well within the capabilities of the NSA, but outside the capabilities of most everyone else but the ultra-rich).

It also should be noted that exact figures are not required. Even a factor of 2 gives the general idea of costs. If the above attack cost $880 of EC2 time, would it really matter? Wrong is relative, and estimates only have to be accurate enough to convey the ballpark.

Most business people are already familiar with thinking in money, and it lends itself naturally to decision makers. If you tell them someone can break your security for $440, they'll listen.

  • 1
    Thank you for your answer. I would suggest to calculate a few options and then choose the minimum. Then you could say: An attacker needs 374226 of xyz to crack your password with a given complexity. – honze Mar 14 '16 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.