| Author |
Javascript 16 from a mathematical perspective |
zeus_the_moose
ASM freak
Posts: 81
Location: Mpls., MN
Joined: 07.02.06
Rank: God |
|
There are a bunch of threads about Javascript 16 already, but I wanted to make one that deals more with the math of the problem, and not so much blind brute forcing.
Let’s start out by examining the pseudo-c of the encryption function:
/* Prototypes */
int indexOf(char *, char);
char charAt(char *, int);
void main(void)
{
char tab[] = /*long string goes here*/;
int index;
int i;
char entry[20];
scanf("%s", entry);
int n = strlen(entry);
unsigned long int sum = 1;
for(i = 0; i < n; i++)
{
index = indexOf(tab, charAt(entry, i)); //assumed you implemented these
sum = sum + (index*n*i)*(index*i*i);
}
}
We can translate this to the following mathematical formula:
If we examine the term of i=0, we see that it is equal to zero. Thus we can drop this term from our equation.
We can make further simplifications by looking at the limits of the summation. The entry element has a maxlength of 20. This tells us that our summation is finite and n will be a constant. If we can consider this we can do the following (using rules of a convergent series):
Simplifying to:
Note that we cannot pull out the index^2 term because this is not constant, it is dependent on i.
Let’s examine the left hand side of the equation. We know that the answer must be a whole number (or integer). We are using integer values for index and i, and the operations we perform on them will give us integer results.
This means that we can derive the possible length of the entry directly from the equation (since it must be integer values). We are given a checksum value of 88692589, subtracting one gives 88692588.
We can then divide by the possible n values from 0 to 20. I will leave this to you as an exercise, but you will find that the only values of n that will work are 9, 12, and 18. Which means the answer we are looking for is one of these lengths.
For simplicity, I will tell you that the length of the password is either 12 or 18 characters long (the case of 9 will not work). The case of 18 sounds a little long to me, so let’s take a look at the case of a password with 12 characters in length.
Our formula for this case will be the following:
Now, we need to write a brute forcer to discover values for index from the tab array that will solve this equation. Personally, I took the top-down approach by starting at the highest possible index (85) for each character and used 12th character as the outer loop working in. Also, I made a few assumptions about the rules for this. First of all, I assume that the answer will not have a space in it (it would be weird for the result url to have an encoded space or %20 in it). This means that the first 19 indexes (0-18) of tab are invalid and we only need to check from 19 to 85. The second assumption that can be made is that the answer will not have 3 of the same characters in a row (i.e. a string like uniiiiix would be a strange answer). The other assumptions we can make by looking at the math of the formula.
First of all, if at any time the current sum is above 7391049 we can continue to the next number (i.e. if using index value of 85 in one of the four loops gives a sum above 7391049, continue to index value of 84).
We can also look at the case when every index value lower than the current one will always fall short of the number we are looking for. For instance in character 2 of the answer string, we look at the highest possible value that we can have for character 1 which will be 7225 (highest index value of 85 and i value of 1 is 85^2*1^3 or 7225). This means if the current index value in the for loop of character 2 gives us a total sum less than 7391049-7225 or 7383824, we will always fall short for the rest of the indexes in the current for loop since we are checking in a linear fashion. If we see that this is the case, we should break out of the current loop.
However, doing it this way will not solve the problem for you as there are a ridiculous number of collisions. For instance, I ran my program for a couple of hours and found enough valid 12 character passwords to fill up 358 MB of a text document and it was only able to get through the first couple of indexes.
To make this a realistic challenge, more information needs to be divulged about the password so that we can make more eliminations. You will never come upon the answer through blind brute forcing as there are hundreds of millions of valid combinations that work, and it would be a daunting task to parse through that many valid entries to find the one which makes the most sense.
~The keyboard is mightier than the sword.~
Edited by zeus_the_moose on 12-05-08 00:28 |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
slpctrl
Member
Posts: 601
Location: 2147483647
Joined: 19.04.07
Rank: God |
|
We live in a society exquisitely dependent on science and technology, in which hardly anyone knows anything about science and technology. -Carl Sagan |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
s3klyma
Member
Posts: 87
Location: \/--'=')'<'('='--&#
Joined: 02.12.07
Rank: Uber Elite |
|
Wow!
I strongly admire the amount of thought that it must of taken
to create those equations. That's incredible. |
  
|
| Author |
RE: Javascript 16 from a mathematical perspective |
zeus_the_moose
ASM freak
Posts: 81
Location: Mpls., MN
Joined: 07.02.06
Rank: God |
|
This challenge is irritating because in real life if a hash collision occurs, you would be granted access (i.e. my found collision string would get passed through md5() and it would match the md5 found in the database for the particular user).
I strongly feel that this challenge is impossible without some sort of knowledge about the plain text of the password (like the last 4 letters are pass or something along those lines). If this was realistic, collisions would equal solved. Anyone who claims this can easily be solved with a bruteforcer in under an hour has clearly been given some sort of hint or rules that would make this challenge possible.
~The keyboard is mightier than the sword.~
Edited by zeus_the_moose on 12-05-08 02:17 |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
slpctrl
Member
Posts: 601
Location: 2147483647
Joined: 19.04.07
Rank: God |
|
|
s3klyma wrote:
Wow!
I strongly admire the amount of thought that it must of taken
to create those equations. That's incredible.
Thanks
We live in a society exquisitely dependent on science and technology, in which hardly anyone knows anything about science and technology. -Carl Sagan |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
s3klyma
Member
Posts: 87
Location: \/--'=')'<'('='--&#
Joined: 02.12.07
Rank: Uber Elite |
|
LOL.
I was talking about zeus_the_moose
 |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
zeus_the_moose
ASM freak
Posts: 81
Location: Mpls., MN
Joined: 07.02.06
Rank: God |
|
Well, I am now certain that the password we are looking for is 12 characters long (as I suspected). The case where there is 9 characters doesn't have a large character set that will get a high enough value that will give us the answer and the case where there is 18 characters has a small character set because most possibilities go over the value we are looking for and those that don't won't give us the answer. This means that the password must be 12 characters in length.
Which means, we have to receive more information to be expected to solve this problem.
~The keyboard is mightier than the sword.~
Edited by zeus_the_moose on 12-05-08 06:40 |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
stdio
Member
Posts: 67
Location:
Joined: 06.04.08
Rank: God |
|
I really enjoyed this read. I had pretty much given up on calculating this after awhile, but didn't look that much into the math behind it.
However you say now you are calculating 11 character length passwords.. yet you showed how they can only be 9,18, or 12.
I'm going to assume a typo, but thats contradicting yourself 
|
|
| Author |
RE: Javascript 16 from a mathematical perspective |
zeus_the_moose
ASM freak
Posts: 81
Location: Mpls., MN
Joined: 07.02.06
Rank: God |
|
hehe sorry, I am a bit tired and made that mistake. It is 12 characters long.
~The keyboard is mightier than the sword.~ |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
Uber0n
Member
Posts: 1454
Location: Sweden
Joined: 13.06.06
Rank: God |
|
Very good explanation zeus_the_moose, discrete mthematics ftw
http://uber0n.darkillusion.org/ |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
clone4
Perl Wisdom Seeker
Posts: 159
Location: print scalar(localhost);
Joined: 25.11.07
Rank: HBH Guru |
|
If I wasn't dumbass on math I would read the whole post, but as I wouldn't understand a sh*t, I just read beggining and end still really impressive...
|
|
| Author |
RE: Javascript 16 from a mathematical perspective |
zeus_the_moose
ASM freak
Posts: 81
Location: Mpls., MN
Joined: 07.02.06
Rank: God |
|
You should see my homework 
~The keyboard is mightier than the sword.~ |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
zeus_the_moose
ASM freak
Posts: 81
Location: Mpls., MN
Joined: 07.02.06
Rank: God |
|
.
~The keyboard is mightier than the sword.~
Edited by zeus_the_moose on 12-05-08 10:50 |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
jjbutler88
Member
Posts: 124
Location: Local to the premises
Joined: 22.04.07
Rank: HBH Guru |
|
IMHO, bruteforcing should always be the last approach, this is very refreshing, kudos to you zeus, later on (when I havnt just got out of bed  ) I will read and really try to understand the mathematics behind this challenge (the only js one that has eluded me so far).
For people learning to program (in any language) who are even the slightest bit into maths, check out:
www.projecteuler.net
Im starting it using python and its proving to be a god language to do it in (because you can treat is as an interpreted language or a compiled language).
 |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
richohealey
Python Ninja
Posts: 943
Location: #!/usr/local/bin/python
Joined: 01.05.06
Rank: Ninja |
|
|
zeus_the_moose wrote:
This challenge is irritating because in real life if a hash collision occurs, you would be granted access (i.e. my found collision string would get passed through md5() and it would match the md5 found in the database for the particular user).
Well it doesn't, so basically, if I can do it, so can someone else.
I PWNT Caity in FOUR MOVES at Chess "Life's not fair; but the root password helps."~ The BOFH
Nice one R3l3ntl3ss^^
Check out proxyElite
[02:24] <kaksii> I SMOKE COCK! |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
foxfire100
Member
Posts: 3
Location:
Joined: 20.05.08
Rank: Wiseman |
|
I'm impressed.
I knew there were mathematical ways to greatly narrow down the strings to try, and I had suspicions that 10 characters wasn't possible. Although I am up way past my bedtime and it is nearing the end of my senior year, so I have ceased to care about math. I honestly didn't even remember you could pull a constant out of a sum when I read through the explanation XD That's how distant I am from math at the moment. |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
lazybum
Member
Posts: 24
Location:
Joined: 18.01.08
Rank: Active User |
|
Hmm, I just got out of calc for the summer so I understand this stuff. However, the second I look at the formulas I think "Ooohh integral c*SNAP* wait whats that big lookin' E thing, is that an = sign?" --- Ah the mind numbing effects of summer. |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
SwartMumba
Member
Posts: 208
Location: ereh m'I ---> XT
Joined: 18.09.07
Rank: Elite |
|
It is called sigma (sigma notation). You use it when you are working with a sum of a series.
Every morning in Africa, a gazelle wakes up. It knows it must run faster than the fastest lion or it will be killed.
Every morning a lion wakes up. It knows it must outrun the slowest gazelle or it will starve to death.
It doesn't matter whether you are a lion or a gazelle. when the sun comes up, you better start running. |
|
| Author |
RE: Javascript 16 from a mathematical perspective |
fallingmidget
Member
Posts: 1053
Location: New Jersey
Joined: 18.09.07
Rank: God |
|
well i still insist there isi a way of doing this challenge without a bruteforcer or things like that and i will find it one day
|
|
| Author |
RE: Javascript 16 from a mathematical perspective |
lazybum
Member
Posts: 24
Location:
Joined: 18.01.08
Rank: Active User |
|
|
SwartMumba wrote:
It is called sigma (sigma notation). You use it when you are working with a sum of a series.
I know, I was just making fun of myself.
It might be possible to find a semi(less recursive at least) linear solution to this if you get rid of the for loop and replace it with its long form, assuming a length of 12. The first index would have sum + 0 because of the multiplication. So you'd be left with the other 11 loops written out long form. Simplify this as much as possible using algebra and set it equal to 88###### and go from there. I haven't solved that far yet so I don't know if it'll work but it should make things easier at least.
'Course the main problem here is that you then end up with an equation with 11 different variables where index would be. So you still likely need to brute force those 11 variables. In addition the first character in this scheme can be ANYTHING since it won't have any effect on the total sum. Even if you can solve for the 11 variables you still have a potential of 255 possible answers. With each possible variable combo increasing the total possible answers exponentially.
Edited by lazybum on 27-05-08 06:26 |
|
Main:
