Parallel Brute-Force-Algorithmus

Question

So war ich bei http://codahale.com/how-to-safely-store-a-password/# suchen und wurde neugierig, wie schnell verschiedene Hash auf einem etwas leistungsfähigen Desktop-Computer bruteforced werden konnte und testen Ich habe allerdings

Die meisten Algorithmen versucht, zu sehen sind Single-Threaded und es fiel mir auf, dass dies eine wirklich interessante Herausforderung bei der Verwendung von C# 4.0 Parallel.net/Plinq Erweiterungen und gleichzeitige Strukturen (wie ConcurrentBag und IProducerConsumer) wäre.

So ist meine Aufgabe wie folgt, baut die effizienteste/performant Brute-Force-Checker eines Passworts von n-Länge und charset [x] mit parallelisiert, dh erzeugt alle möglichen Strings eine bestimmte charset und Länge, bis eine Übereinstimmung gefunden wird . Es sei angenommen, mindestens zwei Kerne und angemessene Menge an RAM

ich werde ihm gebe einen Wirbel selbst, lassen Sie die beste Mann/Frau :)

EDIT

Ersten Versuch gewinnen, ohne die Leistung vergleichen noch und begrenzter Umfang und bekannt Kennwortlänge

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)); 

    } 

nächster Versuch

Verwenden von ParallelEnumerable war nicht clever, da es auf int in der Größe beschränkt ist, müssen Sie ziemlich bald mindestens lange, obwohl ich bezweifle, dass Sie für lange mit großen Passwörtern Zeichensatz halten wird. Ich schätze du musst entweder BigInt gehen oder es danach irgendwie kaputt machen.

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

Warum die NrCombinations Methode und nicht nur

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

Ich würde auch gegen int für nrCombinations weil mit nur sechs Zeichen mit Basis 36 Alphabet empfehlen Sie in Schwierigkeiten geraten (36^6> 2^31). Verwenden Sie long. Ich glaube nicht, dass BigInteger benötigt wird, denn wenn Sie große Zahlen brauchen, wird Brute Force sowieso keine Option sein.

Ich habe diese Idee, dass es möglich sein könnte, Brute Force zu beschleunigen, indem Sie eine Art De Bruijn Sequenzstrom verwenden. Scheint vernünftig, aber ich muss darauf zurückkommen, weil ich gerade keinen Code habe, der zu zeigen wäre.