Brute-force word cracking program using /dev/urandom

Question

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 <pthread.h>
#include <semaphore.h>

#define MULTITHREAD 1
#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;
  pthread_mutex_t *mxq;
};

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;
#if MULTITHREAD == 1
  int nproc = get_nproc();
#else
  int nproc = 1;
#endif
  struct timeval start, end;
  pthread_t worker_threads[nproc];
  pthread_mutex_t mxq;
  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++) {
    pthread_mutex_init(&mxq,NULL);
    for(j = 0; j < nproc;j++) {
      pthread_create(&worker_threads[j], NULL, worker_func, &job);
    }
    sem_wait(&sem);
    sem_destroy(&sem);
    for(j = 0; j < nproc;j++) {
      pthread_join(worker_threads[j], NULL);
    }
    pthread_mutex_unlock(&mxq);
    pthread_mutex_destroy(&mxq);
    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]; 
  size_t bytes_read; 
  char* match;
  int nproc;

  if((fp = fopen("/proc/cpuinfo", "r")) == NULL) {
    perror("open failed");
    exit(EXIT_FAILURE); 
  }
  bytes_read = fread(buffer, 1, sizeof(buffer), fp); 
  fclose(fp); 
  if(bytes_read == 0 || bytes_read == sizeof(buffer)) {
    perror("read failed or buffer isn't big enough.");
    exit(EXIT_FAILURE); 
  }
  buffer[bytes_read] = '\0'; 
  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;
  pthread_mutex_t *mxq = job->mxq;

  word[len] = '\0';
  fd = open("/dev/urandom", O_RDONLY);
  gettimeofday(&start, NULL);
  while(!needQuit(job->sem)) {
    for(i = 0; i < len; i++) {
      read(fd, &rand, sizeof(rand));
      word[i] = 97 + rand % 26; // a-z
    }
    if(QUICKIE_STRCMP(word, job->word) == 0) {
      if(needQuit(job->sem)) break;
      if(pthread_mutex_trylock(mxq) == 0) {
        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)).

Answer 1

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;

   // In thread:
   while(!*job->pNeedToQuit) {
       // ...
       if (foundTheWord) {
           pthread_mutex_lock(mxq);
           if (*job->pNeedToQuit == 0) {
               // Do stuff here as the first thread to find the word.
               *job->pNeedToQuit = 1;
           }
           pthread_mutex_unlock(mxq);
           break;
       }
       // ...
   }