5 ms·

Where do you store the individual salts, or the rules for creating the salts? Do you hash those too? It seems like they'd have to be sitting somewhere so that

Where do you store the individual salts, or the rules for creating the salts? Do you hash those too? It seems like they'd have to be sitting somewhere so that you could salt the input password before hashing to compare with the salted/hashed password in your database. If the salts are sitting in a database, and that database is compromised, aren't we sitting right back where we started with hashed passwords that may be subject to attack by rainbow tables? // question asked by an attorney who knows nothing about this subject but what he's read on HN.

ceejayoz 14y ago
That's why they recommend bcrypt. Generating a rainbow table for a sha1 salted string is very quick with the right hardware. Generating one for a bcrypt string is going to take ages, and improvements in computing power can be dealt with by increasing the work factor for the bcrypt hashed strings in one's database.
- tedunangst 14y ago
  Why in the world would anybody create a rainbow table for a salted string?
  - ceejayoz 14y ago
    The username it's attached to is "admin"? Plenty of situations where cracking the administrator's password via a custom rainbow table is potentially worth it.
    - andrewla 14y ago
      Rainbow tables are a very specific form of attack that allows you to do a single brute force attack against multiple accounts simultaneously. Against a single salted hash, you would not bother to generate a rainbow table; instead you would just stop once you found a match.
    - dllthomas 14y ago
      Sure, if you somehow get the salt but not the hash, and expect to get the hash in the future. Then, precomputing things makes sense while you wait. Otherwise, it's silly - building a rainbow table means 1) using a large amount of storage to store the results, and 2) waisting cycles organizing your data in that space to ensure efficient lookup. Doing this makes no sense if you already have the one hash you're going to check against - just do a regular brute-force attack.
- pwg 14y ago
  Bcrypt was not designed to counter rainbow tables. Although the internal salt does provide that defense. Bcrypt was designed to protect against raw brute force: See: http://static.usenix.org/events/usenix99/provos/provos_html/bcrypt.html http://static.usenix.org/events/usenix99/provos/provos_html/... > "At the time of deployment in 1976, crypt could hash fewer than 4 passwords per second. Since the only known way of inverting crypt is to guess preimages, the algorithm made passwords very difficult to recover from their hashes--so much so, in fact, that the designers of UNIX felt comfortable leaving the password file readable by all users. Today, over 20 years later, a fast workstation with heavily optimized software can perform over 200,000 crypt operations per second. Attackers can now expediently discover plaintext passwords by hashing entire dictionaries of common passwords and comparing the results to entries in a password file." > "While salted passwords defeat lookup tables, given a particular salt and hash, an adversary can still mount a brute force attack by evaluating F(s,t) on every possible password. It follows that the best security one can achieve is $\epsilon\approx 1/\vert F\vert$, where |F| is the cost in gates of implementing F. Usability requirements therefore effect a lower limit on $\epsilon$--if people can only tolerate a one second delay for checking passwords, F can take at most one second to evaluate. F should not take significantly less, however, as this would unnecessarily weaken security." > "The number of gates |A| that an adversary can reasonably muster for an attack increases constantly as hardware improves. Fortunately, so does the speed of machines that must legitimately evaluate F. That means passwords should not be hashed by a single function F with fixed computational cost, but rather by one of a family of functions with arbitrarily high cost. Instead of repeatedly throwing out functions like crypt and MD5 crypt to start over with more expensive but incompatible ones, systems should allow the cost of any password manipulation software to scale gracefully with a tunable parameter. Thus, $\epsilon$ can decrease as fast as hardware improves and users will tolerate. Compromised password databases will then enjoy maximum security against off-line attacks." The purpose of bcrypt was to allow for a single algorithm that can be tuned for existing speed of existing computers to produce a "slow" algorithm. Then, as Moore's law makes computers faster, bcrypt can be progressively slowed to keep pace, so that performing a brute force still takes an unreasonable amount of time.
  - ceejayoz 14y ago
    > Bcrypt was designed to protect against raw brute force Which is precisely what calculating a rainbow table involves.
jgrahamc 14y ago
The salts are just random strings. They can be stored with the hashed passwords. The security of the scheme does not depend on keeping salts secret. It depends on the strength of the hashing algorithm. Two things: 1. Rainbow tables are today an irrelevance because of the speed of computers. What you need to worry about is not precomputed tables, but the ability to compute hashes when needed. The point of the salt is to prevent you precomputing anything. 2. So, suppose you have a database where (hash, salt) has been compromised for each user. Assuming salt was chosen randomly for each user then attacking the database boils down to calculating the hashes for common passwords incorporating the salt. The security of that will depend on the security of the hash algorithm and its slowness.
- hcurtiss 14y ago
  I think I get it. Using a unique salt, they'd have to completely rebuild their entire rainbow table for each password (given a unique salt for each). Is that right? Even then, it seems like they might want to use a smaller dictionary, but rebuilding for each username would still be doable. Just slower. I totally get the slow algorithm part. Seems to me that's the trick. Our IT department is dead set against using password managers. I've been trying to learn why, given companies like lastpass use excessive salting/hashing and slow algorithms. Unfortunately, at this point, I fear my limited knowledge may actually surpass theirs. All I hear is grumbling about all my eggs being in one basket.
- finnw 14y ago
  #1 is not true. Algorithms like bcrypt rely on being so expensive to compute that brute-forcing is prohibitively expensive. bcrypt does use salt. If it did not then it would indeed be vulnerable to rainbow table attacks.

ceejayoz 14y ago

That's why they recommend bcrypt. Generating a rainbow table for a sha1 salted string is very quick with the right hardware. Generating one for a bcrypt string is going to take ages, and improvements in computing power can be dealt with by increasing the work factor for the bcrypt hashed strings in one's database.

tedunangst 14y ago
Why in the world would anybody create a rainbow table for a salted string?
- ceejayoz 14y ago
  The username it's attached to is "admin"? Plenty of situations where cracking the administrator's password via a custom rainbow table is potentially worth it.
  - andrewla 14y ago
    Rainbow tables are a very specific form of attack that allows you to do a single brute force attack against multiple accounts simultaneously. Against a single salted hash, you would not bother to generate a rainbow table; instead you would just stop once you found a match.
  - dllthomas 14y ago
    Sure, if you somehow get the salt but not the hash, and expect to get the hash in the future. Then, precomputing things makes sense while you wait. Otherwise, it's silly - building a rainbow table means 1) using a large amount of storage to store the results, and 2) waisting cycles organizing your data in that space to ensure efficient lookup. Doing this makes no sense if you already have the one hash you're going to check against - just do a regular brute-force attack.
pwg 14y ago
Bcrypt was not designed to counter rainbow tables. Although the internal salt does provide that defense. Bcrypt was designed to protect against raw brute force: See: http://static.usenix.org/events/usenix99/provos/provos_html/bcrypt.html http://static.usenix.org/events/usenix99/provos/provos_html/... > "At the time of deployment in 1976, crypt could hash fewer than 4 passwords per second. Since the only known way of inverting crypt is to guess preimages, the algorithm made passwords very difficult to recover from their hashes--so much so, in fact, that the designers of UNIX felt comfortable leaving the password file readable by all users. Today, over 20 years later, a fast workstation with heavily optimized software can perform over 200,000 crypt operations per second. Attackers can now expediently discover plaintext passwords by hashing entire dictionaries of common passwords and comparing the results to entries in a password file." > "While salted passwords defeat lookup tables, given a particular salt and hash, an adversary can still mount a brute force attack by evaluating F(s,t) on every possible password. It follows that the best security one can achieve is $\epsilon\approx 1/\vert F\vert$, where |F| is the cost in gates of implementing F. Usability requirements therefore effect a lower limit on $\epsilon$--if people can only tolerate a one second delay for checking passwords, F can take at most one second to evaluate. F should not take significantly less, however, as this would unnecessarily weaken security." > "The number of gates |A| that an adversary can reasonably muster for an attack increases constantly as hardware improves. Fortunately, so does the speed of machines that must legitimately evaluate F. That means passwords should not be hashed by a single function F with fixed computational cost, but rather by one of a family of functions with arbitrarily high cost. Instead of repeatedly throwing out functions like crypt and MD5 crypt to start over with more expensive but incompatible ones, systems should allow the cost of any password manipulation software to scale gracefully with a tunable parameter. Thus, $\epsilon$ can decrease as fast as hardware improves and users will tolerate. Compromised password databases will then enjoy maximum security against off-line attacks." The purpose of bcrypt was to allow for a single algorithm that can be tuned for existing speed of existing computers to produce a "slow" algorithm. Then, as Moore's law makes computers faster, bcrypt can be progressively slowed to keep pace, so that performing a brute force still takes an unreasonable amount of time.
- ceejayoz 14y ago
  > Bcrypt was designed to protect against raw brute force Which is precisely what calculating a rainbow table involves.

jgrahamc 14y ago

The salts are just random strings. They can be stored with the hashed passwords. The security of the scheme does not depend on keeping salts secret. It depends on the strength of the hashing algorithm. Two things: 1. Rainbow tables are today an irrelevance because of the speed of computers. What you need to worry about is not precomputed tables, but the ability to compute hashes when needed. The point of the salt is to prevent you precomputing anything. 2. So, suppose you have a database where (hash, salt) has been compromised for each user. Assuming salt was chosen randomly for each user then attacking the database boils down to calculating the hashes for common passwords incorporating the salt. The security of that will depend on the security of the hash algorithm and its slowness.

hcurtiss 14y ago
I think I get it. Using a unique salt, they'd have to completely rebuild their entire rainbow table for each password (given a unique salt for each). Is that right? Even then, it seems like they might want to use a smaller dictionary, but rebuilding for each username would still be doable. Just slower. I totally get the slow algorithm part. Seems to me that's the trick. Our IT department is dead set against using password managers. I've been trying to learn why, given companies like lastpass use excessive salting/hashing and slow algorithms. Unfortunately, at this point, I fear my limited knowledge may actually surpass theirs. All I hear is grumbling about all my eggs being in one basket.
finnw 14y ago
#1 is not true. Algorithms like bcrypt rely on being so expensive to compute that brute-forcing is prohibitively expensive. bcrypt does use salt. If it did not then it would indeed be vulnerable to rainbow table attacks.