[ un ] theoretical

KeyGen Reverse Engineering

This was on a CTF challenge that I checked out that was pretty interesting to work on. Doing these kind of write-ups takes quite a bit but heres the jist of it. Running it produces a string in which I have to provide input within some number of seconds:

So, I have to give a timed response. Running it again:

			
modp@pop-os:~/Downloads$ ./crackme
Challenge: 79975bbd
You have 19 seconds to provide a response
modp@pop-os:~/Downloads$ ./crackme 1111111111111111
invalid response
			
			

			
undefined8 main(int param_1,long param_2)

{
  uint uVar1;
  uint uVar2;
  undefined8 uVar3;
  longlong lVar4;
  long lVar5;
  long in_FS_OFFSET;
  uint local_444;
  int local_440;
  uint local_43c;
  char *local_428;
  time_t local_420;
  undefined local_418 [1032];
  long local_10;
  
  local_10 = *(in_FS_OFFSET + 0x28);
  local_420 = time(0x0);
  lVar5 = local_420 / 0x1e;
  local_43c = 0x80000000;
  generate_table(local_418,0xedb88320);
  uVar1 = update_uint32(local_418,0,lVar5 * 0x1e);
  if (param_1 == 1) {
    printf("Challenge: %08x\n",uVar1);
    lVar5 = local_420 % 0x1e;
    printf("You have %ld seconds to provide a response\n",0x1e - lVar5,lVar5,lVar5);
    uVar3 = 0;
  }
  else {
    lVar5 = thunk_FUN_004004ce(*(param_2 + 8));
    if (lVar5 == 8) {
      lVar4 = strtol(*(param_2 + 8),&local_428,0x10);
      if (*local_428 == '\0') {
        if ((uVar1 & 1) == 0) {
          local_444 = uVar1 / 0x337 + 0xf29ab3f7 ^ 0xe341c9d9;
        }
        else {
          local_444 = uVar1 * 0x39b + 0x8a076da9 ^ 0x8b720af7;
        }
        local_440 = 0;
        while (local_440 < 0x20) {
          if (((local_444 ^ lVar4) & local_43c) != 0) {
            puts("invalid response");
            uVar3 = 0xffffffff;
            goto LAB_00400f6b;
          }
          local_43c = local_43c >> 1;
          local_440 = local_440 + 1;
        }
        if (local_444 == lVar4) {
          uVar2 = update_uint32(local_418,0,uVar1);
          uVar2 = update_uint32(local_418,uVar2,local_444,uVar2);
          puts("Congratulations, you got a flag!");
          printf("%08x%08x%08x\n",uVar1,local_444,uVar2);
        }
        uVar3 = 0;
      }
      else {
        puts("invalid response");
        uVar3 = 0xffffffff;
      }
    }
    else {
      puts("invalid response");
      uVar3 = 0xffffffff;
    }
  }
LAB_00400f6b:
  if (local_10 != *(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return uVar3;
}
			
			

So, given a seed it generates a table and feeds the user input to update():

			
void generate_table(long param_1,uint param_2)

{
  uint local_18;
  uint local_14;
  ulong local_10;
  
  local_18 = 0;
  while (local_18 < 0x100) {
    local_14 = local_18;
    local_10 = 0;
    while (local_10 < 8) {
      if ((local_14 & 1) == 0) {
        local_14 = local_14 >> 1;
      }
      else {
        local_14 = local_14 >> 1 ^ param_2;
      }
      local_10 = local_10 + 1;
    }
    *(local_18 * 4 + param_1) = local_14;
    local_18 = local_18 + 1;
  }
  return;
}

ulong update(long param_1,uint param_2,long param_3,ulong param_4)

{
  uint local_1c;
  ulong local_18;
  
  local_1c = ~param_2;
  local_18 = 0;
  while (local_18 < param_4) {
    local_1c = *(param_1 + (*(local_18 + param_3) ^ local_1c) * 4) ^ local_1c >> 8;
    local_18 = local_18 + 1;
  }
  return ~local_1c;
}
			
			

At first it gets a little bit overwhelming to look at but working through GDB, it becomes clear whats going on to where generate_table() and update() are easily reconstructed.

			
void generate_table(unsigned long *table, unsigned long seed) {
    uint32_t var = 0;
    for (int i=0; i < 256; ++i) {
        var = i;
        for (int j=0; j < 8; ++j) {
            if ((var & 1) == 0)
                var = var >> 1;
            else
                var = (var >> 1) ^ seed;
        }
        table[i] = var;
    }
}

unsigned long update_table(unsigned long *t, unsigned long n, unsigned long s, int length) {
    unsigned long si;
    unsigned long x, xl;
    unsigned long v[length];
    v[0] = 0xffffffff;
    unsigned long v_s, v_t;
    unsigned long k;
    for (int i = 0; i < length; i++) {
        si = (s >> (8*i)) & 0xff;
        xl = (si ^ v[i]);
        x = (unsigned char) (si ^ v[i]);
        k = 4 * x + i;
        v_s = v[i] >> 8;
        v[i+1] = v_s ^ t[x];
    }
    return ~v[length-1];
}

			
			

---