Talk:Rainbow table

Please rewrite article

Someone needs to rewrite much of this article. It is very poorly articulated. Unless one is already very familiar with rainbow tables, it is almost impossible to be able to understand the bulk of this article. I have a background in computer science and I am having trouble following this, but upon reading an article from another source, these concepts are now very clear.

I can rewrite this article when I have time, but I can't rewrite every article on Wikipedia that is written this poorly! Comprehensible explanations are a fundamental purpose of these articles. Just because the authors of an article are not English majors does not mean that clear and articulate explanations should not be expected. —Preceding unsigned comment added by 174.118.8.187 (talk)

[Comment removed. -- intgr [talk] 20:09, 5 November 2010 (UTC)]

Whoa whoa whoa. Off your high horse there, buddy. I'll tell you what makes Anon, above, so important: Anon represents the readership of Wikipedia. The readership is who we, the editors, are responsible to. Wikipedia is for everyone. Anon has the right to say "hey, this article needs work, it's difficult to understand". However, you don't have the right to say "what have you done for Wikipedia". That's not how it works around here. By the way, when you answer someone like Anon, you're representing the project. Your defensive attitude is not the way to do that.

I've tagged the article as needing work. — Hex (❝?!❞) 14:38, 5 November 2010 (UTC)

You're right, I read it now and I'm not proud of what I wrote there. -- intgr [talk] 20:09, 5 November 2010 (UTC)

How about rewriting the opening so that it reads something like this: "A rainbow table is a table of all possible hash values for a particular character set. Helpmethinkofaname

I rephrased the lead, hopefully it reads better now. The definition you gave is not accurate though, rainbow tables are heavily compressed and don't cover all possible values, usually they have 95% or 98% coverage. PS: Type ~~~~ to sign your posts. -- intgr [talk] 03:52, 20 February 2011 (UTC)

Untitled

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

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)

Common uses

The common use section should talk about the common use of Rainbow tables which is what this article is about, not salts in hashes.187.37.49.76 (talk) 11:59, 3 July 2009 (UTC)

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)

No, I think he's right, let's take a look at MD5 for example. Cracking what is essentially a 32 character password is insane, no matter how much space you have to store the tables, and how many eons you have to calculate them. I ran the numbers and even just with numeric passwords, it didn't matter how high I put the settings, I couldn't get the probability of a successful recovery above 0.00% without the disk space calculator overflowing (which happens around the 500 petabyte mark, mind you). Now, I've heard that PHPBB hashes each user's password with MD5 100 times before storing/checking it, so unless rainbow table generators can work around that, I really don't see how one could crack one of those hashes. Even for LM, with only 16 byte hashes, with 1.5 PB of disk space and insanely long chain lengths, I'm looking at 3,700 years of cryptanalysis time for each hash before it fails to find anything with the table's .38% success rate. Oh yeah, and it still wont finish precomputation before the heat death of the universe. So yeah, I'd say multiple hashing works pretty well. —Preceding unsigned comment added by 24.56.210.251 (talk) 22:55, 7 December 2008 (UTC)

No, he's not correct. The issue is that you don't need to generate a table to cover all 32 character hashes; instead, you only have to generate a table covering all hashes that are hashes of valid passwords under consideration. To put it another way, when you apply a hash a fixed number of times that is independent of the user, that's just like applying a single hash function implemented by running the original hash function k times in a row. Nothing changes except the time needed to compute the hash, and to even guarantee that much you need to ensure the hash is nonlinear. Dcoetzee 23:13, 7 December 2008 (UTC)

Further, a double hash such as MD5^2 is ultimately going to be a weaker hash function overall because you've just increased the number of collisions. It now accepts any p where MD5(p) = MD5(pass) as usual, but also any p where MD5(MD5(p)) = MD5(MD5(pass)). The only advantage is that most precomputed work on dehashing these values has been done on MD5 and not MD5^2. MD5^2 is however, in theory, easier to find collisions for and consequently easier to crack. Because of this, salting the pass is a much better solution. Using MD5^100 as mentioned above actually might increase the number of collisions quite significantly and is probably a terrible idea. 71.42.216.123 (talk) 04:54, 9 February 2011 (UTC)

No, you are wrong about collisions:

1) Unless someone is actually trying to find one, MD5 collisions occur with a ridiculous probability, so that's a non-issue.

2) In the ridiculously unlikely event of a MD5 collision, with unsalted hashed passwords, there would be no real danger: some user Bob would be able to log-in with the password of another user Charles (and vice-versa), but only someone looking at the hash database would be able to learn this fact, and unless this person happens to be Bob or Charles he would have no other information about either Bob or Charles' password.

3) In the ridiculously unlikely event of a MD5 collision, with salted hashed passwords, there would be no theoretical consequences at all.

4) No one is trying to find MD5 collisions to "crack" passwords!

5) You are probably confusing MD5 as a non-invertible function (used for storing passwords more safely) and MD5 as a collision-free function (used for digital signatures). MD5 as a collision-free function has been proved unsafe a few years ago, with practical attacks possible and even effective against real world use of SSL certificates. MD5 as a non-invertible function is perfectly safe today, the published theoretical attack against MD5 as a non-invertible function requires insane computing power.

WPcorrector (talk) 05:28, 17 September 2011 (UTC)

Double hashing is now a useless algorithm. Rainbow tables by themselves can handle this - see my first link that will be removed by this team.. In that hash cracking utility, you can reverse the md5 to another md5, then reverse that md5 to the password - as many levels of md5 as you want can be overtaken. I say this is now useless because this can be done only with a rainbow table lookup, and no cracking is required..

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)

How can hash tables be precomputed for salted passwords? You would have to precompute it for each possible salt, which is not feasible. 201.216.245.25 (talk) 17:35, 14 December 2009 (UTC)

For salts, the current attack is to use an md5 cracking algorithm that takes into account the salts. See my links to such tools after it is removed and moved into the discussion space, where it should be.. — Preceding unsigned comment added by 76.23.56.190 (talk) 00:12, 20 May 2012 (UTC)

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)

Brute force and dictionary are the really same things. Only the a priori knowledge about the password, which determines the search space, is different:

"Dictionary" means "clever", while "brute force" means "stupid", where "clever" means assuming cultural knowledge of the person choosing the password (language spoken, spelling variations, prefix and suffix used) and "stupid" means you only assume an upper bound on key length and a set of possible characters.

But ultimately you just have defined some key space that you must then explore, which is really a "brute force" thing. WPcorrector (talk) 05:42, 17 September 2011 (UTC)

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)

I've been trying to find the name's origin for a while too and I'm surprised that no one has added anything about it to the article in the two years+ since this question was asked.

One explanation I've encountered was an off-hand remark by Steve Gibson on the Security Now podcast that the name came from Rainbow Technologies' dongles (the "Sentinel" license manager) -- presumably from successful crack attacks aimed at them. The transcript is here, but some painful googling didn't bear that out at all. In fact, the only real reference I could find was a story that noted such a query/response table would take thousands of years to compile on current versions of the dongle and so cracking groups abandoned that in favor of removing all calls to the Sentinel from the software itself.

Besides, the "Making a Faster Cryptanalytic Time-Memory Trade-Off" paper doesn't treat the term "rainbow" as a proper pronoun. After describing Hellman's previous method, it introduces the term with the sentence "We call our chains rainbow chains" which is the first mention of the word in the paper. This is in the context of the "reduction function" as stated above, but I wish someone could explain the metaphor to us simpletons. Msgohan (talk) 08:11, 27 June 2010 (UTC)

Hmm. I've always thought "rainbow" came from the multiple tables needed to handle each salt. As I recall, the first rainbow tables I heard about were for Unix passwords, which uses 4098 different salts. Around this time we also uses the Rainbow Series to refer to a collection of books. Consequently, I feel that the concept that a salt will defeat a rainbow table is really incorrect. A salt makes the task harder because you need a separate table for each salt. However, I have not found any references that correspond to my recolections. BruceBarnett (talk) 11:07, 6 May 2011 (UTC)

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)

Here's the part that's extremely unclear:

The reduction function takes the results of the hash-function and turns it into another plaintext password guess.

After further reading, my understanding is that the reduction function simply picks a random password from P, using the hash as kind of a pseudorandom seed. Am I correct? This is obliquely implied in the current article, but it's easy to infer that the reduction function does some kind of special magic, when in fact it plays only a minor role. 95.88.6.44 (talk) 22:30, 30 May 2009 (UTC)

Why there is a reduction function is pretty clear; the hash function is a function that maps from password space into hash space. Although the elements of these two spaces are both pieces of data; the spaces are often very different. For example, the input password space in one case could be restricted to alphanumeric text with lengths from 1 to 8. And the output hash space depends on the hashing algorithm, but might be, say, an arbitrary 128-bit binary string. The sizes of the two spaces are very different, so you can't just take the output hash, and somehow use it directly as a password guess. So you need a function to map back from hash space into password space for the next iteration. The function doesn't have to be special or random or anything; pretty much any decent function that maps from hash space into your password space should do, preferably one whose outputs are somewhat well-distributed over the password space. The person who uses your rainbow table will also need to know what reduction function you used. --76.173.203.58 (talk) 23:22, 30 May 2009 (UTC)

I think it would be very helpful to include some of what you just said about reduction function - "any function that maps from hash space into your password space should do, preferably one whose outputs are somewhat well-distributed over the password space" Andreid76 (talk) 20:41, 16 April 2014 (UTC)

The part about the sample reduction function seems wrong to me - 4 characters would not constitute a valid password in that example (6 character alpha passwords). Am I missing something? Andreid76 (talk) 20:41, 16 April 2014 (UTC)

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)

At this time the link to freerainbowtables.com/faq is broken and the site is not responsive. Has it gone away completely? If it is dead then shouldn't the link be removed. BobProulx (talk) 17:08, 5 February 2009 (UTC)

The reference link to Oechslin, Philippe (Mar-Apr 2005). "Password Cracking: Rainbow Tables Explained". (ISC)2 Newsletter. https://www.isc2.org/cgi-bin/content.cgi?page=738. does not resolve to a meaningful page. I think the reference should stay but the url be removed. BobProulx (talk) 17:08, 5 February 2009 (UTC)

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)

Cleaned up Overview

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

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)

You are right indeed: although the search space of any realistic brute force attack is much smaller than the hash values set, a hash collision is possible (yet unlikely). And h(x) = h(y) defines an equivalence condition. WPcorrector (talk) 06:14, 17 September 2011 (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)

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)

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)

Good question - in short, you're right that the behavior is quadratic. The argument about this is in the original paper on page 6. The subtle point not being addressed here is that when using simple hash chains, it's necessary to divide tables into many smaller tables to remain efficient, whereas with rainbow tables they can be t times as large with no adverse effect. The consequence is a factor of t less lookups. Dcoetzee 05:53, 8 December 2008 (UTC)

Defense

"passwords that contain symbols outside the range presupposed, or that are longer than those precomputed"

This wouldn't work against rainbow-attacks. You do not need the original password to hack an account. It's enough to have a password that results in the same hash to be accepted by a system. This paragraph should be deleted in the defense section. 62.218.223.55 (talk) 22:15, 25 September 2008 (UTC)

Actually, the above statement's paragraph holds true for any md5-related hash - all you need is something that goes through the server's md5 algorithm and gets accepted. Without a salt, this means that any value a rainbow table would reverse to is sufficient..

But you'll never find a hash collision by accident. For instance to find a colliding input to a MD5 hash, you would (on average) need to calculate 2¹²⁷ hashes, which is an enormous number. Virtually all human passwords are easier to crack than that. For a sense of perspective, a GPU-accelerated cracker might calculate in the order of 2⁵² hashes per year. Rainbow tables could get you closer, but you'd still be facing astronomical odds. -- intgr [talk] 03:00, 26 September 2008 (UTC)

This defense is a good one. There is almost no chance that an attacker will find a collision. If an attacker were trying to crack any one of 65,536 passwords, he would need to compute (or have tables representing) at least 2¹¹¹ hashes to have a better than 50% chance of finding a collision for any one of them. This is is impossible given current computing power and storage even using large distributed networks. Unicityd (talk) 16:20, 26 September 2008 (UTC)

Self-reference in diagram

Just suggesting eliminating the needless Wikipedia references in the diagram, per Wikipedia:Avoid self-reference. Dcoetzee 00:38, 6 October 2008 (UTC)

Link dead

The link to the (ISC)2 Newsletter in the reference section displays the generic homepage for the site and I can't find the article mentionned ("Password Cracking: Rainbow Tables Explained". (ISC)2 Newsletter. https://www.isc2.org/cgi-bin/content.cgi?page=738).

--212.198.246.189 (talk) 10:29, 24 March 2009 (UTC)

Why does chain count equal chain length?

The article says that if the chains are k elements long (because there are k reduction functions) , you need k chains. Why?174.110.172.156 (talk) 23:13, 14 July 2010 (UTC)

This is when you try to find a hash in the table, I assume. The first use of the word 'chains' refers to the chains actually in the rainbow table (but which have to be recreated, as they are not stored explicitly). The second use refers to the chains created during the look-up operations, when that recreation is done. Athulin (talk) 18:11, 31 July 2010 (UTC)

Faster lookup?

"this use of multiple reduction functions approximately doubles the speed of lookups." - why?

Assuming the "Average" position in the chain (The middle value is the average lookup time for both rainbow and normal tables though rainbow tables get anything towards the end faster and towards the beginning slower), we take a hash 4882 and run it through a 5 iteration chain...

The original table runs it through 2 reductions and 2 hashes and finds the end of the chain, then looks it up for another 2 hashes 2 reductions... total 4 hashes 4 reductions

The rainbow table runs it through Rk-1, 1/1 calculations and Rk-2, 2/2 calculations to find the end of the chain, then another 2 hashes 2 reductions to get the plaintext: total 5 hashes 5 reductions...

What am I missing here? By my math the only time a rainbow lookup is even the same speed as a normal table is when the hash just happens to be at the very end of the chain... In fact the RT should be incrementally slower the further away from the end of the chain the hash lies...

A 5k column chain with the hash at the beginning should be approx 2500 times slower with rainbow tables... Where is my math wrong?—Preceding unsigned comment added by 87.195.101.155 (talk) 20:35, 14 September 2010 (UTC)

Just an idea: single-function chains degenerate easier. Once a hash value has been reached for the second time during a lookup, performing the remaining operations on that chain are wasted, becuase they have already been done before. With the rainbow tables, this happens much less often -- it needs to occur in the same position in the chain. So perhaps 'speed' does not refer tocount of operations, but count of significant operations? Where tracing a chain tail that has already been traced would count as non-significant. Athulin (talk) 10:09, 10 January 2011 (UTC)

Twidwell's hash

I am removing the section on "Twidwell's hash." The key section is below:

For 'Twidwell's hash', the developer uses an asymmetric key infrastructure in addition to hashing. i.e. a public/private key pair is generated, and the public key is stored while the private key gets dropped altogether. To perform the hash, the developer first encrypts the password with the stored public key, and then hashes the result, storing the result in the database. MD5, sha-1, etc. can be used as the hash function, stronger hashing functions are advised. Later, when the database is broken into, the attacker arrives through the rainbow table at the encrypted value, instead of a salt(s)+value(s), or just the possible value(s). There is nothing the attacker can use at this point to arrive at any sort of password in plain text, since it's in an encrypted form at the moment a reverse lookup is done on the hash. Since the site has discarded the only key that can decrypt the encrypted value, no original password can be obtained (Assuming a stable encryption function - public/private key infrastructures have their weaknesses, but stronger asymmetric key algorithms can be employed). The weakness here requires generally a crypto-analyst to break it, which is indeed stronger than reverse lookups, brute forcing, or scripts. Because the attacker now has nothing they can enter into the login form to gain access, rainbow tables and reverse lookups are rendered a useless activity; and most likely any determination of the private key cannot be scripted. This system of password protection is simple to implement, which the majority of development needs, and should be particularly affective at stopping rainbow-table based security issues.

This appears to be WP:Original Research, and further it does not accomplish what it claims. The problem with this approach is that an attacker can simply duplicate the Twidwell's hash algorithm and produce the same hash values for a given password. These can be compared to the hash values store in the system-under-attack's database, just as they would be with any other hash. There is no need to perform a public key decryption operation to check a guessed password. If the same public key is used for all accounts, a rainbow table will still be effective. If a separate public key is used for each account. the effect will be the same as using ordinary salt, and salt is simpler to implement yet completely effective against rainbow tables, as long as the salt is big enough. --agr (talk) 19:11, 15 May 2012 (UTC)

--97.88.168.200 (talk) 09:38, 31 December 2014 (UTC) 'Twidwell's hash seems to be a discussion that points to a non-existent web-site and a link to a non-existent post... plus, there is no relevance to include this in a discussion on rainbow tables.

Response

^^ Think about just how much brute-forcing that would entail.. Using one public key for the entire account would mean you would need to brute-force, just like an md5 rainbow table, all possible password combinations until you found a match for all of them. A dictionary-based attack would probably be employed first. However, it would still take years, and the public key could change at any time, and applied to the database on user login just like switching any md5-based algorithm. I don't know the specifics on how long it would take to brute-force your way from every possible password combination into an encryption, then running an md5 to find a match. My guess is it would take approximately the same amount of time as producing a single rainbow-table - years. Then, running a brute force on every possible encryption key would be a ridiculous approach, since now you're talking about producing a brute-force attack on every possible encryption key, for every possible password, and being able to reverse the md5 of the result.. You would effectively be creating millions or billions of rainbow tables, which is entirely infeasible..

If the above paragraph holds water, this would mean that an attacker would be forced to use a quicker method to obtain the passwords, meaning that they would need to somehow break the encryption algorithm, which is currently not in widespread knowledge except by use of supercomputers. PGP Discussion.. — Preceding unsigned comment added by 76.23.56.190 (talk) 02:14, 20 May 2012 (UTC)

However, we need some discussion on this topic, to move forward. I have found, in my experience, that any combination of salting can be cracked, and the rainbow table gets used for other purposes, when a reversal of an md5 is needed. See my second post in this discussion area for why I have come to that conclusion...

You may be asking how reversing a salted hash is possible - this is because just as I postulated in a post regarding reversing a hash without a rainbow table (which I believe I removed to not give away ideas), it may have been possible to reverse a hash through a separate algorithm if you already knew most of what went into the hash (salt(s)+padding). I found it has already been done. Therefore, any combination of hashing and salting will in the future inevitably be useless, however they are doing this, because in my next discussion post I point you to tools that accomplish exactly the reversal of the different ways you have described in this wikipedia article as ways to modify an md5 to protect against any rainbow-table approach.

Yes, salting makes rainbow-tables more difficult because brute-forcing every possible combination of values takes time. However, this is only because these rainbow tables haven't had processing time to cover a longer character combination - when they do, it will cover the salt(s)+the password, and the attacker will know by the salts exactly which reversal is correct. Rainbow tables at this time work particularly well at reversing an md5 to another md5, and reversing up to 18 characters.. So applying a long salt currently stops that, however..

Applying a salt means we know what went into the hash at a certain point in its calculation. Since we have algorithms that can crack that, this makes a combination of cracking and rainbow-table lookups necessary in order to break into the password. And lo and behold, this is exactly what is going on in the hacking community, rendering your approaches useless..

What this means is that all of the above options of combining salt and hashing is irrelevant by today's standards. I noticed someone discussing ways to hide the salt - if that is possible then there may be your answer...

Today's tools on password cracking/reversal..

Thank you for that rather, weak presentation, moderators of this page.. The above, defenses, are lacking any credible security sources. Any combination of salting and hashing can always be cracked, reversed, etc. For examples in the field see A quick password cracker for straight md5 more specific hash-related cracking, specifically useful with differing salts - when not found it runs a cracking utility until cracked A windows utility used to crack hashes for any combination of salts. You need a better method of storing passwords. All of the above is actually, rather, weak; and in time any salt combination will be reversible. — Preceding unsigned comment added by 76.23.56.190 (talk) 00:14, 20 May 2012 (UTC)

There is nothing on any of the sites you mention above that suggests they can attack salted hashes by any form of look-up table. They all appear to use brute force attacks when salt is used. (Salt does not prevent brute force attacks against an individual password.)

Your say that finding a way to "reverse a hash through a separate algorithm if you already knew most of what went into the hash (salt(s)+padding)" "has already been done." This is a most remarkable claim and I would urge you to disclose the method or any evidence of its existence in a suitable forum. However Wikipedia is not the place to publish WP:Original research.

As for the difficulty of pre computing hashes using your public key method, I would point out that it is a distributed problem and both cyber-criminals and large security organizations have access to thousands of computers that can be harness for such endeavors. There are also some computational efficiencies possible when computing a large number of encryptions using the same public key. Note that using a single public key for a site would allow an attacker who got hold of the entire file of encrypted passwords to attack them all in parallel. Thousands, indeed millions of passwords can be brute forced in essentially the same amount of time as it takes to brute force on password. Salt prevents such parallel attacks as well.--agr (talk) 12:30, 21 May 2012 (UTC)

The last link shows ways to break the following combinations of salt+hashing. I'll list them as they listed it on that site as well. There are numerous tools out there that do this same thing:

   MD5
   md5($pass.$salt)
   md5($salt.$pass)
   md5(md5($pass))
   md5(md5(md5($pass)))
   md5(md5($pass).$salt)
   md5(md5($salt).$pass)
   md5($salt.md5($pass))
   md5($salt.$pass.$salt)
   md5(md5($salt).md5($pass))
   md5(md5($pass).md5($salt))
   md5($salt.md5($salt.$pass))
   md5($salt.md5($pass.$salt))
   md5($username.0.$pass)
   md5(strtoupper(md5($pass)))
   SHA1
   sha1($pass.$salt)
   sha1($salt.$pass)
   sha1(sha1($pass))
   sha1(sha1(sha1($pass)))
   sha1(strtolower($username).$pass)
   MySQL
   MySQL4.1/MySQL5
   MD5(Wordpress)
   MD5(phpBB3)
   MD5(Unix)
   SHA-1(Base64)
   SSHA-1(Base64)
   SHA-1(Django)
   MD4
   NTLM
   Domain Cached Credentials
   MD5(Chap)
   MSSQL
   SHA256
   MD5(APR)
   SHA512
   SHA-512(Unix)

I don't see how the continued claim that salting the password is any longer feasible. What I'm saying is we would be better off coming up with something new... — Preceding unsigned comment added by 75.13.12.166 (talk) 22:56, 1 July 2012 (UTC) This also shows me that 1. nobody in the security world is trying these cracking tools to see what happens, and 2. nobody in the security world is really that aware of what kind of password cracking software is out there. These are just things I found googling, and I ran them with various combinations of salting - they are fairly effective at breaking it, against said claims of using salt. — Preceding unsigned comment added by 75.13.12.166 (talk) 22:59, 1 July 2012 (UTC) I also wasn't clear on reversing an md5. Yes, it's still a brute-force method. It's just that since you already know most of it, the time is greatly reduced.. The goal of reversing an md5 isn't to create the exact match, but rather one such match. In that sense, it is possible to reverse an md5 rather quickly, without the use of a rainbow table, if you know the salt.. If you think that is remarkable you don't know your algorithm to any great detail. — Preceding unsigned comment added by 75.13.12.166 (talk) 23:04, 1 July 2012 (UTC) And then that brings me to the final, which is how long would it take to generate a rainbow table. My assumption was it would take a pretty long time. That calculation may have been largely off. I read somewhere on a single machine it can take as little as a few days. That makes many of our approaches infeasible, since we know we can brute-force rather quickly.

So I guess that leaves us with the age-old problem of how do we properly protect the passwords in storage.. — Preceding unsigned comment added by 75.13.12.166 (talk) 23:09, 1 July 2012 (UTC)

97.88.168.200 (talk) 09:43, 31 December 2014 (UTC)I also do not see personally the relevance in any of the discussion of the previous two segments regarding rainbow tables. Are we just swinging to swing on a swing on wikipedia?

Space-Time Tradeoff

Hey, folks! I think the bit in the very beginning of the article might be backwards. It reads:

"It is a practical example of a space-time tradeoff, using more computer processing time at the cost of less storage when calculating a hash on every attempt, or less processing time and more storage when compared to a simple lookup table with one entry per hash."

Calculating a hash on every attempt would take _no_ storage and _lots_ of processing time, a simple lookup table would take _little_ processing time and _lots_ of space. A rainbow table is a compromise, taking less processing time than calculating every hash, and less storage than a full lookup table. Maybe that's what the bit above meant, but I found it a bit unclear. Thanks! 141.213.55.122 (talk) 17:29, 1 March 2013 (UTC)Scott (sawalls at umich dot edu)

"Rainbow Tables" Subheading

It seems like in an article called "Rainbow Table", "Rainbow Tables" is NOT an appropriate subheading.

Billiam1185 (talk) 18:12, 20 August 2013 (UTC)

"Twidwell's hash?"

Someone pointed this out to me this morning. The discussion on here seems to point to a pretty old blog of mine that I had back in ~2010. I do remember talking about the problem with storing passwords in a database, and discussing the differences between encryption and hashing.

The conclusion from that blog post should have been that it does not matter what method we use to store the data - any breach of the server can easily expose the entire uname/password for any current login system.

This is also true of using certificates instead of passwords, which was the result of a government task force around that time attempting to create better security for internet logins. If you can remember, that was around 2010 and the reason for my original blog entry discussing it, and no - that government taskforce also decided certificates were not much better than current methods and did not proceed with any solution at all.

If you really want my personal opinion, I feel there is no way given current systems and how that relates to any login credentials on the personal device or the server side to actually secure a login for any user or any one site. I do agree with your discussion that salting generally seems to create a user-specific or site-specific breach that helps to mitigate the risk, but actually does nothing to provide any form of enhanced security.

The ending conclusion of that article should have been that to secure a website with a login on the server side we need to better secure the database and operating system instead. The same is true of the perspective of the user's device.

At any rate, I'm happy you all decided to discuss something I posted a while ago, but it seems the concepts were pretty skewed. Thought I would clarify what that blog actually stated for you all.

[Edit] That article never referenced any specific 'new hashing method', btw...

Regards, Jeremiah T.

Salt protects against two types of threats, precomputed tables, and the ability to crack a large set of stolen credentials in parallel. Given the processing power available today salting does not provided complete security. Simple hashes of weak to moderate passwords can be broken by brute force even with salt. But a frequent argument in security that I find problematic goes: we needn't implement measure X against threats A and B because threats C, D and E exist that measure X fails to prevent, even though measure X is cheap and straight forward. At this point no one seems to know how to completely "secure the database and operating system" so I would argue that doing what can, including salt, key stretching and enforcing larger password size, is really essential and long overdue.--agr (talk) 22:35, 31 December 2014 (UTC)

I don't think you understood the conclusion of this. If the original problem was brute forcing a login page (b) or obtaining access to the database (d), both of which led to password leakage (p), there is no way of storing a password (p) in a database (d), in any of the aforementioned attempts, even with hashing methods, that will never yield the original (p) for the entire site given a database breach (d). You stated this yourself, yet then you alluded to the idea that it should be implemented. Instead, I stated that we focus on securing (b) and (d) - NOT spending all of our time trying to 'hide' (p). I hope that is not too difficult of a concept to grasp. The correct answer is to observe that there is no way to 'hide' (p) in (d), and therefore we should spend our time securing databases and servers. However, if we want to assume that we cannot secure the database or operating system (server or client), then the suggestion becomes to create a more secure login method. However, as I discussed above, we did not find a more secure way to do authentication, at least for now. So if all topics of 'securing a login' are a non-starter, and even with salt, key stretching and enforcing larger passwords there still exists vulnerabilities, then absolutely - what are we even talking about at this point? — Preceding unsigned comment added by 97.88.168.200 (talk) 21:49, 4 January 2015 (UTC)