46
\$\begingroup\$

As an attempt to learn multithreading better, I wrote a program to crack the password of a ZIP file. It is sort of slow, processing a three-digit password of the 95 printable ASCII characters in about 1:45 minutes. This is my class that actually handles the cracking:

class DecryptPassword
{
    private readonly List<char> _charList;
    private readonly int[] _currentPassword;
    private readonly string _endPassword;

    public DecryptPassword(List<char> charList, string startPassword, string endPassword)
    {
        _charList = charList;
        _endPassword = endPassword;

        var passwordLength = Math.Max(startPassword.Length, endPassword.Length);

        _currentPassword = startPassword.Select(c => _charList.IndexOf(c)).ToArray();

        while (_currentPassword.Length != passwordLength)
        {
            _currentPassword = _currentPassword.Concat(new [] {0}).ToArray();
        }
    }

    public string CalculatePassword()
    {
        while (true)
        {
            var password = GetPasswordAsString();

            try
            {
                if (ZipFile.CheckZipPassword(Environment.GetFolderPath(Environment.SpecialFolder.Desktop) + "\\CrackMe3.zip", password))
                {
                    return password;
                }
            }
            catch (BadCrcException)
            {
                // For some reason, sometimes a BadCRCException is thrown.
                // I have never had it thrown on the real password,
                // but this may be an issue for that.
                // My best guess is that the speed of access the file,
                // or perhaps accessing it from multiple threads, is the issue
            }

            if (password == _endPassword) { break; }

            CalculateNextPassword();
        }

        return null;
    }

    private void CalculateNextPassword()
    {
        for (var index = _currentPassword.Length - 1; index >= 0; index--)
        {
            if (_currentPassword[index] == _charList.Count - 1)
            {
                _currentPassword[index] = 0;
                continue;
            }

            _currentPassword[index]++;
            break;
        }
    }

    private string GetPasswordAsString()
    {
        return new string(_currentPassword.Select(i => _charList[i]).ToArray());
    }
}

The constructor takes the character set to be used and a beginning and ending range of passwords. For now, it assumes both passwords are the same length, which is useful for when you know the number of characters in the password.

CalculatePassword() iterates over the range of passwords, and returns the password when found. If the password is not found, it returns null.

CalculateNextPassword() will calculate the next password in a manner similar to addition in base-N math.

GetPasswordAsString() will return the current password, stored as an array of ints, as a string.

I generate my tasks like this, leaving Windows to manage the threads. Based on watching it in debug mode, it does create several threads, but not 95:

// characters sorted by ASCII code
private static readonly List<char> CharList = new List<char>
{
    ' ',
    '!',
    '"',
    '#',
    '$',
    '%',
    '&',
    '\'',
    '(',
    ')',
    '*',
    '+',
    ',',
    '-',
    '.',
    '/',
    '0',
    '1',
    '2',
    '3',
    '4',
    '5',
    '6',
    '7',
    '8',
    '9',
    ':',
    ';',
    '<',
    '=',
    '>',
    '?',
    '@',
    'A',
    'B',
    'C',
    'D',
    'E',
    'F',
    'G',
    'H',
    'I',
    'J',
    'K',
    'L',
    'M',
    'N',
    'O',
    'P',
    'Q',
    'R',
    'S',
    'T',
    'U',
    'V',
    'W',
    'X',
    'Y',
    'Z',
    '[',
    '\\',
    ']',
    '^',
    '_',
    '`',
    'a',
    'b',
    'c',
    'd',
    'e',
    'f',
    'g',
    'h',
    'i',
    'j',
    'k',
    'l',
    'm',
    'n',
    'o',
    'p',
    'q',
    'r',
    's',
    't',
    'u',
    'v',
    'w',
    'x',
    'y',
    'z',
    '{',
    '|',
    '}',
    '~',
};

static void Main()
{
    List<Task<string>> tasks;
    StartTasks(out tasks);

    Console.WriteLine(tasks.First(t => t.Result != null).Result);
}

private static void StartTasks(out List<Task<string>> tasks)
{
    var source = new CancellationTokenSource();
    var token = source.Token;

    // split problem into 95 tasks, each group calculates as follows:
    // "c  ", "c !" "c "", ... "c! ", "c!!", ... "c~}", "c~~"
    tasks = CharList.Select(c => StartTask(c + "  ", c + "~~", token)).ToList();

    while (true)
    {
        Task.WaitAny(tasks.ToArray());

        if (tasks.Any(t => t.Result != null))
        {
            Console.WriteLine("Cancelling");
            source.Cancel();
            break;
        }
    }
}

static async Task<string> StartTask(string start, string end, CancellationToken token)
{
    var decryptor = new DecryptPassword(CharList, start, end);
    var task = new Task<string>(() => decryptor.CalculatePassword(), token);
    task.Start();
    return await task;
}

Next on my list is to generate more tasks, especially when working with larger passwords, so basic pointers on how to split the password into groups for each task more efficiently would be welcome, but please do not provide a full solution - I need to think this through myself.

\$\endgroup\$
  • 5
    \$\begingroup\$ Just a question... this is clearly riffing on "I'm in ur base killing ur mans". Since it's a funny title, should it be edited to use "ur" instead of "your"? I know that we often frown on this, but "your" won't have anything to do with future searches for this issue, which should be gotten by keywords "crack" and "password" and the tags. \$\endgroup\$ – Almo Dec 11 '15 at 15:52
  • 5
    \$\begingroup\$ That is messing with the grammar too much for my tastes. \$\endgroup\$ – 23fc9a62-56de-47fb-97b4-737890 Dec 11 '15 at 16:02
  • 1
    \$\begingroup\$ Ok! Was just a thought. :) \$\endgroup\$ – Almo Dec 11 '15 at 16:07
  • \$\begingroup\$ @Almo: knowyourmeme.com/memes/in-ur-base, it's "killing your dudes", with leet-speak spelling at your discretion. \$\endgroup\$ – Peter Cordes Dec 12 '15 at 19:31
  • \$\begingroup\$ Here's the version I'm referring to: blogcdn.com/massively.joystiq.com/media/2008/03/… I've always seen it this way, never saw the one with better spelling. :) \$\endgroup\$ – Almo Dec 12 '15 at 19:51
14
\$\begingroup\$

Passing the CancellationToken to the Task constructor allows Cancel() to work only if the task has not yet started. Also pass the token into CalculatePassword() and check it every loop iteration:

while (true)
{
    token.ThrowIfCancellationRequested();
    // ...
}

Accessing Task.Result ends up calling Task.Wait(). So you're waiting for any task to be done, then waiting again for the first one. Generally, only call Task.Wait() from Main(), and only if the task is already off the main thread.

Here's one way to simplify the task code:

static void Main()
{
    // Start with a background task to avoiding deadlocking the main thread.
    string result = Task.Run(async () => await FindResultAsync()).Result;
    Console.WriteLine(result);
}

private static async Task<string> FindResultAsync()
{
    var source = new CancellationTokenSource();
    var token = source.Token;

    // split problem into 95 tasks, each group calculates as follows:
    // "c  ", "c !" "c "", ... "c! ", "c!!", ... "c~}", "c~~"
    List<Task<string>> tasks = CharList.Select(
        (c) =>
        {
            var decryptor = new DecryptPassword(CharList, c + "  ", c + "~~");
            return Task.Run(() => decryptor.CalculatePassword(token), token);
        }).ToList();

    foreach (Task<string> task in tasks)
    {
        string result = await task;
        if (result != null)
        {
            Console.WriteLine("Cancelling");
            source.Cancel();
            return result;
        }
    }

    return null; // No result.
}

There are still opportunities for optimization here. For example, you could figure out how to evaluate the tasks as they complete, rather than in order.

Consider refactoring DecryptPassword into a static class, converting class members into parameters. Stateless designs are generally easier to parallelize because you don't have to worry about shared state. See Hushpuppy.Http.HttpServer for an example of a stateless, asynchronous design.

Finally, Stephen Cleary's excellent articles on Task.Run Etiquette really helped me understand how to create and consume tasks, and should be required reading for anyone interested in this topic.

\$\endgroup\$
35
\$\begingroup\$

You're not seeing 95 threads because of how Tasks work. The documentation for the Task class says that "tasks typically run asynchronously on a thread pool thread". The thread pool will limit how many tasks will run at one time, so when you call task.Start() when the pool has reached its limit that task won't start executing until one of the pool threads finishes running and becomes available.

Since these are compute intensive threads, having more threads running than you've got hardware threads will actually slightly slow things down due to the extra task switches and related cache misses.

\$\endgroup\$
  • \$\begingroup\$ Yes, I know that a Task != a Thread, and I have heard of the last issue. Good answer, though, so +1. \$\endgroup\$ – 23fc9a62-56de-47fb-97b4-737890 Dec 11 '15 at 15:12
25
\$\begingroup\$

Assumption of a possible bug

I assume that you only have tested this with a password which length is the same as Math.Max(startPassword.Length, endPassword.Length); and if that is true I think this won't work if you won't know the length of the password.

The int[] array has the same length as the result of the Max() call and each overlapping will be taken as 0 into the array which equals " " in the charList.

Assume the password of the file is "aaa" and you pass startPassword = "aaa" and endPassword = "aaaa" then the first call to GetPasswordAsString() will return "aaa " which clearly isn't "aaa".

Naming

A classname should be made out of a noun or a noun phrase but DecryptPassword is named more like a method. In fact it would be a good name for a method.

Constructor

  • The _currentPassword can be created more idiomatic like this

    _currentPassword = startPassword.Select(c => _charList.IndexOf(c))
                       .Concat(Enumerable.Repeat(0, passwordLength - startPassword.Length))
                       .ToArray();
    
  • Because you neither change the charList nor do you use any of the List<T>'s method you should change this to a IList<char>.

CalculatePassword()

Environment.GetFolderPath(Environment.SpecialFolder.Desktop) + "\\CrackMe3.zip"  

As this won't ever change you shouldn't recreate this any time in a loop. Pass the complete filename either into the constructor or into this method.


Consider

  • to precalculate passwords and pass them to the CalculatePassword() method
  • to create copies of that zip file so each task operates on a separate file to avoid file locks
  • to load (if possible) the zip file into memory to avoid the I/O bottleneck
  • to use a char[] instead of an int[] array this will remove the need to call Select().
\$\endgroup\$
  • 3
    \$\begingroup\$ Regarding loading the file into memory: on Linux, I'd use vmtouch to put it into the cache, this way it I don't have to worry whether it actually fits in memory or not, and get the maximum speed if it does. I don't know how one would do that on C#. \$\endgroup\$ – Davidmh Dec 11 '15 at 14:12
  • \$\begingroup\$ The bug is known, but considered an edge case for now. I never intend this to be really used for cracking passwords, but just as a study in solving a time-consuming task asynchronously. \$\endgroup\$ – 23fc9a62-56de-47fb-97b4-737890 Dec 11 '15 at 15:46
  • 1
    \$\begingroup\$ @Davidmh: You mean hoytech.com/vmtouch? Yes, but you don't need vmtouch for that to be good. Any OS's LRU paging algorithms will keep repeatedly-used pages in core. Worrying about manually pinning any of the pages sounds like a bad idea. Best: mmap the zip before spawning threads, so they all have it mapped. (easier than having each thread open/mmap separately, but they'd still all share the same memory pages). Thanks for mentioning vmtouch, though: it looks useful for querying the pagecache. \$\endgroup\$ – Peter Cordes Dec 12 '15 at 19:41
  • \$\begingroup\$ @PeterCordes vmtouch puts them in the cache, but lets the OS evict them whenever it sees fit. Personally, I use it when I know what I am going to do better than the OS (for example, pre-loading a bunch of files at the same time I start to process them, hiding the IO latency, or to explicitly evict them when I know I am done to make room). The great win for me is that the interface is still a file, as many libraries I use require that as an input. \$\endgroup\$ – Davidmh Dec 12 '15 at 23:42
  • \$\begingroup\$ @Davidmh: I know you weren't suggesting using the -l mlock option. My point was that for this task, only the part of the zip file needed to check the password needs to be paged in. And the password-checking program will cause that to happen just fine on its own. There's no non-linear access pattern that would make it more efficient to pre-cache some range of the file. In this case, the first password check will happen right away, so there's no window to hide I/O latency. If checking a zip password only requires looking at the header, paging in the whole file is bad. \$\endgroup\$ – Peter Cordes Dec 13 '15 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.