How exactly does a bcrypt hash prevent rainbow table lookup?

0
votes

I'm very close to understanding exactly how the compare function of bcrypt works, but there are a few missing holes in my knowledge.

My understanding so far:

brcypt gens a hashed password using a plain text password and a randomly generated salt. The hashed password is a combination of the bcrypt version, the hashed salt and the concatenated hashed plain text password. When a user logs in, their plain text password is ran through the compare function. At that point, bcrypt knows how many characters in the hash and from what offset to begin to slice the hashed salt out of the full hash. It then concatenates the salt with the passed in plain text password, running it through the hashing algorithm to arrive at the final hashed string. The hashed string is compared to the hashed string in the database and if there is an exact character match, the password is correct.

2 questions..

  1. Aren't hashes supposed to be impossible to reverse? If so, then how does bcrypt know how to decrypt the hashed salt and then use it to hash the incoming plain text password. That doesn't make any logical sense to me.

  2. If brcypts algorithm is written such that it can always create a hashed salt that it always knows how to decrypt, can't hackers just use that algorithm to grab every hashed password from a database and slice the salts out? Then it could create a rainbow table for every salt and crack each individual password? That seems logical to me.

Pardon if my question doesn't make any sense. Happy to edit.

Read articles, read stack overflow questions, watched videos and asked a senior engineer.

1
hashbcryptrainbowtable
check this – AAA
Also to answer you question 2, that's what a salt does: makes it computationally very expensive/infeasible to design a rainbow table: a hacker would have to create a separate rainbow table for each possible salt (remember that the salt space is quite large). A rainbow table works by precomputing hashes. This is fairly difficult work, to say the least, without a salt. Now, imagine having to do for each possible element of the salt space. Might put up a full answer later, if I have the time. – AAA

1 Answers

0
votes

A rainbow table is a pre-compiled list of every password you can find, and their hash.

Your rainbow table has:

  • hash("password1234")
  • hash("hunter2")
  • hash("correct horse battery staple")

But it doesn't have:

  • hash("ȃ@🙍♽😔ƅ😠☸☑+password1234")
  • hash("ȃ@🙍♽😔ƅ😠☸☑+hunter2")
  • hash("ȃ@🙍♽😔ƅ😠☸☑+correct horse battery staple")

You could go ahead and create a rainbow table that contains every password for this salt. But that's just called a Brute Force attack.

And this second rainbow table doesn't help you with the next website that chooses a different salt:

  • hash("®óó»♠☘☛🙈Ũh+password1234")
  • hash("®óó»♠☘☛🙈Ũh+hunter2")
  • hash("®óó»♠☘☛🙈Ũh+correct horse battery staple")

And to eliminate all the guesswork, and all the difficulty of storing a salt, and deciding a salt: modern password hashing algorithms generate a different random salt for every password for you, and store the salt in the resulting hash string for you:

  • hash("ȼŚ😑¥dĥ😥®µ+password1234")
  • hash("ČɆǝ%ËȌÁpmLȫ+hunter2")
  • hash("♼♄ș♰;⚁f)²ŋì😱³UÍ+correct horse battery staple")

Which is in essence what bcrypt does; it generates a different salt for every password.