[BCACTF19] – manner-of-thpeaking

Soal ini muncul dengan judul yang sangat aneh, kata-kata yang aneh, hint yang aneh, dan file-file yang aneh pula. Seluruh description challenge mengganti huruf S menjadi th. Saya sangat amat clueless ketika pertama kali melihat soal,hint, dan juga file-file yang diberikan.

Ada 2 hint yang diberikan yaitu:

Hint pertama berisi “Pardon my LISP” (masih dengan aturan s->th), dan huruf kedua hanya memberi tahu bahwa backslash adalah escape character.

Untuk file-file serta solver bisa didownload di sini.

Isi dari instruction:

Isi dari printable:

Tebakan pertama saya adalah bruteforce dengan pool of characters yang sudah disediakan.

I’ve hit the point where i was so clueless about this problem. Untungnya, ketka mereview hintnya saya mendapatkan ilham. Ternyata setelah googling LISP, LISP adalah sebuah bahasa pemrograman yang ditemukan sudah cukup lama.

Setelah mengetahui informasi bahwa LISP adalah sebuah programming language, dan ada file bernama instruction, saya melakukan research terhadap CADR LISP dengan harapan CADR adalah sebuah instruksi dari bahasa tersebut. Ternyata, pada page search pertama ditemukan sebuah forum post yang berisi reference terhadap sebuah komentar pada forum lain oleh lee mac yang menjelaskan dengan cukup rinci.

 

Secara singkat, pada LISP berlaku instruksi CDR dan CAR. Instruksi ini berpengaruh dalam list based programming. instruksi car secara singkat berarti mengambil elemen pertama dari list yang tersedia. Sedangkan instruksi cdr membuang elemen pertama, dan mengembalikan list setelah elemen pertama dibuang. Basically, instruksi ini digunakan untuk mengolah data pada list. Saya rasa pembaca akan bingung jika hanya dijelaskan dengan kata-kata Langsung saja dicontohkan.

Jika saya punya sebuah list/array berisi [P,E,T,I,R]*  dan saya ingin mengambil huruf P, T, dan R dari list berikut maka saya harus melakukan beberapa instruksi dari cdr dan car.

*list pada lisp ditandai dengan simbol (), digunakan [] hanya untuk penjelasan semata.

  • Untuk mengambil huruf P, kita cukup melakukan car([P,E,T,I,R]) yang nantinya akan mereturn huruf P ingat car mengambil element pertama
  • Untuk mengambil huruf T, kita harus melakukan 2 kali cdr, lalu car. Yang jika ditulis akan menjadi car(cdr(cdr([P,E,T,I,R]))). Loh kok bisa begitu?? Mari kita ikuti Step-by-stepnya.
    • Aturan yang harus dipatuhi adalah dikerjakan dari yang paling dalam.
    • car(cdr(cdr([P,E,T,I,R]))) -> Mereturn [E,T,I,R] cdr mereturn list setelah membuang elemen pertama.  Dan instruksi berlanjut menjadi car(cdr([E,T,I,R]))
    • car(cdr([E,T,I,R])) -> mereturn [T,I,R] dengan alasan yang sama yaitu cdr mereturn list setelah membuang elemen pertama.  Instruksi dilanjutkan menjadi car([T,I,R])
    • car([T,I,R]) akan mereturn elemen pertama dari list. Yaitu huruf T.

Saya rasa penjelasan untuk car dan cdr seharusnya sudah cukup jelas. Pertanyaan berikutnya adalah: Tapi kan di instruction tidak ada cdr atau car, adanya cadadddddr,cadadr, dll. 

Tenang, bentuk aneh itu hanyalah sebuah singkatan dari kombinasi yang sudah kita lakukan tadi. Untuk mengambil huruf T, kita melakukan car(cdr(cdr([P,E,T,I,R))). Hal ini bisa disingkat sebagai caddr. Jadi, instruction yang ada di file adalah bentuk kombinasi-kombinasi dari car dan cdr. Easy.

Pertanyaan setelahnya adalah: LIST NYA MANA?  Instruksi tanpa list kan tidak berguna….

Ingat bahwa tadi diberikan sebuah file berisi pool of character yang saya tebak digunakan untuk bruteforce di atas. Ternyata, itulah list yang bisa kita gunakan untuk diolah menjadi flag. Hah masa sih?

Kalau kita perhatikan dengan baik dan melakukan parsing dengan baik, bisa dilihat pola dari sebuah list pada LIPS yaitu (). 

Ternyata, isi file tersebut adalah list of lists atau biasa kita kenal sebagai array 2 dimensi. ada 7 lists di dalam list yang dipakai.

Kita sudah tau instruksinya dan cara penggunaannya, kita juga sudah tau isi dari listnya apa. Berarti kita tinggal mencari cara agar flagnya bisa dibentuk. Tapi sabar dulu, kita baru belajar cara mengolah list 1 dimensi. Bagaimana list 2 dimensi diolah oleh instruksi cdr dan car?

Jika saya punya list of lists ([P,E,T,I,R][O,K])  dan saya ingin mengambil huruf PK, bagaimanakah caranya?

Pertama kita data dulu apa saja yang kita punya:

  • List dengan 2 array didalamnya *sebut saja pool*
  • array pertama berisi huruf P,E,T,I,R
  • array kedua berisi huruf O,K

Ya sudah, kita tinggal lakukan sama seperti yang sudah kita pelajari tadi. Ambil huruf P terlebih dahulu, baru huruf K. (Kalau di python tinggal pool[0][0],pool[1][1])

  • Cara mengambil huruf P : caar(pool)=car(car(pool)) = car(car([P,E,T,I,R] [O,K)).
    • Pertama-tama, kita ambil list yang memiliki huruf P. dengan cara car(pool) atau car([P,E,T,I,R] [O,K). car mereturn element pertama dan kebetulan element pertamanya masih berupa list. Return [P,E,T,I,R].
    • Kita lanjutkan dengan mengambil element pertama pada list yang berisi huruf P,E,T,I,R yang di mana huruf P sendiri adalah elemen pertama dari list tersebut dengan cara car([P,E,T,I,R]). Return P.
  • Cara mengambil huruf K juga kurang lebih sama yaitu cadr(pool) = car(cdr(car(cdr(pool))))=car(cdr(car(cdr([P,E,T,I,R] [O,K))))
    • Pertama-tama, ambil list yang memiliki huruf K. yaitu di list ke dua. namun untuk mengambil list kedua, harus menghilangkan list didepannya terlebih dahulu. Oleh karena itu, untuk mengambil list ke-dua dibutuhkan cadr(pool). cdr(pool) akan membuang [P,E,T,I,R]. lalu car([O,K]) akan mengambil list tersebut untuk diolah berikutnya.
    • Setelah dapat listnya tinggal cari hurufnya. Caranya sama yaitu car(cdr([O,K])). Kita buang huruf yang tidak diinginkan dengan cdr (O), lalu kita ambil huruf yang kita inginkan yaitu K.

Does it ring a bell to you? Kita melakukan pencarian huruf dengan 2 kali pencarian. Yang pertama mencari lokasi list, yang kedua mencari lokasi huruf/elemen. Hal ini juga berlaku untuk list of string (string notabene adalah array juga). Jadi, yang kita lakukan adalah mengisi IndexString dan IndexChar supaya bisa mengambil valuenya.

Ketika kita looping dan tidak menemukan huruf yang dicari, maka kita akan lanjut ke string berikutnya (cdr akan menandai IndexString+1). Jika sudah ketemu, maka kita akan menyimpan index dari string tersebut untuk selanjutnya mencari hurufnya (car menandakan perpindahan pencarian dari IndexString ke IndexChar). Selanjutnya, kita harus mencari huruf di string tersebut. Caranya sama yaitu jika tidak ketemu, maka cdr dilakukan dan IndexChar bertambah 1. Jika sudah ketemu, dilakukan car yang menandakan bahwa pencarian telah selesai.

Dengan algoritma ini, kita bisa melakukan scripting untuk melakukan otomatisasi atas step-step tersebut. Beberapa hal yang kita butuhkan adalah:

  • List dari pool printable character yang sudah diparsing dengan benar
  • List instruction yang setiap stringnya diparsing (karena formatnya adalah c[ad]+r. )Kita bisa hilangkan c dan r untuk memudahkan komputasi), dan juga direverse (Karena pengerjaan dari dalam ke luar)
  • Lalu kita butuh loop pertama untuk menjalankan semua instruksi yang ada.
  • Dan loop kedua untuk melakukan pencarian index dari pool yang kita miliki (dengan cara comparison huruf per huruf dari instruksi).
    • Loop kedua memiliki syarat yang harus dipenuhi:
      • Setiap memulai instruksi baru, IndexString dan IndexChar dimulai dari 0, dan boolean chk_str bernilai True (menandai bahwa sedang mencari indexString).
      • Jika bertemu huruf ‘d’ (cdr) ketika chk_str sedang True, maka pencarian string sedang dilakukan dan IndexString +=1.
      • Jika bertemu huruf ‘a’ (car) ketika chk_str sedang True maka pencarian string sudah selesai, dan bisa melakukan assignment chk_str = False supaya menandakan bahwa yang dicari adalah index char.(IndexString disimpan)
      • Jika bertemu huruf ‘d’ (cdr) ketika chk_str sedang False, maka pencarian char sedang dilakukan dan IndexChar +=1.
      • Jika bertemu huruf ‘a’ (car) ketika chk_str sedang False, maka pencarian char sudah selesai dan bisa mengambil huruf dari flag.

Untuk codingannya bisa dilihat di bawah dan dapat didownload di atas.

Leave a Reply

Your email address will not be published. Required fields are marked *