Dictionary attack on encipher.it ciphertexts

decipherit.c

#include <stdio.h>
#include <string.h>
#include <assert.h>

#include <CommonCrypto/CommonCryptor.h>
#include <CommonCrypto/CommonHMAC.h>
#include <CommonCrypto/CommonKeyDerivation.h>

#include <dispatch/dispatch.h>


#define min(a,b) \
  ({ __typeof__ (a) _a = (a); \
     __typeof__ (b) _b = (b); \
     _a < _b ? _a : _b; })


void DeriveHMACKey(uint8_t *hmacKey, const char *password, const char *salt)
{ 
  uint8_t rawkey[256 / 8];
  
  // Use PBKDF2-HMAC-SHA1 to derive a 256-bit key
  CCKeyDerivationPBKDF(
    kCCPBKDF2,
    password, strlen(password),
    (const uint8_t *)salt, 8,
    kCCPRFHmacAlgSHA1, 1000,
    rawkey, sizeof(rawkey)
  );
  
  // And then for some reason, we need to hex encode it
  for (size_t i = 0; i < sizeof(rawkey); i ++)
  {
    hmacKey[2*i]   = "0123456789abcdef"[rawkey[i] / 16];
    hmacKey[2*i+1] = "0123456789abcdef"[rawkey[i] % 16];
  }
}

void TestHMACKey(void)
{
  char *salt = "umUF8dMm";
  char *password = "aaaa";
  
  uint8_t hmacKey[64];
  uint8_t expected[] = "f0a2559d9d242b01599b6d79b3ed108ac03c33848141d19c98317d3926b327ba";
  
  DeriveHMACKey(hmacKey, password, salt);
  assert(memcmp(hmacKey, expected, sizeof(hmacKey)) == 0);
}


void DeriveAESKey(uint8_t *aesKey, const uint8_t *hmacKey)
{
  // Takes the HMAC key, and does strange crypto on it to produce the AES
  // key. Based on Aes.Ctr.encrypt in AES.js.
 
  uint8_t ciphertext[32];
  size_t outlen;
    
  // Encrypt the first 32 bytes of key 1 
  CCCrypt(
    kCCEncrypt,
    kCCAlgorithmAES128,
    kCCOptionECBMode,
    hmacKey, 32,
    NULL,
    hmacKey, 32,
    ciphertext, 32,
    &outlen
  );
  
  // The output AES key is just the first block, doubled
  memcpy(aesKey, ciphertext, 16);
  memcpy(aesKey + 16, ciphertext, 16);
}

void TestAESKey(void)
{
  char *salt = "umUF8dMm";
  char *password = "aaaa";
  uint8_t hmacKey[] = "f0a2559d9d242b01599b6d79b3ed108ac03c33848141d19c98317d3926b327ba";
  
  uint8_t aesKey[32];
  uint8_t expected[] = "\xb2\xd6\xd5\x4e\x83\x22\x6c\x05\x65\xcc\xd2\xcd\x51\x24"
    "\xe1\xa3\xb2\xd6\xd5\x4e\x83\x22\x6c\x05\x65\xcc\xd2\xcd\x51\x24\xe1\xa3";
  
  DeriveAESKey(aesKey, hmacKey);
  assert(memcmp(aesKey, expected, sizeof(aesKey)) == 0);
}


void Decrypt(uint8_t *output, const uint8_t *input, size_t inputsz,
             const uint8_t *aesKey, const uint8_t *nonce)
{
  // Fairly straightforward CTR mode decryption of the message
  uint8_t iv[128 / 8];
  memcpy(iv, nonce, 8);
  bzero(iv + 8, sizeof(iv) - 8);
  
  size_t outlen;
  
  // Create a cryptor in CTR mode
  CCCryptorRef cryptor;
  CCCryptorCreateWithMode(
    kCCDecrypt,
    kCCModeCTR,
    kCCAlgorithmAES,
    ccNoPadding,
    iv,
    aesKey, 32,
    NULL, 0,
    0,
    kCCModeOptionCTR_BE,
    &cryptor
  );
  
  // Decrypt the message
  CCCryptorUpdate(
    cryptor,
    input, inputsz,
    output, inputsz, 
    &outlen
  );
  
  // Can skip CCCryptorFinal()
  CCCryptorRelease(cryptor);
}

void TestDecrypt(void)
{
  uint8_t nonce[] = "\x92\x03\x13\xc6\x7b\xcc\x66\x55";
  uint8_t aesKey[] = "\xf5\xac\x0c\x77\xfa\x5c\x92\x62\x58\x2d\x80\x54\x66\x3c"
    "\xbc\x80\xf5\xac\x0c\x77\xfa\x5c\x92\x62\x58\x2d\x80\x54\x66\x3c\xbc\x80";
  uint8_t ciphertext[] = "\x5b\x78\xcf\xd7\x73\xe4\x2f\x78\x91\x8e\x33\x77\xc9"
    "\xb1\xbe\xc8\x6f\x15\x08\xd9\x41\xa5\x8d\x1f\x0b\x49\x83\xda\x3e\x23\x4b"
    "\xb2\x63\x83\xd7\x52\x42\xa7\x0b\x79\x36\xf8\x58\x70\x2b\xf4\xac\xc2\x4b"
    "\x04\x01\xd2\x91\x87\x1d\x56\x4e\x84\xb7\x06\x5a\x77\x37\x56\xff\xa5\xa6"
    "\x60\x21\x77\x37\x8e\x13\x56\xad\xef\xad\x04\x31\x81\x07\x45\x55\xb5\x52"
    "\xbc\xc7\xa8\x6a\x21\xba\xf4\x96\xfd\xed\x2c\x20\x1f\xa5\x9d";
  
  uint8_t plaintext[100];
  uint8_t expected[] = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
  
  Decrypt(plaintext, ciphertext, sizeof(ciphertext), aesKey, nonce);  
  assert(memcmp(plaintext, expected, sizeof(plaintext)) == 0);
}


int Verify(const uint8_t *expected, const uint8_t *hmacKey,
           const uint8_t *plaintext, size_t plaintextsz)
{
  // Compute an HMAC-SHA1 over the plaintext, and see if it matches
  uint8_t computed[160/8];
  CCHmac(kCCHmacAlgSHA1, hmacKey, 64, plaintext, plaintextsz, computed);
  
  return memcmp(computed, expected, sizeof(computed)) == 0;
}

void TestVerify(void)
{
  uint8_t hmacKey[] = "0d2019ecf6d6e453b562b174e9fe664c7c71d226f5b55bd5f4246747fbb715cd";
  uint8_t plaintext[] = "aaaa";
  uint8_t expected[] = "\xfd\x23\xdf\x4e\xad\x0c\xfa\x6a\x8f\x65\x93\x24\x6b\xc4\x6d\x63\xa2\x81\xdb\x0d";
  
  assert(Verify(expected, hmacKey, plaintext, 4));
}


char **LoadWordList(size_t *wordcount)
{
  FILE *f = fopen("/usr/share/dict/words", "r");
  *wordcount = 0;
  
  // Read the wordlist once to get an idea of how many words are there
  char *line = NULL;
  size_t linesz = 0;
  ssize_t readsz;
  while ((readsz = getline(&line, &linesz, f)) != -1) {
    (*wordcount) ++;
  }
  free(line);
  
  // Allocate enough memory for a lookup table
  char **wordlist = malloc(sizeof(char *) * *wordcount);
  
  // Rewind and read it in again
  rewind(f);
  line = NULL; linesz = 0;
  size_t i = 0;
  while ((readsz = getline(&line, &linesz, f)) != -1) {
    wordlist[i] = strdup(line);
    size_t wordlen = strlen(line);
    if (wordlist[i][wordlen - 1] == '\n')
      wordlist[i][wordlen - 1] = '\0';
    i ++;
  }
  free(line);
  
  return wordlist;
}


int main(int argc, char *argv[])
{
  // Run some sanity checks to make sure we've implemented everything correctly
  TestHMACKey();
  TestAESKey();
  TestDecrypt();
  TestVerify();
  
  // Load our wordlist
  size_t wordcount;
  char **wordlist = LoadWordList(&wordcount);
  printf("Loaded %zu words\n", wordcount);

  // Here's our target message
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wpointer-sign"
#if 0
  char *salt = "CRCfTYrQ";
  uint8_t *hmac = "\x0f\xa5\x59\xc1\x85\x10\x6a\x03\x72\xe7\xfb\x55\x34\xcf\xce\x70\xd9\xac\x6e\xd7";
  uint8_t *nonce = "\x10\x00\xee\xad\xb8\x42\x61\x55";
  uint8_t *ciphertext = "\xae\xfb\x36\x3e\xc9\x0f\xab\x2b\xbb\x63\x1d\xd1\x31"
    "\x34\xe0\xab\x77\x94\x0a\xb0\x33\xbf\xc1\x43\xea\x15\x76\x81\x7c\x9a\x3f"
    "\x69\xe7\xb0\x92\xe3";
#else
  // test message, password is "harmful"
  char *salt = "kdZZG4zw";
  uint8_t *hmac = "\xa8\x0e\x95\x58\x91\x75\x9f\x0f\xc4\xab\x48\x6c\x5f\x71\x02\x96\xa9\x67\x0b\x13";
  uint8_t *nonce = "\x0a\x02\x31\xfc\x4f\xda\x66\x55";
  uint8_t *ciphertext = "\x01\x16\x73\xfa\x1a\x9c\x3f\xc5\x6d\x4e\x2d\x17\xe4"
    "\x0d\xd6\x68\x16\x72\x60\x69\x58\x80\x8e\x2d\x75\x5c\x49\xf5\x92\xaa\x97"
    "\x1c\xaf\x8f\x88\xc5\x80\xe6\xe4\xd2\xf5\x6d\x47";
#endif
#pragma clang diagnostic pop
  
  // Create a group of libdispatch jobs to process a chunk of words at a time
  dispatch_queue_t queue =
    dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0);
  dispatch_group_t group = dispatch_group_create();
  
  __block int done = 0;
       
  for (int i = 0; i < wordcount; i += 1000)
  { 
    int startidx = i;
    int stopidx = min(i + 999, wordcount - 1);
    
    dispatch_group_async(group, queue, ^() {
      if (done) return;
      
      printf("Trying %s ... %s\n", wordlist[startidx], wordlist[stopidx]);
      
      for (int j = startidx; j <= stopidx; j ++)
      {
        if (done) return;
        
        char *password = wordlist[j];
        
        uint8_t hmacKey[64];
        uint8_t aesKey[32];
        uint8_t plaintext[43]; // 36 for target ciphertext
        
        DeriveHMACKey(hmacKey, password, salt);
        DeriveAESKey(aesKey, hmacKey);
        Decrypt(plaintext, ciphertext, sizeof(plaintext), aesKey, nonce);
        if (Verify(hmac, hmacKey, plaintext, sizeof(plaintext)))
        {
          printf("Found password: %s\n", password);
          done = 1;
          break;
        }
      }
      
    });
  }
  
  dispatch_group_notify(group, queue, ^{
    printf("Done, exiting.\n");
    dispatch_release(group);
    exit(0);
  });
  
  dispatch_main();
  return 0;
}