Reverse engineering, Windows internals, x86 magic, low level programming, and everything else I feel like writing about.

CrySyS SecChallenge 2020: Wait for it

Published on 02 Mar 2020

This one is a freebie; you just need to run the program, it prints the flag. Oh wait, I forgot to mention one tiny detail: it might take a REALLY long time.

Categories

Reverse Engineering

Files

Solution

As usual, let’s load the binary into IDA and look at the main function:

void __noreturn start()
{
  __int64 v0; // r10
  __int64 v1; // r9
  int v2; // er8
  __int64 v3; // rax
  char v4; // r8
  signed __int64 v5; // rax
  __int64 v6; // r10
  char buf; // [rsp+1h] [rbp-31h]

  v0 = 0LL;
  v1 = 0x80088091LL;
  while ( 1 )
  {
    v2 = 42;
    v3 = 0LL;
    do
    {
      ++v3;
      v2 = 137 * v2 - 0xFFEF * ((v1 * (unsigned __int64)(unsigned int)(137 * v2)) >> 47);
    }
    while ( 1LL << v0 != v3 );
    v4 = byte_2000[v0] ^ v2;
    qword_4008 += 20000000LL;
    buf = v4;
    v5 = sys_write(1u, &buf, 1uLL);
    v0 = v6 + 1;
    if ( v0 == 64 )
      __halt();
  }
}

We can already see a few things here:

  • v0 is our counter, and the flag is 64 chars long.

  • The flag is in byte_2000, encrypted by xor.

  • The xor key is a rolling key of 32 bits, and is rolled 1 << v0 times.

  • Worst case we must roll it 1 << (v0 % 32) times because the key is only 32 bits, and thus loops after at most that much rolls.

  • Best case we can find a shorter loop in it.

So let’s look for a loop in it:

int nextkey(int v2)
{
  return 0x89 * v2 - 0xFFEF * ((0x80088091LL * (unsigned long long)(unsigned int)(0x89 * v2)) >> 47);
}

int main()
{
  std::map<int, int> keys;
  auto key = 42;
  while(true)
  {
    if (keys.find(key) != keys.end())
      break;
    const auto next = nextkey(key);
    keys[key] = next;
    key = next;
  }
  printf("0x%zX", keys.size());
}

This outputs 0xFFEE as our loop size, which is significantly less than the maximum possible one. Now all we need to do is only do the loop (1 << v0) % 0xFFEE times, and print the results:

unsigned char byte_2000[] = {
  0x19, 0x72, 0x74, 0xF0, 0x35, 0x52, 0xD3, 0x88, 0x0C, 0x28, 0xF3, 0x32,
  0x87, 0x0D, 0xD9, 0x10, 0x59, 0x2F, 0x87, 0xF3, 0xB4, 0x96, 0xF5, 0xDA,
  0x49, 0xB9, 0x8A, 0x20, 0xF0, 0x18, 0x90, 0x30, 0xC5, 0x89, 0x4C, 0x03,
  0x50, 0x6D, 0x08, 0xF1, 0xB3, 0xBC, 0x5B, 0x36, 0xB3, 0x0D, 0xC2, 0x0F,
  0x28, 0x25, 0x62, 0x8E, 0x37, 0x31, 0xA0, 0xEE, 0x39, 0xF0, 0x95, 0x50,
  0xFA, 0xCC, 0x89, 0x86
};

int calckey(int v0)
{
  const auto count = (1ULL << v0) % 0xFFEE;
  auto v2 = 42;
  for(auto v3 = 0ULL; count != v3; ++v3)
    v2 = nextkey(v2);
  return v2;
}

int main()
{
  for (auto i = 0; i < 64; ++i)
    printf("%c", byte_2000[i] ^ (uint8_t)calckey(i));
  return 0;
}

Output:

cd20{L3g3n___w41t_f0r_17______DAA4A444RRRYyYyYyYyYy!!!I!I!I!I!}

related posts