
August 18th, 2006, 06:42 AM
#1
Member
Help with algorithms
Im new to algorithms and am not haveing much luck on google, dont think im useing the right terms but here goes:
Im solveing a crackme, for fun. I've studied the code and determined the serial must add to 2F2 along with some other constraints. It is 6 chars long.
First I figured i could write a nested loop that counts from
1, 1, 1, 1, 1, 1 to 256, 256, 256, 256, 256, 256
That would take way too long, so I come up with an algorithm, it almost works except keeps returning to 256, were everything started. And thats where I need help.
It does not get much further then 255, 255, 127, 4, 1, 1
To descirbe my algorithm, I would first test for sum == target then,
if sum < target I would increase the current value by value = value + (max  value)/2
if sum > target I would reduce the curent value by value = value  (value  min)/2
max would equal 256, and min 0, but once sum < target, I set min equal to curent value since if the current value results in a sum less then what I want, reduceing it further makes no sence.
I think this is called divide and conquer but not sure. Where can I learn more about these type of algorithms?
MyBox:
Asus P5VDCMX
Celeron 2.8GHz
512MB DDR 400
WD 250GB SATA
DVDROM, CDRW
Thermaltake 430W PSU
Netgear WGT624 Router

August 18th, 2006, 09:52 AM
#2
Hi
A general note:
R. Sedgewick has written a book about Algorithms[1], which I still use frequently.
Also check the web for keywords like "backtracking[2]" and "dynamic programming[3]".
Have also a look at the webpage of the International Olympiad in Informatics[4]  an
excellent resource for algorithmic problems, often with documented solutions.
Note that it is a very crucial conceptual difference whether you need one solution
or all solutions  the right choice for the right algorithms is of utmost importance.
More specific about this kind of problems:
It seems not valid here, but in general, "serialnumbers" consist of letters AZ (az) and
numbers 09. A nested loop (with jumps from 58 to 65 and 91 to 97) often is a reasonable
approach.
A boost in performance can be achieved by a clever way of doing the "checks": in the innermost
loop, to the computationally least intensiv checks first, and break after each check if not
successful.
If you have such a nice thing like a "additive checksum", you can do what you do: break
a loop as soon as the partial sum is larger than the intended checksum.
about this problem
You have the classic problem that you have to "reinitialise" a value. Backtracking comes
to my mind, but clearly is too much of an overhead here. Hence, you can do this "manually".
To illustrate this idea, here is a (in principle useless, and yes I know one could use ForLoops
as well ...) example just looking at 2 chars:
Code:
A = 0
B = 0
sum = 240
While (A <= 255)
While (B <= Min(sum  A, 255))
If (A + B = sum) Then
...
End If
B += 1
End While
B = 0 ' <
A += 1
End While
Certainly there are some more ways to decrease the space of possible "configurations", where
a configuration is defined as a 6dimensional vector in the 6dimensional discrete finite
space of your problem. However, you have to be very careful while reducing since often,
the dimensions are not permuteable, ie. you cannot exchange the chars A,B,C,D,E,F.
If the only condition to be satisfied is the "additive checksum" to be 754 (2F2) then you
can exchange the chars, hence you can demand that A <= B <= C <= D <= E <= F, which greatly
reduces the candidate configuration space. Furthermore, once you have found one "solution",
you have actually found 6!/(sim)=720/(sim) valid solutions (where sim is a factor coming
from repetitions in the solution, ie if you have 2x "250" but the other 4 values are unique,
this would be a factor 2. if you have 3x "250" and 2x "15" this number sim would be 3!*2! etc.).
Be careful when you increase a value by more than "1" as you do. If you are not careful
enough, you may miss a/the solution.
I may have misunderstood your current problem  if so, please paraphrase
Cheers
[1]
http://www.amazon.com/gp/product/020...956113?ie=UTF8
[2] http://en.wikipedia.org/wiki/Backtracking
[3] http://en.wikipedia.org/wiki/Dynamic_programming
[4] http://olympiads.win.tue.nl/ioi/
If the only tool you have is a hammer, you tend to see every problem as a nail.
(Abraham Maslow, Psychologist, 190870)

August 18th, 2006, 04:33 PM
#3
This may be stating the obvious, but you could cut down loop work by a dimension by calculating 'F'...
F == 754  (A + B + C + D + E)
IT, ecommerce, Retail, Programme & Project Management, EPoS, Supply Chain and Logistic Services. Yorkshire. http://www.bigi.uk.com

August 18th, 2006, 05:02 PM
#4
Member
sec_ware That was extreamly helpfull, I am well on my way to solveing this problem now.
I am so greatfull for all this information I am adding it to my documentation, and notes. Your explanations are easy for me to understand compared to other sites I viewed.
PS Id give you more AP points but system refuses
MyBox:
Asus P5VDCMX
Celeron 2.8GHz
512MB DDR 400
WD 250GB SATA
DVDROM, CDRW
Thermaltake 430W PSU
Netgear WGT624 Router

August 23rd, 2006, 06:17 AM
#5
Member
UPDATE :)
I am glad to announce I have completed that chalenge. My final progie was able to calculate the corect answer in 2.12 minutes This was achived after realizeing the three conditons
A was determined by value of F, D by C, and E by B
I also noted they problably only used printable characters, reduceing my search futher.
Your secret of A<=B<=C<=D<=E<=F though didnt help this puzzel, I did try this technique of counting and it amazeingly reduces the range by half. Thanks for this great tip!
Your idea Min(sum  A, 255) realy helped me, I realize this meant B would never go larger then needed to develop target sum. So I calculated sum in inner loop, and checked for sum > target
I cannot thank you enough.
MyBox:
Asus P5VDCMX
Celeron 2.8GHz
512MB DDR 400
WD 250GB SATA
DVDROM, CDRW
Thermaltake 430W PSU
Netgear WGT624 Router

August 23rd, 2006, 09:28 AM
#6
Hi
Congratulation!
Your secret of A<=B<=C<=D<=E<=F though didnt help this puzzel, I did try this technique of counting and it amazeingly reduces the range by half. Thanks for this great tip!
This was to be expected  the 6 chars are not interchangeable, which is a necessary
condition for this restriction to be valid.
I also noted they problably only used printable characters, reduceing my search futher.
As said, this makes perfectly sense  now you understand (However, I guess you already
know that) why people say use special characters in your passwords
Continue with the next challenge Have you seen these: crackits[1] by white_scorpion,
formerly known here as lepricaun (there is a thread about them[2]).
Cheers
[1] http://www.whitescorpion.nl/crackits/index.html
[2] http://www.antionline.com/showthread...hlight=secware
If the only tool you have is a hammer, you tend to see every problem as a nail.
(Abraham Maslow, Psychologist, 190870)

August 23rd, 2006, 07:16 PM
#7
Member
Thanks so much, I love these chalenges. Gona try them next.
I did notice, while trying the A<=B trick, that I could use an algortihm next_predicate from the STL library, only after trying to code one my self. I noticed it was extramly fast with a set of 6.
MyBox:
Asus P5VDCMX
Celeron 2.8GHz
512MB DDR 400
WD 250GB SATA
DVDROM, CDRW
Thermaltake 430W PSU
Netgear WGT624 Router
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

