Posted by L�pher Cypher on 01/02/06 05:28

Daemon wrote:

>> Let me see if I understand what you are trying to do. You have
>> characters with ascii codes 32..126, you want to generate all possible
>> strings consisting of characters with those codes, whose length is
>> between some minimum and maximum?
>> Like, if min=3 and max=5 and restricting to set 'a'..'z', it'd be
>> aaa, aab, aac, ..., aaz, aba, abb, ..., zzz, aaaa, aaab, ..., zzzz
>> Right? Then why not use recursion?
>>
>> $startCode = 32;
>> $endCode = 126;
>>
>> function gen(&$resultArray,$min,$max,$parentStr) {
>> global $startCode,$endCode;
>> if (strlen($parentStr)+1 >= $min &&
>> !isset($resultArray[strlen($parentStr)+1])) {
>> $resultArray[strlen($parentStr)+1] = array();
>> }
>> for ($i = $startCode; $i <= $endCode; $i++) {
>> $str = $parentStr.chr($i);
>> if (strlen($str) >= $min) {
>> array_push(&$resultArray[strlen($str)],$str);
>> }
>> if (strlen($str) < $max) {
>> gen(&$resultArray,$min,$max,$str);
>> }
>> }
>> }
>>
>> function generate($min,$max) {
>> $resultArray = array();
>> gen(&$resultArray,$min,$max,"");
>> return $resultArray;
>> }
>>
>> $arr = generate(3,5);
>> echo "<pre>";print_r($arr);echo "</pre>";
>>
>>
>> luph
> Thats incredible... exactly what I was talking about... I will have to
> do some work.. so it doesnt go into an array when its generated, cause
> that'll return a large arrays when you want to create large amounts of
> information.
>
> I saw a brute force script for MD5 and was just amaazed at the
> complexity of the script just returning aa = md5(aa) then ab =
> md5(ab)... and so on.
>
> What I was thinking however, to skip the large returns is to place all
> the characters in their own key postition in an array, much like placing
> rows of data in a table to align with its appropriat column
>
> "Age Sex Country
> 12 M UK
> 15 F USA"
>
> So for the brute force script...
>
> Array (known as $stringArray)
> [0] => position 0 (or known as 1)
> [1] => position 1 (or known as 2)
> ........
>
> And that 0 would change 1 as soon as it went through the loop
> properally, and reset 0 as it soon did so.
>
> And then just simply use:
>
> $gen_string = $null; // Nullify the string before using.
> array_reverse($stringArray) // Reverse the array, or itll look like
> [0].[1].[2]...
> foreach ($stringArray as $key => $string) { // Foreach will go threw the
> array from first to last!!
> $gen_string .= $stringArray[$key]; // I'm sure there was an eiser way
> to do this, but its logical!!
> }
>
> But from this script it'll give me a better opertunity too so.
>
> And so far for the reason I have come up with this idea... hey, its
> logical, its not well known so why not build it!! We need more hackers
> in the world!


All right. Let's see again :) One thing you might want to do is to
gather and return data. The second thing you might want to do is gather
and use data.
In the first case, I hear you - the array could get quite large.
In the second case, you wouldn't need an array at all :) Once you get
the string ($parentStr.chr($i)), you may simply call some method which
uses it:

$str = $parentStr.chr($i);
if (strlen($str) >= $min) {
// array_push(&$resultArray[strlen($str)],$str);
// instead:
tryString($str);
}
....
function tryString($str) {
// let's see if that's the key we are looking for here, or do whatever..
}

Anyways, since you are talking about brute force, I'd assume you know
the decryption algorithm, a part or all of the encrypted data, possibly
a piece of clear text, or a way to figure out that decrypted data
resembles what might be clear text. Then,

1) Read encrypted data
2) Generate next key
3) Apply decryption algorithm using generated key
4) See if decrypted data might be clear text
5) If so, store the key and decrypted data somewhere
6) Goto (2)

You don't need to store any keys unless the program thinks it may be the
key data was encrypted with.

Also, brute force is not usually the way to go :) One should resort to
brute force only when one is desperate or one knows that time-complexity
will be relatively small. :) You may want to take a look at DES, which
is not strong and can be cracked using brute force without waiting
decades ;) When I was taking cryptography class, my team was assigned to
decrypt a message encrypted with German Enigma machine. However, some
simplifications on the algorithm were placed and we knew the last three
characters of the clear text. Nonetheless, it took us about 3 weeks to
crack it using brute force, running the program 24/7, and splitting the
whole keyspace into 3 parts :)


--

- lüpher
---------------------------------------------
"Man sieht nur das, was man weiß" (Goethe)

[Back to original message]