Rainbow Tables / a Vleeptron wtf moment / decrypt THIS, mofo!

an Enigma coding/decoding machine used to encrypt radio communications by the German military during World War II

French military security stole the plans, couldn't make headway with them so gave them to Polish mathematicians, who cracked the Enigma code first, then fled with their electromechanical automatic solving "bombes" to England, where a team at Bletchley Park (halfway between Oxford and Cambridge) led by Alan Turing invented the first high-speed digital computer to tackle the ever-more-complicated German code system. People with skills in literature, languages and word games were as valuable to the team as mathematicians.

Okay, now if anyone has the slightest Clew or Clue or Insight into what the hell these people are talking about, The Vleeptron Advanced Mathematics Resarch Institute (VAMRI) would be very grateful.

I stumbled on these completely mysterious Rainbow Tables by clicking around the dutchpowercows site.

There are ultra-hard codes which the distributed / cooperative computing community is trying to crack. (Sometimes big $$$ prizes!)

So I can tell you that a Rainbow Table is some sort of Platonic Object, or Database, big-ass list of a huge number of numbers.

But what can you do with it? Can it walk the dog? Can it brew coffee? Can it entertain the kiddies?

This Philippe Oechslin dude, I'll bet he's way smart. I wonder what kind of music he likes, I wonder what his hobbies are.

Cryptography seems to be experiencing an explosive challenge from Amateurs with computers and, worse/better, access to giant networks of thousands of cooperating PCs. Big national governments thought they had the monopoly on this Arcane Hobby, because they were the only institutions who could afford the supercomputer hardware.

Woltman's Inequality:

5000 PCs > 1 supercomputer

Anyway, wtf ........ ????

===========================

Your continued donations keep Wikipedia running!

Rainbow table

From Wikipedia, the free encyclopedia

A rainbow table is a lookup table offering a time-memory tradeoff used in recovering the plaintext password from a password hash generated by a hash function, often a cryptographic hash function. A common application is to make attacks against hashed passwords feasible. Salt is often employed with hashed passwords to avoid this attack.

History

Rainbow tables are a refinement of an earlier, simpler, but less efficient algorithm that used the inversion of hashes by looking up precomputed hash chains.

Each table depends on the hash function and the reduce function used. The reduce function is a surjective ("onto") function which maps a hash to a password using the desired character set and password length. Therefore, a reduce function for lowercase alphanumeric passwords of 8 characters length is different than a reduce function for case-sensitive alphanumeric passwords of 5-16 characters length.

A chain is a sequence of passwords. A starting password is chosen, and the following is done to get the next one in the chain:

reduce(hash(a password)) ? next password

After a chain containing a suitable number of passwords is created, the final password in the chain is hashed, and the final hash and the starting password are stored together in the rainbow table.

To reverse a hash, look for it in the table. If it isn't found, the following is done to get another hash to try:

hash(reduce(a hash)) ? next hash

This is repeated until a hash is finally found in the table.

When a match is found, the original password that started the chain that ended with that hash can then be used to generate all the other passwords, and hence hashes, in the chain. Each of the hashes thus generated will be checked to against the original target hash, thus hopefully revealing the correct password.

The end result is a table that contains statistically high chance of revealing a password within a short period of time, generally less than a minute. The success probability of the table depends on the parameters used to generate it. These include the character set used, password length, chain length, and table count.

Success probability is defined as the probability that the plaintext can be found for a given ciphertext. In the case of passwords, the password is the plaintext, and the hash of the password is the ciphertext, so the success probability is the probability that the original password can be recovered from the password hash.

Rainbow tables

Rainbow tables use a refined algorithm by using a number of different reduction functions to create multiple parallel chains within a single "rainbow" table, reducing the probability of false positives from accidental chain collisions, and thus increasing the probability of a correct password crack. As well as increasing the probability of a correct crack for a given table size, the use of multiple reduction functions also greatly increases the speed of lookups. See the paper cited below for details.

Rainbow tables are specific to the hash function they were created for e.g., MD5 tables can crack only MD5 hashes. The theory of this technique was first pioneered by Philippe Oechslin [1] as a fast form of time-memory tradeoff [2] (PDF), which he implemented in the Windows password cracker Ophcrack. The more powerful RainbowCrack program was later developed that can generate and use rainbow tables for a variety of character sets and hashing algorithms, including LM hash, MD5, SHA1, etc.

Defense against rainbow tables

A rainbow table is ineffective against one-way hashes that include salts. For example, consider a password hash that is generated using the following function (where "." is the concatenation operator):

hash = MD5 (password . salt)

To recover the password, a password cracker would have to generate every possible salt for every possible password -- a rainbow table would not necessarily give any benefit.

Salts will, in effect, extend the length and potentially the complexity of the password. If the rainbow tables do not have passwords, the length (e.g. 8 bytes password, and 2 bytes salt, is effectively a 10 byte password.) and complexity (if the salts aren't alphanumeric, but the database only has alphanumeric passwords) then it will not be found. If found, one will have to remove the salt from the password before it could be used.

Also, Rainbow tables tend to have little or no success when extrapolating outside the range of symbols or password length computed into the table. So, choosing a password that is longer or contains symbols not accounted for inside a Rainbow table can be very effective. Because of the sizable investment in computing processing, Rainbow tables beyond 8 places in length are not yet common. However, certain intensive efforts focused on LM hash, an older hash algorithm used by Microsoft, exist in the public domain; for example, the rainbow table available from the Shmoo Group.

Common uses

Nearly all distributions and variations of Unix, Linux, and BSD use hashes with salts, though many applications use just a hash (typically MD5) with no salt. The Windows NT/2000 family uses the LAN Manager and NT LAN Manager hashing method and is also unsalted, which make it one of the more popularly generated tables.

References

* Making a Faster Cryptanalytical Time-Memory Trade-Off, Philippe Oechslin, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings. Lecture Notes in Computer Science 2729 Springer 2003, ISBN 3-540-40674-3

* Rainbow tables explained, Ph. Oechslin, (ISC)2 Newsletter, Mar-Apr 2005

External links

* Ophcrack page by Philippe Oechslin The original rainbow table research with online demo

* Project RainbowCrack

* How Rainbow Tables work An easy to read article on how Rainbow Tables work

Categories: Cryptographic attacks | Search algorithms | Data structures

Powered by MediaWiki
Wikimedia Foundation

* This page was last modified 15:21, 27 January 2007.
* All text is available under the terms of the GNU Free Documentation License. (See Copyrights for details.)
Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a US-registered 501(c)(3) tax-deductible nonprofit charity.