Writing rainbow tables or lookup tables?

[vailixi]

I have a pretty good idea how to write out hash/string pairs in from a wordlist or with nested loops in C++. I'm fine with saving this stuff to a text file because I've been loading the stuff into MySQL tables so I can search for them easily.

But I was curious about how one goes about creating rainbow tables. I want to write my own lookup tables mostly for a better understanding of how they work but l also want to customize the way the program looks up a hash.

Can I just convert a delimitted text file to .rt or .rtc? Basically I have figured out how to write out texts and hash but I want to take it a little further with a way to put them into a lookup table and index the memory locations into a hierarchical structure kinda like you would do with hyperlinks on a web site.

So for example my hash is something like ZzaFDGwfhi423i9E7xz81a... it will start searching at ZzFD... instead of searching through the entire table starting at AAAA or whatever. Also do table lookups already do this. I would think someone else has already thought of something like this an implemented it. It seems like using the memory locations for certain strings as starting points would cut the search time exponentially. I really don't know that much about lookup tables to begin know what the best way of going about this.

Can anybody point me in the way of some suggested reading on the subject?

Here's some simplified examples of what I've been doing.

//Simple example that converts a wordlist from plaintext to plaintext and hash pair tab delimited.
#include <string>
#include <sstream>
#include <iostream>
#include <cctype>
#include <fstream>
#include "md5.h"
using namespace std;
int main ()

{ string line; ifstream infile ("/path/file.txt");

if (infile.is_open())


{ while ( getline (infile,line) )

cout << line << char(9) << md5(line) << endl;

infile.close();
} else cout << "Unable to open file";
return 0; }

Might be wrong I just grabbed a bunch of stuff and copy pasted from some of my source without including a lot.

//Simple version of a string generator that uses nested loops to run through and echo out strings in order like brute force.
#include <iostream>
using namespace std;

int d = 0;

int main()
{



for (int a = 97; a <= 122; a++)
{

for (int b = 97; b <= 122; b++)
{

for (int c = 97; c <= 122; c++)
{
for (int d = 97; d <= 122; d++)
{
//only does four characters if you want more make more loops.
cout << char(a) << char(b) << char(c) << char(d) << endl;
}
}
}
}
    return 0;
}

[Sitwon]

What you seem to be describing is a simple hash lookup table, not a rainbow table. Rainbow tables are different from hash lookup tables. in particular, they are much more compact. They work by computing hash chains and then only storing the end-points of the chains. This technique drastically reduces the amount of storage space required at the expense of requiring a bit more computation in order to perform the lookup operation.

You can read about it in more detail on Wikipedia. http://en.wikipedia.org/wiki/Rainbow_tables

Also, the way you have designed your brute force generator is not scalable. You should not need to paste more loops around it to increase the string length. That's a lot of repeated code. Think about how you might write a generator that can create strings of an arbitrary length with no more than two loops. There are many different solutions.

[vailixi]

Gives me a better understanding of what is going on. You seem to have a pretty good understanding of this stuff.

So hypothetically. I have about a 120GB worth of wordlists. I want to create all of my various hash types and store them in a array of drives. What kind of file should a guy use for lookup tables? Basically I want to be able to create a block of memory for each entry that is the same size so I can use some kind of exponential function against the hash to calculate the memory location of the corresponding plaintext value. In short say you have an 8 character wordlist and a corresponding hash value that is say 32 characters. All of them are alphaloweruppernumeric so it's like (62^8) + (62^32) different addresses. If I generate my entire list of hashes for the entire space and compare them to my list of plain text and hash pairs and insert the plain text value for each hash that has a corresponding value within the wordlist. I can accurately calculate the memory location of the hash and string pair and get a match. I'm pretty sure that would be about the fastest way to get a match. It would be faster than reading through a bunch of files and running comparison operators on every entry.

What types of files would be good for storing this kind of stuff?

Edited October 22, 2013 by vailixi

[Sitwon]

Are you familiar with binary trees?

[Jason Cooper]

All of them are alphaloweruppernumeric so it's like (62^8) + (62^32) different addresses. If I generate my entire list of hashes for the entire space and compare them to my list of plain text and hash pairs and insert the plain text value for each hash that has a corresponding value within the wordlist. I can accurately calculate the memory location of the hash and string pair and get a match. I'm pretty sure that would be about the fastest way to get a match. It would be faster than reading through a bunch of files and running comparison operators on every entry.

What types of files would be good for storing this kind of stuff?

Before you start trying to code something for this I suggest sitting down and working out how much space (62^8)+(62^32) actually takes up.

The method you are trying is a time-memory trade off. Effectively it means that the more you precompute the faster the problem can be solved, but conversely the faster you want to solve the problem the more resources have to have been spent on the precomputations. In this case the precomputations you are proposing would require too much space to be practical (unless you are a large corporation or a nation state).

Rainbow tables do fall into the same category but they have a clever twist that reduces the amount of storage that they require (note this isn't magic, it is gained at the cost of increasing the time it takes to solve the problem).

On another note, if you have already been storing your passwords and their hashes in a database table then just making sure that those fields are indexed will aid looking up the values. Any good database will have indexing algorithms capable of doing fast lookups on large tables. Just be very sure of how much data you are going to want to put into the database (hint if you tried to store 62^8 entries in a table you would find it had 218,340,105,584,896 rows).

[vailixi]

You're definately right on the storage. I'm going to figure out another way to do this.