String handling issue with Free Pascal

[Sogcelak]

Hello everyone. I'm a 23 years old med student, and I usually write programs in my free-time.

I need a little help here with a program that seem to be borderline useless, but nevertheless, I just want to do it. This is not really a game related thing, but unfortunately I can't post in the "General Pascal" section yet.

There is this MD5 hashing thing. And it's not possible to decrypt it because it works one way. I pretty much know that.

What is possible though, to create a program that would Brute Force a hash to see if there is a match.

When I thought about writing this program, I first thought that computing the hashes will be the hard part, but then I saw that Free Pascal in fact has built in functions for MD5 hashing.

And so I was happy to start writing the program, but soon enough it became an epic fail because I can't do the Maths for a simple Brute Force technique.

I tried Repeat cycles and fors and whiles, but I always ended up with all kinds of complications, including disfunctional methods, and stack overflows. So I tried a recursive approach, but then I couldn't really come up with a base condition that both allows every permutation and won't result in a never-ending cycle.

Basically the program structure should be something like this:

1) Ask the user for the hash
2) Ask the user for an estimated maximum length of the original string(I think at least up to 10-12 characters should be possible without stack overflows, but I might be wrong)
3) Start generating all possible combinations of letters(both small and capitalized) of the english alphabet and numbers, from one character length to the maximum length and see if their MD5 hash matches the input hash.
4) Report strings that matched the hash, or report that no match was found.

Basically my problem is Pascal's extremely weird way of handling string variables...



Procedure Fml;
Var
TestStr:string;
i:integer;
Begin

for i:=1 to 5 do
begin

TestStr[i]:='a';

end;

Readln;

End;


One would expect that this ^ code will result in this: 'aaaaa'. But no. The result is this: '' Empty string. Because I should define the string first before I start messing around with it. And this is extremely frustrating because with my approach, I just DON'T KNOW how long the string will eventually be, and also the length of the string will change from 1 to maximum throughout the process and I can not come up with a reasonable way to counter this...

I don't ask you guys, to write the entire code for me, I just need a pointer for this Brute Forcing algorythm because all I found on the internet were Brute Force methods that worked with strings of known length, or that immediately wrote the strings on the screen instead of computing with them further.

Thanks in advance,

Sogcelak

[AthenaOfDelphi]

Hi Sogcelak,

This page (http://www.freepascal.org/docs-html/rtl/system/stringofchar.html) should be the function you want.

StringOfChar will generate a string containing the specified character of the specified length.

So, testStr:=stringOfChar('a',5) will leave testStr='aaaaa'.

Hope that helps.

Just don't use it to try and brute force our passwords ;)

[Sogcelak]

Thanks for your reply! Seems like I was a bit confusing. The function is nice, but it doesn't solve my issues. The code above was not part of my program, just a quick example of the source of my problem.

The main problem is that I can't get the program to test through all variations. It's a mathematical problem that I can't solve because of the weird way Pascal handles strings. This is what my program should really do:

Input1: Hash: e2075474294983e013ee4dd2201c7a73
Input2: Estimated maximum length of original characters: 4
Process:
Md5('0')->0
Md5('1')->0
Md5('2')->0
Md5('3')->0
.
.
.
Md5('9')->0
Md5('a')->0
Md5('b')->0
.
.
.
Md5('z')->0
Md5('00')->0
Md5('01')->0
Md5('02')->0
.
.
.
Md5('0a')->0
Mdt('0b')->0
.
.
.
Md5('a9')->0
Md5('aa')->0
Md5('ab')->0
Md5('ac')->Match Found
Md5('ad')->0
.
.
.
Md5('zzzz')->0

Output: 1 Match found: ac



Pascal has this nice function in the Md5 unit:

hash:=Md5Print(Md5String(string));

So hashing all the possible combinations, once they are generated, is not an issue.

See if there is a match is not an issue, since a single 'if' condition in the loop will do fine.

Making the program generate all the possible variations is the issue, because I can't write a procedure that handles string lengths dynamically. In Pascal your string must have a defined length, and you can't change that. Only deleting from the string, or adding to a string will change its length and it makes things very complicated in this case.

And no, lol I don't want to use it to break your passwords. Besides I wouldn't be able to. When I got my activation code it wasn't hashed in md5 so I guess your passwords aren't stored in md5 either (which is a pretty good decision as it is getting less and less secure). Cheers :D

[SilverWarior]

Hi Sogcelak!

You are on the right track with your approach but you only forgot one thing. You should pre-set the string lenght before changing its idividual characters using SetLenght method (http://www.freepascal.org/docs-html/rtl/system/setlength.html).

Do mind that if you wanna create all posible strings first you would need quite a lot of memory (NumberOfPosibleCharacters exponeted to StringLenght multiplied by 1 byte if using AnsiString or 2 byte if using WideChar (Unicode).
So having 23 posible chars (english alphabet) and strings with 12 characters lenght you would require you to have 19931.234812266 TB of memory.
So you might wanna create them on demmand:
1. Create a string you wish to test
2. Create MD5 hash of that string
3. Compare generaed hash with input hash
4. Free up a string or reuse it for generating next test string.
5. Repeat until you find result or iterate through all posible strings.

Also do note that this is posible for same MD5 hash string to be generated from different data source even if the size of data sources matches. So you would need to test every posible string.

[Sogcelak]

Hi Sogcelak!

You are on the right track with your approach but you only forgot one thing. You should pre-set the string lenght before changing its idividual characters using SetLenght method (http://www.freepascal.org/docs-html/rtl/system/setlength.html).

Do mind that if you wanna create all posible strings first you would need quite a lot of memory (NumberOfPosibleCharacters exponeted to StringLenght multiplied by 1 byte if using AnsiString or 2 byte if using WideChar (Unicode).
So having 23 posible chars (english alphabet) and strings with 12 characters lenght you would require you to have 19931.234812266 TB of memory.
So you might wanna create them on demmand:
1. Create a string you wish to test
2. Create MD5 hash of that string
3. Compare generaed hash with input hash
4. Free up a string or reuse it for generating next test string.
5. Repeat until you find result or iterate through all posible strings.

Also do note that this is posible for same MD5 hash string to be generated from different data source even if the size of data sources matches. So you would need to test every posible string.

For your last statement, I'm very well aware of that. That's why I want to store the matches to be able to list all of them, because there can be more.

And for the memory issue, this is exactly my problem why I can't store these in a file or something like that. It would maket it super easy, but instead I need to rewrite the same string over and over again to avoid stack overflows, and Pascal doesn't like the idea that the string's length might also be changed in the process, and I'm still searching for a counter. A recursive approach would also work, because then with a character length of 12, only 12 strings would be in the memory at a single time, but unfortunately I couldn't come up with a working recursive code for this problem.

[SilverWarior]

And for the memory issue, this is exactly my problem why I can't store these in a file or something like that.

Go and read my post again. I made you a caclulation in order to show how much memory or HDD space you would require in order to save all posible string variations if you have string 12 character long and there can be 23 posible characters. Even if you go and save that to your hard drive I doubt you have computer with almost 20000 terabytes of hard drive space.


and Pascal doesn't like the idea that the string's length might also be changed in the process, and I'm still searching for a counter.

Pascal doesen't have any problems when you change string size. Simply use the function I proposed.


A recursive approach would also work, because then with a character length of 12, only 12 strings would be in the memory at a single time, but unfortunately I couldn't come up with a working recursive code for this problem.

How did you come up to that? Why do you think you would need 12 strings in your memory?
The number of strings in your memory could only be affected by the number of concurent processes you intent touse (multithreading).
For recursive approach you only need one string stored in the memory at any time. The only thing is that this string gets updated every time before MD5 has is generated from it.

[Sogcelak]

I don't want to save all possible strings, just the ones that are matching the hash.

To avoid further misunderstanding, I will copy my current code here, and maybe you could tell me what's wrong because just when I thought it would work, it doesn't really. It runs, it's trying out everything, but something is bugged...




Program Md5BruteForce;

Uses Md5;

Var

hash,test,tri:string;

Num,Max,j:integer;

Results: array[1..100] of string;


Function NextChar(c:char):char; //This is for changing the characters in the string

Begin

if c='z' then NextChar:='0'
else
if c='9' then NextChar:='a'
else
NextChar:=Succ(c);

End;

Procedure ChangeChar(MaxLength,spot:integer; Var Str:string); //The main procedure

Var

counter:integer;
i:integer;

Begin

counter:=0;


if Str[spot]='9' then

begin

if length(Str)<=MaxLength then

begin

for i:=1 to length(Str) do
begin

if Str[i]='9' then counter:=counter+1; //Count the 9s in the string

end;

if counter=length(Str) then
begin

for i:=1 to length(Str) do Str[i]:='a';
Str:=Str+'a'; //If every character is a 9, then change all of them back to 'a', and add a plus 'a' to the string
end

else
begin
Str[spot]:='a';
ChangeChar(MaxLength, spot-1,Str); //The procedure calls itself, until a non-9 character is found
end;
end;
end
else

Str[spot]:=NextChar(Str[spot]); //If a non-9 character is found then it is simply switched to the next character


End;



Begin

for j:=1 to 100 do Results[j]:='' //Clearing the array, just to make sure...

Writeln('Please Give me the hash');
Readln(hash);

Writeln('Please give me the estimated maximum length of the original text(characters)');
Readln(Max);

test:='a';

Num:=1;

Repeat

tri:=MD5Print(Md5String(test));

if tri=hash then

begin

Results[Num]:=test;
Num:=Num+1; //Storing the matches in an array

end;

Write('Now trying: ',test);
Write(' ');
Writeln('Hash: ',tri); //A bit redundant, but it helped me debug the recursion, and it looks cool so I kept it.

ChangeChar(Max,length(test),test); //Go to the next variation

Until length(test)>Max; //Loop ends if the maximum character length is exceeded

if Num>1 then //Checking if there is more than 0 results

begin

for j:=1 to Num do
begin

Writeln('Result #',j,': ',Results[Num]); //Writing out all the results
end;
end
else

Writeln('Sorry, your hash could not be recovered'); //If the search fails...

Readln;

End.



I was testing with the string 'c7' at maximum length 2 and 3. (hash is: 4d3a21d8c684c09c19b93be911827fd5)
The problem is that eventhough it tries every possible permutation now, for some reason it can't list the results. The output is exactly this(except for the long blocks of tries)
'Result #1:
Result #2:'
And that's it. Empty strings. Arrrrgh it's driving me soooo mad, I'm pretty much done with the hard part, and some stupid error is stopping me.

[Sogcelak]

Nevermind, I'm done with it. It was the stupidest error ever.

In the for cycle when I'm writing the results out
Instead of Results[Num] I should use Results[j]

Now the code is fully functional(except for that it takes forever to decode anything beyond 4 character length) Thanks for the input guys.



Program Md5BruteForce;

Uses Md5;

Var

hash,test,tri:string;

Num,Max,j:integer;

Results:array[1..100] of string;


Function NextChar(c:char):char; //This is for changing the characters in the string

Begin

if c='z' then NextChar:='0'
else
if c='9' then NextChar:='a'
else
NextChar:=Succ(c); //Succ=Next Character in ABC order, next number if the character is a number

End;

Procedure ChangeChar(MaxLength,spot:integer; Var Str:string); //The main procedure

Var

counter:integer;
i:integer;
Begin

counter:=0;


if Str[spot]='9' then

begin

if length(Str)<=MaxLength then

begin

for i:=1 to length(Str) do
begin

if Str[i]='9' then counter:=counter+1; //Count the 9s in the string

end;

if counter=length(Str) then
begin

for i:=1 to length(Str) do Str[i]:='a';
Str:=Str+'a'; //If every character is a 9, then change all of them back to 'a', and add a plus 'a' to the string

end

else
begin
Str[spot]:='a';
ChangeChar(MaxLength, spot-1,Str); //The procedure calls itself, until a non-9 character is found
end;
end;
end
else

Str[spot]:=NextChar(Str[spot]); //If a non-9 character is found then it is simply switched to the next character


End;



Begin

for j:=1 to 100 do

begin
Results[j]:=''; //Clearing the array, just to make sure...
end;

Writeln('Please Give me the hash');
Readln(hash);

Writeln('Please give me the estimated maximum length of the original text(characters)');
Readln(Max);

test:='a';

Num:=1;

Repeat

tri:=MD5Print(Md5String(test));

if tri=hash then

begin
Results[Num]:=test;
Num:=Num+1; //Storing the matches in an array

end;

Write('Now trying: ',test);
Write(' ');
Writeln('Hash: ',tri); //A bit redundant, but it helped me debug the recursion, and it looks cool so I kept it.

ChangeChar(Max,length(test),test); //Go to the next variation

Until length(test)>Max; //Loop ends if the maximum character length is exceeded

if Num>1 then //Checking if there is more than 0 results

begin

for j:=1 to Num-1 do
begin

Writeln('Result #',j,': ',Results[j]); //Writing out all the results

end;
end
else
Writeln('Sorry, your hash could not be recovered'); //If the search fails...

Readln;

End.

[SilverWarior]

Now why not implement multithreading to make everything run faster

[Sogcelak]

I actually needed to look up how multithreading exactly works in Pascal. And I still don't get half of it, so that will take some time. Keep in mind I've hardly ever used objects in my programs, only simple ones. This TThread class is a mess compaired to them.

I've deleted the part of the program where it writes out every try, now it just outputs the result, and it is a lot faster now. At 5 character length it still seems unexplainably slow(I haven't tried with more). This multithreading seems like something that could work but I need to study it further before I can implement it in my program.

[User137]

If you would want to optimize it a bit, i would first get rid of NextChar() function. You could put all valid characters in a string constant, something like

const validstr = 'abcd....ABCD....XYZ0123456789';
Then matter of changing character is simply increasing character index by 1.


index:=1;
validstr[index] is 'a'
inc(index);
validstr[index] is now 'b'

[AthenaOfDelphi]

I actually needed to look up how multithreading exactly works in Pascal. And I still don't get half of it, so that will take some time. Keep in mind I've hardly ever used objects in my programs, only simple ones. This TThread class is a mess compaired to them.

I've deleted the part of the program where it writes out every try, now it just outputs the result, and it is a lot faster now. At 5 character length it still seems unexplainably slow(I haven't tried with more). This multithreading seems like something that could work but I need to study it further before I can implement it in my program.

I have a tutorial that covers the basics of multi-threading (http://www.pascalgamedevelopment.com/content.php?135-Tripping-The-Class-Fantastic/view/1).

[Sogcelak]

@User137
That will be implemented in the program, but first I need to optimize other things. If I want to add capitalized characters into the pool of characters my program uses, then it adds another 23 characters and it will make things a hell lot slower even without the NextChar function.

@Athena
That's a really cool guide you have written but erm... The basics, you say?? Unfortunately for me I could understand it until the second page, and there were things I didn't understand on the first page too(VCL thread??, TDXTimer??). It's just too advanced stuff for me. I don't know most of these functions. I don't know how classes handle these public and protected stuffs, or what's that constructor thing, how does inheriting work, what the hell does "try", "except", and "finally" do etc...etc... Hell, I don't even know how the OS exactly handles multithreading. How am I supposed to tell it how to do it, if I don't even know how it should be working? And finally, I also have no idea about how exactly can I use multithreading to fasten up this program. My program does one thing, and it is trying all different combinations of characters, so I don't see what tasks I could give to another thread. See I'm having difficulties with understanding the most basic things about multithreading, that's why I said I needed to study it a bit before I can implement it in my program.

[pitfiend]

@User137
That will be implemented in the program, but first I need to optimize other things. If I want to add capitalized characters into the pool of characters my program uses, then it adds another 23 characters and it will make things a hell lot slower even without the NextChar function.

@Athena
That's a really cool guide you have written but erm... The basics, you say?? Unfortunately for me I could understand it until the second page, and there were things I didn't understand on the first page too(VCL thread??, TDXTimer??). It's just too advanced stuff for me. I don't know most of these functions. I don't know how classes handle these public and protected stuffs, or what's that constructor thing, how does inheriting work, what the hell does "try", "except", and "finally" do etc...etc... Hell, I don't even know how the OS exactly handles multithreading. How am I supposed to tell it how to do it, if I don't even know how it should be working? And finally, I also have no idea about how exactly can I use multithreading to fasten up this program. My program does one thing, and it is trying all different combinations of characters, so I don't see what tasks I could give to another thread. See I'm having difficulties with understanding the most basic things about multithreading, that's why I said I needed to study it a bit before I can implement it in my program.

I think you need to have a look here (http://www.delphibasics.co.uk/). It's a Delphi "starters" site, were most of the language is explained. It is not very updated to last Delphi version, but the basics are there.

[AthenaOfDelphi]

I think you need to have a look here (http://www.delphibasics.co.uk/). It's a Delphi "starters" site, were most of the language is explained. It is not very updated to last Delphi version, but the basics are there.

I would also add http://www.pp4s.co.uk/main/tutorials.html. A good friend of mine has been using the PP4S tutorials to teach herself Delphi and she's found them pretty good although they do have a preference for Free Pascal.

[Sogcelak]

Thanks for the links guys. I will look at them. Especially the Free Pascal one, since that's what I'm using.