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~