RAR passwords, why don't rainbow tables work?

views:

answers:

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?

+2 A:

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.

Andrew Cooper 2010-09-29 00:28:31

@Andrew 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!).

Frankie 2010-09-29 07:41:38

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

Andrew Cooper 2010-09-30 06:36:13

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.

caf 2010-09-30 07:23:44

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

Andrew Cooper 2010-10-01 22:42:50

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.

caf 2010-10-02 06:39:17

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.

André Caron 2010-09-29 00:28:35

+1 A:

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.

Bill Karwin 2010-09-29 00:29:43

+1 A:

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.

2010-09-29 01:16:01

This should've been a comment, not an answer.

Jim Brissom 2010-09-29 01:21:08

This is not entirely correct

NullUserException 2010-09-29 01:46:37

@Jim You need 50 rep to comment.

NullUserException 2010-09-29 01:47:15

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.

Andrew Cooper 2010-09-29 06:05:41

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

Bill Karwin 2010-09-29 15:31:16

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.

2010-10-25 21:31:27

ansaurus

tags:

views:

answers:

RAR passwords, why don't rainbow tables work?

related questions