RAR passwords, why don't rainbow tables work?

Question

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?

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

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

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

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

View more solutions

Comments

[user461234]

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.

[Andrew Cooper]

@user461234: The point of a hash algorithm is that it can't be cracked. It's computationally infeasible to take a hash and work out the plain text that generated it. Having the salt in plain-text doesn't help, except you know that you need to have a rainbow table that was generated using that salt. Generating rainbow tables for a given hash algorithm and all possible salt would again be an end-of-the-universe type of job.

[Frankie]

this is a very good and very detailed explanation. Thank you! Exactly what I was looking for. By the way, some of us do need to sleep! ;) You can check the other user's profile and see for how long he hasn't checked in (in regards to your last comment!).

[Bill Karwin]

@user461234: I'd like to see you remove the part of a hash that comes from the salt. It's like removing the part of concrete that comes from the water you mixed it with.

[Andrew Cooper]

I apologise. We tend to sleep at different times on the other side of globe. ;-)

[caf]

If you have a block's worth of plaintext crib, then you can use rainbow tables against encryption. In this case, the encrypted form of that plaintext block is the equivalent of the "hash" - the theory of rainbow tables is equally applicable.

[Andrew Cooper]

@caf Having the plaintext certainly does help in performing a rainbow table attack against an encryption key, in theory. The problem is the size of the key. For a 128-bit key, you would need nearly 5x10^27 terabytes of storage to store a rainbow table for a single block of plaintext.

[caf]

A rainbow table doesn't take a fixed amount of storage - it's a space/time tradeoff. Only one point in each chain is stored - that's kind of the point, and what differentiates rainbow tables from exhaustive dictionaries. But yes, it's still infeasible against a key with 128 bits of entropy - so keys generated from random sources are safe. Keys that are derived from passwords/passphrases can still be susceptible, and that's what I was referring to - RAR encryption is based on a password. Salts are equally applicable for password-based encryption, for much the same reason.

[user461234]

@user461234: You two have a fundamental misunderstanding of the issue. For example, md5 has been completely mapped - there are widely public tables that can instantly tell you a source plaintext given a hash. Is a salt going to help you? Say your password was "hunter2" and the salt is "xAoE". Then when you look up the hash, you will get "hunter2xAoE" and can trivially separate the salt from the rest of the hash. Think about it, adding extra text to the hashed text obviously can't expand the hash space. Its only use is to obscure things when multiple users have the same password.

[Christian Mann]

@user461234: The trouble with the above approach is that despite the large amount of strings that have been mapped, it's far more likely that "hunter2" appears in the database than that "hunter2xAoE" appears in the database.

[Gilles 'SO- stop being evil']

@user461234: This is wrong. MD5 has not been completely mapped: assuming that by mapping you mean finding an inverse for each hash, that would take about 2^128*16 bytes of storage (5 billion billion billion terabytes). You can't “take out that part of the cracked hash”: cryptographic hashes are designed so that knowing the hash(password+salt) does not give you any advantage in finding the hash(password). Tables of MD5 and the like contain human-readable passwords, say 10^15 of them with a rainbow table. If you add a 64-bit salt (on the low side), the size of the table is multiplied by 10^18.

[Gilles 'SO- stop being evil']

The encryption algorithm is irrelevant here, what matters is the way the key is derived from the password. RAR uses a good key derivation function, but that's irrelevant to the use of rainbow tables anyway (see Andrew's or my answer).

[Gilles 'SO- stop being evil']

The encryption algorithm is irrelevant here, what matters is the way the key is derived from the password. RAR uses a good key derivation function, but that's irrelevant to the use of rainbow tables anyway (see Andrew's or my answer).

[Bill Karwin]

@Gilles - yes, that was my point. I'm guessing you were the one who gave me a downvote, which I think is undeserved. Please reverse your downvote.