2
\$\begingroup\$

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)).

\$\endgroup\$
  • \$\begingroup\$ What are you trying to achieve? A simulation of infinite monkeys? \$\endgroup\$ – 200_success Jul 29 '15 at 16:08
  • \$\begingroup\$ @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. \$\endgroup\$ – Linus Jul 29 '15 at 16:09
  • \$\begingroup\$ Why read from /dev/urandom instead of calling rand()? \$\endgroup\$ – 200_success Jul 29 '15 at 16:13
  • \$\begingroup\$ @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 \$\endgroup\$ – Linus Jul 29 '15 at 16:15
  • \$\begingroup\$ @Linus rand() is not guaranteed to be thread-safe anyway if I'm not mistaken. \$\endgroup\$ – Morwenn Jul 29 '15 at 16:25
4
\$\begingroup\$

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;
       }
       // ...
   }
\$\endgroup\$
  • \$\begingroup\$ That's really a huge difference, however the reason for using random is in fact simulating the infinite monkey theorem. Sure I agree that using a more efficient brute-force method such as to try every combination from a-z for a specified length is WAY better if you want to find the word as fast as possible. However it kind of takes out the main reason I experimented with this program from the first place, that is to see how long it would take to compute the given word with random letters (it might just take one try or never compute!). \$\endgroup\$ – Linus Jul 29 '15 at 19:56
  • \$\begingroup\$ @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. \$\endgroup\$ – JS1 Jul 29 '15 at 20:56
  • \$\begingroup\$ Sorry I didn't make it clear, however I tried using rand_r with a seed generated by /dev/urandom and o'boy was it faster! "abc" was found on average (running a thousand iterations) in 0.0002 seconds! \$\endgroup\$ – Linus Jul 29 '15 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.