Johny_Brav0
asked on
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
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
ASKER
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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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.
@ 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.
ASKER
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.
"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.
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
-rich
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