RAR passwords, why don't rainbow tables work?

问题:

I've been looking around for encryption and I've seen several implementations of Rainbow Tables work like charm on passwords (say windows).

I'm yet to see an implementation of a Rainbow attack on a RAR file. Why is it so. What makes RAR encryption more secure and immune to these sorts of attacks?

回答1:

A rainbow table is an optimization for inverting hash functions: finding the password when all you have is its hash. Although this is not strictly necessary here, I recommend reading What are rainbow tables and how are they used? which has a very good explanation that clears a few common misconceptions.

There are two parts to RAR encryption (or just about anything that uses a password to encrypt some data). First, an encryption key is derived from the password, using a key derivation function (KDF). Then the encryption key is used to encrypt or decrypt the data.

Even if the KDF is a hash function, a rainbow table wouldn't help: the attacker does not have the output of the KDF. When a password is used for authentication, the output of the KDF is what's stored in the database. When a password is used for encryption, the output of the KDF is the secret key which is what the attacker is after.

In any case, rainbow tables only help against unsalted hashes. WinRAR uses a good KDF (PBKDF2) which includes a salt.

A KDF transforms a variable-length string into a fixed-size key. A key property of a KDF is that it must distinct map input strings to distinct keys. A cryptographic hash function (SHA-1, SHA-256, …) achieves this. When the input string is a human-provided password, there are two other important properties which a hash function does not achieve on its own:

• If two people choose the same password, they must not end up having the same key.
• The KDF must be slow to compute, so that an attacker cannot find the password by brute force.

A salt achieves the first property. The second property is achieved by doing something like this: take the password, append the salt, hash the lot; take this hash, append the salt, hash the lot; repeat many times.

A rainbow table is an optimization to compute preimages through “one-way” functions: functions that are easy to compute in one direction but nigh-impossible to inverse, i.e. given x it is easy to compute y=f(x) but given y there is no known method to find x such that y=f(x) other than somehow guessing x and checking. Hash functions are like this. Encryption with a symmetric key is not like this: the attacker cannot compute f any more than he can compute its inverse. Hence rainbow tables cannot help with breaking symmetric encryption.

回答2:

Rainbow tables are used to decode Hashes, not encryption. A rainbow table is just a list of precomputed hashes for some set of possible input.

So if you pre-compute the hash for every possible windows password, when you want to recover an unknown password, all you need is the hash from the SAM database and then look it up in the rainbow table. The rainbow table then gives you a password which will correspond to that hash. This is complicated by password salt, but that's the basic idea.

Rainbow tables don't help with breaking encryption. Theoretically you could pre-compute all possible cypher-text for all possible keys and all possible plain-text input, but you'd probably require more bits to store this data than there are atoms in the universe, not to mention that those atoms would probably have boiled away to nothing before you get there. It would be quicker (albeit still prohibitively slow) just to brute-force the key.

回答3:

Rainbow tables help recover plaintext content from a hash generated by a cryptographic hash function, but RAR files use AES encryption for the file data and headers. It's a different kind of animal.

回答4:

An easy way to beat a rainbow table for hashed passowrds is to use a salt. I'm not familiar with the encryption in RAR files, but the Wikipedia page says RAR3 uses a badass encryption scheme.

回答5:

Andre: Salts don't make hashes harder to crack at all. Since the salt is stored in plaintext right next to the hash, it's easy to just take that part out of the cracked hash...

The purpose of a salt is to make sure that identical plaintexts still have different hashes. For example, say your password is entropy9 and its hash is 649acba24bab481f16ee49cdf0a40870. Now if you see someone else's hash is also 649acba24bab481f16ee49cdf0a40870, then you know their password immediately! Obviously this has implications in non-security contexts too, like with hashmaps etc.