Brute forcing case

[iago]

Here's the problem: I have a case insensitive password (say, "mypassword") and I need to figure out what the case-sensitive version is (say, "MyPassword"). The problem is, doing a check is fairly slow, because this involves network traffic.

So, I'm trying to come up with a way to brute force the case in the most efficient possible way. That means we're going to try putting one character uppercase first, starting with the first characters ("Mypassword", "mYpassword", "myPassword", "mypAssword", etc). Then, two characters uppercase, starting with the first two, "MYpassword", "MyPassword", "MypAssword", "MypaSsword", etc)

More generically, here it is in binary (where the 0 represents lower and the 1 represents upper) -- I put decimals beside them being I'm trying to find a pattern:

0000 (0)
1000 (8)
0100 (4)
0010 (2)
0001 (1)
1100 (12/C)
1010 (10/A)
1001 (9)
0110 (6)
0101 (5)
0011 (3)
1110 (14/E)
1101 (13/D)
1011 (11/B)
0111 (7)
1111 (15/F)

I'm trying to figure out the most simple way of doing this for an arbitrary length password, while maintaining this order. Computational power isn't a big deal, since the bottleneck on this will be the network traffic. That being said, I want to avoid recursion or anything nasty like that.

I don't care what language it's in, since I doubt anybody knows the actual language I'm using (Lua). Pseudocode or just an algorithm is as good as code.

Any thoughts?

<edit> One thought I had was to take standard binary (0001, 0010, 0011, 0100, etc) and sort it by the number of '1's in the number. That would work, but it feels a little ewwy.

[iago]

So, I implemented the idea I had in my edit, and it actually works pretty slick:

local function count_ones(num)
    local count = 0

    while num ~= 0 do
        if(bit.band(num, 1) == 1) then
            count = count + 1
        end
        num = bit.rshift(num, 1)
    end

    return count
end

local function find_password_case(smbstate, domain, username, password)
    -- Figure out how many possibilities exist
    local max = math.pow(2, #password) - 1

    -- Create an array of them, starting with all the values whose binary representation has no ones, then one one, then two ones, etc.
    local ordered = {}

    -- Loop backwards from the length of the password to 0. At each spot, put all numbers that have that many '1' bits
    for i = 0, #password, 1 do
        for j = max, 0, -1 do
            if(count_ones(j) == i) then
                table.insert(ordered, j)
            end
        end
    end

    io.write(nsedebug.tostr(ordered))
end

Outputs:

1: 0
2: 8
3: 4
4: 2
5: 1
6: 12
7: 10
8: 9
9: 6
10: 5
11: 3
12: 14
13: 13
14: 11
15: 7
16: 15

I haven't done the part where it converts the case yet, but that'll be simple.

[iago]

And here's the code I came up to for converting the case.. it's pretty ugly, but such is life with immutable strings:

local function convert_case(str, num)
    local pos = #str

    -- Don't bother with blank strings (we probably won't get here anyway, but it doesn't hurt)
    if(str == "") then
        return ""
    end

    while(num ~= 0) do
        -- Check if the bit we're at is '1'
        if(bit.band(num, 1) == 1) then
            -- Check if we're at the beginning or end (or both) of the string -- those are special cases
            if(pos == #str and pos == 1) then
                str = string.upper(string.sub(str, pos, pos))
            elseif(pos == #str) then
                str = string.sub(str, 1, pos - 1) .. string.upper(string.sub(str, pos, pos))
            elseif(pos == 1) then
                str = string.upper(string.sub(str, pos, pos)) .. string.sub(str, pos + 1, #str)
            else
                str = string.sub(str, 1, pos - 1) .. string.upper(string.sub(str, pos, pos)) .. string.sub(str, pos + 1, #str)
            end
        end

        num = bit.rshift(num, 1)

        pos = pos - 1
    end

    return str
end

1: test
2: Test
3: tEst
4: teSt
5: tesT
6: TEst
7: TeSt
8: TesT
9: tESt
10: tEsT
11: teST
12: TESt
13: TEsT
14: TeST
15: tEST
16: TEST

[Hitmen]

What's the point of asking for help if you're going to solve the problem yourself within half an hour? 

[iago]

Haha, shut up. I'm awesome, that's why.

I figured I'd come up with a hacky solution, just to get me by, then discovered it's actually kind of nice.

I'm open to suggestions on how to improve it, though, on a 14-character password this way takes noticeable time. I'd like a solution that's O(n) instead of mine, which I think is O(nlogn) or O(n²) or something.

[Sidoh]

If it's an arbitrary length of n, and you're trying all combinations, it's definitely O(2^n).  Maybe I'm misunderstanding what you're calling "n"?

If you want to try all combinations, there's no way of escaping that, either -- unless you want to omit certain cases.  If you want a less exact but more efficient approach, it might be worth looking into breaking up the password into dictionary words and trying common ways of capitalizing the words or something.  I kind of doubt that'd be a reasonable approach, but who knows.

[iago]

Yeah, I suck at defining 'n'. I had meant 'n' to mean the total number of combinations, so 2^length. Maybe. I don't know.

For each set of '1's, it's going through the full array from 1 to 2^length. So for 1 '1' it searches the array, then for 2 '1's it searches the array, etc. So I guess the order, where 'n' is the string's length, is O(2^n * n), which isn't significantly worse than the best case, O(2^n).

I don't know, it just doesn't feel like the best way of doing it.

[Sidoh]

Like I said, there's no way avoiding exponential time if you want to look at every case.  There are 2^n cases.

Luckily, passwords aren't very long, right?

[Camel]

Some Java,

Code: [Select]

List<String> findPassword(String original) {
List<String> passwords = new ArrayList<String>();
for (int i = 0; i <= original.length(); i++) {
// Create i capitals in original
passwords.addAll(insertCapitals(original, i));
}
return passwords;
}

List<String> insertCapitals(String original, int howmany) {
List<String> passwords = new ArrayList<String>();

if(howmany == 0) {
// Don't need to add any more capitals; only possibility is the original
passwords.add(original);
} else if(original.length() == 0) {
// We need to add more capitals, but there's nowhere to put them; no possibilities
} else {
// Generate all the cases for the first char uppercase
for (String x : insertCapitals(original.substring(1), howmany - 1))
passwords.add(original.substring(0, 1).toUpperCase() + x);

// Generate all the cases for first char lowercase
for (String x : insertCapitals(original.substring(1), howmany))
passwords.add(original.charAt(0) + x);
}

return passwords;
}


[nslay]

I've actually dealt with generating combinations of fault scenarios in power systems.  I discovered combinadics as a useful way to represent combinations.
http://en.wikipedia.org/wiki/Combinadic

Each component of a combinadic represents a 0 or 1 or in this case a L or U.

I derived two algorithms with this idea.  One can generate all specific (n,m) combination.  The other recognizes that combinadics are analogous to traversal on a perfect directed graph whose edges are defined by:
[latex]
% TODO: Fix LaTeX in forum
\begin{align*}
& G =(V,E) \\
& i < j \Leftrightarrow (i,j) \in E \quad \forall i,j \in V \\
\end{align*}
[/latex]
I do a DFS-like traversal so this gives the following algorithm:

Code: [Select]

#include <stdio.h>
#include <string.h>

#define N       5

void print_case_mask(const char *case_mask);

int main(int argc, char **argv) {
        unsigned long stack[N], t;
        char case_mask[1 + (N >> 3)];

        stack[0] = 0;
        t = 0;
        memset(case_mask,0x00,sizeof(case_mask));

        while (stack[0] < N) {
                case_mask[stack[t] >> 3] ^= 1 << (stack[t] & 0x7);
                print_case_mask(case_mask);

                if (stack[t] >= N-1) {
                        case_mask[stack[t] >> 3] ^= 1 << (stack[t] & 0x7);
                        t -= (t > 0);
                }
                else if (t < N-1) {
                        case_mask[stack[t] >> 3] ^= 1 << (stack[t] & 0x7);
                        stack[t+1] = stack[t];
                        t++;
                }

                case_mask[stack[t] >> 3] ^= 1 << (stack[t] & 0x7);
                stack[t]++;
        }

        return 0;
}

void print_case_mask(const char *case_mask) {
        unsigned long i;
        for (i = 0; i < N; ++i) {
                putchar(case_mask[i >> 3] & (1 << (i & 0x7)) ? 'U' : 'L');
        }
        putchar('\n');
}

Example, output for N=5

Code: [Select]

ULLLL
UULLL
UUULL
UUUUL
UUUUU
UUULU
UULUL
UULUU
UULLU
ULULL
ULUUL
ULUUU
ULULU
ULLUL
ULLUU
ULLLU
LULLL
LUULL
LUUUL
LUUUU
LUULU
LULUL
LULUU
LULLU
LLULL
LLUUL
LLUUU
LLULU
LLLUL
LLLUU
LLLLU

for N=5, this produces the following stack states

• 0
• 0 1
• 0 1 2
• 0 1 2 3
• 0 1 2 3 4
• 0 1 2 4
• 0 1 3
• 0 1 3 4
• 0 1 4
• 0 2
• 0 2 3
• 0 2 3 4
• 0 2 4
• 0 3
• 0 3 4
• 0 4
• 1
• 1 2
• 1 2 3
• 1 2 3 4
• 1 2 4
• 1 3
• 1 3 4
• 1 4
• 2
• 2 3
• 2 3 4
• 2 4
• 3
• 3 4
• 4

You can further make this efficient by noticing sub-stack states repeating later in the sequence.  You could also force the stack size to be no more than N/2 and generate two case masks, where one is the complement.  You'd introduce this into the code

Code: [Select]

char ncase_mask[1 + (N >> 3)];

memset(ncase_mask, 0xff, sizeof(ncase_mask));

/* Annotate the algorithm with bit toggling in the same places as with the first algorithm */


[Joe]

[latex]
% TODO: Fix LaTeX in forum
\begin{align*}
& G =(V,E) \\
& i < j \Leftrightarrow (i,j) \in E \quad \forall i,j \in V \\
\end{align*}
[/latex]

[latex]  \textbf{It works.}[/latex]

But my knowledge of LaTeX doesn't.

[Blaze]

[latex]
% TODO: Fix LaTeX in forum
\begin{align*}
& G =(V,E) \\
& i < j \Leftrightarrow (i,j) \in E \quad \forall i,j \in V \\
\end{align*}
[/latex]

[latex]  \textbf{It works.}[/latex]
But my knowledge of LaTeX doesn't.

It didn't work when he posted it.  It has since been fixed.

[nslay]

[latex]
% TODO: Fix LaTeX in forum
\begin{align*}
& G =(V,E) \\
& i < j \Leftrightarrow (i,j) \in E \quad \forall i,j \in V \\
\end{align*}
[/latex]

[latex]  \textbf{It works.}[/latex]
But my knowledge of LaTeX doesn't.

It didn't work when he posted it.  It has since been fixed.

Awesome, but '%' is the comment delimiter in LaTeX, the TODO line should not appear.