title: Brute forcing DES with a weak key
body: <p>I am taking a course on Cryptography and am stuck on an assignment. The instructions are as follows:</p>
  
  <blockquote>
    <p>The plaintext plain6.txt has been encrypted with DES to encrypt6.dat using a 64-bit key given as a string of 8 characters (64
    bits of which every 8th bit is ignored), all characters being letters
    (lower-case or upper-case) and digits (0 to 9).</p>
    
    <p>To complete the assignment, send me the encryption key before February
    12, 23.59. </p>
    
    <p>Note: I expect to get an 8-byte (64-bits) key. Each byte should
    coincide with the corresponding byte in my key, except for the least
    significant bit which is not used in DES and thus, could be arbitrary.</p>
  </blockquote>
  
  <p>Here is the code to my first attempt in Python:</p>
  
  <pre><code>import time
  from Crypto.Cipher import DES
  
  class BreakDES(object):
      def __init__(self, file, passwordLength = 8, testLength = 8):
          self.file = file
          self.passwordLength = passwordLength
          self.testLength = testLength
          self.EncryptedFile = open(file + '.des')
          self.DecryptedFile = open(file + '.txt')
          self.encryptedChunk = self.EncryptedFile.read(self.testLength)
          self.decryptedChunk = self.DecryptedFile.read(self.testLength)
          self.start = time.time()
          self.counter = 0
          self.chars = range(48, 58) + range(65, 91) + range(97, 123)
          self.key = False
          self.broken = False
  
          self.testPasswords(passwordLength, 0, '')
  
          if not self.broken:
              print "Password not found."
  
          duration = time.time() - self.start
  
          print "Brute force took %.2f" % duration
          print "Tested %.2f per second" % (self.counter / duration)
  
      def decrypt(self):
          des = DES.new(self.key.decode('hex'))
          if des.decrypt(self.encryptedChunk) == self.decryptedChunk:
              self.broken = True
              print "Password found: 0x%s" % self.key
          self.counter += 1
  
      def testPasswords(self, width, position, baseString):
              for char in self.chars:
                  if(not self.broken):
                      if position &lt; width:
                          self.testPasswords(width, position + 1, baseString + "%c" % char)
                          self.key = (baseString + "%c" % char).encode('hex').zfill(16)
                          self.decrypt()
  
  # run it for password length 4
  BreakDES("test3", 4)
  </code></pre>
  
  <p>I am getting a speed of 60.000 tries / second. A password of 8 bytes over 62 characters gives 13 trillion possibilities, which means that at this speed it would take me 130 years to solve. I know that this is not an efficient implementation and that I could get better speeds in a faster language like C or it's flavors, but I have never programmed in those. Even if I get a speed-up of 10, we're still a huge leap away from 10,000,000,000 per second to get in the hours range.</p>
  
  <p>What am I missing? This is supposed to be a weak key :). Well, weaker than the full 256 character set.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>Due to some ambiguity about the assignment, here is the full description and some test files for calibration: <a href="http://users.abo.fi/ipetre/crypto/assignment6.html" rel="nofollow">http://users.abo.fi/ipetre/crypto/assignment6.html</a></p>
  
  <p><strong>EDIT 2</strong></p>
  
  <p>This is a crude C implementation that gets around 2.000.000 passwords/s per core on an i7 2600K. You have to specify the first character of the password and can manually run multiple instances on different cores/computers. I managed to solve the problem using this within a couple of hours on four computers.</p>
  
  <pre><code>#include &lt;stdio.h&gt;      /* fprintf */
  #include &lt;stdlib.h&gt;     /* malloc, free, exit */
  #include &lt;unistd.h&gt;
  #include &lt;string.h&gt;     /* strerror */
  #include &lt;signal.h&gt;
  #include &lt;openssl/des.h&gt;
  
  static long long unsigned nrkeys = 0; // performance counter
  
  char *
  Encrypt( char *Key, char *Msg, int size)
  {
          static char*    Res;
          free(Res);
          int             n=0;
          DES_cblock      Key2;
          DES_key_schedule schedule;
          Res = ( char * ) malloc( size );
          /* Prepare the key for use with DES_ecb_encrypt */
          memcpy( Key2, Key,8);
          DES_set_odd_parity( &amp;Key2 );
          DES_set_key_checked( &amp;Key2, &amp;schedule );
          /* Encryption occurs here */
          DES_ecb_encrypt( ( unsigned char (*) [8] ) Msg, ( unsigned char (*) [8] ) Res,
                             &amp;schedule, DES_ENCRYPT );
          return (Res);
  }
  
  char *
  Decrypt( char *Key, char *Msg, int size)
  {
          static char*    Res;
          free(Res);
          int             n=0;
          DES_cblock      Key2;
          DES_key_schedule schedule;
          Res = ( char * ) malloc( size );
          /* Prepare the key for use with DES_ecb_encrypt */
          memcpy( Key2, Key,8);
          DES_set_odd_parity( &amp;Key2 );
          DES_set_key_checked( &amp;Key2, &amp;schedule );
          /* Decryption occurs here */
          DES_ecb_encrypt( ( unsigned char (*) [8]) Msg, ( unsigned char (*) [8]) Res,
                             &amp;schedule, DES_DECRYPT );
          return (Res);
  }
  
  void ex_program(int sig);
  
  int main(int argc, char *argv[])
  {
      (void) signal(SIGINT, ex_program);
  
      if ( argc != 4 ) /* argc should be 2 for correct execution */
      {
          printf( "Usage: %s ciphertext plaintext keyspace \n", argv[0] );
          exit(1);
      }
  
      FILE *f, *g;
      int counter, i, prime = 0, len = 8;
      char cbuff[8], mbuff[8];
      char letters[] = "02468ACEGIKMOQSUWYacegikmoqsuwy";
      int nbletters = sizeof(letters)-1;
      int entry[len];
      char *password, *decrypted, *plain;
  
      if(atoi(argv[3]) &gt; nbletters-2) {
          printf("The range must be between 0-%d\n", nbletters-2);
          exit(1);
      }
      prime = atoi(argv[1])
  
      // read first 8 bytes of the encrypted file
      f = fopen(argv[1], "rb");
      if(!f) {
          printf("Unable to open the file\n");
          return 1;
      }
      for (counter = 0; counter &lt; 8; counter ++) cbuff[counter] = fgetc(f);
      fclose(f);
  
      // read first 8 bytes of the plaintext file
      g = fopen(argv[2], "r");
      if(!f) {
          printf("Unable to open the file\n");
          return 1;
      }
      for (counter = 0; counter &lt; 8; counter ++) mbuff[counter] = fgetc(g);
      fclose(g);
  
      plain = malloc(8);
      memcpy(plain, mbuff, 8);
  
      // fill the keys
      for(i=0 ; i&lt;len ; i++) entry[i] = 0;
      entry[len-1] = prime;
  
      // loop until the length is reached
      do {
          password = malloc(8);
          decrypted = malloc(8);
  
          // build the pasword
          for(i=0 ; i&lt;len ; i++) password[i] = letters[entry[i]];
          nrkeys++;
  
          // end of range and notices
          if(nrkeys % 10000000 == 0) {
              printf("Current key: %s\n", password);
              printf("End of range ");
              for(i=0; i&lt;len; i++) putchar(letters[lastKey[i]]);
              putchar('\n');
          }
  
          // decrypt
          memcpy(decrypted,Decrypt(password,cbuff,8), 8);
  
          // compare the decrypted with the mbuff
          // if they are equal, exit the loop, we have the password
          if (strcmp(mbuff, decrypted) == 0)
          {
              printf("We've got it! The key is: %s\n", password);
              printf("%lld keys searched\n", nrkeys);
              exit(0);
          }
  
          free(password);
          free(decrypted);
  
          // spin up key until it overflows
          for(i=0 ; i&lt;len &amp;&amp; ++entry[i] == nbletters; i++) entry[i] = 0;
      } while(i&lt;len);
  
      return 0;
  }
  
  void ex_program(int sig) {
   printf("\n\nProgram terminated %lld keys searched.\n", nrkeys);
   (void) signal(SIGINT, SIG_DFL);
   exit(0);
  }
  </code></pre>