MySQL 3.23 hash algorithm

h1[0] = 0x50305735;
h2[0] = 0x12345671;
sum[0] = 7;

h1[i+1] = h1[i] ^ (((h1[i] & 63) + sum[i]) * password[i] + (h1[i] << 8));
h2[i+1] = h2[i] + ((h2[i] << 8) ^ h1[i+1]);
sum[i+1] = sum[i] + ch[i];

Everything is done in 31 bit integer math and you can do (x & 0x7fffffff) to each operation or just once at the end to the last h1 and h2.


Prefixes

We want to reverse this algorithm and the unknowns are "sum" and "password". This is easy enough, all you do is pick a target sum and a password suffix. Let's choose a target sum of 743 (736+7).

You can choose any prefix that has a sum of 743. I like to pick contiguous character sets with a fixed length to make it easy.

Prefixes that are [a-z]{7} with a sum[7] of 743:
7 + a (97) + a (97) + a (97) + a (97) + h (104) + z (122) + z (122) = 743
7 + c (99) + c (99) + c (99) + p (112) + a (97) + s (115) + s (115) = 743
There are 51,681,735 prefixes:

aaaahzz aaaaiyz aaaaizy aaaajxz aaaajyy aaaajzx aaaakwz aaaakxy aaaakyx aaaakzw
aaaalvz aaaalwy aaaalxx aaaalyw aaaalzv aaaamuz aaaamvy aaaamwx aaaamxw aaaamyv
aaaamzu aaaantz aaaanuy aaaanvx aaaanww aaaanxv aaaanyu aaaanzt aaaaosz aaaaoty
...
ugcudga ugcueaf ugcuebe ugcuecd ugcuedc ugcueeb ugcuefa ugcufae ugcufbd ugcufcc
...
zzfacaa zzfbaab zzfbaba zzfbbaa zzfcaaa zzgaaab zzgaaba zzgabaa zzgbaaa zzhaaaa

We calculate the hashes of these prefixes and store them in ram to be searched.
I currently store each of these as:

struct prefix
{
	union
	{
		uint64 hash;
		struct
		{
#ifdef ARC_LITTLE_ENDIAN
			uint32 hash1, hash2;
#else
			uint32 hash2, hash1;
#endif
		};
	};
	uint64 pw;
};

Reversing suffixes

Let n be the length of the unknown prefix (in the code this can be 0).
Let m be the length of the suffix.
Note h1[n+m] and h2[n+m] are known and is the hash you are trying to crack.
Let's choose a password suffix of "bdfhj".

char suffix[m+1] = "bdfhj";

sum[n+m] = 743 + 98 + 100 + 102 + 104 + 106;

for (i = n + m - 1, j = m - 1; j >= 0; i--, j--)
{
	password[i] = suffix[j];

	// Reverse sum 
	sum[i] = sum[i+1] - password[i];

	// Reverse h2
	tmp   = h2[i+1] -               h1[i+1];  //  8 bits reversed
	tmp   = h2[i+1] - ((tmp << 8) ^ h1[i+1]); // 16 bits reversed
	tmp   = h2[i+1] - ((tmp << 8) ^ h1[i+1]); // 24 bits reversed
	h2[i] = h2[i+1] - ((tmp << 8) ^ h1[i+1]); // 31 bits reversed

	// Reverse h1 (password[i] must be even [you can reverse odd characters but it is harder])
	tmp   = h1[i+1] ^ (( h1[i+1]   + sum[i]) << 1);                       //  2 bits reversed
	tmp   = h1[i+1] ^ (( tmp       + sum[i]) * password[i]);              //  3 bits reversed
	tmp   = h1[i+1] ^ (( tmp       + sum[i]) * password[i]);              //  4 bits reversed
	tmp   = h1[i+1] ^ (( tmp       + sum[i]) * password[i]);              //  5 bits reversed
	tmp   = h1[i+1] ^ (( tmp       + sum[i]) * password[i]);              //  6 bits reversed
	tmp   = h1[i+1] ^ (((tmp & 63) + sum[i]) * password[i]);              //  8 bits reversed
	tmp   = h1[i+1] ^ (((tmp & 63) + sum[i]) * password[i] + (tmp << 8)); // 16 bits reversed
	tmp   = h1[i+1] ^ (((tmp & 63) + sum[i]) * password[i] + (tmp << 8)); // 24 bits reversed
	h1[i] = h1[i+1] ^ (((tmp & 63) + sum[i]) * password[i] + (tmp << 8)); // 31 bits reversed
}

We now have h1[n], h2[n], and sum[n] is 743. So all we do is look up h1[n] and h2[n] in the hash table. Don't forget to do (h1[n] & 0x7fffffff) and (h2[n] & 0x7fffffff). If it is found append the suffix and output the answer. Otherwise try a different suffix. Every time you do a look up in the hash table it is equivalent to trying every prefix in the hash table with the given suffix.


Rainbow tables

Also using rainbow tables won't help much if at all. Since if you double the chain length it requires four times more work, but you only get twice as many passwords in the same amount of memory. Also if you use the minimum chain length then it is the same thing as a hash table. So you start out at the same speed then start decreasing performance. It might help if the bottleneck is ram IO, but only for small chain lengths like 5.