GitS 2012 Teaser AL’s Revenge

Category: reverse, crypto
Summary: LLVM bytecode with polynomial inversion
file

$ file 49dd327824d5afe9cdf931ea4b13719f.bin 
49dd327824d5afe9cdf931ea4b13719f.bin: XZ compressed data
$ mv 49dd327824d5afe9cdf931ea4b13719f.bin task.xz
$ xz -d task.xz
$ file task
task: LLVM bitcode

After some searching on what to do with LLVM you can find llmvc: llvm compiler, which produces executable binary:

$ mv task task.ll
$ llvmc task.ll 
$ ./a.out 
./a.out name serial

So, this is a keygen. Luckily, it’s easily catched up with hexrays:

int __cdecl main(int argc, char **argv)
{
  __int64 serial; // ST18_8@2
  const char *status; // [sp+0h] [bp-3Ch]@3
  char name[8]; // [sp+20h] [bp-1Ch]@1
  int v6; // [sp+28h] [bp-14h]@5
  int v7; // [sp+2Ch] [bp-10h]@5
  char **_argv; // [sp+30h] [bp-Ch]@1
  int _argc; // [sp+34h] [bp-8h]@1
 
  _argc = argc;
  _argv = argv;
  *(_DWORD *)&name[4] = 0;
  *(_DWORD *)name = 0;
  if ( argc != 3 )
  {
    printf("%s name serial\n", *_argv);
    exit(1);
  }
  strncpy(name, _argv[1], 8u);
  serial = strtoll(_argv[2], 0, 16);
  if ( VerifySerial(*(_DWORD *)name, *(_DWORD *)&name[4], serial, HIDWORD(serial)) )
    status = "Good";
  else
    status = "Bad";
  puts(status);
  v6 = 0;
  v7 = 0;
  return 0;
}
 
bool __cdecl VerifySerial(unsigned __int64 name, unsigned __int64 serial)
{
  int v2; // eax@7
  __int64 res; // [sp+10h] [bp-24h]@1
  unsigned __int64 _serial; // [sp+20h] [bp-14h]@1
  unsigned __int64 _name; // [sp+28h] [bp-Ch]@1
 
  _name = name;
  _serial = serial;
  res = 0LL;
  if ( HIDWORD(name) & 0x80000000 )
    _name = name ^ 0xA348FCCD93AEA5A7uLL;
  if ( serial & 0x8000000000000000uLL )
    _serial = serial ^ 0xA348FCCD93AEA5A7uLL;
  while ( _serial )
  {
    if ( _serial & 1 )
      res ^= _name;
    v2 = _serial >> 1;
    HIDWORD(_serial) >>= 1;
    LODWORD(_serial) = v2;
    HIDWORD(_name) += _name >> 31;
    LODWORD(_name) = 2 * _name;
    if ( _name & 0x8000000000000000uLL )
      _name ^= 0xA348FCCD93AEA5A7uLL;
  }
  return res == 1;
}

It’s pretty straightforward. VerifySerial function is just a multiplication in GF(2**64) with a reducing polynomial 0xA348FCCD93AEA5A7.

What does that mean?

Polynomials with binary coefficents can be represented as numbers:
x^3 + x + 1 ~ 0b1011 = 0xb
Thus sum of two polynoms is just xor of the numbers.
Multiplication is a bit more complicated and is implemented like this VerifySerial function. Also, if we don’t want the product of the polynomials to have a large power, we should divide it on another polynomial (called reducing polynomial) and take a remainder.
Reducing polynomial here is 0xA348FCCD93AEA5A7.

What we need to?

So, we need to make this equation right:
name * serial = 1
Thus, serial = name ^ -1. This one can easily be calculated.

Here is keygen script.
You can also use maple, matlab, sage, etc.

$ py keygen.py leetmore
leetmore 21706047c9248eae
$ ./a.out leetmore 21706047c9248eae
Good

PS: after a while a source was posted as a hint

Leave a Reply

Your email address will not be published.