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