7

Can anyone give me an idea? Assume the salt(s) is/are known.

For example, if I have a $k$-character long password that is hashed in MD5 versus bcrypt, is there a way to estimate how much more time it would take to brute-force in bcrypt versus MD5?

I know this is a vague question that depends on many factors, but feel free to assume whatever factors you want. Just looking to get an intuitive feel of the differences.

user49572
  • 71
  • 1
  • 1
  • 2

1 Answers1

18

Bcrypt use a configurable iteration count, so the answer to your question is: whatever you want it to be.

If the iteration count is such that one bcrypt invocation is as expensive as 10 computations of MD5, then brute-forcing the password will be 10 times more expensive with bcrypt than with MD5.

If the iteration count is such that one bcrypt invocation is as expensive as 10 millions of computations of MD5, then brute-forcing the password will be 10 million times more expensive with bcrypt than with MD5.

That's the point of having configurable slowness: you can make the function as slow as you wish. Or, more accurately, as slow as you can tolerate: indeed, a slow function is slow for everybody, attacker and defender alike.

An additional factor is that bcrypt is, by nature, quite hostile to GPU optimization; this is due to the kind of operations that are used within the algorithm. MD5 is, by comparison, very easy to implement and run efficiently on a GPU. This means that an attacker may get a substantial boost out of a GPU when cracking MD5-protected passwords; while with bcrypt he will need to use the same kind of CPU as the defender. See this answer for further details.

If we want some realistic figures: with a good GPU (off-the-shelf, a few hundreds of dollars), MD5 speed can reach, say, 10 billion instances per second (see benchmarks there; the machine which goes up to 93 billions per second contains 8 GPU). However, with bcrypt, it would be customary to crank up the iteration count so that each hashing takes 0.1s on your server. Instead of buying a GPU, the attacker will buy (or rent) a couple multi-core CPU and will be able to try, say, 100 passwords per second. With these figures, one can say that bcrypt will make the passwords 100 million times more robust than MD5.

Community
  • 1
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • What makes a hash better to crack with GPU versus CPU? – user49572 Jun 18 '14 at 19:58
  • For the response itself maybe I should use an example. Let's say my password is 6 characters long, random uppercase/lowercase/special character stuff. I hash it in MD5 on one hand, bcrypt in the other. How long would it take you to crack each? What about 7 characters? 8? 9? etc. (assuming a single CPU or a single GPU and typical/average cost settings for bcrypt). – user49572 Jun 18 '14 at 20:00
  • I ask this because in most practical settings, you'll always have people who have really weak passwords, so I am trying to get a sense for how weak the weakest link is. If I use bcrypt for a database of passwords, and someone takes the database, which passwords are (realistically) at risk? For example I imagine no one has cracked a bcrypt hash that was taken from a 15-character password, but can I say the same for 6 characters? – user49572 Jun 18 '14 at 20:08
  • 1
    Bcrypt is hostile to GPU because it uses data-dependent lookups in a 4 kB table (which is continuously updated throughout the algorithm). GPU strive on parallelism, but they cannot do parallel accesses to tables from all their core simultaneously, especially when the target addresses cannot be predicted in advance. – Thomas Pornin Jun 18 '14 at 20:47
  • 1
    @user49572 A password's length is not sufficient to keep it protected. A password must be unique / rare. The reason a lot of passwords are cracked is that hey are commonly used. There are lists (statistics) of the 10^8 most commonly used passwords. The attacker simply works to match the commonly used passwords to usernames. So if you are using a 12/15 character long password and it's not unique, it may already be in some database and will be matched and discovered . That is where the salt comes in. Salt forces the attacker to recompute the hashes of the common passwords. MD5 is too fast. – AturSams Sep 09 '15 at 15:09
  • If a password is sufficiently long and also more importantly, sufficiently rare/unique, it can be reasonably protected with bcrypt. – AturSams Sep 09 '15 at 15:10