Decoding a MD5 hash based on a given formula

Question

I have a task with MD5 hash. I made an API call to the server and was able to get hash. Right now, I have to solve the hash and send my solution to its address.But I have never seen a problem or a coding task like this. Can anyone give me a help with this ?

import fetch from "node-fetch";
const crypto = require('crypto');

const GUID = '6a21be94-c29f-41e1-aa59-0a1029644872'
const SLUG = 'baris-savas-91533'
const baseApi = `http://career.dijitalgaraj.com/hash/${SLUG}`

const apiRequest = async () => {
    const response = await fetch(baseApi, {
        method: 'PUT',
        headers: {
            'Content-Type': 'application/json',
            'X-GUID': GUID
        },
        body: JSON.stringify({
            GUID: GUID
        })
    })
    const data = await response.json()
    return data.hash
}

const HASH = await apiRequest()
console.log(HASH)

//We have splitted the hidden email address into multiple substrings, starting with first two letters and increasing by two letters in each iteration. For example:
// hello@dijitalgaraj.com => he hell hello@ hello@di hello@diji ... hello@dijitalgaraj.com
// We'll refer this substrings as "x" in the following clause.
// Each substring is hashed with the formula: md5(md5(your_email_address) + x + md5(x)) and then added all together as the hash.

// Using the information above, solve the hash, find the hidden email address and send your project to that address. The address is created uniquely for you.

This is the step that I can't proceed.And also it says in notification ==>

1-The mail address can contain numbers, all english letters and special characters: + - . _ @ (understood clearly )

2-Don't try to decode or reverse-engineer md5 hash to solve the problem. ( And here I don't know what to do )

Answer 1

• You can estimate the length of the secret email based on the provided hash (which is a sum of length(email)-1 hashes). MD5 hashes are 128-bit long, and for any given input you expect roughly half of those bits to be on and half to be off. The average MD5 is therefore between 2^128 - 1 (all bits on) and 0, with an expected average of 2^127; so if your input is in the range 14*2^127 to 16*2^127, you should expect around 16 characters of e-mail to guess.
• It is astronomically unlikely that, for a random input, the result of following their procedure of summing up hashes-of-altered-substrings will result in the desired output. So you can simply build strings of the expected length until one hashes to the expected result. Therefore, brute force can work, because if you get the right result, you (with overwhelming probability) have the right email.
• Any information that reduces the search-space will make the process much, much faster. In particular, since you are looking for an e-mail address, it only makes sense to look for valid addresses - greatly reducing the search-space. If you suspect that they may be using the dijitalgaraj.com domain, that's a very large chunk of search-space that you no longer need to look into (16 characters, and 17 if you include the @ sign).
• Building an efficient brute-force cracker will be a significant hurdle; but in general, the only way to brute-force faster is either to reduce the search-space (see above) or search faster. To search faster, you should go as close to the metal as possible (for example, use SIMD instructions to calculate several hashes at the same time in the CPU) and/or use as many machines as possible computing hashes in parallel. You tag the question as JS - but I would certainly not use JS for an efficient, cluster-friendly cracker.

what if instead of sum, you were concatenating hashes?

• Then the problem becomes easy, because you can solve each round incrementally, instead of having to guess the full secret correctly all-at-once.

// let us hash a secret (this is where you start, except you do not know the 2nd argument)
const full_hashed_secret = full("me@home.com", "secret@somewhere.org");
console.log("will try to crack", full_hashed_secret);

// now break it into rounds
const rounds = unjoin(full_hashed_secret, 32);

// now start guessing chars one at a time
let known = ""; 
for (let i=0; i<rounds.length; i++) {
    known += crack("me@home.com", rounds[i], known); 
    console.log("guessing for round", i, rounds[i], "->", known);
}

// last line should have answer: eureka!

// the brute-force part: find the next character(s) of the secret by trial and error
function crack(your_email_address, hash_of_round, prefix) {
  // charset to use; whatever is valid in an e-mail (and yes, this is incomplete)
  const charset = "abcdefghijklmnopqrstuvwxyz0123456789@.";
  if (prefix === "") {
    // no prefix, must guess 2 in a row
    for (let i=0; i<charset.length; i++) {
      prefix = charset.slice(i, i+1);
      for (let j=0; j<charset.length; j++) {
        let guess = prefix+charset.slice(j, j+1);
        if (round(your_email_address, guess) === hash_of_round) {
           return guess;
        }
      }
    }
  } else {
    for (let j=0; j<charset.length; j++) {
      let guess = charset.slice(j, j+1);
      if (round(your_email_address, prefix+guess) === hash_of_round) {
         return guess;
      }
    }
  }
  // no valid guesses, incomplete charset or bad prefix?
  return "??";
}

// un-join a string, splitting it into substrings of length n
function unjoin(s, n) {
  let parts = [];
  for (let i=0; i<s.length; i+=n) {
     parts.push(s.slice(i, i+n));
  }
  return parts;   
}

// (increasing rounds) and then added all together as the hash
// with "added all together" understood as "concatenated together"
function full(your_email_address, secret) {
   let parts = [];
   for (let i=2; i<=secret.length; i++) {
      parts.push(round(your_email_address, secret.substring(0,i)));
   }
   return parts.join("");
}

// one round: md5(md5(your_email_address) + x + md5(x))
// + is understood again as concatenation 
// (but it would not make much of a difference to use addition)
function round(your_email_address, x) {
   return md5(md5(your_email_address) + x + md5(x));
}

// from https://stackoverflow.com/a/60467595/15472
// probably not the fastest, but I only want to prove a point
function md5(inputString) {
    var hc="0123456789abcdef";
    function rh(n) {var j,s="";for(j=0;j<=3;j++) s+=hc.charAt((n>>(j*8+4))&0x0F)+hc.charAt((n>>(j*8))&0x0F);return s;}
    function ad(x,y) {var l=(x&0xFFFF)+(y&0xFFFF);var m=(x>>16)+(y>>16)+(l>>16);return (m<<16)|(l&0xFFFF);}
    function rl(n,c)            {return (n<<c)|(n>>>(32-c));}
    function cm(q,a,b,x,s,t)    {return ad(rl(ad(ad(a,q),ad(x,t)),s),b);}
    function ff(a,b,c,d,x,s,t)  {return cm((b&c)|((~b)&d),a,b,x,s,t);}
    function gg(a,b,c,d,x,s,t)  {return cm((b&d)|(c&(~d)),a,b,x,s,t);}
    function hh(a,b,c,d,x,s,t)  {return cm(b^c^d,a,b,x,s,t);}
    function ii(a,b,c,d,x,s,t)  {return cm(c^(b|(~d)),a,b,x,s,t);}
    function sb(x) {
        var i;var nblk=((x.length+8)>>6)+1;var blks=new Array(nblk*16);for(i=0;i<nblk*16;i++) blks[i]=0;
        for(i=0;i<x.length;i++) blks[i>>2]|=x.charCodeAt(i)<<((i%4)*8);
        blks[i>>2]|=0x80<<((i%4)*8);blks[nblk*16-2]=x.length*8;return blks;
    }
    var i,x=sb(inputString),a=1732584193,b=-271733879,c=-1732584194,d=271733878,olda,oldb,oldc,oldd;
    for(i=0;i<x.length;i+=16) {olda=a;oldb=b;oldc=c;oldd=d;
        a=ff(a,b,c,d,x[i+ 0], 7, -680876936);d=ff(d,a,b,c,x[i+ 1],12, -389564586);c=ff(c,d,a,b,x[i+ 2],17,  606105819);
        b=ff(b,c,d,a,x[i+ 3],22,-1044525330);a=ff(a,b,c,d,x[i+ 4], 7, -176418897);d=ff(d,a,b,c,x[i+ 5],12, 1200080426);
        c=ff(c,d,a,b,x[i+ 6],17,-1473231341);b=ff(b,c,d,a,x[i+ 7],22,  -45705983);a=ff(a,b,c,d,x[i+ 8], 7, 1770035416);
        d=ff(d,a,b,c,x[i+ 9],12,-1958414417);c=ff(c,d,a,b,x[i+10],17,     -42063);b=ff(b,c,d,a,x[i+11],22,-1990404162);
        a=ff(a,b,c,d,x[i+12], 7, 1804603682);d=ff(d,a,b,c,x[i+13],12,  -40341101);c=ff(c,d,a,b,x[i+14],17,-1502002290);
        b=ff(b,c,d,a,x[i+15],22, 1236535329);a=gg(a,b,c,d,x[i+ 1], 5, -165796510);d=gg(d,a,b,c,x[i+ 6], 9,-1069501632);
        c=gg(c,d,a,b,x[i+11],14,  643717713);b=gg(b,c,d,a,x[i+ 0],20, -373897302);a=gg(a,b,c,d,x[i+ 5], 5, -701558691);
        d=gg(d,a,b,c,x[i+10], 9,   38016083);c=gg(c,d,a,b,x[i+15],14, -660478335);b=gg(b,c,d,a,x[i+ 4],20, -405537848);
        a=gg(a,b,c,d,x[i+ 9], 5,  568446438);d=gg(d,a,b,c,x[i+14], 9,-1019803690);c=gg(c,d,a,b,x[i+ 3],14, -187363961);
        b=gg(b,c,d,a,x[i+ 8],20, 1163531501);a=gg(a,b,c,d,x[i+13], 5,-1444681467);d=gg(d,a,b,c,x[i+ 2], 9,  -51403784);
        c=gg(c,d,a,b,x[i+ 7],14, 1735328473);b=gg(b,c,d,a,x[i+12],20,-1926607734);a=hh(a,b,c,d,x[i+ 5], 4,    -378558);
        d=hh(d,a,b,c,x[i+ 8],11,-2022574463);c=hh(c,d,a,b,x[i+11],16, 1839030562);b=hh(b,c,d,a,x[i+14],23,  -35309556);
        a=hh(a,b,c,d,x[i+ 1], 4,-1530992060);d=hh(d,a,b,c,x[i+ 4],11, 1272893353);c=hh(c,d,a,b,x[i+ 7],16, -155497632);
        b=hh(b,c,d,a,x[i+10],23,-1094730640);a=hh(a,b,c,d,x[i+13], 4,  681279174);d=hh(d,a,b,c,x[i+ 0],11, -358537222);
        c=hh(c,d,a,b,x[i+ 3],16, -722521979);b=hh(b,c,d,a,x[i+ 6],23,   76029189);a=hh(a,b,c,d,x[i+ 9], 4, -640364487);
        d=hh(d,a,b,c,x[i+12],11, -421815835);c=hh(c,d,a,b,x[i+15],16,  530742520);b=hh(b,c,d,a,x[i+ 2],23, -995338651);
        a=ii(a,b,c,d,x[i+ 0], 6, -198630844);d=ii(d,a,b,c,x[i+ 7],10, 1126891415);c=ii(c,d,a,b,x[i+14],15,-1416354905);
        b=ii(b,c,d,a,x[i+ 5],21,  -57434055);a=ii(a,b,c,d,x[i+12], 6, 1700485571);d=ii(d,a,b,c,x[i+ 3],10,-1894986606);
        c=ii(c,d,a,b,x[i+10],15,   -1051523);b=ii(b,c,d,a,x[i+ 1],21,-2054922799);a=ii(a,b,c,d,x[i+ 8], 6, 1873313359);
        d=ii(d,a,b,c,x[i+15],10,  -30611744);c=ii(c,d,a,b,x[i+ 6],15,-1560198380);b=ii(b,c,d,a,x[i+13],21, 1309151649);
        a=ii(a,b,c,d,x[i+ 4], 6, -145523070);d=ii(d,a,b,c,x[i+11],10,-1120210379);c=ii(c,d,a,b,x[i+ 2],15,  718787259);
        b=ii(b,c,d,a,x[i+ 9],21, -343485551);a=ad(a,olda);b=ad(b,oldb);c=ad(c,oldc);d=ad(d,oldd);
    }
    return rh(a)+rh(b)+rh(c)+rh(d);
}