How can i find what hashing algorithm was used?

Question

One of my clients has asked me to modify the login page that their board members use to access their materials. The problem here is that the person previously responsible for this has left no documentation behind and the passwords are encrypted with some (seemingly simple) algorithm.

I have access to the hashes, and I know what the passwords are. The javascript is using the hash as their password. My thought is that if I can figure out what the algorithm is that I can create new accounts to suit their request.

Is there a way I can check to see what the algorithm is?

The user is prompted to select their name from a drop down menu and their password is associated with the hash beside their name in the HTML code. The form option looks like this (note that N denotes a numerical value and L denotes a letter).

<option value='Username|NNNNN|LLLLLLLL'>Username

The actual script that parses the value looks like this

<SCRIPT LANGUAGE="JavaScript">
<!-- Begin
var params = new Array(4);
var alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHI";

function check(form) {
    which = form.memlist.selectedIndex;
    choice = form.memlist.options[which].value + "|";
    if (choice == "x|") {
        alert("Please Select Your Name From The List");
        return;
    }
    p = 0;
    for (i = 0; i < 3; i++) {
        a = choice.indexOf("|", p);
        params[i] = choice.substring(a, p);
        p = a + 1;
    }
    h1 = makehash(form.pass.value, 3);
    h2 = makehash(form.pass.value, 10) + " ";
    if (h1 != params[1]) {
        alert("Incorrect Password!");
        return;
    };
    var page = "";
    for (var i = 0; i < 8; i++) {
        letter = params[2].substring(i, i + 1)
        ul = letter.toUpperCase();
        a = alpha.indexOf(ul, 0);
        a -= (h2.substring(i, i + 1) * 1);
        if (a < 0) a += 26;
        page += alpha.substring(a, a + 1);
    };
    top.location = page.toLowerCase() + ".html";
}

function makehash(pw, mult) {
    pass = pw.toUpperCase();
    hash = 0;
    for (i = 0; i < 8; i++) {
        letter = pass.substring(i, i + 1);
        c = alpha.indexOf(letter, 0) + 1;
        hash = hash * mult + c;
    }
    return (hash);
}
// End -->
</script>

Is there anyway I can reverse engineer this so that I can create new user accounts?

Answer 1

The algorithm here is:

function makehash(pw, mult) { // Password and... multiplier?
    pass = pw.toUpperCase(); // Case insensitivity
    var hash = 0;
    for (i = 0; i < Math.min(pass.length, 8); i++) { // 8 char passwords max...
        c = pass.charCodeAt(i) - 63; // A = 2, B = 3, etc.
        hash *= mult;
        hash += c;
    }

    return hash;
}

I cleaned the code up a bit and added some comments. Whoever wrote this is utterly incompetent in the fields coding, security and mathematics. Anyway, it is no "official" algorithm like MD5 or AES, but homebrew and incredibly fault-intolerant. It accepts only letters, is case-insensitive, and ignores all characters after the first 8.

I would highly recommend upgrading everyone's password hash. See also: How to securely hash passwords?

By the way, here is the rest of the code with some formatting:

var params=new Array(4);
var alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHI";

function check(form) {
    which = form.memlist.selectedIndex;
    choice = form.memlist.options[which].value + "|";
    if (choice == "x|") {
        alert("Please Select Your Name From The List");
        return;
    }

    p = 0;
    for (i = 0; i < 3; i++) {
        a = choice.indexOf("|", p);
        params[i] = choice.substring(a, p);
        p = a + 1;
    }
    h1 = makehash(form.pass.value, 3);
    h2 = makehash(form.pass.value, 10) + " ";
    if (h1 != params[1]) {
        alert("Incorrect Password!");
        return;
    }

    var page = "";
    for (var i = 0; i < 8; i++) {
        letter = params[2].substring(i, i + 1)
        ul = letter.toUpperCase();
        a = alpha.indexOf(ul, 0);
        a -= h2.substring(i, i + 1) * 1; // multiplying by one? Seriously?
        if (a<0)
            a+=26;
        page += alpha.substring(a, a + 1);
    };
    top.location=page.toLowerCase() + ".html";
}

I would add comments, but I'm not sure if it's worth it to find any reason in this mess.

Answer 2

Searching for a section of code yields the page this was taken from:

http://www.yaldex.com/FSPassProtect/LoginCoder.htm

among many other locations. This should tell you how to add another entry.

However, this is an extremely insecure authentication mechanism that can be trivially bypassed by anyone remotely competent as all you have to do is guess the page (case-insensitive 8 character string ending in .html) that you will redirected to if you enter the password correctly. And really its won't take a quick script trying 26^8 different URLs; all you have to do is look at the encoded value 'BAFJFFCI' and try up to 10^8 9^7 if there's only one user; if there are multiple users going to the same page, you can reduce the space significantly.

---

Ok, I've deconstructed how this works. Every user in the login form has an option with a value like "User name|35240|BAFJFFCI". The user name is not used anywhere and is irrelevant. The next hash, called h1, is generated by calling make_hash on the entered password string with a multiplier of 3.

def make_hash(pw, mult):
    hash = 0
    for char in pw:
        char_ind = ord(char) - ord('A') +1 # A=1, B=2, C=3, ...
        hash *= mult
        hash += char_ind
    return hash

So if your password is 'insecure', that gets translated into numbers (I=9, n=14, s=19, ...) [9,14,19,5,3,21,18,5], so your hash is 3*(3*(3*(3*(3*(3*(3*(9)+14)+19)+5)+3)+21)+18)+5, which works out to be 35240. Note its case-insensitive. So what's the second value? Well if you type a valid password, it will forward you to a secret page. In my case the secret page was 'AAAAAAAA' which was will be decoded from the field 'BAFJFFCI'

To decode they generate another hash with a multiplier of 10. h2=make_hash(pw, 10) which in my case works out to be h2=105955285. Each digit starting from the left, tells me how many characters to shift by. E.g., 'AAAAAAAA' if you shift the first character forward one letter gives 'B', second character forward 0 gives 'A', shift 'A' forward 5 characters 'F', forward 9 characters 'J', ... and similar to recover 'AAAAAAAA' from 'BAFJFFCI' with the h2 (generated from the password) you simply subtract the letters.

As an attacker this means seeing the hash of each user in the password field there are only ten possible letters for the source page. So 10^8 possible webpages to try and check. If multiple users all get sent forward to the same page, you can easily figure out the destination page, and just go there yourself bypassing the entire authentication procedure.

For example, both 'GCDDGDAJ' and 'BAFJFFCI' are shifted version pointing back to aaaaaaaa.html. By assuming both go to the same page, and seeing 'G', 'B' both originate shifted by 0-9 characters from the same letter, I know the first letter is either A,B,X,Y,Z. I can easily see if its possible for two h2 to forward to the same page by making sure that no letters are further than 9 characters apart (e.g., if in one password there's an 'A' and in the other password in the same spot there's a K,L,M,N,O,P, or Q then the passwords can't go to the same page) and the distance apart also limits the values for the real spot.

---

And for more crypto-analysis:

Also you can find collisions for this hash very simply. For simplicity, I'll analyze a three character password generated with this scheme. So now h1 = 3*(3*c1+c2)+c3). Taking the modulus (remainder after division with symbol %) with respect to 3, you see that h1 % 3 = c3 % 3. Thus if h1 % 3 = 0 the last-letter is in CFILORUX; if h1 % 3 = 1, its in ADGJMPSVY; if h1 % 3 = 2 its in BEHKNQTWZ. You can use this procedure to reduce a three character password down to at most 9^2 = 81 possibilities.

For example, let's say the pw is 'THE' and hash was 3*(3*20+8)+5=209. As 209 % 3 = 2; we know the last character is in BEHKNQTWZ. We can try all 9 choices subtract off the last character, divide by 3 and repeat again. E.g., if the last letter was B, then (209-2)/3 = 69 which means and 69 % 3 = 0, so the middle letter is in CFILORUX. If it was a C, then we get the first letter must be (69-3)=22 = V; hence VCB has a hash of 209. Repeating this for other choices: UFB, TIB, SLB, ROB, QRB, PUB, OXB. If last letter was E; we'd have VBE, UEE, THE, SKE, RNE, QQE, PTE, OWE, NZE. This is fairly easy to iterate through; so you'd have a max of 9^2 = 81 choices (each letter besides the last which is determined by what's left-over; has either 8 or 9 choices). In our case there are 78 choices:

VCB UFB TIB SLB ROB QRB PUB OXB VBE UEE THE SKE RNE QQE PTE OWE NZE VAH UDH TGH SJH RMH QPH PSH OVH NYH UCK TFK SIK RLK QOK PRK OUK NXK UBN TEN SHN RKN QNN PQN OTN NWN MZN UAQ TDQ SGQ RJQ QMQ PPQ OSQ NVQ MYQ TCT SFT RIT QLT POT ORT NUT MXT TBW SEW RHW QKW PNW OQW NTW MWW LZW TAZ SDZ RGZ QJZ PMZ OPZ NSZ MVZ LYZ

These have 78 unique mult=10 hashes that you'd have to try to get the URL (I've sorted them):

1476 1483 1546 1553 1560 1567 1574 1616 1623 1630 1637 1644 1651 1658 1665 1686 1693 1700 1707 1714 1721 1728 1735 1742 1756 1763 1770 1777 1784 1791 1798 1805 1812 1826 1833 1840 1847 1854 1861 1868 1875 1882 1896 1903 1910 1917 1924 1931 1938 1945 1952 1966 1973 1980 1987 1994 2001 2008 2015 2022 2036 2043 2050 2057 2064 2071 2078 2085 2092 2127 2134 2141 2148 2155 2162 2218 2225 2232

Note, that only the first three digits of the mult-10 hash matter in altering the URL so really there were only 62 different values. Or for simplicity I could just find the largest/smallest mod hash, and check the first three digits for everything in between (checking 77 values; after finding VCB and LYZ).

Note, they the full mult-10 hashes all have the same value mod 7 (all 6). This pattern (having the same remainder divided by 10-3=7) will be true in general. So you could also just figure out the first and last allowable password 'VCB' giving mult=10 hash 2232, and 'LYZ' giving mult-10 hash of 1476 and try all ((2232-1476)/7)+1=109 mult-10 hashes in that range separated by 7 and only use the first n-digits from the mult-10 hash.

Again, regardless of the method you'll have a few million URLs to check, which at a rate of 100/second should take under a day.

Answer 3

This hashing algorithm is so insecure that it takes about 2 minutes to calculate all possible passwords and page combination. It generates a list of 20000 to 2500000 possible secret pages that you need to actually check with the server. For @drjimbob's example of 'INSECURE' to 'aaaaaaaa.html' for example, the you need only to check only 26063 possible secret pages. The others fared better, but not really by much. In fact this password scheme actually weakens the security compared to just prompting the user for the URL to the html page. In that case an attacker had to check 26^8 possible pages, however due to the password scheme, an attacker only need to check 0.00122% of all those 26^8 possibilities.

>>> # "insecure", "aaaaaaaa.html"
>>> len(set(y for x,y in find_pages(35240, 'BAFJFFCI')))
3248895

>>> # "password", "mainpage.html"
>>> len(set(y for x,y in find_pages(42691, 'NGLOQEMM')))
2988569

>>> # "theirpwd", "endpages.html"
>>> len(set(y for x,y in find_pages(52219, 'GNLVAPMV')))
3035974

>>> # "asdfvcxz", "nowheres.html"
>>> len(set(y for x,y in find_pages(18215, 'PXAPGWKY')))
2382856

>>> # "zaqxswde", "logintop.html"
>>> len(set(y for x,y in find_pages(64403, 'NUIRTURT')))
2792596




import string
chars = [(c, ord(c) - ord('A') + 1) for c in string.uppercase]
chars = chars[2::3], chars[::3], chars[1::3]
chars = [list(reversed([(a,b,c) for a,(b,c) in enumerate(chs)])) for chs in chars]

def reverse_make_hash(hash, num=8, cur=''):
    """ generates a list of pw such that `make_hash(pw, 3) == hash` """
    if num <= 0 or hash <= 0: return
    if num == 1 and hash > 26: return
    if num == 1 and hash <= 26: 
        yield chr(ord('A') + hash - 1) + cur

    mod = hash % 3
    for i,c,v in chars[mod]:
        n = (hash - v) / 3
        for pot in reverse_make_hash(n, num-1, c + cur): yield pot

# from dr jimbob
def make_hash(pw, mult):
    hash = 0
    for char in pw:
        char_ind = ord(char) - ord('A') +1 # A=1, B=2, C=3, ...
        hash *= mult
        hash += char_ind
    return hash

def find_pages(hash, page):
    results = []
    for p in reverse_make_hash(hash): 
        page_url = ''.join(chr((ord(p)-int(h)-ord('A')) % 26 +ord('A')) for p,h in zip(page, str(make_hash(p, 10))))
        if page_url.isalpha():
            print p, page_url
            results.append((p, page_url.lower() + '.html'))
    return results

a = find_pages(35240, 'BAFJFFCI')  # "insecure", "aaaaaaaa.html"
b = find_pages(42691, 'NGLOQEMM')  # "password", "mainpage.html"
c = find_pages(52219, 'GNLVAPMV')  # "theirpwd", "endpages.html"
d = find_pages(18215, 'PXAPGWKY')  # "asdfvcxz", "nowheres.html"
e = find_pages(64403, 'NUIRTURT')  # "zaqxswde", "logintop.html"