C# brute force

Programovacie jazyky, rady, poradňa...
jozi341
Light Expert
Light Expert
Príspevky: 39
Registrovaný: 29 dec 2007, 16:02

C# brute force

Príspevok od používateľa jozi341 »

Spravil som jednoduchy brute force cracker na md5 hash ale zda sa mi dost pomaly. Priemerna rychlost (generovanie slova, generovanie hashu, porovnanie so vstupnym hashom) je len okolo 250 000 slov za sekundu. V podobnych programoch to bolo okolo 6 000 000 slov/sek. cele to generovanie prebieha v backgroundWorkeri co je osobitny thread. Da sa to nejak zrychlit ? Tu je kod:

//VSTUPNE UDAJE

Kód: Vybrať všetko

private void backgroundWorker1_DoWork_1(object sender, DoWorkEventArgs e)
{
      MD5 md5 = MD5.Create();
     //vstupny hash
      string input = textBox1.Text;
      string hash = "  ";
      byte[] hashBytes;

      MD5 md5 = MD5.Create();
      char = "abcdefghijklmnopqrstuvwxyz0123456789";
      char[] chars = char.ToCharArray();
      string theword;
      int iPasswordLength;

      int iPossibilities = (int)Math.Pow((double)chars.Length, (double)iPasswordLength);
//BRUTE

Kód: Vybrať všetko

       for (int i = 0; i < iPossibilities; i++)
       {
                theword = "";
                int val = i;
                for (int j = 0; j < iPasswordLength; j++)
                {
                    int ch = val % chars.Length;
                    theword = chars[ch] + theword;
                    val = val / chars.Length;
                    if (iPasswordLength < numericUpDown1.Value && iPossibilities == i + 1)
                    {
                        j = 0;
                        i = 0;
                        iPasswordLength += 1;
                    //vypocita pocet kombinacii pre danu dlzku.
                        iPossibilities = (int)Math.Pow((double)chars.Length, (double)iPasswordLength);
                    }
                }
              //ak sa zavola zrusenie procesu
                if (backgroundWorker1.CancellationPending)
                {
                    e.Cancel = true;
                    return;
                }
              //pripravi slovo na vytvorenie hashu
                byte[] inputBytes = Encoding.Default.GetBytes(theword.ToCharArray());
               //vygeneruje hash
                    hashBytes = md5.ComputeHash(inputBytes);
                    hash = BitConverter.ToString(hashBytes).Replace("-", String.Empty);
               //porovnanie vygenerovaneho hashu so vstupnym hashom
               if (hash == input)
                {
                    found = 1;
                    e.Cancel = true;
                    return;
                }
         }
}
Ďakujem za nápady :)
BX
Addict
Addict
Používateľov profilový obrázok
Príspevky: 4572
Registrovaný: 10 jan 2008, 15:30

Re: C# brute force

Príspevok od používateľa BX »

jozi341 napísal:V podobnych programoch to bolo okolo 6 000 000 slov/sek.
A tie podobné programy sú napísané v .NET a používajú takýto "hlúpy" brute-force? :)

Prvé, čo môžeš urobiť, je nepočítať nič, čo nemusíš (prípadne niečo počítať len raz za čas, napr. cancelationPending) a čo najviac toho presunúť mimo cyklov. To ale neurobí taký veľký rozdiel.
Druhé je paralelizácia, napríklad pomocou parallel for
Tretia a asi najlepšia vec, čo môžeš urobiť, je napísať to v Cčku a paralelizovať napríklad pomocou openMP, alebo ešte lepšie - urýchliť to na grafickej karte.

Žiaľ, brute-force je len brute-force. Algoritmus nezrýchliš, môžeš iba zvýšiť výpočetnú silu.
jozi341
Light Expert
Light Expert
Príspevky: 39
Registrovaný: 29 dec 2007, 16:02

Re: C# brute force

Príspevok od používateľa jozi341 »

BX napísal: A tie podobné programy sú napísané v .NET a používajú takýto "hlúpy" brute-force? :)

Prvé, čo môžeš urobiť, je nepočítať nič, čo nemusíš (prípadne niečo počítať len raz za čas, napr. cancelationPending) a čo najviac toho presunúť mimo cyklov. To ale neurobí taký veľký rozdiel.
Druhé je paralelizácia, napríklad pomocou parallel for
Tretia a asi najlepšia vec, čo môžeš urobiť, je napísať to v Cčku a paralelizovať napríklad pomocou openMP, alebo ešte lepšie - urýchliť to na grafickej karte.

Žiaľ, brute-force je len brute-force. Algoritmus nezrýchliš, môžeš iba zvýšiť výpočetnú silu.
Ako sa dá parallel for použiť v tomto prípade?
BX
Addict
Addict
Používateľov profilový obrázok
Príspevky: 4572
Registrovaný: 10 jan 2008, 15:30

Re: C# brute force

Príspevok od používateľa BX »

No na to by si mal prísť sám.

Parallel.For funguje tak, že ti vytvorí K vláken a tie spracovávajú jednotlivé iterácie. Takže musíš hlavne vymyslieť, ako generovať hashe a pritom negeneroval viac krát rovnaké. Na to môže byť buď nejaký pool, z ktorého budú vlákna brať, alebo môžeš napevno priradiť nejaký vzor pre každú 0..K-1 iteráciu.

Na tvojom mieste by som ale venoval pozornosť aj tomu prvému bodu, ten vnútorný cyklus (iPasswordLength) mi príde dosť drahý.
Napísať odpoveď