# Brute-force word cracking program using /dev/urandom

I've been having fun with this program and trying to use different methods and such to achieve the fastest possible word cracking program I can come up with. I'm pretty happy with my current program which is able to crack any three letter word on my computer (Dell Latitude E6400 Dual Core) well under a tenth of a second. I find a significant improvement using multi threading which is to be anticipated granted that most modern computers have 2+ cores.

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <sys/time.h>
#include <time.h>
#include <string.h>
#include <inttypes.h>
#include <semaphore.h>

#define QUICKIE_STRCMP(a, b)  (*(a) != *(b) ? \
(int) ((unsigned char) *(a) - \
(unsigned char) *(b)) : \
strcmp((a), (b)))

struct job {
int *len;
int id;
char *word;
struct timeval *start;
struct timeval *end;
sem_t *sem;
};

int get_nproc     ();
int needQuit      (sem_t *sem);
void *worker_func (void *);

int main(int argc, char **argv) {
char *word;
int i, j, iterations = 1, len;
float *times, sum, lowest, highest;
int nproc = get_nproc();
#else
int nproc = 1;
#endif
struct timeval start, end;
sem_t sem;

if(argc < 2) {
fprintf(stderr, "Usage: %s <word to crack> <iterations>\n", argv[0]);
exit(EXIT_SUCCESS);
}

if(argc > 2) {
iterations = atoi(argv[2]);
}

for(i = 0; argv[1][i]; i++) {
argv[1][i] = tolower(argv[1][i]);
}

len = i;
printf("nproc\t\t: %d\nlength\t\t: %d\niterations\t: %d\n\n\n", nproc, len, iterations);
times = malloc(iterations * sizeof(float));
sem_init(&sem, 0, 0);

struct job job = {
.len = &len,
.word = argv[1],
.start = &start,
.end = &end,
.sem = &sem,
.mxq = &mxq,
};

for(i = 0; i < iterations; i++) {
for(j = 0; j < nproc;j++) {
}
sem_wait(&sem);
sem_destroy(&sem);
for(j = 0; j < nproc;j++) {
}
times[i] = (((end.tv_sec - start.tv_sec)*1000000.0f)
+ (end.tv_usec - start.tv_usec)) / 1000000.0f;
printf("iteration [%d]\t: took %f seconds.\n\n", i+1, times[i]);
}
lowest = highest = times[0];
for(i = 0; i < iterations;i++) {
sum += times[i];
if(times[i] > highest) highest = times[i];
if(times[i] < lowest) lowest = times[i];
}
printf("\nSTATS:\n\ttotal time:\t%f\n\taverage time:\t%f\n\tlowest time:\t%f\n\thighest time:\t%f\n",sum, sum / (float) iterations, lowest, highest);

free(times);
}

int get_nproc() {
FILE* fp;
char buffer[2048];
char* match;
int nproc;

if((fp = fopen("/proc/cpuinfo", "r")) == NULL) {
perror("open failed");
exit(EXIT_FAILURE);
}
fclose(fp);
perror("read failed or buffer isn't big enough.");
exit(EXIT_FAILURE);
}
match = strstr(buffer, "cpu cores");
if(match == NULL) {
fprintf(stderr, "failed to locate line starting with cpu cores\n");
exit(EXIT_FAILURE);
}
sscanf(match, "cpu cores\t: %d", &nproc);
return nproc;
}

int needQuit(sem_t *sem) {
int sval = 0;
sem_getvalue(sem, &sval);
return sval;
}

void *worker_func(void *param) {
struct job *job = param;
int fd, i, len = *job->len;
unsigned int rand;
char *word = malloc(len+1);
struct timeval start;

word[len] = '\0';
fd = open("/dev/urandom", O_RDONLY);
gettimeofday(&start, NULL);
while(!needQuit(job->sem)) {
for(i = 0; i < len; i++) {
word[i] = 97 + rand % 26; // a-z
}
if(QUICKIE_STRCMP(word, job->word) == 0) {
if(needQuit(job->sem)) break;
gettimeofday(job->end, NULL);
*job->start = start;
}else{
break;
}
sem_post(job->sem);
printf("found string\t: %s\n", word);
break;
}
}
close(fd);
free(word);
}


Now, I want your help to even further optimize this code to run faster. There ought to be something that can be improved. This is the makefile I'm using to compile the program:

all: crack

crack: crack.o
gcc $^ -o$@ -lpthread

crack.o: crack.c
gcc $^ -g -c -O3 -o$@


Theoretically, the program should be faster using unsigned char instead of unsigned int because it only needs to read one byte from /dev/urandom instead of 4 (or whatever the size of int proves to be on one's system)).

• What are you trying to achieve? A simulation of infinite monkeys? – 200_success Jul 29 '15 at 16:08
• @200_success pretty much, yes. It was just an idea I had. Only that I wish to complete it as fast as possible for a given string. – Linus Jul 29 '15 at 16:09
• Why read from /dev/urandom instead of calling rand()? – 200_success Jul 29 '15 at 16:13
• @200_success I initially used rand() but for a multithread program that proved to be slower than using a single thread. But using /dev/urandom was twice as fast as using a single thread with /dev/urandom – Linus Jul 29 '15 at 16:15
• @Linus rand() is not guaranteed to be thread-safe anyway if I'm not mistaken. – Morwenn Jul 29 '15 at 16:25

## Random letters

There's a few things that I don't like about randomly guessing the string.

1. Reading from /dev/urandom is going to be slower than using rand_r(). As mentioned in the comments, rand() is not thread safe, but rand_r() is. I tried replacing the read from /dev/urandom with rand_r() and it made the program roughly 50x faster.
2. Using a random guess in the first place is inefficient. First, it's slow to generate a random string. Second, you might try the same random string multiple times. It would be better to just brute force try every combination in succession.

I ran your program trying to find a five letter word. It took between 1-2 minutes on my computer to succeed. Then I modified your main loop like this:

  memset(word, 'a', len);
while(!needToQuit) {
if(QUICKIE_STRCMP(word, job->word) == 0) {
// (same code here as before)
break;
}
// Move on to the next combination in a brute force manner.
for (i=len-1;i>=0;i--) {
if (word[i] < 'z') {
word[i]++;
break;
}
word[i] = 'a';
}
}


I tried looking for zzzzz (the worst case) with this modified program, and it took 0.03 seconds. It could handle zzzzzzz (7 letters) in 19 seconds. This is over 2 magnitudes of order faster than the random method. This was all single threaded, but you could also modify this technique to use threads to split up the search space. For example, thread 1 could start at aaaaa and thread 2 could start at naaaa.

## Semaphore not needed

Currently, you use a semaphore so that when one thread finds the word, it can notify the other thread that it should stop. But this turns out to be very slow. In your main loop, this part:

  while(!needQuit(job->sem)) {


is very slow. You could just use a shared variable and it would do the same thing. You just need to use the mutex you already have for when you want to set it. For example:

   // In main:
int needToQuit = 0;
// For all jobs:
job->pNeedToQuit = &needToQuit;

while(!*job->pNeedToQuit) {
// ...
if (foundTheWord) {

• @Linus Ok in your question you just said "the fastest possible word cracking program I can come up with" so I didn't know that the random thing was a requirement. So given that it is, I suggest you try out rand_r() and see if it makes your program faster than reading /dev/urandom. – JS1 Jul 29 '15 at 20:56