Параллельный алгоритм грубой силы

Question

Поэтому я посмотрел на http://codahale.com/how-to-safely-store-a-password/ и мне стало любопытно, как быстро можно использовать различные хэши на довольно мощном настольном компьютере, и я испытал желание протестировать его

Большинство алгоритмов, которые я видел, хотя и являются однопоточными, и меня поразило, что это будет действительно интересной проблемой при использовании расширений Parallel.net/Plinq C# 4.0 и параллельных структур (таких как ConcurrentBag и IProducerConsumer).

Поэтому моя задача заключается в том, чтобы создать наиболее эффективную / эффективную проверку bruteforce пароля n-длины и набора символов [x] с использованием распараллеливания, то есть генерировать все возможные строки заданного набора символов и длины, пока не будет найдено соответствие. Предположим, по крайней мере, два ядра и разумное количество оперативной памяти

Я собираюсь сделать это сам, пусть победит лучший мужчина / женщина:)

РЕДАКТИРОВАТЬ

Первая попытка без сравнения производительности, ограниченной области действия и известной длины пароля

    char[] chars = new 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' };

    public long NrCombinations(int nrChars, int stringLength)
    {
        Func<long, int, long> power = null;
        power = (i, p) => p == 1 ? i : i * power(i, p - 1);

        return power(nrChars, stringLength);
    }


    public static bool StringArrayEquals(char[] a, char[] b)
    {
        if (a.Length != b.Length)
            return false;
        for (int i = 0; i < a.Length; i++)
        {
            if (!a[i].Equals(b[i]))
                return false;
        }
        return true;
    }

    public char[]  GenerateString(int i, int stringLength)
    {
        char[] current = new char[stringLength];
        for (int i = 0; i < stringLength; i++)
        {
            double remainder = i % this.chars.Length;   
            i = i / this.chars.Length;         
            current[i] = this.chars[(int) remainder];
        }
        return current;
    }

    public bool IsMatch(int i, char[] password)
    {
        return StringArrayEquals(GenerateString(i, password.Length), password);
    }

    private int GetMatching(string passwordString)
    {
        char[] password = passwordString.ToArray();
        int nrCombinations = (int)NrCombinations(this.chars.Length, password.Length);

        return ParallelEnumerable.Range(0, nrCombinations).WithDegreeOfParallelism(10).FirstOrDefault(i => IsMatch(i, password));

    }

Следующая попытка

Использование ParallelEnumerable было непростым делом, поскольку его размер ограничен int, но вскоре вам понадобится, по крайней мере, долго, хотя я сомневаюсь, что это продержит вас надолго с кодировками больших паролей. Думаю, вам нужно либо пойти на BigInt, либо начать что-то ломать после этого.

    public long NrCombinations(int nrChars, int stringLength)
    {
        Func<long, int, long> power = null;
        power = (i, p) => p == 1 ? i : i * power(i, p - 1);

        return power(nrChars, stringLength);
    }


    public string GenerateString(long number, int sentenceLength)
    {
        char[] current = new char[sentenceLength];
        for (int i = 0; i < sentenceLength; i++)
        {
            double remainder = number % this.chars.Length;   
            number = number / this.chars.Length;         
            current[i] = this.chars[(int) remainder];
        }
        return new string(current);
    }

    public bool IsMatch(string hash, long  i, int passwordLength)
    {
        string generated = GenerateString(i, passwordLength);
        string hashed = GetMasterHash(generated, this.site);
        return string.Equals(hashed, hash);
    }

    private string GetMatching(string hash,int passwordLength)
    {
        string result = string.Empty;
        int stringlength = passwordLength;
        long  nrCombinations = NrCombinations(this.chars.Length, stringlength);
        long x = 0;

        Parallel.For(0, nrCombinations, (i, loopState) =>
        {
            if (IsMatch(hash,i, passwordLength))
            {
                x = i;
                loopState.Stop();
                return;
            }
        }); 


        if (x > 0)
        {
            result = this.GenerateString(x, passwordLength);
        }

        return result;

    }

Answer 1

Почему NrCombinations метод, а не только

long combinations = (long)Math.Pow(base, stringLength);

Я бы также рекомендовал против int за nrCombinations потому что только с шестью символами с вашим базовым алфавитом 36 вы попадете в беду (36^6 > 2^31). использование long, Я не думаю BigInteger Это необходимо, потому что если вам нужны эти большие числа, грубая сила не будет выбором в любом случае.

У меня есть идея, что можно было бы ускорить грубую силу, используя своего рода поток последовательности де Брюйна. Кажется разумным, но я должен вернуться к этому, потому что у меня нет кода, чтобы показать прямо сейчас.