Length of the password, and size of the rainbow table, are red herrings. Size does not matter. What matters is entropy.
Rainbow tables are not really relevant here, for two main reasons:
Building the table is expensive. A table "covers" a number of possible passwords; let's call it N. There are N distinct passwords that will be broken through the table. No other will be. It so happens that every single one of these N passwords must have been hashed during table construction. Actually, a lot have been hashed several times; building a table which can crack N passwords has a cost of roughly 1.7*N hash invocations. That's more expensive than brute force. In fact, brute force requires on average 0.5*N hashes, so the table building costs more than three times as much.
Thus, a rainbow table is worth the effort only if it can be applied at least four times, on four distinct password hashes that shall be cracked. Otherwise, it is a big waste of time.
Rainbow tables cannot be applied more than once. That's because of salts. Any password hashing which has been deployed by a developer with more brain cells than a gorilla uses salts, which are non-repeating variation parameters. The effect of salts is equivalent to using a different hash function for each user. Since a rainbow table must be built for a specific hash function, one at a time, it follows that a rainbow table will be able to crack only one password hash in all. Combine with the previous point: rainbow tables are simply not useful.
Now, of course, there are a lot of deployed systems where passwords are not hashed with human-level competency. Ape-driven development has resulted in many servers where a simple unsalted hashing is used; and even servers where passwords are stored as cleartext or some easily reversible homemade encoding. But one could say that if your password is to be managed by such sloppily designed systems, then extra password entropy will not save you. A software system which utterly fails at applying sane, documented techniques for protecting a password, which is the archetypal sensitive secret data, is unlikely to fare any better in any of its other components. Crumminess and negligence in software design are like cockroaches: when you see one, you can be sure that there are hundreds of others nearby.
Now let's assume that reasonable password hashing was employed, combining salts (to defeat table-based and parallel attacks) and configurable slowness (to make hashing more expensive). E.g. bcrypt. This answer is a lengthy exposition of how passwords should be hashed.
For instance, consider a server using bcrypt, configured so that, on that server, verifying a password hash takes 0.01s worth of CPU time. This would still allow the server to handle 100 user logons per second, an extremely high figure, so the server will not actually devote a lot of its computing power to password hashing.
Now, imagine an attacker who got his hands on some password hashes, as stored on the server (e.g. he stole an old backup, or used an SQL injection attack to recover parts of the database). Since bcrypt is salted, the attacker will have to pay the full brute force attack cost on each password; there is no possible parallel cost sharing, and, in particular, no precomputed tables (rainbow or not) would apply.
Our attacker is powerful: he rents one hundred servers of computing abilities similar to the attacked server. This translates to 10000 password tries per second. Also, the attacker is patient and dedicated: he accepts to spend one month of computing on a single password (so that password must protect some very valuable assets). In one month at 10000 passwords per second, that's about 26 billions of passwords which will be tried.
To defeat the attacker, it thus suffices to choose passwords with enough entropy to lower the success probability of the attacker to less than 1/2 under these conditions. Since 26 billions is close to 234.6, this means that the password entropy shall be at least 35.6 bits.
Entropy is a characteristic of the method used to generate the password, and only loosely correlated with the length. Password length does not imply strength; length is just needed to make room for the entropy. For instance, if you generate a password as a sequence of random letters (uppercase and lowercase), then 7 characters accumulate almost 40 bits of entropy, which, by the calculations made above, should be fine. But this absolutely requires that the letters are chosen randomly, uniformly, and independently of each other. Not many users would go to the effort of using a computer PRNG to produce a new password, and then accept to learn it as it was generated (I do that, but when I explain it to my work colleagues they look at me in a weird way).
As this famous question hints at, human memory can be at odds with entropy, and a longer password with more structure may be a better trade-off. Consider that the "correct horse" method ends up with "only" 44 bits of entropy for 25 letters or so (by the way, take note that a 25-letter password can have less entropy than an 8-letter password). The extra typing can be worthwhile, though, if it allows an average user to remember a 40-bit entropy password.
Despite all the propaganda of Hollywood movies, Secret Services rarely involve stupendously advanced technology (for that matter, they are also quite short on dry Martinis, leggy blondes and motorbike chases). Any rationally managed Secret Service will avoid spending 10k$ on breaking your password, since 1k$ will be more than enough to hire two goons to break your kneecaps. Ultimately, this is all a matter of relative cost.
So let's get practical. To generate a password, use this command on a Linux system:
dd if=/dev/urandom bs=6 count=1 2> /dev/null | base64
This outputs a password consisting of eight characters among lowercase letters, uppercase letters, digits, '/' and '+'. It is easily shown that each such password offers a whooping 48 bits of entropy. The important rules are:
- Generate the password and then accept it. Don't go about producing another one if you don't like what you got. Any selection strategy lowers your entropy.
- Don't reuse passwords. One password for each site. That's the most important damage containment rule. If you have trouble remembering many passwords, you can "write them down" (password managers like KeePass may help).
- If 48 bits of entropy are not enough, then you are using a password in a weak system, and that is what you need to fix.
- Your enemies are after your money, not your freedom. Don't try to defeat phantasmagorical three-letter agencies; concentrate on mundane criminals.
