Breaking Daniel J. Bernstein’s Algorithm

kaleb horvath
Sep 8, 2018 · 2 min read

If you have done any research into hashing functions, you have most likely heard of Daniel J. Bernstein’s hashing algorithm. It is often referred to as the most efficient and secure hashing algorithm. While I give Mr. Bernstein full credit for his experimental and trivial algorithm that is great for learning environments, I do not condone the use of DJB in any practical application.

Let us start by looking at the simple algorithmic expression for DJB-2.

{H * 33} sum Ki

To elaborate, acquiring the hash for an arbitrary integer i , as an index of any arbitrary string K , is as simple as multiplying it by 33 (randomly selected) and then performing summation with i .

Does it seem to simple and easy to reverse? It is! Here is a simple pattern reversal expression of the same algorithm, where N is the resultant of the last expression.

N diff {Ki // 33} 

All we are doing is calculating the difference of a resultant hash N and an arbitrary integer i as an index of any arbitrary string K and then performing floor division over the randomly selected prime number from the original pattern.

This theory is all fine and dandy, but what about an actual implementation? I have pieced together a relatively efficient C version borrowing from http://www.cse.yorku.ca/~oz/hash.html.

unsigned long hash (unsigned char* K) {
unsigned long H = 5381;
int i;

for (i = 0; i < strlen(K); ++i) {
H = ((H << 5) + H) + K[i];
}
return H;
}

To clarify, (H << 5) + H) is the same as doing {H * 33} because H was set to the number 5381.

Improving Upon DJB-2

The standard DJB or DJB-2 algorithm uses basic summations and multiplications as well as added fluff steps to make it more interesting. First of all, let us shave away those fluff steps.

unsigned long hash (char* K) {
unsigned long H = 0;
int i;

for (i = 0; i < strlen(K); ++i) {
H = (H * 33) + K[i];
}
return H;
}

This should already improve the speed by a large margin. Now we can get rid of those pesky summations and replace them with XOR operations which will achieve both more secure and much faster results.

H = (H * 33) ^ K[i];

Already, we have a better and more secure version of the DJB-2 algorithm. Why this algorithm was over-complicated and over-blown is beyond me.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade