PlaidCTF2014 Write Up: rsa(forensic450)

Sebenarnya kami tidak berhasil menyelesaikan challenge RSA ini tepat waktu, jadi kami tidak mendapatkan poin. Tapi karena kami sudah berhasil menyelesaikan challengenya, jadi kami tuliskan pembahasannya.

Inti dari solusinya adalah berdasarkan paper: "Reconstructing RSA Private Keys from Random Key Bits"

http://cseweb.ucsd.edu/~hovav/papers/hs09.html

Ada source code yang bisa didownload di situ, tapi sourcenya perlu dimodifikasi. Berikut ini adalah modifikasi yang saya lakukan:

Program aslinya akan menghasilkan RSA key (atau membaca dari  file), merusak key tersebut, lalu merekonstruksi kembali keynya. Bagian membaca dari file diganti agar membaca bit yang tersedia dan bit yang tidak tersedia dianggap corrupt.

Saya menambahkan opsi -x <corrupted_file>. File input harus diperbaiki dulu supaya nilai modulus benar. Ini bisa didapatkan dari public key:

openssl pkey -pubin -in public.pub -text -noout
Contoh file input berdasarkan soal:

Jalankan program:

./rsa -x corrupted.pem

Hasilnya: solution0.asn

Ubah ke format der:

openssl asn1parse -genconf solution0.asn -out newkey.der

Check bahwa keynya benar, dan tuliskan ke PEM:

openssl rsa -in newkey.der -inform der -text -check > key.pem

Decrypt pesan:

openssl rsautl -decrypt -in encrypted -out plaintext.txt -inkey key.pem

Hasilnya adalah:

crypt0>>>f0rensics3~

PlaidCTF2014 Write Up: curlcore (Forensic250)

Dalam challenge ini, Kita diberi sebuah file coredump dari curl yang sedang mengakses sebuah situs https, dan sebuah file capture pcap, serta beberapa library pelengkap curl. Tadinya ingin meload file ini di gdb untuk melihat session master key, tapi ternyata meload file ini sulit dilakukan. Setelah mencari-cari di Internet, didapat link ini yang menyatakan bahwa kita bisa langsung mengekstrak dari key dari memori dengan mudah jika kita tahu session idnya:
http://www.cloudshield.com/blog/advanced-malware/how-to-decrypt-openssl-sessions-using-wireshark-and-ssl-session-identifiers/
Jadi solusinya cukup mudah: cari session id menggunakan wireshark di paket handshake, dan didapat:

19ab5edc02f097d5074890e44b483a49b083b043682993f046a55f265f11b5f4

Kemudian kita cari di curlcure nilai hex tersebut, dan kita mundur sedikit untuk mendapatkan master keynya:

191e5042e6b31371aa65258e13b2dc714d984df8d68fad678ff0a2fc49476d65c3a161f718572c3f5db8566a0de89e58

Keduanya kita masukkan ke file sslkey.txt (semuanya satu baris):

RSA Session-ID:19ab5edc02f097d5074890e44b483a49b083b043682993f046a55f265f11b5f4 Master-Key:191e5042e6b31371aa65258e13b2dc714d984df8d68fad678ff0a2fc49476d65c3a161f718572c3f5db8566a0de89e58

Lalu kita pakai file ini di wireshark:

Kita sekarang bisa melihat requestnya:

Dan jika kita ikuti SSL Streamnya:

Kita mendapatkan flagnya.

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

PlaidCTF2014 Write Up: doge_stege (Forensics100)

Ini adalah soal kategori forensik tapi sebenarnya bisa juga kategori steganography.

Berikut adalah deskripsi soalnya:

You were startled to learn the The Plague has been behind many of the most popular internet memes. We believe he hides information in these funny pictures with steganography in order to broadcast his messages through time without detection. Find the hidden message, stop the signal.

Hidden message adalah sebuah gambar berikut.

Kita diminta untuk mencari flag yang tersembunyi dari gambar.

Soal ini sangat mudah diselesaikan dengan stegsolve, dengan beberapa kali klik sudah terlihat pada random color map terlihat teks tersembunyi.

Karena warnanya diacak, kita bisa melakukan beberapa kali klik untuk melihat beberapa variasi warna sampai terlihat teks tersembunyi, pctf{keep_doge_alive_2014} yang menjadi flag.

PlaidCTF2014 Write Up: MtPox (Web150)

Ini adalah soal kategori web application tapi juga menggunakan teknik kriptanalisis.

Berikut adalah deskripsi soalnya:

The Plague has traveled back in time to create a cryptocurrency before Satoshi does in an attempt to quickly gain the resources required for his empire. As you step out of your time machine, you learn his exchange has stopped trades, due to some sort of bug. However, if you could break into the database and show a different story of where the coins went, we might be able to stop The Plague.

Oke skenarionya sepertinya disetting supaya mirip dengan bitcoin dan MtGox. Berikut adalah tampilan web aplikasi PlaidCoin exchange.

Setelah melihat-lihat dan mencoba web tersebut vulnerable terhadap Local File Inclusion pada file "index.php". Kita bisa melihat source code admin.php dengan membuka url "index.php?page=admin.php". Berikut adalah source code dari admin.php.

Perhatikan bahwa ketika belum terotentikasi kita diberi 2 cookie: 

• auth berisi serialize(false), yaitu "b:0;"
• hsh berisi sha256(SECRET + ";0:b")

Apa itu SECRET ? Kita tidak tahu isi dari SECRET, tapi kita diberitahu bahwa SECRET adalah 8 byte dan sangat kecil peluang untuk dibrute force.

Perhatikan lagi source code di atas baris 5-8, kita ingin membuat $auth bernilai true sekaligus ingin agar cookie hsh yang kita kirimkan diterima sebagai cookie yang valid.

Oke kalau begitu kita harus mengirim cookie auth yang bila di-unserialize menjadi true dan sekaligus hasil dari sha256(SECRET + strrev(cookie auth)) sama dengan cookie hsh yang kita kirimkan. 

Kita hanya punya hsh berisi sha256(SECRET + ";0:b"), bagaimana caranya kita bisa membuat sha256(SECRET + ";1:b") padahal kita tidak tahu SECRET ?

Jawabannya adalah dengan hash length extension attack, silakan baca di ilmuhacking tentang lebih detil bagaimana attack ini bekerja.

Jadi kondisinya sekarang:

• Dari hsh cookie diketahui bahwa sha256(SECRET + ";0:b") = ef16c2bffbcf0b75672...
• Jika kita ingin unserialize(str) bernilai true, maka str tersebut harus diawali dengan "b:1;" (sisanya boleh berisi string apapun, tidak akan mengubah hasil unserializenya).

Dengan hash extension attack, bila diketahui sha256(SECRET + ";0:b") = X, kita bisa mencari sha256(SECRET + ";0:b" + padding + append) tanpa mengetahui SECRET.

Perhatikan bahwa kita bisa menyelesaikan soal ini bila append berisi ";1:b" :

1. cookie auth yang kita kirim adalah append + pending + "b:0;" (dibalik karena ada strrev di baris ke-7) yaitu cookie auth = "b:1;" + append + "b:0;"
2. unserialize("b:1;"+padding+"b:0;") adalah true karena diawali dengan "b:1;"
3. sha256(SECRET + strrev(cookie auth)) adalah sha256(SECRET+";0:b"+padding+";1:b")

Tugas kita sekarang tinggal mencari tahu berapa nilai sha256(SECRET+";0:b"+padding+";1:b") tanpa tahu SECRET.

Dengan tools hash_extender kita bisa dengan mudah mendapatkan nilai sha256(SECRET+";0:b"+padding+";1:b") tanpa perlu tahu SECRET. Output dari tools tersebut tinggal kita balik kemudian diubah menjadi bentul url encoded sehingga hasilnya menjadi 2 cookie berikut:

Dengan dua cookie tersebut kita akan menembus otentikasi dan masuk ke halaman admin.

Selanjutnya dari source code jelas terlihat ada SQL injection pada parameter query. Selanjutnya saya serahkan saja pada sqlmap untuk melakukan eksploitasi sql injection.

PlaidCTF2014 Write Up: Twenty (Crypto20)

Ini adalah soal kategori kriptografi, seperti biasa kita diberi ciphertext dan diminta untuk men-dekrip menjadi plaintext.

Berikut adalah deskripsi soalnya:

It's so far in the past, computers haven't even been imagined, let alone used. But somehow The Plague has already been here, building an evil army of hackers. Can you find his secret message?

Ciphertext yang diberikan adalah:

fvoxoxfvwdepagxmwxfpukleofxhwevefuygzepfvexwfvufgeyfryedojhwffoyhxcwgmlxeylawfxfurwfvoxecfezfvwbecpfpeejuygoyfefvwxfpwwfxojumwuxfuffvwawuxflecaazubwjwoyfvwyepfvwuxfhwfjlopwckaohvfjlzopwoaahevupgwpfvuywjoywjdwyfufjupouvbuaajwuaoupkecygjwoyfvwuxxdofvyeacmwbvuzoyhlecpwzcbroyhdofvfvwgcgwdveheffvwrwlxfelecpxuzwuygfvexwfvufbuyfgempoyhxcofxbplfelecpcybawxujfexwffawgoxkcfwxfvechvflecgfubrawfvoxdofvuaoffawjepwfubfmcffvwyuhuoyzcghwkubrwpxogeyfryediubroxvwgufwupwswplfojwofvoyrezaorxuyhmcfxvofjuyfvwlpwubepkepufoeyuygojukwpxeyozobufoeyezzpwwgejzepuaaleczoaagebrwfxaorwfvufxubeybwkfzepwohyfeluaadvoawaudlwpxjcggldufwpuygfpexxfuaaecfezmcxoywxxoxiuoazepjwuyglecpwxcoyhjwbosoaalwnvomoffvoxoyfvwbecpfpeejheeygeofogupwlecbeyhpufcaufoeyxfvwzauhoxxoybwywdbplkfejohvfvuswyxumubrgeepxocxweagbplkfe

Kalau dilihat sepintas ada banyak pola dan perulangan huruf, ini adalah ciri dari substitution atau shift cipher.

Saya menggunakan tools substitution cipher solver yang menggunakan algoritma hill climbing untuk mencari kunci. Hill climbing adalah salah satu algoritma optimasi dan dekripsi adalah salah satu problem optimasi. Skor optimasi diukur berdasarkan kemiripan hasil dekripnya dengan teks bahasa inggris yang dilihat dari statistik 4-gram. Bila hasil dekripsinya banyak mengandung 4 huruf (THEY, HAVE,TION dsb) yang banyak ditemukan dalam bahasa inggris, maka skornya akan tinggi, semakin tinggi skor berarti semakin mendekati ke kunci yang benar. Bila skor masih rendah, kita akan mencari kunci lain dengan mengubah sedikit kunci sebelumnya agar skornya semakin tinggi.

Dalam waktu singkat hill climbing berhasil menemukan kunci substitusinya.