/*
* crypt.c
* Known plaintext attack on the worm's stream cipher
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM_BYTES  50
/* #define RAND_KEY   1 */

#define MUL      0x39906773uL
#define MUL_INV  0x66d815bbuL
#define MASK     0xffffffffuL
#define MOD      0xffffu

unsigned char bytes[NUM_BYTES];

void get_data(void)
{
  int i;
  unsigned long state, key[4];

#if RAND_KEY
  srand(time(NULL));
  for (i = 0; i < 4; i++)
    key[i] = (((unsigned long) rand() << 17)
        ^ ((unsigned long) rand() << 9) ^ rand()) & MASK;
#else
  /* use the worm's key */
  key[0] = 0x78912389uL;
  key[1] = 0x94e7bc43uL;
  key[2] = 0xba5de30buL;
  key[3] = 0x7bc54da7uL;
#endif

  state = (((key[0] + key[1]) * key[2]) & MASK) ^ key[3];
  for (i = 0; i < NUM_BYTES; i++) {
    state  = (((state * MUL) & MASK) % MOD) >> 1;
    state += i + key[i&3];
    state  = (((state * MUL) & MASK) % MOD) >> 1;
    bytes[i] = state & 0xff;
  }

  printf("Actual values\n");
  state  = (((key[0] + key[1]) * key[2]) & MASK) ^ key[3];
  state  = (((state * MUL) & MASK) % MOD) >> 1;
  state += key[0];
  state  = (((state * MUL) & MASK) % MOD) >> 1;
  printf("x[1]=%04lx\n", state);
  for (i = 0; i < 4; i++) {
    state = (key[i] * MUL) & MASK;
    printf("key[%d]=%08lx  k=%04lx  u=%08lx\n",
        i, key[i], state % MOD, MASK - state);
  }
} /* get_data */

struct key_info {
  unsigned short key[4];
};

int good_key(int pos, unsigned key)
{
  int i, j, changed, good, want1, want2, byte;
  unsigned long lo, hi, newlo, newhi, x, y, z;

  lo = 0;
  hi = MASK;
  do {
    changed = 0;

    for (i = (pos ? pos : 4); i < NUM_BYTES; i += 4) {
      x = (bytes[i-1] * MUL) & MASK;
      want1 = bytes[i];
      want2 = (want1 + 1) & 0xff;
      good  = 0;
      newlo = MASK;
      newhi = 0;

      for (j = 0; j < 0x80; j++) {
        y = (x & 0xffffu) + (x >> 16);  /* y = x % 0xffff, nearly */
        while (y >= MOD) y -= MOD;
        y = (((y >> 1) + i) * MUL) & MASK;
        z = (y & 0xffffu) + (y >> 16) + key;  /* 0..0x2fffc */
        z = (z & 0xffffu) + (z >> 16);        /* 0..0x10000 */
        if (z >= MOD) z -= MOD;
        byte = (z >> 1) & 0xff;

        if (z & 1) {
          if (byte == want1) {
            newlo = 0;
            newhi = MASK;
            good  = 1;
          }
        }
        else {
          if (byte == want1 && y <= hi) {
            if (newlo > y) newlo = y;
            newhi = MASK;
            good  = 1;
          }
          else if (byte == want2 && y > lo) {
            if (newhi <= y) newhi = y - 1;
            newlo = 0;
            good  = 1;
          }
        }

        x = (x + (MUL<<8)) & MASK;
      } /* for j */

      if (!good) return 0;
      if (lo < newlo) { lo = newlo; changed = 1; }
      if (hi > newhi) { hi = newhi; changed = 1; }
    } /* for i */
  } while (changed);

  return 1;
} /* good_key */

int good_set(int pos, struct key_info *key)
{
  int i, j, k, good, bit, byte, kstop;
  unsigned x, y;

  for (i = pos; i < NUM_BYTES; i += 4) {
    x = (bytes[i-1] * MUL) & MASK;
    good = 0;
    kstop = 4 - pos;
    if (i + kstop > NUM_BYTES) kstop = NUM_BYTES - i;

    for (j = 0; j < 0x80; j++) {
      y = (x & 0xffffu) + (x >> 16);
      while (y >= MOD) y -= MOD;
      y = (((y >> 1) + i) * MUL) & MASK;
      y = (y & 0xffffu) + (y >> 16) + key->key[pos];
      y = (y & 0xffffu) + (y >> 16);
      if (y >= MOD) y -= MOD;
      bit = y & 1;
      y >>= 1;
      byte = bytes[i];
      if (bit == 0 && ((y-1)&0xff) == byte)
        y = (y - 1) & 0x7fff;

      if ((y&0xff) == byte) {
        for (k = 1; k < kstop; k++) {
          y = (y * MUL) & MASK;
          y = (y & 0xffffu) + (y >> 16);
          while (y >= MOD) y -= MOD;
          y = (((y >> 1) + i + k) * MUL) & MASK;
          y = (y & 0xffffu) + (y >> 16) + key->key[pos+k];
          y = (y & 0xffffu) + (y >> 16);
          if (y >= MOD) y -= MOD;
          bit = y & 1;
          y >>= 1;
          byte = bytes[i+k];
          if (bit == 0 && ((y-1)&0xff) == byte)
            y = (y - 1) & 0x7fff;
          if ((y&0xff) != byte) break;
        } /* for k */
        if (k >= kstop) { good = 1; break; }
      }

      x = (x + (MUL<<8)) & MASK;
    } /* for j */

    if (!good) return 0;
  } /* for i */

  return 1;
} /* good_set */

void check_sequence(struct key_info *key)
{
  int seed, i, pos, bit, byte, want;
  unsigned long state, add, lo[4], hi[4];

  for (seed = 0; seed < 0x80; seed++) {
    state = bytes[0] | (seed << 8);
    for (i = 0; i < 4; i++) {
      lo[i] = 0;
      hi[i] = MASK;
    }

    for (i = 1; i < NUM_BYTES; i++) {
      state = (state * MUL) & MASK;
      state = (state & 0xffffuL) + (state >> 16);
      while (state >= MOD) state -= MOD;
      state = add = (((state >> 1) + i) * MUL) & MASK;
      pos = i & 3;
      state = (state & 0xffffuL) + (state >> 16) + key->key[pos];
      state = (state & 0xffffuL) + (state >> 16);
      if (state >= MOD) state -= MOD;
      bit = state & 1;
      state >>= 1;

      byte = state & 0xff;
      want = bytes[i];
      if (bit) {
        if (byte != want)
          break;
      }
      else {
        if (byte == want && add <= hi[pos]) {
          if (lo[pos] < add) lo[pos] = add;
        }
        else if ( ((byte - 1) & 0xff) == want && add > lo[pos] ) {
          if (hi[pos] >= add) hi[pos] = add - 1;
          state = (state - 1) & 0x7fff;
        }
        else
          break;
      }
    } /* for i */

    if (i >= NUM_BYTES) {
      printf("x[1]=%04x\n", bytes[0] | (seed<<8));
      for (i = 0; i < 4; i++) {
        printf("k[%d]=%04x  min=%08lx  max=%08lx\n", i, key->key[i],
            lo[i], hi[i]);
      }
    }
  } /* for seed */
} /* check_sequence */

void guess_key(void)
{
  int pos, i;
  int num_old, num_new, max_old, max_new;
  unsigned key;
  struct key_info *new_keys, *old_keys, *temp_keys;

  max_new = 100;
  max_old = 100;
  new_keys = malloc(sizeof(struct key_info)*max_new);
  old_keys = malloc(sizeof(struct key_info)*max_old);
  if (new_keys == NULL || old_keys == NULL) {
    printf("Memory allocation failed\n");
    exit(1);
  }
  num_old = 1;

  for (pos = 3; pos >= 1; pos--) {
    num_new = 0;

    for (key = 0; key < MOD; key++) {
      if (good_key(pos, key)) {
        for (i = 0; i < num_old; i++) {
          old_keys[i].key[pos] = key;
          if (pos == 3 || good_set(pos, &old_keys[i])) {
            if (num_new >= max_new) {
              max_new += 100;
              new_keys = realloc(new_keys, sizeof(struct key_info)*max_new);
              if (new_keys == NULL) {
                printf("Memory allocation failed\n");
                exit(1);
              }
            }
            new_keys[num_new] = old_keys[i];
            num_new++;
          }
        } /* for i */
      }
    } /* for k */

    printf("%d possibilit%s for k[%d]\n", num_new,
        (num_new == 1 ? "y" : "ies"), pos);

    num_old = num_new;
    i = max_old; max_old = max_new; max_new = i;
    temp_keys = old_keys; old_keys = new_keys; new_keys = temp_keys;
  } /* for pos */

  free(new_keys);

  for (key = 0; key < MOD; key++) {
    if (good_key(0, key)) {
      for (i = 0; i < num_old; i++) {
        old_keys[i].key[0] = key;
        check_sequence(&old_keys[i]);
      } /* for i */
    }
  } /* for key */

  free(old_keys);
} /* guess_key */

int main()
{
  get_data();
  guess_key();
  return 0;
} /* main */

/* end crypt.c */