/*
 * my attempt at writing a zip knownplaintext decryptor
 *
 * by W.J.Hengeveld  sep 1995
 *    itsme@xs4all.nl
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define DATALEN   128
#define MAXPADLEN  16
#define CRYPTHDR   12

#define FALSE  0
#define TRUE   1

#define FACTOR      134775813L
#define INVFACTOR  3645876429L

struct zipHeader {
  long sig;            // == 0x04034b50      // 00
  int  version;                              // 04
  int  flags;                                // 06
  int  method;                               // 08
  long datetime;                             // 0a
  long crc32;                                // 0e
  long storedSize;                           // 12
  long fileSize;                             // 16
  int  nameLength;                           // 1a
  int  extraLength;                          // 1c
  char filename[1];    // nameLength bytes followed by extraLength bytes
};

// 12 bytes of random padding before crypt file
//    the 12th random byte == MSB of crc32

int verbose=0;

void dump(u_char *s,int n)
{
  int i,j;
  for (i=0 ; i<n ; i+=16)
  {
    printf("%04x : ", i);
    for (j=0 ; j<16 ; j++)
      if (i+j>=n)
        printf("   ");
      else
        printf("%02x ",s[i+j]);
    printf(" - ");
    for (j=0 ; j<16 ; j++)
      if (i+j>=n)
        putchar(' ');
      else
        if ((s[i+j]&0x7f)<' ')
          putchar('.');
        else
          putchar(s[i+j]);
    putchar('\n');
  }
}

ulong crc32tab[256];
ulong invcrc32tab[256];

// 256 * 64 words, for each key3 value the corresponding 14 bits of key2
u_short **key2tab;

int init_key2tab(void)
{
   int i;
   int len[256];
   u_char key3;
   printf("Initializing key2 tab ");
   memset(len, 0, 256*sizeof(int));

   key2tab = (u_short**)malloc(sizeof(u_short*)*256);
   if (key2tab==NULL)
   {
      printf("Out of memory in  init_key2tab\n");
      return 1;
   }
   for (i=0; i<256; i++)
   {
      key2tab[i] = (u_short*)malloc(sizeof(u_short)*64);
      if (key2tab[i]==NULL)
      {
         printf("Out of memory in  init_key2tab\n");
         return 1;
      }
   }
   printf("- alloced ");
   i=0;
   do
   {
      key3 = ((i+3)*(i+2))>>8;
      key2tab[key3][len[key3]++]=i;
      i+=4;
   } while (i);
   printf("- done\n");
   return 0;
}

// to find a match between (K-1)*INVFACTOR & L
//   start at  key1tab[(k*51)&0xff]
int *key1tab;

int init_key1tab(void)
{
   ulong calc;
   int i;

   key1tab=(int*)malloc(256*sizeof(int));
   if (key1tab==NULL)
   {
      printf("Out of memory in  init_key2tab\n");
      return 1;
   }
   memset(key1tab, -1, sizeof(int)*256);
   calc=-1*INVFACTOR;
   for (i=0 ; i<256 ; i++)
   {
      if (key1tab[calc>>24]==-1)
         key1tab[calc>>24]=i;
      calc+=INVFACTOR;
   }
   return 0;
}

ulong calccrc32tab(u_char c)
{
   ulong val = c;
   int i;
   for (i=0 ; i<8 ; i++)
   {
      if (val&1)
        val = (val>>1)^0xEDB88320L;
      else
        val = (val>>1);
   }
   return val;
}

void initcrc(void)
{
   ulong val;
   int i;
   if (verbose)
      printf("initializing crc tabs ");
   for (i=0 ; i<256 ; i++)
   {
      val = calccrc32tab(i);
      crc32tab[i]=val;
      invcrc32tab[(int)(val>>24)] = (val<<8) ^ i;
   }
   if (verbose)
      printf("- done\n");
}

ulong crc32(ulong prev, u_char c)
{
   return (prev>>8) ^ crc32tab[(int)((prev&0xff)^c)];
}

ulong invcrc32(ulong crc, u_char c)
{
   return (crc<<8)^invcrc32tab[(int)(crc>>24)]^c;
}

// these are local to recurse_key2 & crackzip
u_char *key3List;
ulong *key2List;
u_short **key2List_14;    // lists of 64 values for bits 16-2
ulong *key1List;
ulong *key0List;
u_char *plainText;

int  listLen;
ulong key1_start=0;   // for debugging
ulong key2_start=0;   // for debugging

// key0[n-1] = invcrc32(key0[n], plain[n-1])
// key0[n] = crc32(key0[n-1], plain[n-1])
void calckey0(int n)
{
   ulong crctab1;
   ulong crctab2;
   ulong crctab3;

   // key0[n+4] = key0[n+3] ^ crctab1
   crctab1 = crc32tab[(int)((key0List[n+3]&0xff)^plainText[n+3])];
   key0List[n+4]   |= crctab1 & 0xff000000L;
   key0List[n+3] |= ((crctab1^key0List[n+4])&0xff)<<8;

   // key0[n+3] = key0[n+2] ^ crctab2
   crctab2 = crc32tab[(int)((key0List[n+2]&0xff)^plainText[n+2])];
   key0List[n+3]   |= crctab2 & 0xff000000L;
   key0List[n+2] |= ((crctab2^key0List[n+3])&0xffff)<<8;

   // key0[n+2] = key0[n+1] ^ crctab3
   crctab3 = crc32tab[(int)((key0List[n+1]&0xff)^plainText[n+1])];
   key0List[n+2]   |= crctab3 & 0xff000000L;
   key0List[n+1] |= ((crctab3^key0List[n+2])&0xffffffL)<<8;

   key0List[n+3] = (key0List[n+2]>>8) ^ crctab2;
   key0List[n+4] = (key0List[n+3]>>8) ^ crctab1;
}

int checkkey0(int n)
{
   ulong calcedk0;

   calcedk0 = invcrc32(key0List[n+2], plainText[n+1]);
   if ((key0List[n+1]&0xff)!=(calcedk0&0xff))
      return 1;

   key0List[n+1]=calcedk0;
   return 0;
}

void recurse_key1(int n)
{
   ulong calcedn_1;
   int   i;
   ulong key_n;
   ulong match;
   int  tryone;

   if (n==0)
   {
      printf("%08lx %08lx %08lx\n", key0List[listLen-1], key1List[listLen-1], key2List[listLen-1]);
      return;
   }
   key_n = key1List[n];                  //  key(n) + LSBk0[n+1]
   match = key1List[n-1] & 0xff000000L;
//
// misschien: i=invcrc32(key0List[n+2], plainText[n+1])&0xff;
//    (als  2<n<ListLen-5 )
//
   if (2<n && n<listLen-5)
   {
      i=(int)invcrc32(key0List[n+2], plainText[n+1])&0xff;
      tryone=TRUE;
      key_n -= i;
   }
   else
   {
      i=0;
      tryone=FALSE;
   }

   calcedn_1 = key_n*3645876429L;   // == LSBk0[n] + key(n-1)
   do   // only loop when n>listLen-4
   {
      key_n--;
      calcedn_1 -= INVFACTOR;   // == LSBk0[n] + key(n-1)

      if ((calcedn_1 & 0xff000000L)==match
          || ((calcedn_1-255)&0xff000000L)==match)
      {
         key0List[n+1] = i;
         if (n+4==listLen-1)
            calckey0(n);
         if (n+4<listLen-1 && n>2)
            if (checkkey0(n))  // check & set key0List[n+1] from n+2 value
               continue;

         key1List[n-1] = calcedn_1;
         key1List[n]   = key_n+1;         // current value : 32 bits known
         recurse_key1(n-1);
      }
   } while (!tryone && ++i<256);
}

void do_key1(void)
{
   int  n = listLen-1;
   ulong key_n;
   ulong match;
   long  l;
   ulong calcedn_1;

   key_n = (key1List[n] & 0xff000000L)|key1_start;
   match = key1List[n-1] & 0xff000000L;

// this can be done stepping with  0xe1  and  0x56 !!!
// - try  +0x56 -> try +0xe1, +0x137
// - try +0x137 -> try +0x56, +0x137
// +56, +e1
// +56, +137 +137
// +56, +137 +137 +137
//
//  0x56*3645876429L =  0x4900c2b4de
// 0x137*3645876429L = 0x107ffc6110b
//                          ^^

   for (l=0 ; l<0x1000000L ; l++)
   {
      if ((l%0x1000)==0) printf("\rkey1 - %08lx\r", key_n);
      calcedn_1 = (key_n-1)*INVFACTOR;   // == key(n-1) + LSBk0[n]

      if ((calcedn_1 & 0xff000000L)==match
          || ((calcedn_1-255)&0xff000000L)==match)
      {
         key1List[n-1] = calcedn_1;   // now bits23-8 are known approx
         key1List[n] = key_n;         // current value
         recurse_key1(n-1);
      }
      key_n++;
      if (key1_start) break;
   }
}

void recurse_key2(int i)
{
   ulong calcedPrev;
   u_short  match;
   int  k;
   ulong bit10;

   if (i==0)
   {
      do_key1();
      return;
   }

   calcedPrev = invcrc32(key2List[i], 0);
// now find a key2[i-2] for which  bits 15-10 are equal
   match = calcedPrev&0xfc00;
   calcedPrev &= 0xffff0000L;   // bits to copy to key2

   for (k=0 ; k<64 ; k++)
   {
      if ((key2List_14[i-1][k]&0xfc00)==match)
      {
        key2List[i-1] = calcedPrev | key2List_14[i-1][k];
        key2List[i] &=~3;
        bit10 = invcrc32(key2List[i], 0)^key2List[i-1];
        key2List[i] = key2List[i]|((bit10>>8)&3);
        if (i+1<listLen)
           key1List[i+1]=invcrc32(key2List[i+1], key2List[i])<<24;
        recurse_key2(i-1);
      }
   }
}

void do_key2(int n)
{
   int  i;                // index in key3List
   ulong *pKey2;

   pKey2 = &key2List[n];
   key2List[n]=key2_start<<16;
   do {
      printf("\rkey2 - %08lx\r", *pKey2);
      for (i=0 ; i<64 ; i++)
      {
// set LSW
         *pKey2 = (*pKey2 & 0xffff0000L)|key2List_14[n][i];
         recurse_key2(n);
      }
      *pKey2+=0x10000L;   // try next
      if (key2_start) break;
   } while (*pKey2&0xffff0000L);
}

// calculates <keys> from plaintext & ciphertext
int crackzip(ulong *keys, int len, u_char *plaintext, u_char *ciphertext)
{
   int  i;                // index in key3List

   key3List=(u_char*)alloca(sizeof(u_char)*len);
   key2List=(ulong*)alloca(sizeof(ulong)*len);
   key1List=(ulong*)alloca(sizeof(ulong)*len);
   key0List=(ulong*)alloca(sizeof(ulong)*len);

   key2List_14=(u_short**)alloca(sizeof(u_short*)*len);

   listLen = len;         // set global
   plainText = plaintext; // set global

   if (key0List==NULL || key1List==NULL || key2List==NULL || key3List==NULL
       || key2List_14==NULL)
   {
      printf("Out of stack space in crackzip\n");
      return 1;
   }
   for(i=0 ; i<len ; i++)
   {
      key3List[i]=plaintext[i] ^ ciphertext[i];
      key2List_14[i]=key2tab[key3List[i]];
   }
   memset(key2List,0,sizeof(ulong)*len);
   memset(key1List,0,sizeof(ulong)*len);
   memset(key0List,0,sizeof(ulong)*len);
   do_key2(len-1);

// calc back keys, to n=0
   return 0;
}

// 134775813 = 3 * 17 * 131 * 20173
// 3645876429= 3^2 * 13 * 1607 * 19391
// 134775813 * x = k * 2^32 + 1
// 134775813 * 649090867 = 2^32 * 20368432 - 1
// 134775813 * 649090867 = 2^32 * 20368432 - 1
// 134775813 * 3645876429 = 1 + 2^32 * 114407381
void update_keys(ulong *keys, u_char c)
{
   u_short temp;
   keys[0]=crc32(keys[0], c);
   keys[1]=(keys[1]+(keys[0]&0xff))*FACTOR+ 1;
   keys[2]=crc32(keys[2], keys[1]>>24);
   temp = keys[2]|3;
   keys[3]=((temp*(temp^1))>>8)&0xff;
   if (verbose>1)
      printf("update keys(%02x) : %08lx %08lx %08lx %02lx\n",
         c, keys[0], keys[1], keys[2], keys[3]);
}

u_char calcback_keys(ulong *keys, u_char cipher)
{
   u_short temp;
   u_char plain;
   keys[2] = invcrc32(keys[2], keys[1]>>24);
   keys[1] = (keys[1]-1)*INVFACTOR - (keys[0]&0xff);
   temp = keys[2]|3;
   keys[3] = ((temp*(temp-1))>>8)&0xff;
   plain = cipher^keys[3];
   keys[0] = invcrc32(keys[0],plain);
   return plain;
}

void initialize_keys(u_char *password, ulong *keys)
{
   keys[0]=0x12345678L;
   keys[1]=0x23456789L;
   keys[2]=0x34567890L;
   while (*password) update_keys(keys, *password++);
   if (verbose)
      printf("initialized keys\n");
}

void zipencrypt(ulong *keys, int len, u_char *plaintext, u_char *ciphertext)
{
   if (verbose)
      printf("start encrypting\n");
   while (len--)
   {
     *ciphertext++ = *plaintext ^ keys[3];
     update_keys(keys, *plaintext++);
   }
   if (verbose)
      printf("done encrypting\n");
}

void decrypt(ulong *keys, int len, u_char *ciphertext, u_char *plaintext)
{
   if (verbose)
      printf("start decrypting\n");
   while (len--)
   {
      *plaintext = *ciphertext++ ^ keys[3];
      update_keys(keys, *plaintext++);
   }
   if (verbose)
      printf("done decrypting\n");
}

int htob(char c)
{
  if (c>='0' && c<='9') return(c-'0');
  if (c>='a' && c<='f') return(c-'a'+10);
  if (c>='A' && c<='F') return(c-'A'+10);
  return(0);
}

// convert hex ascii data to binary, returns # bytes stored
int asciiHexToBin(u_char *p, char *s)
{
  int n=0;
  while (s[0] && s[1])
  {
    *p=(u_char)(htob(*s++)<<4);
    *p++ |= htob(*s++);
    n++;
  }
  return(n);
}

void cleanup(void)
{
   int i;
   if (key1tab) { free(key1tab); key1tab=NULL; }
   if (key2tab)
   {
      for (i=0 ; i<256 ; i++)
         if (key2tab[i]) { free(key2tab[i]); key2tab[i]=NULL; }
      free(key2tab);
      key2tab=NULL;
   }
}

void usage(void)
{
   printf("Usage: zippw [options] [cipherfile] [plaintextfile] [pad bytes]\n");
   printf("   -c  : crack\n");
   printf("   -d  : decrypt\n");
   printf("   -e  : encrypt\n");
   printf("   -i  : calculate inverse CRC\n");
   printf("   -knX: set initial values for key1 & key2 search\n");
   printf("   -l  : plaintext length for cracking\n");
   printf("   -oXX  : specify starting offset in file\n");
   printf("   -pSS  : specify password\n");
   printf("   -r  : calculate CRC\n");
   printf("   -t  : print crcTab entry\n");
   printf("   -v  : verbose\n");
}

#define DO_ENCRYPT 1
#define DO_DECRYPT 2
#define DO_CRACK   4
#define DO_CRC     8
#define DO_INVCRC 16
#define DO_CRCTAB 32

void main(int argc, char **argv)
{
   int i;
   int actionFlags=0;
   char *cipFile=NULL;    // ciphertext file
   char *plnFile=NULL;    // plaintext file

   int  f;
   long offset=0;
   char *password=NULL;
   ulong keys[4];
   u_char  cipherData[DATALEN+CRYPTHDR];
   u_char  plainData[DATALEN+CRYPTHDR];
   int   nRc;
   int   padIndex=0;
   u_char  pad[MAXPADLEN];
   ulong a;
   u_char  b;
   int   dataLen=-1;

   memset(pad, 0, MAXPADLEN);

   atexit(cleanup);

   for (i=1 ; i<argc ; i++)
   {
      if (argv[i][0]=='-')
         switch(argv[i][1])
         {
            case 'c': actionFlags|=DO_CRACK;   break;
            case 'd': actionFlags|=DO_DECRYPT; break;
            case 'e': actionFlags|=DO_ENCRYPT; break;
            case 'i': actionFlags|=DO_INVCRC;    break;
            case 'k':
               switch(argv[i][2])
               {
                  case '1': key1_start = strtol(argv[i]+3, 0, 16); break;
                  case '2': key2_start = strtol(argv[i]+3, 0, 16); break;
               }
               break;
            case 'l': dataLen=atoi(argv[i]+2);    break;
            case 'o': offset = strtol(argv[i]+2, 0, 16); break;
            case 'p': password = argv[i]+2; break;
            case 'r': actionFlags|=DO_CRC;       break;
            case 't': actionFlags|=DO_CRCTAB;    break;
            case 'v': verbose++; break;
            default:
              printf("Invalid Option: %s\n", argv[i]);
              usage();
              exit(1);
         }
      else if (cipFile==NULL && (actionFlags&(DO_CRACK|DO_DECRYPT)))
         cipFile=argv[i];
      else if (plnFile==NULL && (actionFlags&(DO_CRACK|DO_ENCRYPT)))
         plnFile=argv[i];
      else
      {
         padIndex+=asciiHexToBin(pad+padIndex, argv[i]);
      }
   }
   if (cipFile==NULL && (actionFlags&(DO_CRACK|DO_DECRYPT)))
   {
      printf("No cipher textfile specified\n");
      usage();
      exit(1);
   }
   if (plnFile==NULL && (actionFlags&(DO_CRACK|DO_ENCRYPT)))
   {
      printf("No plain text file specified\n");
      usage();
      exit(1);
   }
   if (password && actionFlags&DO_CRACK)
   {
      printf("Password specified with crack option\n");
      usage();
      exit(1);
   }
   if (password==NULL && actionFlags&(DO_ENCRYPT|DO_DECRYPT))
   {
      printf("No password specified with en/decrypt option\n");
      usage();
      exit(1);
   }
   if ((actionFlags&(DO_ENCRYPT|DO_DECRYPT)) == (DO_ENCRYPT|DO_DECRYPT))
   {
      printf("cannot specify both encrypt & decrypt options\n");
      usage();
      exit(1);
   }
   if (actionFlags&(DO_CRC|DO_INVCRC) && padIndex<5)
   {
      printf("need at least 5 bytes of data with crc functions\n");
      usage();
      exit(1);
   }
   if (cipFile)
   {
      f=open(cipFile, O_RDONLY);
      if (f<0)
      {
         perror(cipFile);
         exit(1);
      }
      lseek(f, offset, SEEK_SET);
      nRc=read(f, cipherData, DATALEN);
      if (nRc==EOF)
      {
         close(f);
         perror(cipFile);
         exit(1);
      }
      close(f);
   }
   if (plnFile)
   {
      f=open(plnFile, O_RDONLY);
      if (f<0)
      {
         perror(plnFile);
         exit(1);
      }
      lseek(f, offset, SEEK_SET);
      nRc=read(f, plainData, DATALEN);
      if (nRc==EOF)
      {
         close(f);
         perror(plnFile);
         exit(1);
      }
      close(f);
   }
   if (actionFlags&DO_ENCRYPT)
   {
      memmove(plainData+CRYPTHDR, plainData, DATALEN-CRYPTHDR);
      memcpy(plainData, pad, CRYPTHDR);
   }
   if (dataLen==-1) dataLen=16;

   initcrc();
   if (actionFlags & DO_CRACK)
      init_key2tab();
   else
      initialize_keys((u_char*)password, keys);

   if (actionFlags&DO_ENCRYPT)
   {
      if (verbose)
      {
         printf("plain text data:\n");
         dump(plainData, DATALEN);
      }
      zipencrypt(keys, DATALEN, plainData, cipherData);
      if (verbose)
      {
         printf("cipher text data:\n");
         dump(cipherData, DATALEN);
      }
   }
   else if (actionFlags&DO_DECRYPT)
   {
      if (verbose)
      {
         printf("cipher text data:\n");
         dump(cipherData, DATALEN);
      }
      decrypt(keys, DATALEN, cipherData, plainData);
      if (verbose)
      {
         printf("plain text data:\n");
         dump(plainData, DATALEN);
      }
   }
   else if (actionFlags&DO_CRACK)
   {
      crackzip(keys, dataLen, plainData, cipherData);
   }
   else if (actionFlags&DO_CRC)
   {
      a=pad[0];
      a=(a<<8)|pad[1];
      a=(a<<8)|pad[2];
      a=(a<<8)|pad[3];
      b=pad[4];
      printf("crc32(%08lx, %02x) = %08lx\n", a, b, crc32(a,b));
   }
   else if (actionFlags&DO_INVCRC)
   {
      a=pad[0];
      a=(a<<8)|pad[1];
      a=(a<<8)|pad[2];
      a=(a<<8)|pad[3];
      b=pad[4];
      printf("invcrc32(%08lx, %02x) = %08lx\n", a, b, invcrc32(a,b));
   }
   else if (actionFlags&DO_CRCTAB)
   {
      b=pad[0];
      printf(" %02x -> crctab = %08lx  invcrctab = %08lx\n", b,
          crc32tab[b], invcrc32tab[b]);
   }
}