I taught the elves how to create passwords with JavaScript and they lost the password. This is a problem, because the central elven computer system does not keep copies of passwords. It simply stores the hash, which by its nature is practically impossible to decode. What can I do?
The Puzzle: Decoding The Code 🔐
Dev Advent Calendar puzzle 17 🎅 can be summed up like this: How to hack a password using JavaScript? How to bruteforce a hash table?
Obviously the problem is unsolvable. The hash cryptographic functions are inviolable. Before tackling the problem it is better to understand what is meant by a hash function
Cryptographic hash function
Wikipedia explains well what the characteristics are.
How does it work? A hash function takes data and converts it to a fixed-size binary string. Each dataset produces a different hash. And similar data produces very different hashes.
These algorithms are designed to resist various types of attacks and have 3 levels of security:
- Pre-image resistance: Given a hash value h, it should be difficult to find any message m such that h = hash(m). This concept is related to that of a one-way function. Functions that lack this property are vulnerable to preimage attacks.
- Second pre-image resistance: Given an input m1, it should be difficult to find a different input m2 such that hash(m1) = hash(m2). This property is sometimes referred to as weak collision resistance. Functions that lack this property are vulnerable to second-preimage attacks.
- Collision resistance: It should be difficult to find two different messages m1 and m2 such that hash(m1) = hash(m2). Such a pair is called a cryptographic hash collision. This property is sometimes referred to as strong collision resistance. It requires a hash value at least twice as long as that required for pre-image resistance; otherwise collisions may be found by a birthday attack.
This allows you to be sure that if two hashes are identical then the starting data are the same.
An example of use are passwords. If we want to create an identity verification system, it is dangerous to create a database with the passwords of the various users. It is advisable to keep only the hash of the passwords. When someone tries to log in, we compare the hash generated by the request with the saved hash: if they are identical then the password is correct.
This thing fascinates me. Being able to verify the correctness of a password without having to know it. Another feature fascinates me a lot: two similar passwords have very different hashes.
This makes it very difficult to trace the starting password.
Calculate the Hash of a password
To make the problem manageable it is necessary to simplify. The rules of engagement are these:
- we know the hash of the password to find
- we know what form the starting password had:
<UPPER CASE LETTER>-<3-DIGIT-NUMBER>. For exampleX-348,L-239,V-111.
This is a great help. We can create a list of potential passwords to test. Then we calculate the hash of each one until we find the correct one.
In NodeJS it is easy to find the hash of a string. Just use the crypto API:
Create a list of potential passwords
The simplest way to create a list of potential passwords to test is to use two nested for loops. I use the first one to scroll through the letters of the alphabet:
I then insert a second loop to iterate through all numbers from 0 to 999
So I create a test variable:
I use the String.prototype.padStart() method to make each password have exactly 3 numbers. This way I can transform A-0 to A-000, C-12 to C-012 and so on.
I get the hash
Finally I compare it with what I already have:
I quit the function immediately: I don’t need to check the other passwords. Once I found the one generating the correct hash I also found what I was looking for.
The complete code looks like this:
To Refractor
It is a simple and understandable solution. But I can do better. I can delete the nested loop. I can also delete one of the two returns. This way I can get something clearer:
Actually you could simplify it even more by adding the listPassword argument instead of calculating it inside the function. But the puzzle doesn’t allow me to do that.
I have decided to extract from the bruteForcePassword function everything that is not related to the problem: the creation of the password list and the comparison of the hashes:
The isPassword function returns the password directly and not a boolean value. This way I can take advantage of JavaScript’s ability to treat strings as truthy and null values as falsy. I need it to simplify the exit from the for...of loop.
To generate the password list, I break down the problem into several parts. First I need an array containing the numbers 0 to 999. I create this function:
There is a good discussion on stackoverflow on this problem. In short, I can create an array of n elements with Array(n). If I add the Array.prototype.keys() method and then use the spread operator, I can get an array of n elements each of which contains a number that represents the index of its position:
I use this array with theArray.prototype.map() method to add the missing 0s to the first 100 elements.
I can easily create an array containing the letters of the alphabet:
This time I don’t use keys(): I can leave all the elements of the array null and then use the index to get the charCode of the letter I want to insert.
I create a helper function to join letters and numbers:
I add the desired character to each element of the array with numbers. Finally I create the list of potential passwords:
By combining everything I get my solution:
That’s all. This puzzle is related to the number 11:
I have saved in this list the solutions to the other problems of this challenge:
