Brute-force password cracker

Question

I am trying to write a program to find a zip file's password. I know the password consists of only lower-case letters and it's length does not exceed 6 characters. I wanted to check the passwords of length 1 first, then length 2 and so on.

So I used breadth first search, but then I realized that BFS consumes so much memory, and std::queue makes things even worse. So I had to switch to depth first search. BUT... depth first search does not check the shortest passwords first. So that's a problem. How can I improve the memory management in my bfs function, Or change my dfs function so that it would check the shortest passwords first (I'm not sure if the latter is even possible)

Also my estimation is that the bfs function would be using about 2 Gigabytes of memory. How can I fix this?

#include <iostream>
#include <queue>

std::string key = "banana";

void checkPassword(std::string s) {
  if (s == key) { //example checker function
    std::cout << "Password is : " << s << std::endl;
  }
}

void bfs(std::string s = "") {
  std::queue <std::string> q;
  q.push(s);
  while(q.size()) {
    std::string u = q.front();
    checkPassword(u);
    q.pop();
    if (u.size() < 6) {
      for (int i = 'a'; i <= 'z'; i++) {
        u += i;
        q.push(u);
        u.pop_back();
      }
    }
  }
}

void dfs(std::string s = "") {
  checkPassword(s);
  if (s.size() < 6) {
    for (int i = 'a'; i <= 'z'; i++) {
      s.push_back(i);
      dfs(s);
      s.pop_back();
    }
  }
}

int main() {
  dfs();
  std::cout << "Finished Time : " << clock() / (double) CLOCKS_PER_SEC;
}

Answer 1

There are some things I've seen that may help you improve your code.

Pass references where practical

The dfs() routine doesn't really need to create a duplicate string. Instead, it could simply reuse a passed string. We do that by changing the prototype to this:

void dfs(std::string &s) 

And then call it like this:

int main() {
    std::string s;
    dfs(s);
    std::cout << "Finished Time : " << clock() / (double) CLOCKS_PER_SEC;
}

On my machine, the original code takes 6.3 seconds, but when modified like this, takes 4.7 instead, making a very easy improvement.

Prefer iterations to recursion

Recursive functions are often a good way to approach a programming task, but there is a tradeoff in terms of memory and time. Specifically, one can often reduce or eliminate the computational cost of a function call and reduce or eliminate the memory overhead as well by converting from a recursive to an interative function. In this case, I'd advise altering the code so that the prototype is something like this:

bool brute(const std::string &alphabet, size_t len)

It's then a simple matter of calling the function with increasing sizes until either the password is found or you run out of combinations. For generating the combinations, I'd suggest using std::next_permutation something like this SO question shows.

Look at similar questions here

Another nice source of advice is other similar questions. For example, this question is very similar and the answers are generally applicable to your code.