Real Password Cracker - Codewars Challenge - Javascript

Question

There is a challenge on Codewars that asks you to decipher SHA-1 hashes.

(I think) I need to require Crypto in order to do so. I found this example of how to create SHA-1 Hash from a String in JS using Crypto:

let x = "Geek"
function createSha1 (x) {
    const crypto = require('crypto'), 
    let hashPwd = crypto.createHash('sha1').update(x).digest('hex'); 
    return hashPwd;
}

So then basically I need to do the opposite, correct? The argument is given to the function as a SHA-1 hash, so we need to take that and turn it into a string - How can you decode a SHA-1 hash? Because according to this article, you can't.

It was suggested by a friend that I would need to

generate the hash, and then start looping and generating it for “a”, “b”, “c”, …“aa”, “ab”, “ac”… etc, and stop when the hashes match and return it.

So then to generate 'normal' hash, I would do something like:

function stringToHash(string) {            
  let hash = 0;  
  if (string.length == 0) return hash;  
  for (let i = 0; i < string.length; i++) { 
      let char = string.charCodeAt(i); 
      hash = ((hash << 5) - hash) + char; 
      hash = hash & hash; 
  }  
  return hash; 
} 

But of course, I don't know what string I should use for the argument there, because Codewars is giving us SHA-1 hashes as arguments already: e6fb06210fafc02fd7479ddbed2d042cc3a5155e.

It's the nature of this site, but I hate to post an answer to this challenge right away. Please give hints / direction prior to a working solution first if possible.

Thanks!

Answer 1

I don't use that site so not familiar with the format.

It wants you to brute force it, can get it to pass on Test but not on Attempt, it just always times out

Here is the code, knowing its only going to be either code or test we can reduce charset, but it still times out. maybe you know why.

const crypto = require('crypto');

const alpha = 'abcdefghijklmnopqrstuvwxyz';

function* permutator(length = 4, prev = "") {
  if (length <= 0) {
    yield prev;
    return;
  }
  for (const char of [...alpha])
    yield* permutator(length - 1, prev + char);
}

function passwordCracker(hash) {
  const it = permutator();

  while (true) {
    const v = it.next().value
    if (v && crypto.createHash('sha1').update(v).digest('hex') === hash)
      return v
  }
}

---

Edit, it gives hints that its expecting to see at least 5 chars, if you fake it, with something like:

function passwordCracker(hash) {
  // Good Luck
  let map = {
    'e6fb06210fafc02fd7479ddbed2d042cc3a5155e': 'code',
    'a94a8fe5ccb19ba61c4c0873d391e987982fbbd3': 'test',
  }
  return map[hash]; 
}

Errors with:

Test Results:
 Fixed tests
 testing...
expected undefined to equal 'try'
...
 harder testing...
expected undefined to equal 'cgggq'

So that means you can't cheat with a reduced charset, it will need to be a-z, work backwards (because it will pass before 5) and be at least 5 long.

On my computer, the above code takes way longer than 12seconds which is the limit :(

Answer 2

Ideal cryptographic hashes are designed specifically as one way functions, making it infeasible to simply apply an inverse transform to get the plain text back out. Something else you should be aware of is due to the compression nature of hash functions you will have issues with the pigeon hole principal, meaning that multiple things can hash to the the same value.

There are several ways of solving this problem though that don't require you to create an inverse.

Bruteforce

As your friend mentioned, the easiest thing to do would be just to try to brute force the hash. Assuming that they picked something that is say 6 characters long, it should take less than a second. If you know anything about the nature of the password then your work is easier. For example if you are told the password maybe between 4-6 chars long and it contains at least one number and uppercase you can create a character set to use in your brute force. This assumes that the password is a straight hash or with some known salt.

Rainbow Tables

This is somewhat related to brute forcing, but someone has spent the time and precomputed as many possible hashes as they can. You can find these tables online and simply have to look up your hash. Most common passwords, words, phrases, and alphanumeric combinations have been enumerated and can be looked up within several miliseconds. Again these assumes that the values are run through hash as is without salts ect.

Length Extensions

With sha1, you can simply forge something that hashes to the same exact value using something called length extension. This is probably outside of what you need, but is something worth a look if you are really interested in cryptoanalysis.

Answer 3

Brute force or dictionary attack

In general, you can't reverse hashes. What you can do instead is to try various plausible candidates for the input data, hash them, and check if you got the correct answer. This is how most 'password hash cracking' works in practice, with various well established tools (hashcat, john the ripper, etc) and online services, however that's probably not relevant since you're expected to code the solution yourself.

The main thing that determines how fast you'll find the solution is your choice of candidate solutions. Looping through all the letters and trying out all possible combinations as your friend suggested - the brute force solution - is a possibility. It's worth noting that it will succeed only if you're looping through the correct 'alphabet' - if you're trying only the lowercase letters, then you will intentionally ignore options that include a number or an uppercase letter or some other symbol.

Another commonly used option is to assume that the password is weak and run a 'dictionary attack', trying out various options that are more likely to be chosen by humans than a random sequence of letters. It may be a literal dictionary, trying English words; it may be a list of known frequently used passwords (e.g. https://github.com/danielmiessler/SecLists has some lists like that), or it may be a dictionary combined with some 'mutation rules' - e.g. if the list includes 'password' a cracking tool might automatically generate and try also 'password2' and 'Password' and 'passw0rd' among other options.

In your particular case the password is weak enough so that both brute force and a dictionary attack will work. For more difficult hashes that won't be the case.