I'm in your .zips crackin' your passwords

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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().