Brute Force Password Cracking via Orthometer Class

Don’t worry about people stealing an idea. If it’s original, you will have to ram it down their throats. — Howard Aiken



Years ago I bought a CD full with password protected PKSFX archives. It came with 4 passwords, leaving the option to purchase the other passwords if desired. I was young and poor, so buying those passwords was out of question. I also was brought up in the communistic GDR and some part deep inside of me just thought that this buisiness model was just wrong. I had purchased the CD believing all contents was free for me to use. Obviously being poor and believing something is not right is a poor excuse for trying to steal. I did mention though that I was young – and not very wise yet. Another point contributing to my defense is the fact that I never managed to actually break any of those passwords.

At that time, I sat down and wrote a little application in turbo pascal which was trying to brute force crack the passwords. Now there is nothing illegal about that as long as one is not successful and it was a good exercise. Several days ago I sorted out a heap of old CDs and guess what? I stumbled over the CD I was mentioning. Now all the applications on the CD are absolutely useless nowadays. And being successful cracking the passwords would probably still be illegal (you know how it is – even useless things do have copyrights and if you cant make money selling them anymore, why not suit people for breaking those copyrights). Nevertheless I felt an itching in my fingers – I really had to rewrite that little application – with modern programming languages – on modern hardware.

Needless to say that all this was absolutely not about speed. If it was about speed I would have done the whole thing in assembler, and I might still do. It was just curiosity that drove me. The choice of C# because of its simplicity. Talking about simplicity: I have no clue how I ever managed to write this back then. Unfortunately I lost the code so I will never know how I did actually implement it. I had a hard time putting all this together today – with more knowledge, and a little bit more wisdom.

First I thought the implementation would actually be quite simple. Create a dictionary (or rather character set including all the symbols used to generate the password string, but I like to see each symbol as word and the password string as sentence if that makes sense) and then just treat it as a number system whose base n equals the amount of symbols in it. Conversions between numbering systems should be a simple thing for each programmer.

It did not work out quite well I must admit. The problem is, that the decimal, hexadecimal and even the binary system all do not care about leading zeros. If we look at them as symbols though they are in fact a different symbol than “normal” (or non-leading, trailing) zeros. So if using the BaseN conversion approach one will simply not get all possible combinations. For example if the character “a” is the first symbol in your character set all two symbol sentences will start with a “b” (if “b” is the second character of course). You are missing out on all possible sentences starting with an “a”.

So I did some web crawling and had to figure that I am either not good at it or that there simply is not much good information about creating an algorithm like that. I found some information on “orthometers” though which kind of was exactly what I needed. What the hell is an orthometer? It is, for example, the thing in your car which shows the distance you have been driving so far. Orthometers also have been used on displays in railroad stations and the like – airports as well. In the early days of the web every second homepage used to have an orthometer like display which told the visitor how many other people had been visiting the site before him/her.

An orthometer always has a fixed length and it is pretty straight forward to loop through it and show every possible combination of letters – including leading zeros of course (or leading “a”s). Now one performs another loop which in turn performs this loop as often as the string length we desire.

The first mentioned approach, just converting the numbering systems and use the decimal system as counter would have been implemented like this:

while (true)
{
    remainder = number % this.charSet.Length;               // calc the modulo
    number = number / this.charSet.Length;                  // get the dividend
    newSentence.Insert(0, this.charSet[(int)remainder]);    // insert the char at the beginning
    if (remainder == 0) break;
}

It takes the variable number, puts the character which is pointed to by the modulo of the number and the size of the character set (the remainder) at the beginning of the new orthometer/password string, and continues to do so with the new divisor as long as the remainder is not zero.

To get a fixed length sentence though, instead of stopping the loop whenever the remainder is zero, we continue doing it SentenceLength times (where SentenceLength is the length of the orthometer (i.e. password) string):

for (int i = 0; i < SentenceLength; i++)
{
    remainder = number % this.charSet.Length;               // calc the modulo
    number = number / this.charSet.Length;                  // get the dividend
    newSentence.Insert(0, this.charSet[(int)remainder]);    // insert the char at the beginning
}

Logically, as we are inserting the remainder at the beginning of the string, in the first case it will stop whenever it reaches the zero, in the latter case it will continue adding zeros (or rather the first symbol of our character set) until the whole string is padded. That is pretty much all there is to it. Now you can throw an integer at the function and it will return the corresponding number of the numbering system with the base of characterset size.

To get all possible combinations of all characters in a given character set one has to perform this loop characterset size to the power of sentence length times. That is for a sentence length of 4 and a character set of CS = { ‘a’, ‘b’ } that has a length of 2 the loop has to be performed 2 ^ 4 = 16 times.

Possible sentences = { aaaa, aaab, aaba, aabb, abaa, abab, abba, abbb, baaa, baab, baba, babb, bbaa, bbab, bbba, bbbb }

As usually we dont know the length of the password, we need yet another loop to loop through different sentence lengths, predefined by minLength and maxLength.

As the C# class I created is quite lengthy (due to extensive commenting) I refrain from posting it here. Instead you can download a sample application I programmed at the bottom of this article. The source for the class itself you will find in Orthometer.cs, the implementation and usage example in Program.cs. The application starts 7z.exe (the SevenZip commandline executable) in a new process, providing the password as a commandline parameter. After execution of 7z.exe it checks the exit code and if that one equals zero it has found the password, else it continues:

Here a screen shot of an unsuccessful cracking attempt (i.e. minLength and maxLength set to 1) of the file workdir.7z (the actual password is “abc”):

Password not found

An here a screen shot of a successful cracking attempt:

Password found

As a last note: after running this application you will realize how slow this is. The biggest (or smallest …) bottleneck here actually is 7z.exe and the format of the archive .7z as well. Zip files work a lot faster, but even then it will take ages to brute force a password with a decent length. As my goal was not to actually provide a working and speedy brute force cracker, but to study and implement a variable length orthometer I have to conclude that I, nevertheless, indeed fulfilled it. Optimization could be done in several ways. First of all I would implement my own unpacking algorithm to get rid of the overhead of starting new processes. This would also create the possibility to perform the unpacking in memory. First of all this would be faster than having to read the file from the harddrive every time, also this would allow threading, the next thing I would implement to speed up things. Obviously you can implement threading while accessing the harddrive, but due to its (the harddrives) slowness you would just create another bottleneck. Last but not least (actually this should be the first thing to consider) I would choose a different programming language, namely assembler, to use as few clock cycles as possible for each operation.

Another thing to consider is the use of BigIntegers for the loops. The Integer Type simply does not allow big enough numbers to create passwords longer than 12 characters, if the character set only consists of lowercase characters that is (remember? characterset size ^ sentence length?).

[dm]5[/dm]

VN:F [1.9.18_1163]
Rating: 0.0/5 (0 votes cast)
Tuesday, January 27th, 2009 at 21:47
102 visits
  • KonstantinMiller
    Jul 6th, 2009 at 19:36 | #1

    Hello. I think the article is really interesting. I am even interested in reading more. How soon will you update your blog?

    VA:F [1.9.18_1163]
    Rating: 0.0/5 (0 votes cast)
    • Jul 6th, 2009 at 20:09 | #2

      I only sporadically update this blog, whenever I do find some interesting stuff that aint to complex. The last few months I have had some quite big projects, far too big to write articles about and far too time-consuming to leave much time for this blog. A few days ago I did a little C# crackme – nothing fancy, but it shows how any “protection” doesnt make much sense if it does not use an obfuscator. That might also make a good article about weather protections make much sense at all. Still I need to find the time to actually write the post about it, even though the code is finished. Also I am working on an XNA control library – again far too much code to post here, but if that is finished I will post the library and obviously the info on how to implement, use and extend it. Next would be a small game actually implementing that library and possibly an article about implementing a state pattern for a game. Maybe :P

      VN:F [1.9.18_1163]
      Rating: 0.0/5 (0 votes cast)

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>