5 ms·

I'm in the middle of researching re-evaluating rainbow table attacks in light of Moore's law, GPUs and Crack (lookup) tables, I've also looked into countermeasu

by iuguy 13y ago

I'm in the middle of researching re-evaluating rainbow table attacks in light of Moore's law, GPUs and Crack (lookup) tables, I've also looked into countermeasures. What you're describing is partially correct. When you crack passwords (either with rainbow tables or by brute force) you generate an iterator or use a dictionary and work through this generating hashes (with rainbow tables this works via a series (or chain) of what are called hash reduction functions instead of a plain iterator). You then compare the hash you've generated against all the hashes being subjected to the crack. Where there's a match, you win! If you're targeting a single hash and it's unsalted, rainbow tables will work as they're precomputed. It's inefficient, but it'll work. If you're using a salt, rainbow tables need to be pre-computed for the salt - I actually did this years back with a team for oracle 10g SYS and other default user passwords as the username was used as the salt. If you're targeting a single hash and it's salted then the iterative or dictionary approach will still work in roughly the same time as the salt is known. Separating the salt means you have to brute force it which is a PITA but generally because the way hashes tend to be stored (remember we're talking about a mechanism that shouldn't really be used anyway) the salt needs to be accessible by that system so you can dump the salt out regardless. Depending on where my current research goes it looks like some salting mechanisms may be feasibly pre-computable now beyond those that use predictable salts. GPUs allow you to create and traverse enormous chains in rainbow tables and while having to precompute per salt will be a PITA it looks like it is possible with sufficient storage and GPU power.

csense 13y ago
What if a site uses 128-bit salts generated by a good (perhaps hardware-based) RNG?
- mikegioia 13y ago
  That will remove pre-computed rainbow tables from the equation.
  - iuguy 13y ago
    Only really for the time being (and a considerable time to come, Quantum and Biological computing enhancements notwithstanding) but for a salt that big it makes far much more sense to use a key derivation function as you're effectively generating two keys otherwise (one user generated, the other - salt - via PRNG).
chiph 13y ago
If you're targeting a single hash I was going to mention this. If your user record has a column called "IsSuperuser", then an attacker is going to concentrate on those users, since the reward for cracking them is so much higher. Individual salts or not, with multi-GPU based brute-forcing, they won't stand long.
- iuguy 13y ago
  Indeed, the best resource I've found for adversely affecting brute-force password cracking comes from the *coin cryptocurrencies. GPUs allow us to generate much much longer chains in rainbow tables than before. This means that there's a re-evaluation of space trade-off based on chain length, so simple salting mechanisms (e.g. 4 char alphanumeric such as Cisco Type 5) become feasible. For now they're not incredibly practical for full mixalphanum 1-8 at 99.99% probability but it looks possible.
  - chiph 13y ago
    Since rainbow tables are now functionally obsolete, perhaps the best use of a salt is not to add randomness, but to enforce a minimum length. So if your salt is 40 chars, even if a user puts in a one-character-long password they're still at a length of 41 and will get some protection. Combine that with a skip + take algorithm (not just appending the salt and password together) where you interleave the salt and password, and you might have some improved defense.
    - Coincoin 13y ago
      Nope, a salt is public. Its only purpose is to force you to brute force one hash at a time. It might also protect you against some attacks particular to your hashing algorithm. It does not slow down the brute force itself. A lonely salted one letter password is as weak as an unsalted one.
      - chiph 13y ago
        Given that an attacker is going to focus on high-value accounts if they can, slowing down a brute force attack on a per-hashed-value basis is pretty much your only defense. Adding complexity (like you would when defending against a rainbow table attack) adds little value when defending against a GPU-based attack that can crank out a billion hashes a minute. So what you can do is add artificial length to the password + salt combination by using a very long salt. By necessity, you'd have to use a better hashing algorithm that will have a lower chance of an attacker getting lucky with a collision, and maybe is "slower" than other hash algorithms.

by iuguy 13y ago

csense 13y ago

What if a site uses 128-bit salts generated by a good (perhaps hardware-based) RNG?

mikegioia 13y ago
That will remove pre-computed rainbow tables from the equation.
- iuguy 13y ago
  Only really for the time being (and a considerable time to come, Quantum and Biological computing enhancements notwithstanding) but for a salt that big it makes far much more sense to use a key derivation function as you're effectively generating two keys otherwise (one user generated, the other - salt - via PRNG).

chiph 13y ago

If you're targeting a single hash I was going to mention this. If your user record has a column called "IsSuperuser", then an attacker is going to concentrate on those users, since the reward for cracking them is so much higher. Individual salts or not, with multi-GPU based brute-forcing, they won't stand long.

iuguy 13y ago
Indeed, the best resource I've found for adversely affecting brute-force password cracking comes from the *coin cryptocurrencies. GPUs allow us to generate much much longer chains in rainbow tables than before. This means that there's a re-evaluation of space trade-off based on chain length, so simple salting mechanisms (e.g. 4 char alphanumeric such as Cisco Type 5) become feasible. For now they're not incredibly practical for full mixalphanum 1-8 at 99.99% probability but it looks possible.
- chiph 13y ago
  Since rainbow tables are now functionally obsolete, perhaps the best use of a salt is not to add randomness, but to enforce a minimum length. So if your salt is 40 chars, even if a user puts in a one-character-long password they're still at a length of 41 and will get some protection. Combine that with a skip + take algorithm (not just appending the salt and password together) where you interleave the salt and password, and you might have some improved defense.
  - Coincoin 13y ago
    Nope, a salt is public. Its only purpose is to force you to brute force one hash at a time. It might also protect you against some attacks particular to your hashing algorithm. It does not slow down the brute force itself. A lonely salted one letter password is as weak as an unsalted one.
    - chiph 13y ago
      Given that an attacker is going to focus on high-value accounts if they can, slowing down a brute force attack on a per-hashed-value basis is pretty much your only defense. Adding complexity (like you would when defending against a rainbow table attack) adds little value when defending against a GPU-based attack that can crank out a billion hashes a minute. So what you can do is add artificial length to the password + salt combination by using a very long salt. By necessity, you'd have to use a better hashing algorithm that will have a lower chance of an attacker getting lucky with a collision, and maybe is "slower" than other hash algorithms.