6
$\begingroup$

With unsalted passwords becoming rare, and stream ciphers having a significantly large state, are there currently any widely deployed systems still vulnerable to such time-memory-data trade-off attacks?

If I were to show a small generic improvement to rainbow tables, what would be a good problem to demonstrate on?

$\endgroup$
5
$\begingroup$

If you just want to provide a generic improvement I'd just target password hashing. If you think that directly running passwords through a cryptographic hash is history then I can show you plenty of StackOverflow questions where it is still being performed.

For a generic attack you don't need a new problem; just focus on your improvement and let your solution be interesting on its own merit.

| improve this answer | |
$\endgroup$
3
$\begingroup$

Rainbow tables haven't been too relevant for a few years now. The problem is (1) they're really large, and therefore hard to move to a target computer and (2) anyone serious about password cracking has a GPU farm that can essentially recreate a rainbow table within a few seconds.

The last time I looked at this, a modestly-sized GPU farm could try all passwords up to length 6 in 1-2 seconds. This means that encoding those passwords into a rainbow table would really not make that much sense. Moreover, as you pointed out, most passwords are salted anyway, meaning we'd need rainbow tables for each salt value, and for larger salts this is completely impractical.

I can't imagine too many scenarios where rainbow tables might be the best choice. Perhaps a casual cracker who can afford the terabytes needed (drives are cheap) but cannot afford to build a cracking cluster, and who has the time to download the tables (or have them shipped via DVD).

That said, reasonable improvement to the algorithm would probably still be publishable. As long as your improvement isn't completely trivial.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ GPUs shouldn't make a bit of difference, just allow handling a larger password space. If you speed up direct attack you speed up the rainbow table attack as well, both offline and online phase. $\endgroup$ – Meir Maor Feb 10 '18 at 17:13
3
$\begingroup$

Rainbow tables as a concept are useful as a generic baseline against which to compare putative attacks on preimage-resistant functions such as $k \mapsto \operatorname{AES}_k(473)$. Any attack that gives worse price/performance ratio than parallel rainbow tables should not be construed to actually break a cryptosystem, even if in a myopic view of costs it runs ‘faster than brute force’1. See djb's paper ‘Understanding brute force’ for details on this.


1 …at significantly greater memory cost.

| improve this answer | |
$\endgroup$
1
$\begingroup$

They can be very useful. It depends on what you are trying to accomplish. For example, if you have been hire by a firm to do penetration testing, and you know their WiFi SSID, you can generate some Rainbow Tables ahead of time before you arrive on site and that will dramatically increase your speed for cracking their WPA2-PSK passwords. If you don't know their SSID, a little social engineering can usually get it.

| improve this answer | |
$\endgroup$

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.