can you crack it?

[HeavenAgain]

ok here is a problem that i found, and i ammm stuck
the problem is to get trypass equal to passhash (both are int)
and pass is a String, which could be in the range from 0 - 8 digits, i'm guessing from 0 to 255 char could all be possible
so ya... any ideas or hints would be great!
nooo brute force!!! its going to take 8 days+ or even month..... agessss

code:

int passhash = 0x1a98b; int trypass = hash(pass); if(passhash == trypass) you winnnnnn else you lose :( private int hash(String target)    {        int hash = 0;        for(int i = 0; i < target.length(); i++)            hash += target.charAt(i) * i * i;        return hash;    }

[Dan]

Did you make up this hashing system or did some one eletes? I ask becues this method of hasing a password is very insecure and there a colisions all over the place.

In fact if i am looking at this right the 1st letter of the password could be replaced with anything and it could still work.

Edit: Also brut force would not take months but hours to days in this case (esptaly with all of the colesions there are)

[HeavenAgain]

well, i didnt make this, i found this on a "fun" site, called hackquest, this is one of the applet question

and yes, the first letter could be anything, BUT becuase of the int 0x1a98b, and target.charAt(i) * i * i the word will be a unique word, since it its it is times the postion it is at, thats my guess, so you will probably find the first letter last?

edit: well... heres what i found on brute force, if you go on this website look down at the bottom, theres a table showing how long a brute force can take and for both upper and lower case, it will take 3 years so... ya........

[Dan]

Well to prove my point this array if coverted in to a stirng will get the same hash:

{0, 255, 255, 255, 255,255,255,255,255,255,255,76,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2}

I found this using math not brout force, it probly is not the same pass but since there are tones of colesions like i side there are many right awasers.

Edit: You may notice that you can put in as many chars with a value of 0 to increase or decrease the length of the password with out effect the hash. The brut force whould deftaly not take years, they are not accoutning for the colesions in there system witch means there are alot of awasers to the same hash witch means less time to brut force. Also you could make an algorthm to find a password that whould make the hash that whould take seconds, for the one i found to your hash i used a penceil, paper and caluator and my brain.

Edit 2: to covert thos ints in to a string you can test in your code you can do this

Java:

import java.util.* ..... int passint[] = {0, 255, 255, 255, 255,255,255,255,255,255,255,76,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2};                 StringBuffer pass = new StringBuffer("");                 for(int i = 0; i < passint.length; i++){                         pass.append((char)passint[i]);                 }

There is probly a better way to covert it however i am to lazy to look up the java doc.

[HeavenAgain]

well, yes, but that is way more than 8 digits? the maximum you can enter is 8 digits... so ummm

[Dan]

The password can not be 8 letters and match that hash. It has to be at least 12. Also thess coneslions happen at all lengths for example:

"dan" and "fan" will have the same hash and "hash" and "bash" will have the same hash.

Also you can get ones that will add up to the same like char(0) + char(2) and a pass of char(0) + char(0) + char(1).

[HeavenAgain]

ya, i just noticed that too, maybe i read the code wrong....
here is the applet code, i'm pretty sureee it says password filed size is 8

code:

import java.applet.Applet; import java.applet.AppletContext; import java.awt.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.net.URL; public class Challenge5 extends Applet    implements ActionListener {    public void stop()    {    }    public Challenge5()    {        SubmitButton = null;        PasswordField = null;        SubmitButton = null;        PasswordField = null;        SubmitButton = new Button();        PasswordField = new TextField("", 8);    }    public void destroy()    {    }    public void actionPerformed(ActionEvent actionevent)    {        String pass = PasswordField.getText();        String base = getDocumentBase().toString();        char urlchars[] = {            '\261', '\320', '\323', '\327', '\336', '\324', '\352', '\232', '\343', '\333',            '\311'        };        String crypturl = new String(urlchars);        int passhash = 0x1a98b;        int trypass = hash(pass);        crypturl = decode(crypturl, pass);        base = base.substring(0, base.lastIndexOf('/') + 1);        String newurl;        if(passhash == trypass)            newurl = base + crypturl;        else            newurl = base + "level105.php";        try        {            getAppletContext().showDocument(new URL(newurl), "_self");        }        catch(Exception exception)        {            exception.printStackTrace();        }    }    private String decode(String target, String phrase)    {        for(; target.length() > phrase.length(); phrase += phrase);        String s1 = "";        for(int i = 0; i < target.length(); i++)            s1 = s1 + "" + (char)(int)(Math.pow(Math.log(i), 0.0D) * (double)((target.charAt(i) - phrase.charAt(i) - i) + 5) - Math.pow(Math.log(i), 0.0D));        return s1;    }    public void start()    {    }    private int hash(String target)    {        int hash = 0;        for(int i = 0; i < target.length(); i++)            hash += target.charAt(i) * i * i;        return hash;    }    public void init()    {        SubmitButton.setLabel("submit");        SubmitButton.addActionListener(this);        PasswordField.setEchoChar('*');        PasswordField.setForeground(new Color(192, 192, 192));        add(PasswordField);        add(SubmitButton);        setBackground(new Color(0, 0, 0));    }    private Button SubmitButton;    private TextField PasswordField; }

[Dan]

Prof that it has to be more then 8 chars:

255 x 0 x 0 = 0
+ 255 x 1 x 1 = 255
+ 255 x 2 x 2 = 1275
+ 255 x 3 x 3 = 3570
+ 255 x 4 x 4 = 7650
+ 255 x 5 x 5 = 14025
+ 255 x 6 x 6 = 23205
+ 255 x 7 x 7 = 35700

So with 8 letters the highest value is 35700 for the has. However your hash has a dec value of 108939.

Since 35700 < 108939 the password has to have more chars.

Now the reason why it is hard to give you the same password you hashed is becues there are so many right awasers. The set of passwords that makes the same hash is almost infident and is only lmisted by the size a string can be on the computer.

Edit: it has been some time since i did java fileds but i think that just means it only shows 8 chars in the filed at a time, i don't think it stops it from being more then 8. If it dose who ever made this must not like you :p

[HeavenAgain]

ummm, that is srange then... how can this problem be solved.... it says

code:

PasswordField = new TextField("", 8);

then i'm guessing it wants me to find the url instead? and the pass was just a trick?
OR japanese or chiense letter nahh

edit: ah ha, i think i see it now, the code says is 8, but the acuall thing can accpet more.. i'll try the colision method and hope it works

[Dan]

HeavenAgain @ 15th June 2007, 3:30 pm wrote:

edit: ah ha, i think i see it now, the code says is 8, but the acuall thing can accpet more.. i'll try the colision method and hope it works

Well you could just use the string i posted, or change the 1st char in it to anything to get a differnt string that will still work. There are probly shorter strings that will work too, however i found the easyest one for me just using a penicel and papper. Also if you are more daring you could try to make a string that has all printable chars that will work, however it whould be alot longer and more work (if there is such a colesion).

[Dan]

I just looked at the applet, and it seems the way to hack it is more complex then just finding any password that works with that hash.

The decode function uses the ascii of the pass to decdoe the url. This means that any coslesion other then the right one probly will not help you much.

However i whould have to take the time to look in the decode method more and think about it witch i am to busy to do right now :p

[HeavenAgain]

oh umm i see, the decode takes in the pass too, so they work together i guess?
back to the drawing boarddd
and i thought just figuring out the hash would be finsiihed guess i didnt think much

[Dan]

I just took another look at this and found a solution, however i just don't whont to post it so i am going to write up how i did it and edit this post. Give me a few mins

Part 1
The hash fuction in this challange is a bit of a decoy in that you don't have to trick it or use it at all to find the url. However it dose play a role if you whont to put the password in the applet (tho this is no nessarsy).

The 1st thing we show take a look at is:

Java:

char urlchars[] = {            '\261', '\320', '\323', '\327', '\336', '\324', '\352', '\232', '\343', '\333',            '\311'        };

Now this tells us the URL is of length 11 however this dose not mean that the password is, in fact from the has function and my prof about it's length above we know the password most be longer then this. But as i side befor we don't need the password to break the system, just the url.

Next we take a look at the decode method:

Java:

private String decode(String target, String phrase)    {        for(; target.length() > phrase.length(); phrase += phrase);        String s1 = "";        for(int i = 0; i < target.length(); i++)            s1 = s1 + "" + (char)(int)(Math.pow(Math.log(i), 0.0D) * (double)((target.charAt(i) - phrase.charAt(i) - i) + 5) - Math.pow(Math.log(i), 0.0D));        return s1;    }

There are a few tricks here to throw you off, the 1st one is Math.pow(Math.log(i), 0.0D), this is log(i)^0, no matter the value of i it will allways be 1. The 1st time this is used it is timesing the rest so it has no effect (anything timesed by 1 is the anything part). We can simplify this line to this:

Java:

s1 += "" + (char)(int)(target.charAt(i) - phrase.charAt(i) - i + 4);

Now from this we can tell this method can be revered to find the password from the url. To find part of the url to start this process we can look at this line:

Java:

if(passhash == trypass)            newurl = base + crypturl;        else            newurl = base + "level105.php";

From this we can make an educated guse that the last part of the url we whont to find is .php. When we use this knowalge and put it threw the decode method to find the pass we get ionS (the password is case censtive). This is not the end of the password as it needs more on the end to make a vaild hash however we just need the beging of the pass to find the url.

Now "ion" is a commen ending of words in the english langue and the "S" being captizied leads us to blive that it is a start of a new word. So the easyest way to find the beging is to assume the 1st part is one word and the we can make a quick script to search for words that match this layout. I did this in java:

Java:

import java.io.*; public class wordlist{         static char urlchars[] = {            '\261', '\320', '\323', '\327', '\336', '\324', '\352', '\232', '\343', '\333',            '\311'         };          static String cryurl = new String(urlchars);                         public static void main(String args[]){                  try {                                 BufferedReader in = new BufferedReader(new FileReader("words"));                                 String str;                                 while ((str = in.readLine()) != null) {                                         if(str.length() == 10 && str.endsWith("ion"))                                                 System.out.println(str + "  ->   " + decode(cryurl, str + "S"));                                 }                                 in.close();                         } catch (IOException e) {}         }                 private static String decode(String target, String phrase){                 for(; target.length() > phrase.length(); phrase += phrase);                 String s1 = "";                 for(int i = 0; i < target.length(); i++)                         s1 = s1 + "" + (char)(int)(Math.pow(Math.log(i), 0.0D) * (double)((target.charAt(i) - phrase.charAt(i) - i) + 5) - Math.pow(Math.log(i), 0.0D));                 return s1;         } }

I then searched google for a long list of english words and pasted them in the words file. I then ran my script. It ouputed alot of posable matches however only one of them hadd a nice url come out. This loutput looked like this:

code:

....... ....... ....... divination  ->   Qj_oprt.php domination  ->   Qdhoprt.php emigration  ->   Pflqlrt.php encryption  ->   Perfect.php equitation  ->   Pb`ojrt.php escalation  ->   P`rwrrt.php ........ ....... ......

As you can see the encryption -> Perfect.php line sticks out and is very fiting. This gives us the url and also tells us the 1st part of the password "encryptionS". The url is all we need to get by, however i will do a part 2 where we find the full password in a bit.

[Dan]

Part 2
This is the easy part, we allready have all we need to find the last part of the password. We just have to modify the method we allready used.

We know the 1st letter of the 2nd work of the password is S, and using a modifed version of my prof above about the length of the hash we know the 2nd word has to be 5 chars assuming the 1st letter is a cappetel "S" and the rest are lower case.

Now all we have to do is modify our wordlist search code to search for 5 letter words, starting with S that give the right hash.

Java:

import java.io.*; public class wordlist{         public static void main(String args[]){                  try {                                 BufferedReader in = new BufferedReader(new FileReader("words"));                                 String str;                                 while ((str = in.readLine()) != null) {                                         if(str.length() == 5 && str.startsWith("s") && hash("encryptionS" + str.substring(1)) ==  0x1a98b)                                                 System.out.println(str);                                 }                                 in.close();                         } catch (IOException e) {}         }                 public static int hash(String target) {                 int hash = 0;                                 for(int i = 0; i < target.length(); i++) {                         hash += target.charAt(i) * i * i;                 }                                 return hash;         } }

And it only outputs one word for my wordlist:

code:

dan@localhost ~ $ java wordlist sucks

Now we know the hole password is "encryptionSucks" and this gives us both the right hash and the right url.

[HeavenAgain]

yes, it worked O_O..