Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Typically when rainbow tables are discussed MD5 hash is used as an example. It's not quite clear whether this attack is specific just to MD5 or to a certain subset of hashes or to just any hash function.

Is rainbow table attack applicable to any hash?

share|improve this question
add comment

2 Answers

Rainbow tables are a size optimization of lookup tables at the cost of time. This is the typical time/memory tradeoff found everywhere in computer science.

However, hash functions themselves are not really susceptible to rainbow table attacks. Rather, it's a specific use of a hash function that may (or may not) be susceptible to rainbow tables. And, even then, rainbow tables are used essentially for finding pre-images of hash functions; e.g., given $H(x)$, find $x$.

For example, suppose you are using a hash function to store the fingerprints of files---just files in general. If you allow sufficiently large files to be stored, say, then this scheme is not going to be very susceptible to rainbow tables: the 'space' of possible inputs to the hash function is just going to be too big to generate a useful rainbow table. You might be able to do it for some subspace, which may or may not be useful, but probably not. The point is that: (1) there are many possible inputs, so many that the table would be huge to be exhaustive, and (2) "all files" is rather general, and while some files are undoubtedly more common than others, this statistical bias is not really well-known.

On the other hand, if you are doing password hashing with the naive "just hash the password", then the space of possible passwords is rather small (for most services), and, most importantly, the distribution of passwords is very non-uniform. A password like 123456 is vastly more common than AvdJv89}{. Hence, you can generate a rainbow table with the top X most common passwords and get significant "coverage" with the table. Given that the goal of password hashing is to keep plaintext passwords out of the hands of attackers for as long as possible, this is quite bad, especially given that the users who are using passwords like 'password123' are probably going to be doing similar things for other services. Thus, with rainbow tables against password hashes, the real idea is to hit the weakest X% of users. That one user with a 48-char password is probably security-conscious enough that it's not worth the effort to break his password, so attackers are mostly interested in users whose passwords are insecure. And, at any rate, that assumes the service allows long passwords; my university allows only up to 24 characters for whatever reason.

This attack is possible really because the preimages we are interested in are (1) few in number and (2) highly biased towards certain preimages. Also, crucially, we already "know" the most common inputs to the hash function. This is why "salting" passwords breaks the rainbow table attack: the random "salt" prevents us from knowing the common inputs, since now there's a salt being sent into the hash function too. If it is a "global" salt and is known to the attacker, then the attacker can generate a rainbow table that uses the 'salt' (a 'pepper' more accurately). But for the case of a real per-user random salt, rainbow tables aren't a possible line of attack.

To answer your question more directly, all of the generic cryptographic hash functions are vulnerable when used in a vulnerable way: MD5, SHA1/2/3, etc. On the other hand, the popular key derivation functions of today (PBKDF2, bcrypt, scrypt) are not vulnerable because they use a salt internally. (Also, for properly-tuned KDFs, the generation of a useful rainbow table would take a very, very, very long time even if a salt weren't used.) The faster the hash function, the faster the rainbow table can be generated, so MD5 is "less secure" against rainbow table attacks in that sense than SHA2.

Keep in mind that the whole point of a rainbow table is to pre-compute values to make finding preimages fast. If you can't predict the preimages you're interested in, then the whole attack is foiled.

share|improve this answer
add comment

Rainbow table attacks can be done against any hash. There is no limitation of the hash algorithms.

share|improve this answer
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.