Prog 3... Optimization?

Put your programming skills to the test in these challenges.

Prog 3... Optimization?

Post by mzungudo on Fri Feb 24, 2012 8:58 am
([msg=64596]see Prog 3... Optimization?[/msg])

I was really hoping never to have to ask for specific help on any mission... but at this point I need to know where my problem is before I set off to try and solve it.

I have been working on this mission for about 2 days. I have read all the forum posts and the walk-through article, I completely understand the php code and how it works. I have created a program in both Perl and Java that successfully completes the decryption using a brute-force method that is as efficient as I can imagine. However the Perl program requires 7.5 minutes and the java program requires even longer to decode the message. So the problem is the time required to decrypt. Here is a list of where the problem may be and I would like to know others ideas on which area seems most likely the problem:

1. The brute force method used (vague to keep from spoiling): From what I can tell I am using the same idea as others. Loop through possibilities of first letter in the serial taking into account ranges and killing impossible combinations. I get 576 combos for first value. Using these possible combos move to next letter in serial, calc the intmd5Total for each one and find new list of possible combos. on This step I get around 4000 combos. Repeat this method until i get to a character I know is in the serial. This allows me to kill LOTS of possible combos. I continue this process until I have reached the end of the PWhash. I incorporate this knowledge into my brute-forcer and quickly determine the PWhash within a few more steps and from there the program quickly finishes off to the end. The biggest problem is between the characters 6 and 7 of the serial because the total possible combinations reaches around 650,000 and requires 3+ minutes to go through. Also the characters 26 to 27 cause a problem for the same reasons. Those two spots account for around 7 minutes of the 7.5 minute runtime. The number of loops used to get combos up to and including character 7 is 68,876,384 while the Total loops to do the whole program is 93,922,808;. I have tried thinking of methods that would skip these characters and continue on to later characters that are known, but the loss of knowledge of the intMd5 value seems to only increase the number of possible combinations and loops necessary to pick up in a new place.

2. The language I am using: I understand perl might be slower than a compiled language like C. Also, I only started learning perl a week ago so I am by know means an expert at writing the most efficient code possible. The only other language I know right now is Java, so I tried it in that and got slower results. Do i need to breakdown and learn C?

3. The computer I am using. A brute force program requires lots of processor cycles. My only computer is a netbook asus eeepc 1201N with a quad-coreish like setup totaling 1.6Ghz. However, perl doesn't do its best to utilize this quadcore like setup and the script only ever runs at 25% cpu utilization so really its like running on a 400Mhz machine.

I could really use some help with this as I am completely stuck. If someone could perhaps look at my code or run my code on their faster machine, or suggest a different brute forcing method, or convert my code to C and see if it runs faster... anything that could help. I would really like to know where my problem is!

-- Fri Feb 24, 2012 3:42 pm --

Well I automated the perl script to keep trying the mission over and over again (sorry to HTS for spamming your server >.<) to get a variety of times and I eventually won. It decrypted one of the strings in 1 minute. However the time ranges still go from 1 min to 8 min with an average around 5min. I would really like to know how to optimize this code so I can pass the mission each time. Though this makes me wonder if it really has a lot to do with my crappy netbook doing the crunching instead of a standard desktop. Please any help would be appreciated from someone who would be willing to look at my code. Please PM me.

-- Sun Mar 11, 2012 6:36 am --

As another update to anyone finding this helpful. Me and QtDevl worked out a slightly more efficient system which is a hybrid between finding all possibilities each step of the way and using a recursive tree structure to brute-force the possibilities. This proved to be faster than either method alone. On top of that, I extended my program to fork 3 times to take advantage of my dual-core dual thread (ie quad-coreish) processor. Because each search path is independent of the others we can split the program into 3 programs (or more depending on your processor) each searching 1/3 of the total possibilities. In my case it allowed my program to utilize 75% of the processor instead of 25% (i didn't bother to use 100% since that might cause other problems). With these amendments I can get the correct solution in the required time 95% of the time. If I were using a proper desktop with a 3+GHz processor then that should easily move to 100% since the program would then be nearly twice as fast.

If anyone has found this helpful and has further questions feel free to pm me and I can help answer your questions.
mzungudo
New User
New User
 
Posts: 4
Joined: Fri Feb 24, 2012 7:48 am
Blog: View Blog (0)


Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests