Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

With large computing power (like what you can get in the Amazon cloud for example) you can generate huge rainbow tables for passwords. There also seems to be some large rainbow tables reachable that you have to pay for.

What are the largest tables that secret services could possibly use and what's the maximum characters you can have for the password?

I am wondering how long passwords should be considered when you choose a new password yourself? (This is not the question here!)

What is the maximum password-length those huge underground rainbow-tables (used by evil forces) are hosting?

share|improve this question
8  
Even a single bit es enough to resist rainbow tables if you use properly salted hashes. –  CodesInChaos Jun 10 at 8:56
2  
Shouldn't this renamed to "how to choose a secure password", instead of bating users in due to the "intriguing" title? –  Longpoke Jun 10 at 21:24
1  
Better would be, if someone in fact finds out up to which length those underground rainbow-tables are. That was my initial question, and it is not answered yet. I wonder why @TomLeek gets so many upvotes –  rubo77 Jun 10 at 21:28
3  
@TomLeek gets so many upvotes, because he explains quite well the misunderstanding your question is based on. As he says, "the maximum password-length" is irrelevant to "those huge underground rainbow-tables". The answer is not (except for the small appendix at the end) about how to create a strong password, but about "what password is not threatened by those rainbow tables". Which is what you meant to ask, even if you didn't realize it ;-) –  AviD Jun 11 at 6:54
    
Rainbow tables are utterly useless unless you're doing something horribly wrong in your password hashing. –  R.. Jun 11 at 13:24
add comment

5 Answers

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:

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

  2. 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:

  1. 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.
  2. 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).
  3. 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.
  4. Your enemies are after your money, not your freedom. Don't try to defeat phantasmagorical three-letter agencies; concentrate on mundane criminals.
share|improve this answer
1  
Character set of base64 is the character set of Base64. As I wrote: lowercase letters, uppercase letters, digits, '+' and '/'. –  Tom Leek Jun 10 at 13:08
3  
"Using the password twice" makes about as much good to security as sacrificing a goat to propitiate the gods. Do it if it makes you feel safer, but scientifically such doubling does not improve entropy (entropy is "what the attacker does not know", and he knows that you write the password twice because you just admitted doing it on a public forum). –  Tom Leek Jun 10 at 13:09
2  
@SPRBRN Special characters are not more secure than letters, what matters is the total number of possible characters. Using a password consisting of the same string repeated twice makes it longer, but adds at most one bit of entropy (if you flip a coin to decide whether to use the short or the long password, and the attacker doesn't know the length of your password): it's not worth it. –  Gilles Jun 10 at 13:09
7  
Regarding “Don't go about producing another one”: it's ok to re-draw if you don't like one; if you redraw N passwords then the entropy is only reduced by log₂(N) bits, e.g. if you generate 16 passwords and choose one then you still get an acceptable 48-log₂(16)=44 bits of entropy. What you must not do is generate a password and mentally tweak it to something you prefer: that reduces the entropy very quickly. –  Gilles Jun 10 at 13:18
3  
I don't agree redrawing reduces the entropy, as long as it is not based on a known rule. When creating a public key, I redid the process a couple of times until the randomart was "nice looking", but you would need a full model of my artistic taste to know which ones would look "good" or "bad", so the entropy is the same. And I have a beautiful private key. –  Davidmh Jun 10 at 22:34
show 19 more comments

To answer your revised question:

As for the maximum precomputed password length, there isn't one. Precomputed password hashes are precomputed from dictionaries, not from sequential scans of the keyspace. While some sequential generation of very short passwords may be common, it typically isn't more than just a few characters. The space requirement for storing all the 256-bit hashes for 8-character passwords is on the order of exabytes; not beyond technical capability, but certainly beyond any sort of cost-benefit consideration.

Plus, if the server storing the passwords uses salts for each one, then the whole precomputation idea goes out the window. Done. No rainbow tables. They no longer work. Salted hashes are resistant to rainbow tables, as explained here.

Still, you're thinking about it wrong

The length of the password is entirely irrelevant. All that matters -- the only thing that matters, is how many passwords will the attacker try before guessing the correct one, and how long does each guess take?

If the attacker guesses your password first, then no amount of complexity will save you, and no amount of server-side storage complexity will save you. It's as easy for the attacker to log in as it is for you. Game over.

If your password is on the list, but it's 500 down from the top, then the amount of time required for the attacker to get to yours is 500 times the amount of time each attempt takes. If it takes 1 second per password, then you've got about 8 minutes. Will the attacker give up after 5 minutes? If he does, then you're safe. If he doesn't, then you're not.

Per your original point, if your password is on the top 500 list, then the precomputed hashes will be available. Obviously that only matters if the passwords aren't stored salted.

If your password is random, and comes from a 48-bit keyspace (approx. 8-characters alphanumeric), then on the average the attacker will have to try attacker must try 247 passwords before getting to yours. How long will that take? If the passwords are store with PBKDF2 tuned to ⅕ second per attampt (as LUKS uses), then it'll take just under 1 million years to guess your password.

On the other hand, with the same password, if he has the hardware to try 5 million guesses per second, then you're down to just under a year. 5 billion and it's less than a day.

A better way to do it

My advice is to use a random, unguessable password that you don't remember, but rather store in a browser-integrated password manager like KeepPass, LastPass or 1Password. In that case, there's no additional cost to you between 6 characters and 24, so you might as well choose a long one -- say 14 or 18 character. That should be more than enough.

The key here is the browser-integrated password manager. An attacker guessing your random password is not the attack vector your care about. It's not going to happen. Instead, you care about phishing. That's much more likely to happen, and browser-integrated password managers will save you.

share|improve this answer
    
How did you arrive at such a large rainbow table size? My estimation was only 100 GB or so. But I'm hardly an expert on rainbow tables, so I might be off. –  CodesInChaos Jun 11 at 8:01
    
@CodesInChaos If you use real rainbow tables with that whole chaining thing, then you can compress it quite a bit. But I'm just talking about simple indexed-lookup precomputation sets as seen on most websites. –  tylerl Jun 11 at 18:34
    
Using a password manager introduces a single point of failure. The average password database is locked with a simple password the owner can easily remember. Since none of the stored passwords are remembered (as the owner just copy-pastes them instead of typing them), the password database has to be backed up regularly and ported to different devices. Anyone getting their hands on the database would thus still be able to access all of your accounts as soon as he cracks a single simple password. What's worse - people even store bank credentials in their password safes these days. –  Robbert Jun 12 at 12:45
    
I know people use it for convenience, I do too, but I would never dare recommend using them as a single solution to your entire web security. –  Robbert Jun 12 at 12:46
    
@Robbert while I understand your opinion, you have to look at the attack profile and best or most likely alternative to any solution. You can't say don't do X without providing a solution at the same time. The naive recommendation of "use unique random passwords for everything and memorize them all" is theoretically ideal but beyond untenable. It never happens because it can't happen. You need a real-world solution that is designed by looking at what attack is likely and built from there. –  tylerl Jun 12 at 18:05
show 1 more comment

I am the author of the http://passwordcreator.org/ website. I built the site because I wanted an easier way to generate secure passwords for myself. While doing the research for the site, I learned a great deal about secure passwords.

There are distributed password crackers out there that can make 100 billion guesses per second. The NSA which is government sponsored (large budget) may be able to do an order of magnitude more.

To be secure for a year or more from this type of attack, your password must be chosen randomly from several quintillion possibilities. For password constructed randomly from the 95 characters available on most keyboards, that means that you need at a password that is at least 10 characters long for decent security right now.

If you password is generated in other ways (there are several algorithms available on my site), your password may have to be even longer to achieve the same resistance against guessing.

At 10 characters, I pretty much have to write down my random password. If that is the case for you as well, I would recommend that you increase the length to at least 14 characters which will remain secure for a longer period of time.

share|improve this answer
    
Is that 1e11 10-character string comparisons, 1e11 SHA-1 calculations, or 1e11 PBKDF2 calculations with a decent iteration count? Because we're talking about offline password cracking here. –  Gilles Jun 10 at 21:51
    
Not string comparisons, SHA-1 calculations. I know that isn't the best way to hash passwords, but when you are creating a password that is stored in somebody else's database, it is better to assume that they haven't implemented it ideally. See: security.stackexchange.com/questions/43683/… –  Stephen Ostermiller Jun 11 at 0:39
add comment

From Robert Graham excellent blog http://blog.erratasec.com/2011/06/password-cracking-mining-and-gpus.html

This is only true for random passwords, with an attacker going for exhaustive search. When attacking real people passwords, you try other approaches first.

Economics of password cracking

share|improve this answer
    
Hum, 4 years late, I somehow saw it as new... –  Bruno Rohée Jun 16 at 12:42
add comment

Assuming 256bit (32 byte) hashes and assuming you want to cover all possible passwords with 80 different characters (26 lowercase, 26 uppercase, 10 numbers, 18 other characters), these are the required rainbow-table sizes. I calculated this using the formula (80 ^ length ) * (32 + length).

However, keep in mind that the table below is for all possible combinations of 80 different characters. When you use less characters or only create the hashes for passwords which follow certain patterns (like all l337speak permutations of words in the dictionary), you end up with a lot less space.

Length Size  Unit  
1        2.5 KiloByte          
2      212   KiloByte
3       17   MegaByte
4        1.3 GigaByte
5      112   GigaByte
6        9   TeraByte
7      744   TeraByte
8       59   PetaByte
9        4.7 ExaByte
10     391   ExaByte
11      31   ZettaByte
12       2.5 YottaByte

Decide for yourself which order of magnitude is still within plausible technical abilities of the attackers you consider. But when you want my opinion, I think that:

  • A 5-character rainbow table (112 GB) is small enough to exchange it over todays broadband internet
  • 6 characters (9 TB) is the limit of what a hobbyist or independent professional cracker can handle with consumer-grade hardware
  • A 7-character rainbow table (744 TB) would fit into a SAN rack in a datacenter, so it would be within the technical abilities of a professional company to store such a table.
  • An 8-character rainbow-table with 59 PB is technically quite challenging, but databases of that scale exist: Facebook manages a database with over 100PB of data, CERN has a database of 200PB of data generated by the LHC experiments. So it is within reach for a really large corporation or a government-agency with a million-dollar budget.
  • 9 characters and above seems implausible with todays technology.
share|improve this answer
    
So 7 chars is already 744 TB pure data to be stored for just one salt. How much would a databasse use, that stores those? I guess it is much less, cause the data are stored compressed –  rubo77 Jun 16 at 11:30
    
@rubo77 Hashes are data which is already as dense as it can be, so they can not be compressed further. That means you can assume that the actual database-storage would rather be more than less. –  Philipp Jun 16 at 11:54
    
Trivia: When you would develop a way to store one bit of information in a single atom and then convert the whole planet Earth into an atomic data-store, you could store a 25 character rainbow table in it. –  Philipp Jun 16 at 12:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.