Talk:Rainbow table

From Wikipedia, the free encyclopedia

An editor has requested that a suitable Open Directory Project category be found or created for this article. Remove this template after one has been found or created.

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? 7 Relevant Linking 8 History section? 9 Cleaned up Overview 10 Overview 11 Table Entry 12 Quadratic lookup

[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. —Preceding unsigned comment 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)

Agreed. I was going to post exact same comment. This part - "To recover the password, a password cracker would have to generate every possible salt for every possible password" is just plain wrong. Care to reword it ? Alex Pankratov 04:57, 26 June 2007 (UTC)

I took a liberty of removing the above statement. I made few attempts at correcting it, but in a reworded form it did not carry genuinely useful information as it was redundant to the paragraph that follows. Alex Pankratov 06:21, 26 June 2007 (UTC)

I believe the discussion of salts is wrong. Hash tables can still be precomputed if the salt is appended to the hash, as opposed to being prepended saving some of the work, so normally the password entry is actually

    hashed = salt . hash( salt . password) 

and not

    hashed = hash( password . salt )

as described in the document. nuffin (talk) 19:15, 31 May 2008 (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)

I believe it comes from the multiple reduction functions. Martin Hellman's original idea had only one reduction function -- these tables would be 'monochromatic'. Athulin (talk) 07:13, 3 April 2008 (UTC)

[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)

[edit] Relevant Linking

The link to www.freerainbowtables.com has been removed a number of times. I am sorry I did not read this earlier:

If the link is to a relevant and informative site that should otherwise be included, please consider mentioning it on the talk page and let neutral and independent Wikipedia editors decide whether to add it. This is in line with the conflict of interests guidelines.

I believe the site is relevant to the topic, as it is the largest community based rainbow tables generation project. Many table sets are also available for download from this site. More so for free than any other site. I will not personally replace the link as I do not want to break the rules of Wikipedia. —Preceding unsigned comment added by 203.214.3.248 (talk • contribs)

I am a member of the freerainbowtables.com community so take this comment as it is. However, I'd also like to support the addition of the link to this article. The site is a community oriented and a community supported rainbow tables site. All the tables are open to the public to download at will with no strings attached. It is quickly becoming the most viable place on the web to get rainbow tables and though other sites may have more, this site will overtake them all. 66.93.244.36 04:01, 27 February 2007 (UTC)

There are many different free rainbow table sites available, but I wouldn't say any one will "overtake them all". Communities should work together; thats the purpose of distributed rainbow table generation. As said, since the communities should have a clear link to eachother of information and interest, if one link is posted for these type of rainbow table collaborative projects, the others should be posted as well, in the interest of open communication and cooperation of parties. --Silivrenion 12:07, 21 April 2007 (UTC)

The obvious problem here is that Wikipedia is not a link directory, and it shouldn't [have to] link to all projects. I would much rather not deal with checking external links at all — in a perfect world, we would offload that responsibility to some established link directory web sites. This is already encouraged by the external links guideline. Unfortunately, DMOZ does not have a category for rainbow table communities/web sites, and I am not aware of any others. (I have already placed a "directory request" template in the header of this talk page) -- intgr 12:21, 21 April 2007 (UTC)

[edit] History section?

Is the "history" section really necessary? It takes up a good chunk of the article, and ultimately is NOT describing Rainbow Tables, but is instead describing the concept that predated Rainbow Tables. Maybe it is better to just link to an article on the older concept, and keep this article JUST about Rainbow Tables. Konky2000 19:47, 5 November 2007 (UTC)

Is there such article ? If there's not, then I suspect it's going to be quickly deleted on a lack of notability grounds if created. I'd say, the history section should be renamed and trimmed down a bit, but ultimately kept here. Alex Pankratov 20:30, 5 November 2007 (UTC)

Articles on specific companies, products, people, etc. get speedy deleted; technical articles are not. -- intgr [talk] 08:45, 6 November 2007 (UTC)

[edit] Cleaned up Overview

I'm planning to replace existing Overview section, which I find to be too chatty and somewhat confusing, with the following.

[edit] Overview

A rainbow table is a compact representation of related plaintext password sequences (or chains). Each chain starts with an initial password, which is passed through a hash function. Resulting hash is then fed into a reduction function, which produces different plaintext password. The process is then repeated for a fixed number of iterations. Initial password and the last hash value of the chain comprise a rainbow table entry.

Recovering a password using a rainbow table is a two step process. First, the password hash is run through the above reduce-hash sequence. The structure of the table and its reduction function guarantee that the running hash will match a final hash of one of the chains. This yields the initial password of the chain. Second, the iteration is repeated starting with this initial password until the original hash is found. The password used at the last iteration is the password being recovered.

The table content does not depend on the input of the algorithm. It is created once and then repeatedly used for the lookups unmodified.

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.

Any feedback is appreciated. Thanks, Alex Pankratov (talk) 22:09, 21 November 2007 (UTC)

I'm updating the Overview as per above. Please use this thread to discuss any issues with new version. Thanks, Alex Pankratov (talk) 23:05, 24 November 2007 (UTC)

Should it not say "is equivalent to the password being recovered"? After all, more than one password can have the same hash - or are typical password-hashes longer than all feasible passwords? How could this be clearly formulated? PJTraill (talk) 23:03, 9 March 2008 (UTC)

It is not clear from this text that there are several reduction functions -- which is the fundamental idea of the rainbow tables. Nor do I think that the second sentence of the last paragraph is correct: the time-memory tradeoff as I understand is that vs a full look-up table. It's much faster than a rainbow table, but also takes much more space -- the tradeoff then is trading off lookup-time to improve storage space. This is not something unique to rainbow tables -- it was part of Martin Hellman's original idea.79.102.100.41 (talk) 07:07, 3 April 2008 (UTC)

[edit] Table Entry

According to the Overview, the initial password and the last hash value of the chain comprise a rainbow table entry. But from the figures and the example a table entry ends with a password, not a hash value.

84.126.102.72 (talk) 02:42, 9 February 2008 (UTC)

Yeah, there seems to be something wrong with the picture Porttikivi (talk) 14:07, 13 February 2008 (UTC)

[edit] Quadratic lookup

Concerning the use of variable reduction function in rainbow tables vs. the older constant reduction functions, the article points out that the newer method avoids redundant chains due to collisions (which is obviously true); however, it also states As well as increasing the probability of a correct crack for a given table size, this use of multiple reduction functions approximately doubles the speed of lookups. which I don't believe.

Given a chain length of N=100,in the older scheme, a lookup would consist of 100 reduction–hash steps. In the rainbow table proper, however, one would have to run a chain of length one starting with the last reduction function R(100), then a chain of length two starting with R(99), and so on, up to a chain of length hundred starting with R(1). This makes alltogether around N²/2=5000 reduction–hash steps. The quadratic behaviour will tremendously increase the lookup procedure for large chain length.

Did I misunderstand something, or is the article wrong? 77.5.124.57 (talk) 22:43, 6 April 2008 (UTC)