Cryptography - rainbow tables and the purpose of the reduction function

I am trying to understand rainbow tables.
So far I understand that plaintexts can be hashed and stored in a table to take away the need to generate hashes when used a second time.
What I dont get is the reduction function:
Is it just an easy way to make a load of table entries i.e. put in one plaintext, hash, reduce, hash and so on - making it a job for the computer and not some monkey having to enter table entries?

If im wrong please tell me its purpose.
Thank you
Who is Participating?

Security SamuraiCommented:
LanMan hash, windows default until Vista and greater came around: http://en.wikipedia.org/wiki/LM_hash
The "reduction" function is the matching part. Building RT is technically slower than exhausting all possible combinations, mainly due to I/O of a hard-drive vs the I/O of matching in memory. But once a RainbowTable is written to disk, searching it is magnitudes faster. A rainbowtable is a sorted, and reduced data set, in essence. So instead of storing the complete hash, or the complete plain-text, only a certain length are stored. So when you load a password hash to search for, the RT program perhaps only looks for the first 6 chars of the hash, rather than the entire hash. When it finds matches, and it will find several when the length of the hash is truncated to 6, it will look at the plain-texts that go along with those "matches" and then it will do the full comparison of the hash...
The partial hash "598DDC" matches the following plain-texts: as | 3M~!2a | ((((ha0 | _*,ss4k | :.,<<  |
So the chain is:
598DDC:
as          = 598DDCE280126E140 <--- full hashes
3M~!2a   = 598DDC3B609DD44B
((((ha0   = 598DDCE1D662609E1
_*,ss4k  = 598DDCDB96E95CF42
:.,<<      = 598DDCC96F750993C
Again, my example is over simplified, but it should give you a visual of how it's done. These plain-texts (above) all have hashes that begin with 598DDC at the beginning. So the rainbow table knows that to find the rest of the hash for an absolute match, it will have to fully hash (in memory) the plain-texts listed in the chain. It's never a 1-to-1 match, again that would take up an incredible amount of space. The LM hash again is limited to 69 chars and limited to 7 chars in length, other hashes use all 96 chars on the keyboard, far less limited in length (usually) and are salted, and salted hashes are not good candidates for RT's unless a fixed salt is used. LM rainbowtables are 99.9% effective and occupy 64Gig's of space.
-rich
0

Security SamuraiCommented:
To store the plain-text and hash of a certain hash in a much much smaller space, let's use LM for example, 69 printable chars, 7 chars max. LM is case insensitive, all uppercase A-Z, 0-9, space, and all other chars on the keyboard. Just storing all possible combinations of the plain-text will take up over 7gig's right there. Then if we add the hash's (16 chars long each) and you essentially multiply 7gig by 16 and get 112gig... add a space or some other separator to differentiate between hash and plain-text and it jumps 7gig more... I think my math is off, 112/119G still seems too small.
Nonetheless a flat text file is very very large and would take time to search through, possibly slowing down the time it takes to crack smaller hashes than it would to actually brute-force them.
Rainbow tables get complicated, but they actually do some brute forcing of their own believe it or not..
This is a good explanation: http://kestas.kuliukas.com/RainbowTables/
But bad examples (I think) are given. For arguments sake let's say:
qwerty = 598DDCE2660D3193
zx9wo = 598DDCE2C3286B64

These plain texts are not similar at all, but their hashes do begin with similar strings "598DDCE2"
That is an over-simplification of what is being done, but those two plain-texts would be in the same "chain" as each other if they hashed like that. So the rainbow program see a LM password that looks like "598DDCE2" and goes there to look up all the plain-texts in there, then FULLY hashes each plain-text until the exact match if found... Again I've over simplified it...
-rich

0

Author Commented:
What's LM? So I'm wrong about the reduction function being used to speed up building the rainbow table?
Am I right - reduction function is used to create chains that are used to crack hash in the way that e.g. If you have a hash of a plaintext that is in a large chain u can find it's plain text.
Cheers for response, need a bit more help though.
0

Exec ConsultantCommented:
Believe you may already know that there is pre-computed chains in the RainbowCrack project. If you know that SHA-2 (or hash using salt that consists of random bits in the one way function) hashes are used, we can forget rainbowcrack as it will be computationally intensive (though there is h/w acceleration and grid support, e.g. http://www.insidepro.com/) and maybe do a dictionary attack (crossing finger).

@ http://project-rainbowcrack.com/table.htm

LM rainbow tables speed up cracking of password hashes from Windows 2000 and Windows XP operating system.
NTLM rainbow tables speed up cracking of password hashes from Windows Vista and Windows 7 operating system.
MD5 and SHA1 rainbow tables speed up cracking of corresponding hashes, respectively.

Nonetheless, as explained by richrumble, reduction is used as the term as it is converting the cipher hash (which maybe longer) to another plain guess (not original). This process is used as part of the hash chain strategy to achieve Time-Memory Trade-Off" to crack and derive the original plaintext. Wiki also has a good explanation @ http://en.wikipedia.org/wiki/Rainbow_table.

This strategy is considered to be more efficient than having a big chunk memory space to do a one to one brute force matching, not resource wise as the longer you need to crack, the value of the secret dropped - time is of essence ....

Rainbow tables effectively solve the problem of collisions with ordinary hash chains by replacing the single reduction function R with a sequence of related reduction functions R1 through Rk.

Increasing the length of the chain decreases the size of the table. It also increases the time required to iterate over each chain, and this is the time-memory trade-off of the rainbow table. In a simple case of one-item chains, the lookup is very fast, but the table is very big. Once chains get longer, the lookup slows down, but the table size goes down.
0

Author Commented:
Well I believe im making some progress.

"So the rainbow program see a LM password that looks like "598DDCE2" and goes there to look up all the plain-texts in there, then FULLY hashes each plain-text until the exact match if found."

You start with a password hash, then the RT sees truncated hash similar to password hash. Then the RT looks up all plaintexts that match the truncated hash and hashes them completely until a match is found.

I now have a basic understanding - cheers.

If I want to start asking about salt, WPA and essid's then should I start a new question?

The reason I ask is a while back my WEP got cracked by somebody and ive been intrigued ever since.
0

Security SamuraiCommented:
A new question is best then for additional info on a different topic. Again I've over simplified it, it's more complex than what I've laid out, but that's the basic idea.
-rich
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.