Implementing a Hashing Algorithm in Node.js

kaleb horvath
Sep 5, 2018 · 5 min read

All hashing algorithms are based off of a few basic concepts: bitwise operations and bitshifting. First, let us review basic bitshifting.

Foundations

00101 shifted left by 1-bit  is 01010
00101 shifted left by 2-bits is 10100
00101 shifted left by 3-bits is 01001

Notice the last one. When shifted left by 3-bits, the binary number wrapped around to produce a new place value. This same process continues on and on. Bit wise operations are a little bit more complicated. There are three main operations we need to be concerned about: AND, OR, and XOR. AND checks to make sure each bit is a 1, if so returns 1. For example:

0 & 1 = 0 Because both bits are not one.
0 & 0 = 0 Because both bits are not one.
1 & 1 = 1 Because both bits are one.

This continues in a sort of iteration for larger binary numbers.

011 & 101 = 001 Because the first two are not both ones, but the   last one is, so we get a one in the last bit place.

As for OR, it checks to make sure each bit matches to both being 0’s or both being 1's.

0 | 0 = 1 Because both bits are the same. 
1 | 0 = 0 Because both bits are not the same.

Pretty simple, right? XOR is the same as OR, except it checks to make sure that both bits are opposite.

0 ^ 1 = 1 Because both bits are positive.
0 ^ 0 = 0 Because both bits are the same.

The important thing to remember with these bitwise operations is that they are like packed little if-statements that yield new numbers base on two input numbers. Super simple.

The second main thing that hashing needs to do is convert each character in the string to an ASCII integer. In Node, we can just do:

character.charCodeAt();// -or- //string.charCodeAt(iterator);

Getting Started

Now that we have all the basics out of the way, lets get started! I would like to implement a pretty simple hashing algorithm known as Daniel J. Bernstein’s Second Algorithm, or simply DJB2. Here is some code to get started:

var djb2 = function (string) {
// some code here
}

We will write all of our code within that function and call it accordingly. Now, in essence, hashing one character works sort of like this:

1. Convert character to ASCII integer. 
2. Do bitwise operations with ASCII integer and hash number.
3. Loop through the entire string and do steps 1-2.

Every algorithm has different hash numbers. The DJB2 algorithm specifically uses 5381 as its hash.

var djb2 = function (string) {
var h = 5381; // our hash
}

Next, we can statically declare an iterator in the spirit of clarity.

var djb2 = function (string) {
var h = 5381; // our hash
var i = 0; // our iterator
}

Now we should go ahead and loop through all the characters in the string.

var djb2 = function (string) {
var h = 5381; // our hash
var i = 0; // our iterator
for (i = 0; i < string.length; i++) {
// hash code here
}
}

Now that we are in the loop, we need to grab the ASCII integer from the current character in the string.

var djb2 = function (string) {
var h = 5381; // our hash
var i = 0; // our iterator
for (i = 0; i < string.length; i++) {
var ascii = string.charCodeAt(i); // grab ASCII integer
}
}

Okay, awesome! Almost done! Now we need to perform bitwise operations between hash or h and the ASCII integer or ascii . You will recognize some of these bitwise operations from the Foundations section of this tutorial.

var djb2 = function (string) {
var h = 5381; // our hash
var i = 0; // our iterator
for (i = 0; i < string.length; i++) {
var ascii = string.charCodeAt(i); // grab ASCII integer
h = ((h << 5) + h) + ascii; // bitwise operations
}
}

Now that h or our hash is completely modified using all ASCII integers in the string, we can return h as the real hash.

return (h & 0xffffffffff).toString(16);

0xffffffffff ensures that the hash returned is an unsigned 32-bit hash. The .toString(16) converts the hash to hexadecimal.

All in all, our code should look like this…

var djb2 = function (string) {
var h = 5381; // our hash
var i = 0; // our iterator
for (i = 0; i < string.length; i++) {
var ascii = string.charCodeAt(i); // grab ASCII integer
h = ((h << 5) + h) + ascii; // bitwise operations
}
return (h & 0xffffffffff).toString(16);
}

If we run some tests, we should get some interesting results.

console.log(djb2('password'));
console.log(djb2('hellomynameis'));
console.log(djb2('wowsonweredyoufindthis'));

The above should return stuff like this…

17f6dc387720539c1c6dd7ff

As you can see, while each string is different, it returns exactly 32-bits of hex data as the hash. Changing even one bit in the string will change the entire hash. This is an okay way to store passwords and hide them from the average user, but it could be made better.

More Secure DJB2 Variants

That was pretty cool, but we can greatly improve upon Mr. Bernstein’s method by using much more complicated bitwise operations in our hash function. Let us go ahead and explore these alternatives.

h = ((h << 5) ^ h) ^ ascii;

The above uses ^ instead of plane-old +. If you recall, ^ is the XOR operation. XOR is both faster and more secure than just addition.

Another way to improve speed is shift the hash left by 3-bits instead of 5. Yes, this will take the security down a notch, however using XOR will make up for it. We should now have something like this…

h = ((h << 3) ^ h) ^ ascii;

This new version of DJB2 is now faster and more secure than the original. If it seems to take longer, try shifting the original DJB2 hash around by 2 or 3 bits.

Let us convert the DJB2 hash number to binary.

5381 -> 1010100000101

Now we are ready to shift.

1010100000101 << 01 = 10101000001010
1010100000101 << 10 = 101010000010100

Shifting left by 10 or 2 bits actually performs what is known as sign extension. We extended the bit-mask of the hash number. This fills more buffers with zeros so that we have more room for bitwise, in turn rewarding us with saved time.

Our new, faster, and more secure hash algorithm should look like this:

var djb2_better = function (string) {
var h = 5831 << 2;
var i = 0;
for (i = 0; i < string.length; i++) {
var ascii = string.charCodeAt(i);
h = ((h << 3) ^ h) ^ ascii;
}
return (h & 0xffffffffff).toString(16);
}

Thanks for reading!

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