Cryptography - rainbow tables and the purpose of the reduction function

Posted on 2011-04-27
Last Modified: 2012-05-11
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
Question by:Johny_Brav0
    LVL 38

    Expert Comment

    by:Rich Rumble
    To store the plain-text and hash of a certain hash in a much much smaller space, let's use LM for example, 69 printable chars, 7 chars max. LM is case insensitive, all uppercase A-Z, 0-9, space, and all other chars on the keyboard. Just storing all possible combinations of the plain-text will take up over 7gig's right there. Then if we add the hash's (16 chars long each) and you essentially multiply 7gig by 16 and get 112gig... add a space or some other separator to differentiate between hash and plain-text and it jumps 7gig more... I think my math is off, 112/119G still seems too small.
    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:
    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...


    Author Comment

    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.
    LVL 38

    Accepted Solution

    LanMan hash, windows default until Vista and greater came around:
    The "reduction" function is the matching part. Building RT is technically slower than exhausting all possible combinations, mainly due to I/O of a hard-drive vs the I/O of matching in memory. But once a RainbowTable is written to disk, searching it is magnitudes faster. A rainbowtable is a sorted, and reduced data set, in essence. So instead of storing the complete hash, or the complete plain-text, only a certain length are stored. So when you load a password hash to search for, the RT program perhaps only looks for the first 6 chars of the hash, rather than the entire hash. When it finds matches, and it will find several when the length of the hash is truncated to 6, it will look at the plain-texts that go along with those "matches" and then it will do the full comparison of the hash...
    The partial hash "598DDC" matches the following plain-texts: as | 3M~!2a | ((((ha0 | _*,ss4k | :.,<<  |
    So the chain is:
    as          = 598DDCE280126E140 <--- full hashes
    3M~!2a   = 598DDC3B609DD44B
    ((((ha0   = 598DDCE1D662609E1
    _*,ss4k  = 598DDCDB96E95CF42
     :.,<<      = 598DDCC96F750993C
    Again, my example is over simplified, but it should give you a visual of how it's done. These plain-texts (above) all have hashes that begin with 598DDC at the beginning. So the rainbow table knows that to find the rest of the hash for an absolute match, it will have to fully hash (in memory) the plain-texts listed in the chain. It's never a 1-to-1 match, again that would take up an incredible amount of space. The LM hash again is limited to 69 chars and limited to 7 chars in length, other hashes use all 96 chars on the keyboard, far less limited in length (usually) and are salted, and salted hashes are not good candidates for RT's unless a fixed salt is used. LM rainbowtables are 99.9% effective and occupy 64Gig's of space.
    LVL 60

    Expert Comment

    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. and maybe do a dictionary attack (crossing finger).


    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 @

    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.

    Author Comment

    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.
    LVL 38

    Expert Comment

    by:Rich Rumble
    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.

    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Join & Write a Comment

    There are many reasons malware will stay around and continue to grow as a business.  The biggest reason is the expanding customer base.  More than 40% of people who are infected with ransomware, pay the ransom.  That makes ransomware a multi-million…
    When the confidentiality and security of your data is a must, trust the highly encrypted cloud fax portfolio used by 12 million businesses worldwide, including nearly half of the Fortune 500.
    Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.
    Here's a very brief overview of the methods PRTG Network Monitor ( offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…

    754 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    20 Experts available now in Live!

    Get 1:1 Help Now