/          All Posts       Projects       GitHub       More...
🔗

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.

Newer Older
3 comments



Formatting cheat sheet.