A Simple Low-Overhead Rainbow Table

And thus, the format of our rainbow tables must meet the following goals:
	•	No wasted space
	•	One lookup confirmation of the presence of a match

And with this, we can easily build a format which conforms to these goals.

We start with our directory structure.  We have a tables directory, which we will refer to as "tables/" from here. Within this, we place files named 0000-FFFF, corresponding to the first 2 bytes (in hex) of our CRC.  If no CRC exists that begins with this, the file doesn't exist.

The files themselves begin with a header that corresponds to the following struct:
[code]

struct rainbowHeader_s {
	char                                    magic[4]; // RAIN
	unsigned long long int  offsets[0xFFFF];
};

[/code]

The member `magic' is a magic identifier to both identify the format of the file and the byte order for the system (4E494152 on little-endian systems, 5241494E on big-endian).  The `offsets' member is a bit more complicated, as it stores offsets to string tables once hashes are created for said strings.

To insert a string into the tables, you must do the following:
	•	Hash the string and run a shortening function on the result (we'll discuss later what methods could be used for shortening).  We will use the shortened result 0xDEADBEEF for our examples.
	•	Take the first 2 bytes of the result (0xDEAD) and check for the existence of a matching file in tables/ and if it doesn't exist, create it.
	•	Load the header of the file and look to see if an entry in the offsets table exists for the last two bytes and create one if it doesn't already exist.
	•	Append an entry to the end of the linked list to store the string.