PlaidCTF2014 Write Up: g++ (Reversing200)

Tantangan reversing kali ini agak unik karena bukan mereverse binary, tapi source code sebuah file C++. Source codenya menggunakan template dan macro secara ekstensif. Saya tidak akan membahas sampai detail, hanya beberapa point penting saja. Nama file yang diberikan adalah solveme.cpp dengan Makefile yang akan menghasilkan file key.h. Dibutuhkan waktu beberapa detik untuk mengkompilasi file ini, karena compiler perlu menjalankan template untuk menghasilkan program statik (jadi kita tidak bisa menghack binary-nya). Untuk bisa memahami program ini, saya mengekspansi dulu makronya dengan g++ –E

g++ –E solveme.cpp > expanded.cpp

Di titik itu, kode masih cukup sulit dipahami, tapi ada bagian yang cukup penting, yang mengakses keynya cuma template “r” ini:

template <int a, int b>
struct r { 
  static const int rr = d<g<((a)<<2)>::r,g<((a)<<2)+1>::r,g<((a)<<2)+(1<<1)>::r,g<((a)<<2)+(1<<1)|1>::r,key<b>::r,key<b+1 +1 +1 +1>::r,key<b+1 +1 +1 +1 +1 +1 +1 +1>::r,key<b+1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1>::r>::r;
};

Template r ini cuma dipakai di satu tempat untuk mengurangi sebuah nilai di kiri:

template <int n>
struct gg {  static const int r = (m<((u<n,n|2>::r)),(((1<<(1<<3))|1)),(((1<<(1<<3))|1))>::r) - r<(n>>2),((n)&3)>::rr;
};

Kita sederhanakan sedikit dengan menghitung konstantanya

template <int n>
struct gg { 
  static const int r = (m<((u<n,n|2>::r)),257,257>::r) - r<(n>>2),((n)&3)>::rr;
};

Di titik ini, field r dihitung dengan mengurangi bagian sisi kiri dengan sisi kanan (di bagian program berikutnya bisa dipahami ini harus 0). Template sisi kiri ini konstan terhadap key, jadi bisa diprint satu per satu. Hasilnya adalah konstanta ini:

{15, 25, 172, 31, 100, 17, 225, 137, 162, 71, 187, 191, 11, 105, 176, 94};

Berbagai penyederhanaan lain dilakukan. Yang paling banyak berpengaruh adalah template n yang ternyata hanya menghitung a-b, a+b, dan operasi identitas, semuanya secara rekursif. Setelah ini ditulis ulang, semuanya jadi lebih jelas. Di akhir, saya mendapatkan persamaan linear dengan modulo seperti ini:

( (k_12*202 -   68*k_4  ) -    ( k_8*87 -  13*k_0)  ) mod 257 = 15
( (k_13*202 -   68*k_5  ) -    ( k_9*87 -  13*k_1)  ) mod 257 = 25
( (k_14*202 -   68*k_6  ) -    ( k_10*87 -  13*k_2)  ) mod 257 = 172
( (k_15*202 -   68*k_7  ) -    ( k_11*87 -  13*k_3)  ) mod 257 = 31
( (k_12*122 -   244*k_4  ) -    ( k_8*71 -  29*k_0)  ) mod 257 = 100
( (k_13*122 -   244*k_5  ) -    ( k_9*71 -  29*k_1)  ) mod 257 = 17
( (k_14*122 -   244*k_6  ) -    ( k_10*71 -  29*k_2)  ) mod 257 = 225
( (k_15*122 -   244*k_7  ) -    ( k_11*71 -  29*k_3)  ) mod 257 = 137
( (k_12*42 -   228*k_4  ) -    ( k_8*247 -  173*k_0)  ) mod 257 = 162
( (k_13*42 -   228*k_5  ) -    ( k_9*247 -  173*k_1)  ) mod 257 = 71
( (k_14*42 -   228*k_6  ) -    ( k_10*247 -  173*k_2)  ) mod 257 = 187
( (k_15*42 -   228*k_7  ) -    ( k_11*247 -  173*k_3)  ) mod 257 = 191
( (k_12*90 -   148*k_4  ) -    ( k_8*39 -  125*k_0)  ) mod 257 = 11
( (k_13*90 -   148*k_5  ) -    ( k_9*39 -  125*k_1)  ) mod 257 = 105
( (k_14*90 -   148*k_6  ) -    ( k_10*39 -  125*k_2)  ) mod 257 = 176
( (k_15*90 -   148*k_7  ) -    ( k_11*39 -  125*k_3)  ) mod 257 = 94

Sampai di titik ini saya sempat bingung bagaimana menyelesaikannya, dicoba memakai wolfram online, inputnya terlalu panjang. Ternyata ini bisa diselesaikan dengan Mathematica, dan untungnya ada versi gratisnya untuk Raspberry Pi. Dengan  menggunakan commandline wolfram, persamaan tersebut bisa diubah menjadi:

LinearSolve[{{13, 0, 0, 0, -68, 0, 0, 0, -87, 0, 0, 0, 202, 0, 0, 0},
{0, 13, 0, 0, 0, -68, 0, 0, 0, -87, 0, 0, 0, 202, 0, 0},
{0, 0, 13, 0, 0, 0, -68, 0, 0, 0, -87, 0, 0, 0, 202, 0},
{0, 0, 0, 13, 0, 0, 0, -68, 0, 0, 0, -87, 0, 0, 0, 202},
{29, 0, 0, 0, -244, 0, 0, 0, -71, 0, 0, 0, 122, 0, 0, 0},
{0, 29, 0, 0, 0, -244, 0, 0, 0, -71, 0, 0, 0, 122, 0, 0},
{0, 0, 29, 0, 0, 0, -244, 0, 0, 0, -71, 0, 0, 0, 122, 0},
{0, 0, 0, 29, 0, 0, 0, -244, 0, 0, 0, -71, 0, 0, 0, 122},
{173, 0, 0, 0, -228, 0, 0, 0, -247, 0, 0, 0, 42, 0, 0, 0},
{0, 173, 0, 0, 0, -228, 0, 0, 0, -247, 0, 0, 0, 42, 0, 0},
{0, 0, 173, 0, 0, 0, -228, 0, 0, 0, -247, 0, 0, 0, 42, 0},
{0, 0, 0, 173, 0, 0, 0, -228, 0, 0, 0, -247, 0, 0, 0, 42},
{125, 0, 0, 0, -148, 0, 0, 0, -39, 0, 0, 0, 90, 0, 0, 0},
{0, 125, 0, 0, 0, -148, 0, 0, 0, -39, 0, 0, 0, 90, 0, 0},
{0, 0, 125, 0, 0, 0, -148, 0, 0, 0, -39, 0, 0, 0, 90, 0},
{0, 0, 0, 125, 0, 0, 0, -148, 0, 0, 0, -39, 0, 0, 0, 90}
}, {15, 25, 172, 31, 100, 17, 225, 137, 162, 71, 187, 191, 11, 105, 176, 94}
, Modulus -> 257
]

Hasilnya:

{67, 43, 43, 95, 148, 209, 143, 156, 162, 149, 136, 150, 95, 67, 45, 45}

Kita coba jadikan string di python:

>>> s = [67, 43, 43, 95, 148, 209, 143, 156, 162, 149, 136, 150, 95, 67, 45, 45]
>>> [chr(x) for x in s]
['C', '+', '+', '_', '\x94', '\xd1', '\x8f', '\x9c', '\xa2', '\x95', '\x88', '\x96', '_', 'C', '-', '-']

Hasilnya depannya dan belakangnya benar, tapi tengahnya salah. Karena operasi mod 257, sebagian solusinya perlu kita kurangkan dari 257.

>>> [chr(257-x) for x in s]
['\xbe', '\xd6', '\xd6', '\xa2', 'm', '0', 'r', 'e', '_', 'l', 'y', 'k', '\xa2', '\xbe', '\xd4', '\xd4']

Ok sekarang tengahnya benar, kita bisa gabungkan:

>>> [chr(257-x) if x>95 else chr(x) for x in s]
['C', '+', '+', '_', 'm', '0', 'r', 'e', '_', 'l', 'y', 'k', '_', 'C', '-', '-']

Atau dalam bentuk string:

>>> "".join([chr(257-x) if x>95 else chr(x) for x in s])
'C++_m0re_lyk_C—'

Itulah flagnya