Talk:Rainbow table

From Wikipedia, the free encyclopedia

This page was moved in accordance with a request on Wikipedia:Requested moves. —Cleared as filed. 01:01, 22 November 2005 (UTC)

Contents 1 Revisions 2 Strength of double hashing 3 Salts 4 Dictionary vs Brute Force Attacks 5 Where's the "rainbow" name from? 6 Reduce?

[edit] Revisions

I revised the article to remove the reference to DES, which seemed like a distracting tangent, to eliminate mention of "tokens" and just talk about salt instead (the term salt is not used exclusively with DES as opposed to one-way hashes — see the salt article), and to clean up the writing a bit. For instance, I eliminated the ellipses after the formulas. I also changed "md5sum" in the formulas to just "MD5". There is no need to bother the reader with a particular program for doing MD5 hashes when we are just talking about the abstract concept of hashing. The only change I am uncertain of is replacing "success probability of the table" with "probability of the table successfully cracking the password". The two seem equivalent to me, but I am not familiar with rainbow tables and the term "success probability" could be a term of art. I would appreciate opinions either here or on my talk page. --DavidConrad 03:41, 13 January 2006 (UTC)

Found it. This page [1] defines "success probability" as "the probability you can find the plaintext of the ciphertext". So my restatement of it is essentially correct, but I will incorporate this definition into the article. --DavidConrad 03:54, 13 January 2006 (UTC)

[edit] Strength of double hashing

Would doing a double hash be just as good as a salt? If you know the salt then you could generate rainbow tables for it. Which brings us to the same problem again. —The preceding unsigned comment was added by 198.54.202.210 (talk • contribs).

Hashing passwords twice would not prevent attacker from using this table - he would just generate table by hashing twice instead of once. Ofcourse it would double the time for preparation of attack. Ad salt: salt is meant to be different for each user. Efectivity of rainbow table lies in its reusability: once the table is generated, it used to lookup unlimited amount of hash values. But if system uses the same salt for all users, then atacker can prepare table using this salt and mount attack the usual way.--Alvin-cs ✉ 13:01, 12 March 2006 (UTC)

[edit] Salts

I changed the top section of the article as I thought it was a) confusing and b) inaccurate. I think the description of the effect of a salt is somewhat incorrect. I think (and someone correct me if I'm wrong) that the addition of a salt would require the tables to be generated for every single possible salt to reach the same effectiveness against a salted hash as the rainbow table has against a salt-less hash. Basically the salt makes it so that intead of a single hash generator, there are 2ⁿ generators, where n is the number of bits in the salt. Thoughts? —Bradley 19:53, 9 June 2006 (UTC)

[edit] Dictionary vs Brute Force Attacks

The password "guesses" in a rainbow table are generated by the reduction function, which applies a transform to the hash of the previous password guess. They are not based on word lists or lists of most-likely passwords and hence the attack is closer to brute force attack than it is a dictionary attack. —Bradley 14:47, 19 June 2006 (UTC)

[edit] Where's the "rainbow" name from?

I heard the origin of the name somewhere, but can't recall it and can't find a source. Someone who knows this, please add. --(unsigned)

[edit] Reduce?

What is the 'reduce' function? --Apoc2400 01:40, 30 October 2006 (UTC)

Someone in the last day decided to turn some of the text descriptions into equations. Here are the original paragraphs:

A rainbow table is constructed by building chains of possible plaintext passwords. Each chain is developed by starting with a randomly selected "guess" of the plaintext password and then successively applying the one-way hash followed by a reduction function. The reduction function takes the results of the hash-function and turns it into another plaintext password guess. The intermediate password guesses are then discarded and the first and last are stored in the rainbow table. This table takes time and memory to build, but must only be built once at which point, it can then very quickly recover unknown passwords.

Recovery of plaintext passwords is then done by taking the hash password, applying the reduction function, and looking-up the result in the rainbow table. If no match is found, then the hash and reduction functions are applied again and that result is then looked-up. This is repeated until a match is found. Once a match is found, the chain that resulted in the match is reconstructed to find the previously discarded intermediate value, which is then a plaintext password for the given hash.

It sounds like a "reduction function" is just any function (not specified here) that "takes the results of the hash-function and turns it into another plaintext password guess". I am not an expert on this; perhaps Oechslin's papers would shed more light on this. --Spoon! 02:03, 30 October 2006 (UTC)

I have just added a smal explaination of this kind of function. Feel free to expand it; I'll also try to help if my explaination is still unclear. --DerGraph 13:18, 16 November 2006 (UTC)