Does there exist an algorithm for iterating through all strings that conform to a particular regex?

Question

I'm making a script to try and hack into an account whose login password is at least 8 characters long and includes at least 1 number, 1 special character and 1 capital letter. I will use brute force. Is there a compact, elegant and efficient way to iterate through every possible string that matches a given regular expression? Are there any C# classes that already do this or will I have to invent the wheel?

Desired:

CoolClass pswExpIter = CoolClass(pswExp);
for ( string thisExp = pswdExpIter.first(); thisExp != pswdExpIter.offend(); thisExp = pswdExpIter.next()) 
{
      if (login("John Doe", thisExp)
      {
           // do something
           break;
      }          
}

a google search lead to this - http://stackoverflow.com/questions/5767605/looping-through-regex-matches — Ziv Weissman, Jun 22 '15 at 18:32
@ZivWeissman: That is a different question. This question is about producing every possible match, not about iterating over the matches in a given input. — StriplingWarrior, Jun 22 '15 at 18:35
Even if you eliminated special characters, there are 96 trillion 8 character combinations, 5,416 trillion 9 character combinations, etc. If you were able to go through 1,000 combos a second, it would take you tens of thousands of years to go through just the 8 character ones. — David Deutsch, Jun 22 '15 at 18:36
@DavidDeutsch Maybe I could narrow it down to expressions that contain real words in the dictionary? — , Jun 22 '15 at 18:37
There's https://code.google.com/p/xeger/ - generates a matching input for a regex. This problem, however, is not trivial, as it's entirely possible to create a regex that matches any input or that doesn't match any input. — xxbbcc, Jun 22 '15 at 18:39
@PeterThiel: That would change the question quite a bit, wouldn't it? You can't produce a REGEX that says "contains real words in the dictionary." There are plenty of tools out there that use dictionaries, and transformations on the words in those dictionaries, to attempt brute-force attacks like this. Is there a reason you're not using one of those? Is this just an intellectual exercise? — StriplingWarrior, Jun 22 '15 at 18:40
From the fact that there is a digit, a "special" character and a captial, we can deduce that those are all allowed, as are lower case letters. Let's assume this is relatively insecure; doesn't allow any others and only has 5 "special" characters allowed. For the minimum size of 8 characters there are 5×10×26×5⁶⁷ = 8.809142651×10⁴⁹ possibilities (more, I'm assuming the same order). If we can manage a billion tries a second, then that'd take 2.791448859×10³³ years. That's 2.023082229×10⁴¹ times longer than the universe has been around. Implementing the brute-force efficiently is not the problem. — Jon Hanna, Jun 22 '15 at 18:44
Also if it's over the web it doesn't have to be efficient; even a slow algorithm producing passwords to try will have raced ahead of the actual attempts. — Jon Hanna, Jun 22 '15 at 18:46

score 3 · Answer 1 · answered Jun 22 '15 at 18:55

It is not difficult to enumerate the strings, as follows:

Construct a DFA using any of the usual algorithms.
The DFA is effectively a graph. Do a breadth-first traverse of the graph, without the usual step of removing an edge from the workqueue if its destination has already been visited. At each node marked as accepting, print the transitions leading to the node.

Since it is necessary to maintain the transition history for every node on the queue, this algorithm will rapidly run out of memory. An alternative for the particular use case you have in mind is to a depth-first traverse, stopping when the desired string length is reached. That will not use much memory, but it will still take an awful lot of time unless you have some way to further restrict the possibilities.

score 1 · Answer 2 · answered Jun 22 '15 at 18:45

Here is the kind of thing you are looking for:

    char[] availableChars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_=+*".ToArray();
    IEnumerable<string> CreatePassword(int size)
    {

        if (size == 1 )
        {
            foreach (var c in availableChars)
            {
                yield return c.ToString();
            }
            yield break;
        }

        foreach (var password in CreatePassword(size - 1))
        {
            foreach (var c in availableChars)
            {
                yield return password + c;
            }
        }
    }

Good luck :)

score 0 · Accepted Answer · answered Jun 22 '15 at 20:04

Let's say the domain is as following

String domain[] = { a, b, .., z, A, B, .. Z, 0, 1, 2, .. 9 };

Let's say the password size is 8

ArrayList allCombinations = getAllPossibleStrings2(domain,8);

This is going to generate SIZE(domain) * LENGTH number of combinations, which is in this example (26+26+10)^8 = 62^8 = 218,340,105,584,896 combinations

Then you can enumerate all possible string up\at to a specific size like this

// get all possible combinations up to a given size
static ArrayList getAllPossibleStrings1(ArrayList domain, int maxSize)
{
    ArrayList list = new ArrayList();
    int i = 1;

    list.AddRange(domain);

    while(++i <= maxSize)
        for(String a in list)
            for(String b in domain)
                list.Add(String.Concat(a,b));

    return list;
}

// get all possible combinations at a given size
static ArrayList getAllPossibleStrings2(ArrayList domain, int size)
{
    ArrayList list = new ArrayList();
    ArrayList temp = new ArrayList();
    int i = 1;

    list.AddRange(domain);

    while(++i <= maxSize)
    {
        for(String a in list)
            for(String b in domain)
                temp.Add(String.Concat(a,b));

        list.Clear();
        list.AddRange(temp);
        temp.Clear();
    }

    return list;
}

Does there exist an algorithm for iterating through all strings that conform to a particular regex?

3 Answers3