4
\$\begingroup\$

This is my brute force string generator from my password recovery program. I use it to test md5 hashes against a given 'lost password' hash.

I went for iteration instead of recursion as it was required to multi-thread the application; the program was part of last semester's coursework. I am continuing it for personal satisfaction.

The function runs from curr : last; which are vector, an for a 5 character string the contents may look like {0,0,0,0,0} and {26,26,26,26,26} respectively. curr is used by the generator to hold the itr equivalent of the string, a string is then created by using the itr against a charset called alphabet. The charset can vary depending on user input elsewhere in the program.

Before I tidied it up for the 'cleaner code' marks it took less than a third of the time. I'd ideally like to keep it within the class and maintain readability but regain the speed.

For speed comparison I have been testing single threaded performance, previously I was able to complete aaaaa : zzzzzin around 8s, now it takes 26s. Time is measured as how long it takes for the function to return so there should be no external factors.

I would prefer suggestions on how to decrease run time but I am open to generalized improvements as well.

My original version with no classes:

void brute(int min, volatile unsigned int top, std::vector<int> curr, std::vector<int> last, std::vector<unsigned char> & alphabet, std::string & hash) {
    auto make_string = [](std::vector<int> & its, std::vector<unsigned char> & chars) {
        string s = "";
        for (auto i : its)
            s += chars[i];
        return s;   
    };

    auto cmp_hash = [](std::string password, std::string hash) {
        md5_hash md5;
        if (md5.hash(password) == hash) {
            std::cout << "\npassword: " << password << "\n\npassword hash: \n" << md5.hash(password) << "\n\nMatches entered hash: \n" << hash << "\n\n";
            task_complete = true;
            return true;
        }
        return false;
    };

    //add all up to the last
    while (curr != last && !task_complete) {

        if (cmp_hash(make_string(curr, alphabet), hash))
            return;

        //add 1 to low digit
        curr[0]++;

        //if low digit has looped past max
        if (curr[0] == top + 1) {
            //iterate through all digits
            for (unsigned int i = 0; i < curr.size() && (curr[i] == top + 1); ++i) {
                //set it to min and increase value of next digit up by 1
                curr[i] = min;
                if (i != curr.size() - 1) {
                    ++curr[i + 1];
                }
            }
        }
    } 

    //and add the last 
    if (cmp_hash(make_string(last, alphabet), hash))
        return;

}

My code with the classes:

Passwords class:

#pragma once

#include <string>
#include <chrono> //to get time in ms
#include <atomic> //^

#include <boost/iostreams/device/mapped_file.hpp> // for mmap
#include "tasker.h" //for my farmer worker
#include "md5hash.h" //for openssl md5 hash
#include "Messages.h" //to meet coursework requirements

class passwords
{
public:

    //alter bruteforce limit
    void bf_limit(int);

    //run the application
    void run();

    passwords();
    ~passwords();   

private:

    ///Functions
    //get dictionary file
    void get_passwords(std::string);
    //perform dictionary attack
    void compare_hash(std::vector<std::string> &, size_t, size_t, std::string &);
    //subdivide dictionary task
    void split_dictionary(std::vector<std::string> & tasks, std::string & comparison);

    //setup character set to use
    void get_types();
    //peform bruteforce attack
    void brute(unsigned int, std::vector<int>, std::vector<int>, std::vector<unsigned char> &, std::string &);
    //subdivide brutefoce task
    void split_bruteforce(int, std::vector<unsigned char> &, std::string &);

    ///Variables
    //characters to bruteforce
    int bf_chars;
    //threads that will be used
    int global_threads = 1;
    //limit bf chars
    const int bfc_limit = 5;

    //required thread-safe items
    std::atomic_bool task_complete = false;

    //important input
    std::vector<unsigned char> alphabet = { 97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122 };  //a-z
    const std::vector<std::string> cout_types = { "Uppercase Letters", "Numbers", "Special Characters", "Extended ASCII (128 - 255)" };
    const std::vector<std::vector<unsigned char>> types_v = {
        { 65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90 },                           //A-Z
        { 48,49,50,51,52,53,54,55,56,57 },                                                                           //0-9
        { 32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,58,59,60,61,62,63,64,91,92,93,94,95,96,123,124,125,126,127 },//Special characters
        { 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255 } //extended ascii
    };

    std::vector<std::string> password_vec;

    //basic requirments
    std::string filename;
    std::string hash;
    std::string password;

    //output
    Messages * msg;

    ///Future improvements
    //single Tasker * farm
};

And the brute force function:

void passwords::brute(unsigned int top, std::vector<int> curr, std::vector<int> last, std::vector<unsigned char> & alphabet, std::string & hash) {

    //md5 functionality
    md5_hash md5h;

    const int min = 0;

    //construct string from vector of alphabet iterators
    auto make_string = [this](std::vector<int> &curr) {
        std::string s = "";
        for (auto i : curr) {
            s.push_back(this->alphabet[i]);
        }
        return s;
    };

    //compare hash with password
    auto cmp_hash = [this, &md5h](std::string &password) {
        if (md5h.hash(password) == this->hash) {
            msg->add_task(new MessageTask("\npassword: " + password + "\n\npassword hash: \n" + md5h.hash(password) + "\n\nMatches entered hash: \n" + this->hash + "\n\n")); 
            task_complete = true;
            return true;
        }
        return false;
    };

    //generate strings
    ///all up to the last

    while (curr != last && !task_complete) {

        if (cmp_hash(make_string(curr)))
            return;
        //add 1 to low digit
        curr[0]++;

        //if low digit has looped past max
        if (curr[0] == top + 1) {
            //iterate through all digits
            for (unsigned int i = 0; i < curr.size() && (curr[i] == top + 1); ++i) {
                //set it to min and increase value of next digit up by 1
                curr[i] = min;
                if (i != curr.size() - 1) {
                    ++curr[i + 1];
                }
            }
        }
    }

    ///and the last 
    if (cmp_hash(make_string(last))) 
        return;

}

I am aware that I might have just shoehorned my code to fit into the class structure but I am not entirely sure how else to do it.

\$\endgroup\$
  • \$\begingroup\$ Have you profiled your code ? This will help finding the bottleneck \$\endgroup\$ – Yk Cheese May 15 '17 at 5:57
  • \$\begingroup\$ Yes, I have profiled it, it didn't reveal anything catastrophically​ wrong. \$\endgroup\$ – Anroca May 15 '17 at 12:44
  • \$\begingroup\$ Comparing your results for your two programs would probably show you where you have your loss of speed \$\endgroup\$ – Yk Cheese May 15 '17 at 15:17
  • \$\begingroup\$ adding character by character in make_string is bad; depending on your library there will be several invisible string-copy operations. As you already know the final string size, you should reserve() the space needed before building the string. \$\endgroup\$ – jvb May 17 '17 at 9:40
  • \$\begingroup\$ @jvb switched it out for a char array just there and saw a massive improvement. Using reserve didn't help all that much where I was initializing the string but probably would have helped had I reserved outside of the loop. \$\endgroup\$ – Anroca May 17 '17 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.