I have some spare time, and a few hundred DJB2-hashed values sitting around. I thought I'd try to do something "useful" and invert DJB2, such that I could calculate the plaintext of the hashes (which has long since been lost, a fact that is often bemoaned).
For those who don't know, DJB2 is implemented like this: (C#)
public int Djb2(string text)
{
int r = 5381;
foreach (char c in text)
{
r = (r * 33) + (int)c;
}
return r;
}
Text is a string of ASCII characters, so DJB2 has a lot of collisions, a fact that I knew full well going in to this. Fortunately, the plaintext I have has characteristics that will allow me to use heuristical filtering, so false positives shouldn't be much of an issue :)
My algorithm is essentially this, plus some recursion-control (pesudocode):
reverse(hash):
y = hash mod 33
for c in [65, 120]:
if c mod 33 == y:
print reverse((hash - c) / 33), c
In other words, find the remainder of the hash / 33. Then, for all the ASCII values from 65 to 120, check to see if the value / 33 has the same remainder. If it does, subtract it from the hash, divide the hash by 33, and continue the algorithm. In this way, we only investigate promising paths, because we know that the subtraction of C must leave a number that is evenly divisible by 33.
For example, here is the algorithm working to decode a simple hash:
- $h = 177676$
- $y = h\mod{33} = 4$
- Values of $c$ where $4\equiv c\mod{33}$: $70$ and $103$
- I can now pursue only those two values of $c$. (In this case, $103$, or 'g', was correct)
Thus, I know my algorithm works to reverse the hashing process. Unfortunately, I ran into a nasty problem. Djb2 will rapidly overflow the bounds of an int
, often with plaintext as small as four characters. This overflow essentially results in r
being implicitly modded by $2^{32}$.
Normal division won't work. I asked a question on programming SE about division in this case, and was informed about the multiplicative inverse of 33. Unfortunately, I don't need a division operation (yet), I need a remainder operation! This is proving to be much trickier, and I'm not sure it's even possible.
Here's an illustrative example:
- $h = 2090289493$ <-- h is actually $6385256691\pmod2^{32}$ because of the overflow
- $y = h\mod{33} = 28$ <-- Incorrect! Should be 32
Here is an example of the algorithm using the operation $\Omega$ and an $h$ that has overflowed. This is what I'd like to do, but I don't know what operation $\Omega$ represents.
- $h = 2090289493$
- $y = h\ \Omega\ {33} = 32$
- Values of $c$ where $32\equiv c\mod{33}$: $65$ and $98$
- I can now pursue only those two values of $c$.
Am I on the right track with reversing DJB2 (can it be reversed?)? Is there some way of finding the remainder of a large number that has been modded by $2^{32}$?