This is Part 4 of a five part series:

  1. Introduction
  2. Encryption and Hashes
  3. Simple Hashes and Collisions
  4. Reduction Functions (you are here)
  5. Rainbow Tables and Chains

Reduction functions are at the heart of how rainbow tables work.

To understand reduction functions, lets look at a set of two-digit values that are “encrypted” into four-digit hashes.  For example, using the sample hashing algorithm described in Part 3, the number 10 is encrypted into 0823:

 p     h
10  0823

Now, imagine if we had a special function that could somehow map a 4 digit hash to a 2 digit number.  Because hashes are irreversible, the two digit number is not the original password.  But, it is a two digit number, which means it is a valid password.  For example,  a really simple reduction function could take the last two digits of a four digit number.  That would map the hash 0823 into the plaintext 23:

   h    p
0823   23

That’s all a reduction function is – a function that consistently maps a hashed value into a valid plaintext value. It is worth repeating that the reduction funtion is NOT the inverse of the hash.  In the example above, 0823 “reduces” to 23, but 23 does not hash into 0823 (23 hashes into 5603).

It is also important that the results of the reduction function be valid plaintext. This is easy to do in our samples where we’re dealing with two and four digit numbers. But let’s say you are dealing with a system that allows passwords to be only alphanumerics, no special characters.  If your reduction function results in characters like !,@,#, or $, then you’ll be saying !@#$ because you’ll get invalid plaintext!

In part 3, we looked at the fact that all encryption algorithms can have collisions.  This is also true for reduction functions.  In fact, the situation tends to be worse for reduction functions, because chances are that your maximum password size is much shorter than the size of your hashed values.  In our simple example, we’re mapping four digit numbers into two digit numbers.  Clearly, we’ll frequently collide!

The collisions are a real problem for rainbow tables.  One strategy to reduce (but not eliminate) their impact is to use multiple reduction functions.  In Part 5, we talk about R1 and R2.  In those samples, R1 is our function above – the last two digits.  R2 is equally simple – it just takes the first two digits.

Let’s go look at rainbow tables in Part 5!

  1. Introduction
  2. Encryption and Hashes
  3. Simple Hashes and Collisions
  4. Reduction Functions
  5. Rainbow Tables and Chains (next)
About these ads