Multithreaded generic bruteforcer

En programmation, si il y a bien une chose à retenir,c’est celle là : éviter de réinventer la roue à chaque fois.

Malheureusement, (ou heureusement 🙂) pour moi, cette fois ci je n’ai pas eu le choix…
L’idée de coder un simple bruteforce me trottait dans la tête depuis un moment, et j’avais déjà fait plusieurs essais plus ou moins concluants en C# et en C++.

Il en existe déjà des centaines, tous plus performants les uns que les autres, en C, C++, ou sur GPU. Le C# n’étant pas un langage réputé pour ses performances incroyables, j’ai donc visé un autre but : un bruteforcer générique (et multithread).

Le principe est simple : on a un charset, un liste d’éléments d’un type donné, et à partir d’un motif de départ, on génère toutes les combinaisons possibles.
en pratique, mon implémentation n’est certainement pas la meilleure, mais j’ai l’excuse de travailler avec un type générique :p

static private void RecursiveNext<T>(IList<T> charSet, ref List<T> current, int startIndex = 0)
{
 if (startIndex >= current.Count)
 {
  //on est en dehors de la longueur du motif courant, et il faut agrandir :
  current.Add(charSet[0]);
  return;
 }
 //index de l'item suivant dans le charSet
 int indexOfNew = (charSet.IndexOf(current[startIndex]) + 1) % charSet.Count;
 current[startIndex] = charSet[indexOfNew];//0 //overflow tout seul correctement si IndexOf() retourne -1;
 //si c'etait le dernier element du charSet, et que donc on est revenu au debut,
 //il faut passer à l'élément de poids superieur
 if (indexOfNew == 0)
 {
  RecursiveNext<T>(charSet, ref current, startIndex + 1);
 }
}

Pour tous vous dire ça ne me plait même que moyennement :

– J’avais commencé par retourner un IList plutôt que modifier directement l’élément, mais comme c’est un type référence, s’il est modifié “de l’intérieur” (avec Add() ou l’indexer), la modification n’est plus locale à la fonction, ce qui pose quelque problèmes…
– j’ai donc mis le paramètre en ref, histoire d’indiquer qu’il sera bien modifié, mais un ref et un type IList (une jolie interface) ça ne marche plus très bien, j’ai donc du passer au List.

Comme je ne fais pas les choses à moitié, j’ai mis et arrangé tout ça dans une classe, que je vous épargnerai ici.

Bref, tout cela est bien gentil, mais moyennement intéressant.
Passons aux choses sérieuses : le multithread.

Ce genre d’algorithme devrait typiquement pouvoir grandement profiter d’une exécution en parallèle, tout ce qu’il faut, c’est arriver à partager le calcul entre n threads.
Comme réinventer la roue est long et qu’il y a toujours la possibilité que ça finisse en cube, j’ai bien sur fait une petite recherche avant de commencer.
Et là, c’est le vide.

Je n’ai strictement rien trouvé dans ce domaine, mis à part ceci : Distributing_exhaustive_attack_using_Cain.htm
Un petit logiciel open source d’un gars qui a eu le même problème que moi, mais moins d’ambition : il a uniquement codé la répartition, pas le bruteforce en lui même.
C’est du C++ mais je n’ai pas fais le difficile. C’est pour comprendre son code que ça a été difficile par contre, et je n’ai d’ailleurs toujours pas réussi. (je vous laisse jeter un coup d’oeil si vous voulez ^^)
Il a donc fallut que je réfléchisse un peu…

exemple avec un charSet de deux caractères, “0, 1” et une longueur maxi de 3 caractères :

0
1
00
10
01
11
000
100
010
110
001
101
011
111

On remarque assez vite qu’on obtient une magnifique énumération de 0 à 7 en binaire,
et que le principal problème pour paralléliser le calcul,c’est de trouver rapidement le nieme terme du bruteforce.
Avec le charSet “0,1,2,3,4,5,6,7,8,9” je vous laisse deviner à quoi ressemblerait la sortie…

Si on fait naïvement comme wikipédia nous dit pour passer d’un système de numération à un autre, on obtient presque le résultat voulu, à la différence près que tous les passages “00”, “000”, etc, n’existent plus !

Pour que ça marche, on ne doit compter que pour une longueur de combinaison fixe, en ajoutant un padding de 0 :
on compte aura donc, pour la longueur 2, de 00 à 11, et pour la longueur 3, de 000 à 111

voici donc mon implémentation, et en bonus l’opération inverse, dont on ne se sert pas, mais qui ne coute rien à coder 🙂 je précise que BigInteger fait partie du framework 4.0, namespace System.Numerics.

static public IList<T> FromBase10<T>(IList<T> charSet, BigInteger value, int padding = 0)
{
 int baseN = charSet.Count;
 BigInteger division = 0;
 int modulo = 0;
 List<T> result = new List<T>();
 do
 {
  division = value / baseN;
  modulo = (int)(value % baseN);
  result.Add(charSet[modulo]);
  value = division;
 } while (division != 0);
 for (int i = result.Count; i < padding; i++)
 {
  result.Add(charSet[0]);
 }
 //result.Reverse();
 return result;
}

static public BigInteger ToBase10<T>(IList<T> charSet, IList<T> value)
{
 int baseN = charSet.Count;
 BigInteger result = 0;
 for (int i = 0; i < value.Count; i++)
 {
  result += charSet.IndexOf(value[i]) * BigInteger.Pow(baseN, i);
 }
 return result;
}

Et voilà ! Il ne reste plus qu’a faire la partie répartition en n threads :

pour simplifier la chose, et aussi parce que je sais que lors de la création de mes threads, je ne pourrai passer qu’un seul objet en paramètre, j’ai organisé tous les éléments nécessaires au calcul d’une partie d’un bruteforce en une classe :

/// <summary>
/// rassemble les parametres necessaires pour un calcul de bruteforce
/// </summary>
/// <typeparam name="T"></typeparam>
public class WorkParams<T>
{
 public IList<T> CharSet { get; set; }
 /// <summary>
 /// delegate comparant le bruteforce de la façon voulue,
 /// pour renvoyer true si un résultat es trouvé, false sinon
 /// </summary>
 public Func<T, bool> Comparer { get; set; }

 /// <summary>
 /// doit etre en meme nombre que EndPatterns
 /// </summary>
 public List<T> StartPatterns { get; set; }
 /// <summary>
 /// doit etre en meme nombre que StartPatterns
 /// </summary>
 public List<T> EndPatterns { get; set; }

 /// <summary>
 /// nombre de motifs dans les listes de motifs.
 /// il y a autant de motifs que de nombre d'éléments dans le motif final.
 /// </summary>
 public int PatternCount { get { return StartPatterns == null ? 0 : StartPatterns.Count; } }

 public WorkParams(IList<T> charSet, List<T> startPatterns, List<T> endPatterns, Func<T, bool> comparer)
 {
 this.CharSet = charSet;
 this.Comparer = comparer;
 this.StartPatterns = startPatterns;
 this.EndPatterns = endPatterns;
 }

 /// <summary>
 /// attention, l'initialisation n'est pas complète il faut aussi attribuer les listes de motifs !
 /// </summary>
 /// <param name="CharSet"></param>
 /// <param name="comparer"></param>
 public WorkParams(IList<T> CharSet, Func<T, bool> comparer)
 {
 this.CharSet = CharSet;
 this.Comparer = comparer;
 this.StartPatterns = new List<T>();
 this.EndPatterns = new List<T>();
 }

 /// <summary>
 /// pour clarifier le debug...
 /// </summary>
 /// <returns></returns>
 public override string ToString()
 {
 System.Text.StringBuilder sb = new StringBuilder();
 for (int i = 0; i < this.PatternCount; i++)
 {
  sb.Append(string.Format("{{{0}}}>{{{1}}}, ", string.Join(",", this.StartPatterns[i]), string.Join(",", this.EndPatterns[i])));
 }
 return sb.ToString();
 }
}

Ce qui me permet ensuite de vous présenter la partie la plus intéressante : celle gérant la répartition du travail entre n threads :
après ce qui a été dit, les commentaires et le code parlent d’eux mêmes…

public static List<WorkParams<T>> LoadBalance<T>(IList<T> charSet, int minLength, int maxLength, int threadCount, Func<IList<T>, bool> comparer)
{
 List<WorkParams<T>> result = new List<WorkParams<T>>();
 // un objet parametre par thread
 for (int i = 0; i < threadCount; i++)
 {
  result.Add(new WorkParams<T>(charSet, comparer));
 }
 for (int i = minLength; i <= maxLength; i++)//pour chaque sous longueur
 {
  /*
  * nombre de combinaisons total pour la longueur voulue.
  * exemple pour un charset de A à Z, avec une longueur de 3 :
  *      debut : AAA
  *      fin :   ZZZ
  *      keySpace : 26^3
  */
  BigInteger keySpace = BigInteger.Pow(charSet.Count, i);
  //nombre de calculs pour chaque thread
  BigInteger subRange = keySpace / threadCount;
  BigInteger remainder = keySpace % threadCount;
  /*
  * repartition du reste entre chaque subrange,
  * par exemple, pour le charset précédent, si on veut découper les 17576 en 3 threads,
  * on obtiendra : (nombre de calculs par thread)
  * t1 => 5859
  * t2 => 5859
  * t3 => 5858
  */
  BigInteger[] subrangesList = new BigInteger[threadCount];
  for (int j = 0; j < threadCount; j++)
  {
   if (remainder > 0)
   {
    subrangesList[j] = subRange + 1;
    remainder--;
   }
   else
   {
    subrangesList[j] = subRange;
   }
  }
  //calcul des motifs de début/fin pour chaque thread
  BigInteger lastStart = 0;
  for (int k = 0; k < threadCount; k++)
  {
   if (subrangesList[k] == 0)
   {
    break;
   }
   result[k].StartPatterns.Add(FromBase10(charSet, lastStart, i));
   lastStart += subrangesList[k];
   result[k].EndPatterns.Add(FromBase10(charSet, lastStart - 1, i));
  }
 }
 return result;
}

Et enfin , il ne reste plus qu’a lancer le bruteforce en lui même, sur autant de threads qu’on veut 🙂 Voici la méthode de calcul :

/// <summary>
/// methode lancée en parallèle pour chaque thread
/// </summary>
/// <param name="parameters"></param>
protected void ThreadedWorker(object parameters)
{
 if (!(parameters is WorkParams<T>))
 {
  throw new ArgumentException("type de parameters non reconnu, utiliser WorkParam<T>");
 }
 WorkParams<T> p = (WorkParams<T>)parameters;
 //exécute tout le travail demandé
 for (int i = 0; i < p.PatternCount; i++)
 {
  //utilise la classe de base pour calculer chaque sous etape du bruteforce
  BruteForce<T> worker = new BruteForce<T>(p.CharSet, p.StartPatterns[i], p.EndPatterns[i]);
  do
  {
   if (this.CancelAsyncWorkers)
   {
    return;
   }
   if (Comparer(worker.CurrentPattern)) // appel la fonction utilisateur
   {
    //leve l'évènement
    MatchFound(this, new MatchFoundEventArgs(worker.CurrentPattern));
    //annule les autres threads
    this.CancelAsyncWorkers = true;
    return;
   }
  } while (worker.LoadNext());
 }
}

La classe BruteForce utilisée, est une classe utilisant la méthode décrite au début, pour calculer un bruteforce simple, d’un motif à un autre, sur le charset voulu.
Ce bout de code n’est là que pour montrer à quoi peut ressembler le calcul final, il ne compilera pas sans quelque ajouts (que j’ai omis pour éviter de surcharger ce post…)

Voici donc mon implémentation d’un bruteforce générique multithread en C#
Toujours intéressant pour son aspect algorithmique…
Si vous cherchez les perfs en revanche, vous serez déçus : sur un quad core i5 760, j’atteint péniblement 2 millions de combinaisons par seconde, à vide (c’est à dire sans aucun calcul utile, d’un md5 par exemple) et 4 millions en modifiant le code pour l’optimiser pour des chaines de caractères. (à revérifier un jour si j’ai la motivation de faire un test correct)

Fin.