PHP's crypt challenge

Question

A friend gave me a challenge: he encrypted a string using PHP's crypt function (CRYPT_STD_DES) (from PHP4). I know the salt used to encrypt, and as crypt is a one-way algorithm I must use brute-force method, and I know that passwords only consist of lower-case letters.

Now, I have machine with 16 cores (2x Xeon), and lots of RAM. What is most efficient way to implement this force attack (I assume I'll have to use PHP, which is not quite ok, but if any of you have ideas...)

[EDIT]

And i forgot to mention, encrypted representaction is 13chars length, and string is less than 8 letters, just like a simple password encryption :)

Answer 1

This is a quick try in C of the code (compiled with gcc -O2 -lcrypt)
on Ubuntu 10.04.1

  #define _XOPEN_SOURCE
  #include <unistd.h>
  #include <stdio.h>
  #include <stdlib.h>

  void inc(char *p)
  {
     int i;
     for (i=0 ; i<8 && p[i]=='z' ; i++);
     if (i >= 8) exit(printf("Not found :-(\n"));
     if (!p[i]) p[i]='a';
     else p[i]++;
     while (--i >= 0) p[i]='a';
  }

  int main ()
  {
    char *salt = "XY";
    char *buzz = "XYaAbBcCZ0123";

    char pass[] = { 'a',0,0,0,0,0,0,0,0 };

    while(1)
      if ( ! strcmp(crypt(pass, salt), buzz))
        exit(printf("Found %s :-)\n", pass));
      else
        inc(pass);
  }

That code should run within a day or two (2.10^11 combinations) on a nowadays pc, you can run it on several machines, one doing from "a" to "gzzzzzzz", another from "haaaaaaa" to "nzzzzzzz" etc... for instance.