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

From the PHP manual:

crypt() will return a hashed string using the standard Unix DES-based algorithm or alternative algorithms that may be available on the system.

Some operating systems support more than one type of hash. In fact, sometimes the standard DES-based algorithm is replaced by an MD5-based algorithm. The hash type is triggered by the salt argument. Prior to 5.3, PHP would determine the available algorithms at install-time based on the system's crypt(). If no salt is provided, PHP will auto-generate either a standard two character (DES) salt, or a twelve character (MD5), depending on the availability of MD5

In other words, the crypt() function just calls the Operating System's crypt() function from the C library. This means two things.

First, the type of encryption is standardized. You don't need to use PHP to run the brute force, you just need to know the algorithm used. Many programs like Cane and Abel or Jack the Ripper are able to break several algorithms via brute force, dictionary, or rainbow table attacks.

Second, the type of encryption is based on the Operating System on which is was encrypted. This means you may have to try several different encryption methods unless there's an obvious clue as to which was used (the pattern of the encrypted string may clue you in to something).

I would definitely NOT suggest trying to use PHP to brute force it, as interpreted languages run much slower than their compiled counterparts.

Answer 2

The most efficient (though probably the least challanging) way is probably to find someone who has already implemented it (use John the Ripper for example).

Answer 3

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.