Need help with brute force code for crypt(3)

Question

Hello, I am trying to develop a program in C that will "crack" the crypt(3) encryption used by UNIX. The most naive way to do it is brute forcing I guess. I thought I should create an array containing all the symbols a password can have and then get all possible permutations of them and store them in a two-dimensional array (where all the 1 character passwords get's saved in the first row etc.) through for loops. Is there any better way to do this? It's pretty messy with the loops.

Answer 1

As the commenters on the question point out - you don't have the necessary RAM, and you don't need to store it all.

Covering the permutations in sort sequence is not the most efficient approach to password cracking, although it will ultimately be effective.

An approach to achieving full coverage is to iterate 0 through the number of permutations and encode the value with the size of your character set as a base. This can be scaled to the size of your character set quite easily.

(pseudocode, but you get the idea)

passChars = '[all characters used in this attempt]'

permutationCount = 8^len(passChars) #crypt(3) only uses 8 chars

output = ''

for looper = 0 to permutationCount - 1
    localTemp = looper
    while localTemp > 0
        output += passchars[localTemp%len(passchars)] # % being modulus
        localTemp = floor(localTemp/len(passChars))

Answer 2

Assuming only 62 different characters can be used, storing all the possible 8 character passwords requires 62^8=198 Terabytes.

To anwser you loop question, here is some code to loop over all the possible passwords of a given len, using the characters for a given set:

int len = 3;
char letters[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
int nbletters = sizeof(letters)-1;

int main() {
    int i, entry[len];
    for(i=0 ; i<len ; i++) entry[i] = 0;
    do {
        for(i=0 ; i<len ; i++) putchar(letters[entry[i]]);
        putchar('\n');
        for(i=0 ; i<len && ++entry[i] == nbletters; i++) entry[i] = 0;
    } while(i<len);
}

The main part is the last for loop. In most cases, it only increments the first entry, and stops there, as this entry has not reached nbletters. If the entry reaches nbletter, it means it has to return to zero, and it's the turn of the next entry to be incremented. It is indeed an unusual loop condition: the loop continues until there is no overflow. The looping only occurs in the worst case: when several entries are on the last element.

Imagine the case where the current word is "zzzc". In turn, each entry is incremented, its overflow is detected, it is reset to 0, and the next entry is considered, until the last entry which does not overflow, to give "000d".