4 ms·

> A rainbow table approach is easily defeated by length. Only somewhat true. This XKCD is absolutely wrong - https://xkcd.com/936/ https://xkcd.com/936/ 10 b

> A rainbow table approach is easily defeated by length. Only somewhat true. This XKCD is absolutely wrong - https://xkcd.com/936/ https://xkcd.com/936/ 10 billion MD5s a second should be easy. So the XKCD pass phrase goes from 550 years -> to one hour, on a normal GPU, for one person. Rainbow tables mean after that one hour on their gaming PC no one else has to do it. Start adding in other requirements to the pass phrase the hour goes up, and perhaps you have to rent some cloud time, but only one person once has to do it once. But, if you assume it's likely other sites use seeds, then rainbow tables are out, and length can matter again. And that's reasonable. You need to wreck as many points in the attackers chain as possible. That's the game.

thaumasiotes 5y ago
> But, if you assume it's likely other sites use seeds, then rainbow tables are out, and length can matter again. I'm not sure what you're saying here. If by seeds you mean "salts", they're not relevant -- the whole point of a rainbow table is that you precalculate the hash of every possible password. If it's salted, you'll see the salt in the plaintext and just remove it. But a rainbow table for long passwords will develop pretty extreme storage requirements, and take a long time to compute.
- aaron695 5y ago
  > If by seeds you mean "salts" Yep > If it's salted, you'll see the salt in the plaintext and just remove it. No. You can't use rainbow tables on salted data. Maybe when a framework has a default common salt that people forget to change. > rainbow table for long passwords will develop pretty extreme storage requirements, Not really, that's the point of rainbow tables. They can be reasonable, they are not lookup tables. If you are looking at large ones, they can be compacted at the expense of time. For "CorrectHorseBatteryStaple" the rainbow table will not contain "sdfgnWlgiuwreFrglrkemnmZflgh". You map the chain to your search space. So after CorrectHorseBatteryStaple might be SimpleFineChairBook or S1mpleFineChairB00k or SimpleFine@ChairBook depending on your space.
  - thaumasiotes 5y ago
    > No. You can't use rainbow tables on salted data. There's something about this that you're failing to understand, but I'm not sure what it is. A rainbow table is a collection of key-value pairs. The key is a hash, and the value is input that produces that hash. Suppose my password on a website is "password". The MD5 hash associated with that password is 5f4dcc3b5aa765d61d8327deb882cf99 . If you dump the user database and see this: +--------------+----------------------------------+ | user | password | +--------------+----------------------------------+ | thaumasiotes | 5f4dcc3b5aa765d61d8327deb882cf99 | +--------------+----------------------------------+ You can look up that hashed value by any number of means (it's well known) and learn that the plaintext input to the hash was "password". If you salt the password, nothing changes. When you dump the database, you'll see this instead: +--------------+----------------------------------+-------+ | user | password | salt | +--------------+----------------------------------+-------+ | thaumasiotes | 9caa7f6693553ed9129bb0c7a0c8aa50 | bEanx | +--------------+----------------------------------+-------+ Then, when you reverse the hash, you'll learn that the plaintext input was "passwordbEanx". You also know that the suffix "bEanx" is the salt, so you can log in as me using the password "password", which is "passwordbEanx" with the salt removed. A rainbow table can tell you that 9caa7f6693553ed9129bb0c7a0c8aa50 came from "passwordbEanx" just as easily as it can tell you that 5f4dcc3b5aa765d61d8327deb882cf99 came from "password". That's what rainbow tables do. > they are not lookup tables This is flat wrong; that's exactly what a rainbow table is. > For "CorrectHorseBatteryStaple" the rainbow table will not contain "sdfgnWlgiuwreFrglrkemnmZflgh". You map the chain to your search space. This is a possibility, but it's also an admission that making a rainbow table at the desired length is infeasible. You trim the space of passwords you can look up down to something that you hope contains your target's password. Now you don't have a rainbow table up to 30 characters, you have a rainbow table for a list of common passwords. But once you've done that, you are vulnerable to password security policies. You can no longer crack uncommon passwords, and uncommon passwords are the problem rainbow tables are meant to solve. Common passwords you can often just guess.
    - aaron695 5y ago
      Salts might be 100 characters in length. It could be a book. It could be a jpeg. Examples - https://api.wordpress.org/secret-key/1.1/salt/ https://api.wordpress.org/secret-key/1.1/salt/ No rainbow table will contain those. bEanx actually works pretty as a fine salt, it wrecks Rainbow tables. But just like comments people understand salts more if they look complicated. Check out this https://rsheasby.medium.com/rainbow-tables-probably-arent-what-you-think-30f8a61ba6a5 https://rsheasby.medium.com/rainbow-tables-probably-arent-wh... It explains Rainbow Tables != Lookup Tables

thaumasiotes 5y ago

> But, if you assume it's likely other sites use seeds, then rainbow tables are out, and length can matter again. I'm not sure what you're saying here. If by seeds you mean "salts", they're not relevant -- the whole point of a rainbow table is that you precalculate the hash of every possible password. If it's salted, you'll see the salt in the plaintext and just remove it. But a rainbow table for long passwords will develop pretty extreme storage requirements, and take a long time to compute.

aaron695 5y ago
> If by seeds you mean "salts" Yep > If it's salted, you'll see the salt in the plaintext and just remove it. No. You can't use rainbow tables on salted data. Maybe when a framework has a default common salt that people forget to change. > rainbow table for long passwords will develop pretty extreme storage requirements, Not really, that's the point of rainbow tables. They can be reasonable, they are not lookup tables. If you are looking at large ones, they can be compacted at the expense of time. For "CorrectHorseBatteryStaple" the rainbow table will not contain "sdfgnWlgiuwreFrglrkemnmZflgh". You map the chain to your search space. So after CorrectHorseBatteryStaple might be SimpleFineChairBook or S1mpleFineChairB00k or SimpleFine@ChairBook depending on your space.
- thaumasiotes 5y ago
  > No. You can't use rainbow tables on salted data. There's something about this that you're failing to understand, but I'm not sure what it is. A rainbow table is a collection of key-value pairs. The key is a hash, and the value is input that produces that hash. Suppose my password on a website is "password". The MD5 hash associated with that password is 5f4dcc3b5aa765d61d8327deb882cf99 . If you dump the user database and see this: +--------------+----------------------------------+ | user | password | +--------------+----------------------------------+ | thaumasiotes | 5f4dcc3b5aa765d61d8327deb882cf99 | +--------------+----------------------------------+ You can look up that hashed value by any number of means (it's well known) and learn that the plaintext input to the hash was "password". If you salt the password, nothing changes. When you dump the database, you'll see this instead: +--------------+----------------------------------+-------+ | user | password | salt | +--------------+----------------------------------+-------+ | thaumasiotes | 9caa7f6693553ed9129bb0c7a0c8aa50 | bEanx | +--------------+----------------------------------+-------+ Then, when you reverse the hash, you'll learn that the plaintext input was "passwordbEanx". You also know that the suffix "bEanx" is the salt, so you can log in as me using the password "password", which is "passwordbEanx" with the salt removed. A rainbow table can tell you that 9caa7f6693553ed9129bb0c7a0c8aa50 came from "passwordbEanx" just as easily as it can tell you that 5f4dcc3b5aa765d61d8327deb882cf99 came from "password". That's what rainbow tables do. > they are not lookup tables This is flat wrong; that's exactly what a rainbow table is. > For "CorrectHorseBatteryStaple" the rainbow table will not contain "sdfgnWlgiuwreFrglrkemnmZflgh". You map the chain to your search space. This is a possibility, but it's also an admission that making a rainbow table at the desired length is infeasible. You trim the space of passwords you can look up down to something that you hope contains your target's password. Now you don't have a rainbow table up to 30 characters, you have a rainbow table for a list of common passwords. But once you've done that, you are vulnerable to password security policies. You can no longer crack uncommon passwords, and uncommon passwords are the problem rainbow tables are meant to solve. Common passwords you can often just guess.
  - aaron695 5y ago
    Salts might be 100 characters in length. It could be a book. It could be a jpeg. Examples - https://api.wordpress.org/secret-key/1.1/salt/ https://api.wordpress.org/secret-key/1.1/salt/ No rainbow table will contain those. bEanx actually works pretty as a fine salt, it wrecks Rainbow tables. But just like comments people understand salts more if they look complicated. Check out this https://rsheasby.medium.com/rainbow-tables-probably-arent-what-you-think-30f8a61ba6a5 https://rsheasby.medium.com/rainbow-tables-probably-arent-wh... It explains Rainbow Tables != Lookup Tables