TL; DR: kami merekayasa balik program yang ditulis untuk arsitektur CPU yang sama sekali tidak dikenal tanpa dokumentasi pada CPU (tanpa emulator, tanpa ISA, tanpa segalanya) hanya dalam sepuluh jam. Dari artikel ini Anda akan belajar bagaimana kami melakukannya ...
Akhir pekan lalu, tim CMU PPP dan saya berpartisipasi dalam tim Dragon Sector Teaser CTF 2019 untuk bersantai dan menjauh dari tenggat waktu
CHI 2020 yang keras . Dragon Sector adalah tim Polandia yang disegani dengan sejarah
CTFs yang menarik, jadi saya bertanya-tanya apa yang mereka miliki.
Setelah menyelesaikan "ummmfpu", tugas yang mencakup rekayasa balik bytecode untuk mikrokontroler floating point uM-FPU, saya memutuskan untuk berpartisipasi dalam kompetisi untuk memecahkan masalah Petualangan CPU, yang pada saat itu tidak diselesaikan oleh tim mana pun (sebagai hasilnya hanya kami yang menyelesaikan tugas).
Berikut ini deskripsi tugas Petualangan CPU:
Kakek saya di tahun 60an terlibat dalam pengembangan komputer. Menata barang-barang di lotengnya, aku menemukan mobil aneh. Di sebelah mesin itu ada tumpukan kartu punch bertanda "Game Petualangan Naga". Setelah beberapa waktu, saya berhasil menghubungkannya ke peralatan modern, tetapi permainannya terlalu rumit dan saya tidak bisa menyelesaikannya tanpa curang. Bisakah kamu membantuku? Saya melampirkan transkripsi kartu punch yang digunakan dalam mesin. Dikatakan bahwa mesin memiliki 4 register tujuan umum, 1 kibibyte data memori dan 32 kibibyte memori perintah. Untuk memainkan game, sambungkan ke server sebagai berikut: socat tcp4-connect:cpuadventure.hackable.software:1234 fd:0,rawer Petunjuk: prosesor mesin ini unik, jangan coba-coba mencari informasi di dalamnya.
game.bin
Setelah terhubung ke server, kami menerima informasi berikut:
THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.
SELECT AN OPTION:
- GO (N)ORTH
- GO (E)AST
- (T)ALK TO VALIS
- (D)RINK
- SHOW (I)NVENTORY
YOUR CHOICE:
Bagus Ini adalah game petualangan jadul. Setelah memainkannya sedikit, kami menyadari bahwa Anda dapat melawan musuh dan mendapatkan bendera dari karakter Valis ini jika kami menyenangkannya:
YOUR CHOICE: T
YOU ENTER THE TAVERN AND APPROACH VALIS.
- HEY, I WAS WONDERING IF YOU COULD HELP ME FIND THE FLAG?
- THE FLAG? MAYBE, BUT FIRST, I NEED A REDBULL.
- I... I DON'T HAVE A REDBULL.
- WELL THEN, MAKE YOURSELF USEFUL AND FIND ONE.
THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.
SELECT AN OPTION:
- GO (N)ORTH
- GO (E)AST
- (T)ALK TO VALIS
- (D)RINK
- SHOW (I)NVENTORY
YOUR CHOICE:
Langkah pertama
Saya tidak bermain game terlalu lama, menyadari bahwa kemungkinan besar lebih penting untuk merekayasa balik file
game.bin . Saya membukanya di hex editor, berharap untuk melihat nilai-nilai biner. Bayangkan betapa terkejutnya saya ketika saya melihat ini:
11001111110100000011110011001000111000001100110100000000000000110010011101010000001101001111100001111111001100111000000011 ...
Ini
benar-benar file biner - file teks yang tidak mengandung apa pun selain karakter ASCII 1 dan 0. Kita tahu bahwa ini kemungkinan besar adalah kode mesin prosesor, tetapi selain memiliki 4 register, 1 kbyte memori data, dan 32 kibibyte dari instruksi memori,
tidak ada yang diketahui tentang itu. Oleh karena itu, tugas serius pertama kita adalah menentukan ukuran unit file biner ini (misalnya, apakah ia memiliki dimensi 8-bit? Atau, mungkin, ia memiliki dimensi 12-bit atau 18-bit, seperti pada beberapa
arsitektur kuno ?)
Untuk mengetahui ukuran file yang tidak dikenal, saya menggunakan trik lama - Saya mengubah ukuran kotak teks sampai panjang garis putus sesuai dengan perataan. Metode ini sangat bagus untuk hal-hal seperti beberapa teks terenkripsi XOR, format file tidak dikenal (tidak terkompresi), dan kode dari CPU yang tidak dikenal:
Ubah ukuran kotak teksDari pemeriksaan cepat ini, saya menemukan bahwa ukuran unit file ini harus menjadi pembagi 20 (lebar jendela selaras). Untuk mengetahui ukuran pastinya, saya dengan cepat menulis sebuah skrip yang mencari garis berulang panjang (dengan asumsi bahwa kode apa pun telah mengulangi urutan stereotip). Baris pengulangan terpanjang adalah blok 425-bit berikut, ditemukan pada 43625 dan 44510:
10000011111110000001010100011111110100000101100010111000001001000101000100001000100001010001011000101000000001111111111100010000011110010100100001010100111100000110000010100000101000101000011110001111001101111001010100001010000111110100001010000110010011011110011111000000111011101000000001100000110000111101011010111011000100100010100000111000100011100011000000000101010101100010111000001010000001101010010000000011000001100
Karena jarak antara pengulangan adalah 885, kami sampai pada kesimpulan bahwa dimensi harus 5 bit, yaitu CPU yang tidak dikenal harus memiliki byte 5-bit. Kemajuan!
Kami mencari penyandian kartu punch 5-bit dan dengan cepat menyelesaikan penyandian lama
dengan kode Baudot . Dan faktanya - ketika kami menggunakan decoder online untuk memecahkan kode beberapa fragmen, kami mendapat teks yang bisa dibaca!
ā©DRAGONā©HEREā§; ā§ā§ā©SHEā©APPEARSā©TOā©BEā©GUARDINGā© BEBERAPAKINDā©OFā©Aā©BOTTLEā§; &. &. ā©āTHEREā©ISā©Aā©B
LSB Baudot ITA yang disempurnakan kode 425-bit
Kemudian kami mencoba men-decode seluruh file menggunakan kode Bodo, tetapi dalam sekitar 20 ribu bit pertama kami mendapat sampah, setelah itu ada teks yang dapat dibaca dengan sempurna. Ini menjelaskan kepada kita bahwa bagian pertama file milik bagian "kode", diikuti oleh bagian "data", yang berisi baris konstan. Kami berasumsi bahwa mesin tersebut mungkin menggunakan kode Bodo untuk I / O, dan karena itu menyimpan garis konstan dalam pengkodean Bodo dalam memori juga. Untuk membuat segmen kode lebih mudah dibaca, saya memutuskan untuk menyandikannya menggunakan basis-32 encoding, mirip dengan pengkodean heksadesimal, tetapi memperluasnya dengan alfabet 0-9a-v. Inilah yang terlihat seperti file game.bin dengan bagian pertama dikodekan oleh base-32 dan bagian kedua diterjemahkan oleh Bodo (file lengkap diposting di sini:
game.b32 ):
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf1sf24p5f3r9c11qad0f0sf1df26p5f39c21qad0f05f1ff26p5f39c41qad0f08f1df26p5f39c81qad0f0hf1ef26p5f3r1c00qaq15c20qcl0f01f1of27p5f3p3g3psf35c10qal0f02f1nf27p5f3p3g3psf3rf0hf1nf27p5f3f05f16f27p5f3rf84f95101311fl0f510f84907qa40b518447qa40b514f84f95k9m0k9m0k9m0907qa40b511447qa40b512ruougf10f20g0i9g0i910931b320u2u1u0ro9f0o9f0ojh0o9f0o9f0o9f0olj0o9f0o9f0o9f0o9f0o9f0o9f0o9f0o9k1onp0o9f0o9f0o9f0o9f0onf0ot82odi0o9f0o9f0o9f0o9f0o9f0o9f0o9f0olg0o9f0f0gf1df24p5f3r9c11qa835548755
[...]
93e9n59ka8fo87r85g8ui8ml8ed87b9h89u291u82333333333456789abcdb01234567892)%c3BOTTLE OF SOPLICA PIGWOWAENEMY HEALTH:
YOU ATTACK
YOU APPROACH REDFORD.
YOU ENTER THE TAVERN AND APPROACH VALIS.
[...]
Untuk kesederhanaan, saya akan memanggil unit lima-bit "byte" di bawah ini. Di antara satu sama lain dalam tim, kami menemukan nama-nama lain untuk mereka - saya menyebut mereka kibbles, dan Zak - hacks.
Arsitektur prosesor terbalik tidak dikenal
Sekarang kita turun ke bagian yang sulit - rekayasa balik 4000 byte kode yang berjalan pada arsitektur CPU unik yang sama sekali tidak dikenal. Dari kode tersebut, cukup jelas bahwa ini harus berupa serangkaian instruksi dengan
panjang variabel , karena tidak mungkin untuk menemukan pola pengulangan stabil yang terlihat di dalamnya. Saya menghabiskan beberapa jam untuk hal ini, kemudian anggota tim saya Zachary Wade (@ zwad3) mulai membantu saya. Pertama-tama, saya mulai mencari potongan kode duplikat, menyarankan bahwa mereka akan sering menggunakan sejumlah kecil instruksi. Saya mulai membagi kode menjadi urutan berulang yang lebih pendek yang lebih nyaman untuk analisis. Saya ingin mengatakan bahwa itu adalah proses yang ketat, tetapi pada kenyataannya, algoritma samar berikut ini terutama digunakan:
- Kami memeriksa kode dan mencari apakah ada sesuatu yang berulang di dalamnya
- Lakukan prosedur pencarian dan ganti untuk memasukkan baris baru di sebelah pengulangan ini
- Jelajahi persamaan / perbedaan antara garis yang dihasilkan.
- Ulangi proses ini selama sekitar satu jam ...
Sebagai contoh, salah satu pola yang saya temukan adalah "0f0.f", di mana "." menunjukkan karakter yang tidak dikenal. Saya memecahkan string pada pola ini dan mendapatkan yang berikut:
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf
1sf24p5f3r9c11qad0f0sf
1df26p5f39c21qad0f05f
1ff26p5f39c41qad0f08f
1df26p5f39c81qad0f0hf
1ef26p5f3r1c00qaq15c20qcl0f01f
1of27p5f3p3g3psf35c10qal0f02f
Sangat membantu! Dari baris kedua dan ketiga kita melihat bahwa ada "... p5f3r9c ..." dan "... p5f39c ...", dan ini mengisyaratkan kepada kita bahwa "r" adalah opcode byte tunggal, yaitu, "... 5f3" adalah akhir dari satu opcode, dan " 9c .. āadalah awal dari yang lain. Dalam dua baris terakhir kita melihat "p5f3r1c ..." dan ini berarti "1c .." adalah opcode lain, dan "p3 ..." juga opcode lain.
Saya terus membagi instruksi berulang-ulang dengan cara yang sama, menggunakan persamaan dan perbedaan dari blok yang sama untuk menemukan instruksi yang mungkin. Pada akhirnya, saya mendapat sesuatu seperti ini:
pv83
pi70
pk00
p7a0
qfgv
pjg3
f0k
f13
f28
p5f3
pv10
pk40
pn60
f0s
f1s
f24
p5f3
r
9c11
qad0
f0s
f1d
f26
p5f3
9c21
qad0
f05
f1f
Saya berasumsi bahwa "p" dan "q" adalah instruksi dengan tiga byte operan, "f0", "f1" dan "f2" adalah instruksi dengan satu operan, dan "9c" adalah instruksi dengan dua operan. Namun, saya tidak tahu apa masing-masing instruksi ini.
Jadi saya membuka direktori semua instruksi "p" yang saya soroti, dan menemukan bahwa saat ini instruksi yang paling sering dengan "p" adalah "p5f3". Selain itu, melihat tempat-tempat di mana itu terjadi, saya menemukan bahwa itu selalu didahului oleh instruksi "f0", "f1" dan "f2". Melihat semua operan "f0", "f1" dan "f2", saya perhatikan bahwa operan f2 selalu dalam kisaran 4-8. Mengingat bahwa CPU memiliki 32 kb memori program untuk pengalamatan yang membutuhkan 15 bit, saya berasumsi bahwa "f0", "f1" dan "f2" memuat beberapa alamat dengan f2 sebagai byte tinggi. Ketika saya menghubungkan beberapa alamat ini bersama-sama, saya menemukan bahwa mereka semua menunjuk tepat ke awal garis konstan di bagian data. Saya menemukan fungsi
print ! Segera diikuti bahwa "p5f3" sebenarnya semacam instruksi untuk mencetak saluran atau panggilan; jika Anda memperhitungkan operan tiga byte, maka kemungkinan besar itu adalah "panggilan". Sekali lagi, melihat instruksi "p", saya menyadari bahwa tiga byte operan menunjukkan alamat dalam
urutan langsung (little-endian) , yaitu, byte terakhir dari operan adalah byte tertinggi dari alamat.
Itu adalah terobosan besar! Kami telah mengidentifikasi instruksi pertama kami. Setelah melihat bahwa "f0" dan "f1" digunakan di beberapa tempat lain, saya berasumsi bahwa mereka tidak memuat alamat, tetapi salah satu dari empat register (misalnya, f0 memuat register 0) dengan konstanta 5-bit dengan pengalamatan langsung. Ini logis untuk p5f3 - ia memuat tiga argumen register untuk fungsi 3f5 ("print_string").
Saya mulai menulis disassembler yang mengenali idiom "cetak" (f0x, f1x, f2x, p5f3), menempatkan substitusi dari garis yang dicetak dalam kode yang dibongkar. Karena banyaknya baris dalam program, kode yang dibongkar dengan cepat menjadi sangat mudah dibaca, dan menjadi lebih mudah untuk mengetahui lokasi blok fungsi (kode pembongkaran penuh ada di
sini ):
0: call 38v
4: call 7i
8: call k
c: call a7
g: q vgf
k: call 3gj
o: print 83k # 'SELECT AN OPTION\x0e:\r\n\r\n\x0f\x00'
15: call 1v
19: call 4k
1d: call 6n
1h: print 4ss # '\r\nYOUR CHOICE\x0e: \x0f\x00'
1u: ret
1v: unk 9
20: unk c
21: unk 1
22: unk 1
23: q 0da
27: print 6ds # '\x0e- \x0fGO \x0e(\x0fS\x0e)\x0fOUTH\r\n\x00'
2k: unk 9
2l: unk c
2m: unk 2
2n: unk 1
2o: q 0da
2s: print 6f5 # '\x0e- \x0fGO \x0e(\x0fN\x0e)\x0fORTH\r\n\x00'
39: unk 9
3a: unk c
3b: unk 4
3c: unk 1
3d: q 0da
3h: print 6d8 # '\x0e- \x0fGO \x0e(\x0fE\x0e)\x0fAST\r\n\x00'
3u: unk 9
3v: unk c
40: unk 8
41: unk 1
42: q 0da
46: print 6eh # '\x0e- \x0fGO \x0e(\x0fW\x0e)\x0fEST\r\n\x00'
4j: ret
Dari cuplikan kode kecil ini, saya berhasil mengetahui beberapa aspek: instruksi "q0" harus menunjukkan beberapa percabangan bersyarat (karena digunakan untuk melewati pencetakan arah yang tidak perlu dalam fungsi 1v), dan instruksi "9c11", "9c21", "9c21", "9c41", " 9c81 "harus menunjukkan semacam instruksi AND - mereka memeriksa bit yang ditetapkan untuk melihat apakah arahan ini diizinkan (ini jelas ditunjukkan dengan penggunaan" 1 "," 2 "," 4 "dan" 8 "dalam instruksi ini).
Selama dua jam berikutnya, Zachary Wade (@ zwad3) dan saya memilah-milah berbagai instruksi, membuat dan menyempurnakan asumsi kami tentang apa yang mereka lakukan. Memiliki banyak pernyataan cetak yang dapat dibaca membuat pekerjaan kami jauh lebih mudah. Kami memutuskan bahwa masing-masing dari kami secara individual akan menulis disassembler sendiri sehingga kami dapat memeriksa instruksi dengan langkah kami sendiri dan membagikan temuan kami.
Rekayasa kode terbalik
Setelah beberapa jam, saya mulai membuat kemajuan besar dalam pembongkaran. Setelah memeriksa kode yang berfungsi dengan inventaris pengguna (lebih khusus lagi, fungsi "minum" dan setiap handler yang terkait dengannya), kami menemukan instruksi untuk menyimpan dan memuat dari memori (jangan lupa bahwa CPU memiliki 1 kibibyte memori data). Kemudian kami menemukan bahwa beberapa instruksi aritmatika / logis (ALU) mengambil operan memori (misalnya, "9c41" berarti "mengeksekusi DAN dengan nilai pada alamat data 1 dengan nilai 4"). Dari ini, kami dapat membuat ulang variabel dalam memori data, misalnya, di [0] pengidentifikasi NPC disimpan di lokasi saat ini, dan di [6,7] kesehatan pemain saat ini disimpan (semakin rendah 5 bit dalam [6], 5 bit tertua di [7] ]). Pada tahap ini, saya beralih dari instruksi reverse engineering ke annotating kode saya dibongkar dan reverse engineering program itu sendiri. Di bawah ini adalah notasi lucu saya untuk nilai 5-bit:
_start:
call init
L4:
call check_moves
call print_menu
call handle_command
br 4
print_menu:
call print_itemname
print 83k # 'SELECT AN OPTION\x0e:\r\n\r\n\x0f\x00'
call print_moves
call print_npcmenu
call print_itemmenu
print 4ss # '\r\nYOUR CHOICE\x0e: \x0f\x00'
ret
print_moves:
and 0y1, [1]
brz 2k
print 6ds # '\x0e- \x0fGO \x0e(\x0fS\x0e)\x0fOUTH\r\n\x00'
2k: and 0y2, [1]
brz 39
print 6f5 # '\x0e- \x0fGO \x0e(\x0fN\x0e)\x0fORTH\r\n\x00'
39: and 0y4, [1]
brz 3u
print 6d8 # '\x0e- \x0fGO \x0e(\x0fE\x0e)\x0fAST\r\n\x00'
3u: and 0y8, [1]
brz 4j
print 6eh # '\x0e- \x0fGO \x0e(\x0fW\x0e)\x0fEST\r\n\x00'
4j: ret
print_npcmenu:
add 0y0, [0]
brz 6m
sub 0y2, [0]
br<c> 5p
print 7o1 # '\x0e- (\x0fT\x0e)\x0fALK TO \x00'
call print_npcname
call print_crlf
5p: sub 0y1, [0]
brz 6m
print 7n2 # '\x0e- (\x0fF\x0e)\x0fIGHT \x00'
call print_npcname
call print_crlf
6m: ret
print_itemmenu:
print 7nh # '\x0e- (\x0fD\x0e)\x0fRINK\r\n\x00'
print 765 # '\x0e- \x0fSHOW \x0e(\x0fI\x0e)\x0fNVENTORY\r\n\x00'
ret
Kami masih memiliki banyak opcode yang tidak dikenal, misalnya, meskipun kami menemukan bahwa "qa" adalah percabangan bersyarat pada nol (branch-on-zero, brz), kami tidak dapat memahami apa "qc" itu (ditunjukkan di atas sebagai br <c>). Tetapi itu sudah cukup untuk mulai memahami logika program.
Bahkan, permainan memungkinkan pemain untuk bergerak di sekitar peta 8 Ć 8 di mana NPC (naga, banteng merah, dan manusia) ditempatkan secara acak. Anda dapat bertarung dengan NPC apa pun (bahkan Valis, meskipun tidak ada item menu yang sesuai). Selama pertempuran, Anda dapat menyerang musuh, menyebabkan kerusakan atau kehilangan acak, setelah itu musuh menyerang pemain, juga menyebabkan kerusakan atau kehilangan secara acak. Anda juga dapat memilih kunci pelindung, berkat musuh yang meleset atau mengenai perisai tanpa menyebabkan kerusakan. Akhirnya, Anda dapat menipu dengan meningkatkan kesehatan Anda menjadi 1000, tetapi dalam kasus ini, variabel tersembunyi ("curang", alamat 10) diatur ke 1. Jika pemain berhasil membunuh musuh, sebuah objek jatuh darinya, biasanya sebotol alkohol (jelas, game ini bukan untuk anak-anak).
NPC Valis utama, dari mana pemain harus menerima bendera, memiliki mesin negara di mana dia meminta pemain untuk beberapa item - sekelompok minuman banteng merah (jelas diperoleh saat mengalahkan musuh banteng merah), berbagai minuman campuran (misalnya, gin dan tonik - untuk mendapatkannya, Anda perlu mengalahkan naga biru dan naga abu-abu, dan kemudian mencampur benda-benda yang dijatuhkan dari mereka), dan strip daya, yang dapat diperoleh jika Anda mengalahkan orang NPC lain dalam permainan (Redford) atau membantunya. Jika Anda memenuhi semua rangkaian permintaan yang panjang ini, dia akan memberi Anda bendera, tetapi
hanya jika variabel "curang" tidak sama dengan 1. Artinya, tugas kami adalah memenangkan permainan tanpa curang. Karena kita mulai dengan hanya 100 HP, seperti semua musuh, dengan jalan yang biasa maka tidak mungkin untuk mengalahkan semua musuh (untuk mendapatkan semua hal yang perlu Anda kalahkan sekitar 20 lawan). Penting untuk memodifikasi RNG entah bagaimana, sehingga musuh selalu merindukan.
Angka acak dihasilkan oleh fungsi yang mirip dengan semacam PRNG (alamat 37a), tetapi menggunakan instruksi unik yang tidak digunakan di tempat lain, jadi kami tidak dapat merekayasa baliknya. Namun, kami perhatikan bahwa ia memuat vektor statusnya dari tiga alamat di memori ([11], [12] dan [13]), yaitu, status penuhnya hanya membutuhkan 15 bit. Ini berarti bahwa RNG harus memiliki periode pendek - tidak lebih dari 2 ^ 15 = 32768 panjangnya.
Sementara kami (tidak berhasil) mencoba untuk membalikkan implementasi RNG, Jay Bosamia (@ jay_f0xtr0t) dan Matthew Savage (@thebluepichu) mengimplementasikan exploit. Dengan hanya mengirimkan perintah "perisai" 100.000 kali berturut-turut, kami dapat memperoleh urutan "serangan" musuh dan "meleset" sesuai dengan output bit dari RNG. Kami memastikan bahwa urutan ini berulang dengan periode 32767. Berkat ini, kami dapat merakit eksploitasi utama kami - ketika bertarung dengan musuh pertama yang kami temui, kami menutup perisai kami 40 kali untuk menciptakan kembali urutan hit dan miss, mencari urutan ini dalam urutan periodik yang besar, dan kemudian menemukan kapan harus melindungi dan kapan harus menyerang sehingga musuh selalu merindukan. Lalu kami hanya berkeliling seluruh peta dalam mode
killhobo , membunuh semua orang dan mengumpulkan jarahan mereka. Pada akhirnya, kami kembali ke Valis dan dengan sopan meminta bendera kami, yang kami terima:
DrgnS{m4kin9-v4lis-happy-w1th-n4t1ve-b4ud0t-cpu}
Fuh! Memang, petualangan yang nyata. Saya masih tidak dapat sepenuhnya percaya bahwa kami berasal dari string biner dan kurangnya dokumentasi prosesor untuk dua pembongkaran yang hampir lengkap dan kode pembongkaran yang bersih dalam waktu kurang dari 10 jam! Semua kode tersedia di GitHub:
disassembler saya ,
disassembler Zachary ,
kode disassembled mentah saya ,
kode disassembled beranotasi saya ,
klien Matt's Exploit .