Dalam tulisan ini saya akan membahas tentang random number, dan bagaimana attack terhadap random number generator bisa sangat berbahaya. Selama ini kita sering mendengar tentang random number tapi banyak yang belum paham betapa pentingnya random number dalam keamanan informasi dan apa bahaya yang terjadi bila random number yang dipilih tidak cukup random?
Randomness
Apakah yang dimaksud dengan random/acak ? Bagaimana kita mendefinisikan sesuatu bisa disebut acak atau bukan ?
Sebenarnya sulit menentukan apakah sesuatu itu benar-benar random atau bukan. Tapi secara umum kita menyebut sesuatu itu random bila kita tidak melihat adanya pola atau keteraturan atau urutan (absence of pattern, absence of order), walaupun absence of order juga tidak menjamin benar-benar random.
Suatu deretan angka tidak bisa dibilang random bila deretan angka itu digenerate oleh suatu prosedur/algoritma tertentu yang deterministik, artinya setiap kali prosedur tersebut dijalankan lagi, deretan angka yang keluar akan selalu sama dengan yang sebelumnya.
Beberapa properti yang bisa dipakai untuk menilai randomness adalah:
- Even distribution
- Unpredictability
- Uniqueness
Even Distribution
Even distribution maksudnya adalah semua hasil yang mungkin mempunyai peluang yang sama. Sebagai contoh kalau kita melempar dadu, setiap sisi mempunyai peluang yang sama, tidak boleh berat ke salah satu sisi saja. Dalam waktu yang cukup lama, data yang digenerate secara random seharusnya akan mengcover hampir semua data set secara merata (tidak berkelompok di salah satu bagian saja).
Kalau himpunan semua nilai yang mungkin digambarkan sebagai pixel dalam monitor anda, number generator yang baik akan secara merata mengisi semua pixel yang ada, tidak berkelompok di satu area tertentu.
Tiga gambar di bawah ini memperlihatkan distribusi random number yang merata, mulai dari masih sedikit sampai makin banyak.
Semakin banyak bilangan yang digenerate, akan semakin merata bilangan itu menutupi area-area yang kosong.
Perbedaan antara password yang dibuat oleh manusia dan random password generator terlihat dari distribusi penggunaan karakternya. Password yang dibuat manusia distribusinya tidak merata karena sangat dipengaruhi oleh bahasa yang dipakai. Bahasa manusia jelas tidak random, sehingga password yang diturunkan dari bahasa tersebut juga tidak mungkin random. Bila dalam bahasa inggris, huruf yang paling sering dipakai adalah ‘e’, maka frekuensi huruf e akan terlihat menonjol dibanding huruf lainnya.
Berbeda dengan password yang digenerate oleh password generator, dari 26 huruf yang ada, semua huruf punya peluang yang sama sehingga distribusinya merata. Tidak ada satu huruf yang lebih sering dipakai dibandingkan huruf yang lain.
Perbedaan ini menunjukkan bahwa password yang dipilih manusia sangat jauh dari random. Hal ini terlihat dari grafik distribusi karakter password yang dibuat oleh manusia. Terlihat ada karakter-karakter yang terlihat menonjol karena sering dipakai, ada juga karakter-karakter yang jarang atau tidak pernah dipakai dalam password.
Password yang digenerate oleh password generator memiliki distribusi karakter yang merata. Grafik di bawah jelas menunjukkan bahwa semua karakter mempunyai peluang yang sama, tidak ada karakter yang sangat sering, lebih sering, jarang dipakai atau tidak pernah dipakai.
Unpredictability
Unpredictability maksudnya adalah data-data yang sudah lebih dulu muncul tidak bisa dipakai untuk memprediksi data apa yang akan muncul berikutnya karena setiap data tidak ada hubungannya dan tidak tergantung dengan data yang lain (independent).
Apa yang terjadi kalau random number yang akan muncul bisa diprediksi sebelumnya?
Mesin di kasino memiliki random number generator di dalamnya untuk mengacak kartu, bila random number yang muncul sudah bisa diprediksi sebelumnya, dia akan bisa selalu memenangkan permainan. Dalam buku The Art of Intrusion, ada satu bab yang menceritakan tentang kesuksesan 3 orang melakukan hacking mesin kasino dengan cara memprediksi random number.
Quote berikut dengan singkat menceritakan apa yang mereka lakukan, “Reverse engineering the operation of the machine, learned precisely how the random numbers were turned into cards on the screen, precisely when and how fast the RNG iterated, all of the relevant idiosyncrasies of the machine, and developed a program to take all of these variables into consideration so that once we know the state of a particular machine at an exact instant in time, we could predict with high accuracy the exact iteration of the RNG at any time within the next few hours or even days”.
Dalam dunia security predictability bisa berakibat fatal, misalnya memprediksi password yang digenerate oleh password generator, memprediksi session id, memprediksi activation link dan masih banyak lagi lainnya.
Uniqueness
Bila kita mengambil sederetan data acak (misalkan 10 karakter acak), kecil peluangnya kita menemukan 10 karakter acak tersebut berulang (repetition), semakin panjang deretan angka yang kita ambil, semakin kecil peluangnya berulang. Karena random number terdistribusi secara merata dan antara satu data dan lainnya tidak saling berhubungan, maka kecil peluang kemunculan dua data yang berulang.
Pseudo Random Number Generator (PRNG)
Komputer sebagai mesin yang deterministik tidak mungkin bisa menghasilkan sesuatu yang random. Deterministik disini maksudnya adalah suatu prosedur tertentu diberi input yang sama, outputnya juga akan selalu sama. Output hanya akan berbeda bila inputnya berbeda.
Komputer bekerja mengikuti langkah-langkah yang sudah ditetapkan dalam algoritma program. Tidak mungkin sebuah komputer bekerja dengan cara yang acak tanpa mengikuti alur langkah-langkah algoritma.
Machines are deterministics, their operation is predictable and repeatable
Begitu juga random number yang digenerate komputer juga adalah hasil dari komputasi algoritma tertentu yang deterministik, oleh karena itu hasil random numbernya tidak benar-benar random atau disebut dengan Pseudo Random.
Salah satu implementasi PRNG adalah dengan menggunakan algoritma enkripsi simetris seperti AES-128 dalam counter mode seperti gambar di atas.
Random number yang pertama muncul adalah hasil enkripsi dengan kunci yang diambil dari suatu sumber yang cukup random (sebagai seed), dan message yang dienkrip adalah angka 0. Random number berikutnya adalah hasil enkripsi dengan kunci yang sama (seed), namun message yang dienkrip adalah angka 1, berikutnya message yang dienkrip adalah 2 dan seterusnya sehingga membentuk deretan angka yang cukup random.
Kalau diperhatikan gambar implementasi PRNG di atas, jelas terlihat bahwa bila orang lain mengetahui seednya, maka semua random number yang akan muncul dan yang sudah muncul bisa diketahui dengan mudah.
Sekali lagi perlu diingat bahwa prosedur PRNG adalah deterministik, jadi dengan seed yang sama dan algoritma yang sama, maka deretan angka random yang muncul juga akan selalu sama. Deretan angka random hanya akan berbeda bila seed yang diberikan berbeda.
- Dengan seed x, maka yang muncul adalah x0,x1,x2…
- Dengan seed y, maka yang muncul adalah y0,y1,y2…
- Dengan seed z, maka yang muncul adalah z0,z1,z2…
Remember: Same seed, same sequence of numbers
Apa yang terjadi bila seed diketahui pihak luar? Bila orang lain tahu seed yang diberikan pada suatu PRNG, maka dia bisa mengetahui semua deret random number yang sudah muncul dan yang akan datang.
When the state of the random number generator is leaked all future random numbers are predictable – Steffan Esser
Oleh karena itu sangat penting untuk menggunakan seed dari sumber yang benar-benar random agar tidak terjadi kebocoran seed.
PRNG Period/Cycle
Kelemahan lain dari PRNG adalah adanya periode/siklus perulangan, setelah PRNG men-generate sekian banyak random number, dia akan kembali lagi mengulang deretan angka yang sama seperti dari awal lagi.
Contohnya dengan seed x, maka deretan angka yang muncul adalah x0,x1,x2…(setelah sekian banyak random number)…x0,x1,x2…dan seterusnya
Contohnya dengan seed x, maka deretan angka yang muncul adalah x0,x1,x2…(setelah sekian banyak random number)…x0,x1,x2…dan seterusnya
Source of Seed
Sebagai input untuk PRNG, seed haruslah berasal dari sumber yang benar-benar random. Sumber yang dinilai random adalah aktivitas fisik yang non-deterministic antara lain:
- Pergerakan mouse
- Penekanan tombol keyboard
- Thermal noise
- Radioactive activity
Sebenarnya sumber true random number sangat banyak di alam. Hampir semua kejadian di alam bila kita perhatikan dengan seksama terjadi dengan cara yang random, seperti gerakan awan, ombak di laut, pergerakan atom/molekul dalam zat dan masih banyak lagi. Dengan sensor atau alat observasi yang tepat kita bisa memanfaatkan banyak kejadian di alam sebagai sumber true random number.
Beberapa operating system menyediakan random pool yang siap pakai seperti /dev/random. /dev/random siap memberikan random number kapanpun diminta yang berasal dari environmental noise dalam CPU, jadi random numbernya bisa dibilang cukup random karena berasal dari aktivitas fisik (non-deterministik).
Random Number as Seed to PRNG
Dibutuhkan effort lebih untuk mendapatkan bilangan random yang non-deterministik dan berasal dari aktivitas fisik di luar komputer. Sumber-sumber yang memberikan bilangan random yang non-deterministik biasanya hanya bisa menyediakan random number dalam jumlah yang terbatas, sedangkan PRNG bisa memberikan random number dalam jumlah yang sangat banyak (tergantung sebanyak apa angka yang keluar sebelum terjadi perulangan, repetition cycle).
Karena keterbatasan itu maka perlu dikombinasikan antara random number non-deterministik dengan PRNG. Bila dibutuhkan random number dalam jumlah banyak yang tidak bisa disediakan oleh random number non-deterministik, maka kompromi yang bisa dilakukan adalah dengan mengambil random number dari PRNG yang diberi seed dari random number yang diambil dari sumber luar yang non-deterministik.
Dalam gambar implementasi PRNG di atas juga terlihat bahwa prosedur PRNG memiliki input yang berasal dari “random pool” yang digambarkan sebagai awan. Random pool ini berasal dari sumber-sumber yang non-deterministik seperti pergerakan mouse, keyboard, thermal noise sampai aktivitas radioaktif.
Random Number Role in Security
Random number memegang peranan critical dalam menjamin keamanan data. Aplikasi random number dalam bidang security yang crucial antara lain:
- Generating password
- Generating session ID
- Generating activation/confirmation code
- Generating symmetric/asymmetric encryption key
- and many more…
Bila random number yang digunakan untuk men-generate password atau encryption key lemah, seorang hacker bisa mendapatkan password atau encryption key dengan melakukan komputasi di komputernya kemudian dengan leluasa menguasai account, server atau membuka data yang dilindungi dengan enkripsi.
Agar lebih terbayang bagaimana pentingnya random number yang kuat dalam menjaga security, berikut ini ada 4 studi kasus web application real world yang menggunakan weak random number dan cara eksploitasinya.
Case Study #1: Predicting Captcha (CaptcaPHP 2.3)
Lab Download: CaptchaPhp 2.3 dan solusicapcay.php
Sebagai contoh kasus weak random number, kita akan melakukan breaking captcha pada CaptchaPHP versi 2.3 tanpa melakukan image processing sedikitpun, murni hanya dengan “predicting the captcha”. Kelemahan ini dilaporkan oleh Julio Vidal.
Captcha memberikan soal berupa gambar berisi teks yang harus kita baca untuk membuktikan bahwa kita adalah manusia, bukan software. Idenya sederhana, bila kita bisa membaca isi teks dalam gambar, maka kita akan dipercaya sebagai manusia. Dalam tulisan saya sebelumnya tentang menjebol captcha dengan OCR saya memakai teknik optical character recognition yang mencoba membaca isi teks dalam gambar dengan algoritma tertentu. Tergantung dari tingkat kerumitan gambar, tingkat keberhasilan teknik OCR kecil, kecuali bila gambarnya benar-benar jelas (tidak mengandung noise dan gangguan-gangguan apapun).
Kali ini kita tidak memakai teknik OCR, kita akan melakukan prediksi isi teks dalam gambar, tanpa melibatkan image processing bahkan gambar captchanya tidak disentuh dan tidak dilihat sama sekali. Tingkat akurasi prediksi ini sangat tinggi, hampir 100% sukses. Bagaimana caranya kita bisa memprediksi captcha dengan akurasi yang sangat tinggi?
Weak Seeding
Sebelumnya kita harus pahami bahwa dengan mengetahui seed suatu pseudorandom number generator (PRNG), kita bisa memprediksi semua random number yang akan di-generate oleh PRNG tersebut.
Captcha selalu memberikan soal yang berisi teks yang berbeda-beda setiap kali diminta. Teks yang ada pada gambar captcha dipilih secara random dengan fungsi rand(). Dalam captchaphp 2.3 ini PRNG terlebih dahulu diberi initial state, atau seed dengan formula: ‘microtime() + time()/2 -21017′ seperti terlihat dalam source code di bawah ini:
Sepintas source code di atas tidak bermasalah, namun kalau diperhatikan pada pemanggilan fungsi srand(), terlihat bahwa sumber entropi yang dipakai untuk seed sangat lemah, yaitu waktu dalam detik dan mikrodetik. Seeding yang lemah ini menjadi malasah besar karena seperti yang sudah kita bahas sebelumnya, bila seed suatu PRNG bocor (diketahui orang lain), maka orang tersebut akan bisa memprediksi semua random number yang akan di-generate.
Kenapa PRNG harus diberi seed dari sesuatu yang tidak diketahui pihak luar? Karena bila seednya sampai diketahui orang lain, maka orang tersebut akan bisa memprediksi semua random number yang akan digenerate.
Masalahnya adalah waktu bukanlah sesuatu yang rahasia, waktu adalah sesuatu yang universal, hanya berbeda pada zona waktu saja. Kalaupun ada perbedaan waktu dengan jam server, kita bisa mengetahui waktu di server dari banyak cara, antara lain dengan header ‘Last-Modified’ atau header ‘Date’ dari HTTP server.
Integer Truncation Seed
Kalau kita baca dokumentasi php dari fungsi srand() dan microtime(), diketahui bahwa fungsi srand() ini meminta input bertipe integer, sedangkan formula ‘microtime()+time()/2-21017′ menghasilkan floating point karena ada operasi pembagian dan microtime() menghasilkan angka microsecond bertipe floating point. Karena ada perbedaan tipe, yang diminta integer, sedangkan yang diberikan adalah floating point, maka akan terjadi integer truncation, semua angka dibelakang koma akan dipotong sehingga hanya tersisa integernya saja.
Dalam contoh skrip kecil berikut terlihat bahwa dengan adanya truncation dari floating point ke integer, ‘microtime()+time()/2-21017′ akan sama saja dengan ‘time()/2-21017′. Jadi bisa dikatakan bahwa satu-satunya sumber entropi untuk seed adalah time().
Oke, kini kita sudah tahu bahwa satu-satunya sumber entropi untuk seeding adalah unix time dalam second. Sekarang dari mana kita bisa mengetahui berapa unix time yang dipakai dalam seeding untuk men-generate random text dalam captcha ?
Leaked time() Seed
Kunci untuk bisa melakukan prediksi random number dengan akurat adalah dengan mengetahui internal state (seed) dari PRNG.
Dalam kasus ini kita bisa mengetahui dengan pasti berapa unix time yang dipakai sebagai seed karena adanya parameter __ec_i. Apakah parameter __ec_i ini ? Perhatikan source html dari captcha berikut:
Dalam source htmlnya ada parameter __ec_i yang berfungsi sebagai tracking ID dan secara internal dipakai untuk menentukan jawaban captcha. Mari kita lihat bagaimana __ec_i ini digenerate:
Ternyata komponen kedua setelah ‘ec.’ adalah hasil dari fungsi time(), yaitu unix time. Jadi kalau parameter __ec_i berisi ‘ec.1343036274.fea073dc38def100d18b21adf211d946′, maka unix time pada saat __ec_i tersebut digenerate adalah 1343036274.
Perhatikan dalam source di atas, ketika memanggil srand() kita memakai fungsi time(), kemudian 2 baris dibawahnya kita men-generate parameter __ec_i yang juga memakai fungsi time(). Meskipun ada perbedaan antara waktu pemanggilan time() yang pertama (pada saat srand) dan yang kedua (pada saat generate __ec_i), namun karena dua waktu ini adalah detik, maka dua kejadian ini sebagian besar terjadi dalam detik yang sama, sangat jarang terjadi di detik yang berbeda.
Jadi dalam kasus ini internal state (seed) dari PRNG sudah bocor dari parameter __ec_i, dengan membaca parameter __ec_i seseorang bisa mengetahui seed yang dipakai untuk generate random teks dalam captcha.
Predicting The Captcha
Oke, sekarang kita sudah bisa tahu seed yang dipakai untuk generate teks dalam captcha dari parameter __ec_i, selanjutnya bagaimana cara prediksinya?
Perhatikan contoh prediksi pada gambar di atas. Dari parameter __ec_i ‘ec.1343083228.f38f0267daff24ef5ace74d079b2a50c’ kita ketahui bahwa unix time adalah 1343083228 dan timestamp ini digunakan sebagai seed untuk generate random teks dalam captcha. Saya memodifikasi sedikit captchaphp 2.3 yang asli, agar menerima masukan berupa unix time dan memakainya sebagai seed untuk men-generate random teks.
Terlihat bahwa random teks yang digenerate oleh skrip hasil modifikasi yang dijalankan secara local sama persis dengan isi teks dalam gambar captcha yang diberikan server. Ini membuktikan dengan seed dan PRNG yang sama, random number yang digenerate siapapun, kapanpun, dimanapun (di client maupun di server) akan sama persis, artinya kita sudah sukses melakukan prediksi yang 100% akurat. Tanpa menyentuh dan melihat gambar captchanya sama sekali, hanya berbekal unix time kita bisa dengan akurat memprediksi isi teks dalam gambar captcha.
Bila skrip itu dijalankan berulang-ulang kali dengan seed yang sama, maka random teks yang dihasilkan juga akan sama persis. Selama seednya sama, hasil random teksnya juga akan sama.
Modifying Script
Skrip prediksi dibuat dari script captchaphp 2.3 yang asli dengan beberapa modifikasi kecil berikut ini:
Pada modifikasi di atas, saat memanggil srand(), kita tidak lagi memakai fungsi time(), tapi memakai argument dari command line, argv[1].
Modifikasi terakhir adalah dengan mengganti isi fungsi easy_captcha::form() dengan 1 baris saja seperti di atas. Hanya itu saja modifikasi yang dilakukan untuk membuat script prediksi, intinya hanya pada saat seeding kita memakai inputan user bukan fungsi time(), selebihnya kita mengikuti prosedur yang sama (tidak kita modifikasi) dengan captchaphp 2.3 aslinya untuk men-generate teks random dalam captcha.
Case Study #2: Predicting Password Reset Token (Joomla <= 1.5.6)
Lab Download: Joomla 1.5.6 dan Script attack Joomla 1.5.6
Metode otentikasi ketika melakukan reset password umumnya adalah dengan mengirimkan suatu token berupa string acak yang dikirimkan ke email user. Token ini kemudian harus dimasukkan dalam form atau dalam bentuk parameter di URL, bila token yang dimasukkan benar, maka server percaya bahwa dia adalah pemilik account yang sah karena token ini hanya dikirim ke email yang hanya bisa dibuka oleh pemilik account yang sah.
