0

Assuming I have a bcrypt sha1 hash, which I know it's salt, wouldn't it be possible to get one of those 13GB password list, hash every password with the known salt creating a custom rainbow table, and then compare?

I know bcrypt is a slow hashing algorithm so using a huge password list would take time, but would it be feasible if the list were shorter? (lets say, 100 password as an example.)

Thanks

  • 1
    As an aside, there's no such thing as "a bcrypt sha1 hash". Bcrypt and sha1 are separate hashing algorithms. – Xiong Chiamiov Feb 13 '17 at 19:28
  • 1
    I think you misunderstand the point of a rainbow table. A rainbow table allows you to reuse the results of hashing passwords across every hashed password in a corpus. When a unique per-entry salt is used, there can be no reuse, so creating a rainbow table makes no sense. You just hash every candidate password and compare against the target hash immediately; waiting until you've hashed every possible candidate before comparing is just a massive waste of time and resources. – Stephen Touset Feb 13 '17 at 19:51
  • What would stop you in one word: Time. E.g. your death long before the program finished. Sure, you could reduce the number of passwords to try, but it's difficult to talk about feasibility with 100 passwords, or 1000, or 10000, because the chance that one of your 100 passwords would match any single given hashed one would be close to 0. So yes, you could certainly try, but failure would be almost guaranteed (though I read somewhere that the 10000 most common passwords get you access to 98% of accounts - but I doubt that's true) – Pascal Feb 13 '17 at 21:17
3

Yes, it's possible. Don't need the rainbow table - that would only benefit you if you had multiple passwords using the same salt - since you can directly test the passwords.

Could take a while though - if you can calculate 1000 hashes per second, and you are using an alphabet of 64 characters (A-Z,a-z,0-9, plus a couple of symbols), looking for passwords of exactly 8 characters, the formula would be 64^8 (to get the number of passwords) divided by 1000, to get the number of seconds required. For that example, it's 281474976711 seconds. Or 8925ish years. Input your own hash checking speed to work out the actual time - it will vary based on your system.

  • I think this is not what I meant. Obviously, I could try every possible password (64^8) and that would take much time. I meant to try just with the most common passwords (like from a dictionary). Also assuming we had extra information, let's say, language, we could make the dictionary even smaller. How can I calculate the time it would take to hash all those passwords to create a rainbow table? – Pedro Javier Fernández Feb 13 '17 at 17:49
  • @PedroJavierFernández: if you can compute 1000 hashes per second and want to create a rainbow table with a fixed salt then you need 0.1 seconds obviously for 100 password, 10 seconds for 10.000 password etc. – Steffen Ullrich Feb 13 '17 at 18:03
  • As Steffen says, the formula is there - you can plug in whatever numbers you need. For the top 1000 passwords, it would take 1 second to generate them all. You asked for a formula for all passwords in your comment to the other answer. – Matthew Feb 13 '17 at 20:33
2

Yes. Since the hashing algorithm is also used for validating logins on the server, it can't be so slow as to make checking it computationally infeasible (like with brute-forcing a 4096-bit RSA key or something). But that's not the purpose of bcrypt.

As an attacker, you have cost-benefit analyses to run for any action you take. For instance, one way to get access to every user account on a site is to just buy the company. But the amount you'd have to pay for this is almost certainly more than you'd gain from the accounts (plus more than you can front).

You can crack those bcrypt hashes. But is the value you get from them worth more than the time and computer rental (or hardware and electricity) costs you pay to do so? Ideally, the site operator has tuned their cost factor so the answer is no.

1

Feasible is a matter of what time you think is reasonable. If you have the time, and if you can keep paying the electricity bill for your cracking machine, you can crack any password imaginable. Keep in mind that time could mean thousands of years, depending on the length of the password.

  • What would be the required time if the password were 7 or 8 characters long? Is there any formula to calculate requiered time? – Pedro Javier Fernández Feb 13 '17 at 17:22
  • That is going to depend on a number of factors. Hardware used to crack, password complexity. I'm not aware of any formula to compute this. Just remember that longer password = better. – user52472 Feb 13 '17 at 17:32
  • Assuming bcrypt was tuned to take 0.01s/attempt of attacker time on a custom ASIC, and the 8-character password is strictly alphanumeric (no symbols). There are just under 2^48 possible passwords, so on average you'll need 2^47 attempts to guess the average completely-random password. At 0.1s/attempt this would require nearly 70,000 processor-years. So you could do it in a year with 70,000 ASICs which would cost you well over $1mm in design and manufacturing costs alone. Keep in mind that these numbers are very hand-wavy, and should be considered a very rough estimate. – Stephen Touset Feb 13 '17 at 19:59

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.