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?
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.
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.
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.
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.
