Rangkuman Kuis Kode: PRNG Sequence Guessing

PRNG Sequence Guessing merupakan sebuah kuis yang menarik dibahas. Kuis yang berkategori security ini dapat ditemukan di laman HackerRank. PRNG yang dijadikan kuis adalah java.util.Random. Menurut penulis, kuis ini menarik untuk dijadikan bagian sesi demo ketika melakukan presentasi untuk menyadarkan pentingnya secure coding kepada pengembangan perangkat lunak yang masih pemula. Sebagai informasi saja, OWAPS telah menyarankan untuk tidak menggunakan library tersebut untuk keperluan yang sensitif sesuai berita di laman ini. Bilamana dilakukan scanning menggunakan perangkat lunak static code analysis, maka baris kode yang mengimplementasikan library tersebut akan dideteksi sebagai kerentanan.

Image Source: softwaresecured.com

Penulis berkesempatan untuk menyelesaikan kuis tersebut pada libur panjang akhir pekan paskah 2021. Lumayan untuk menghabiskan waktu untuk kegiatan yang menurut penulis bermanfaat (ini relatif -red). Pengerjaan kuis ini terdiri dari empat langkah. Langkah pertama dan kedua adalah penyiapan kode dan analisa kode di bahasa yang digunakan. Selanjutnya penulis membuat dua jenis solusi pada langkah ke tiga dan ke empat. Dalam kesempatan kali ini penulis menggunakan Golang sebagai bahasa yang digunakan.

Langkah 1 dan 2: Penyiapan Code Awal dan Analisa

Langkah pertama yang dilakukan adalah menulis ulang implementasi java.util.Random method nextInt(int) dari bahasa Java ke bahasa Golang. Referensi kode dalam bahasa Java dapat dilihat di sini. Sembari menulis baris kode di langkah pertama, pada langkah kedua dipelajari juga baris per-baris bagaimana kode-kode tersebut bekerja. Dari analisa tersebut didapati hal yang menarik bahwa terdapat kemungkinan beberapa bit dari seed dapat diketahui (leaked) hanya dengan melihat nilai keluaran dalam format biner. Dalam kasus nextInt(int) yang mengeluarkan angka acak (random number) dengan nilai batas (limit), banyaknya bit yang dapat diketahui dapat ditentukan dengan mencari faktor dari batasan nilai yang merupakan perpangkatan dari dua atau number mod 2^L di mana L adalah jumlah leaked bit.

type JavaUtilRandom struct {
    seed uint
}

func (r *JavaUtilRandom) SetSeed(seed uint) {
    r.seed = (seed ^ 0x5deece66d) & ((1 << 48) - 1)
}

func (r *JavaUtilRandom) SetSeedDirect(seed uint) {
    r.seed = seed
}

func (r *JavaUtilRandom) next(bits uint) uint {
    if bits < 1 {
        bits = 1
    } else if bits > 32 {
        bits = 32
    }
    r.seed = (r.seed*0x5deece66d + 0xb) & ((1 << 48) - 1)
    retval := r.seed >> (48 - bits)
    return retval
}

func (r *JavaUtilRandom) NextInt(n uint) int {
    if n <= 0 {
        return 0
    }

    if (n & -n) == n {
        return int((n * r.next(31)) >> 31)
    }

    bits := r.next(31)
    val := bits % n
    for (bits - val + n - 1) < 0 {
        bits = r.next(31)
        val = bits % n
    }
    return int(val)
}

func isMatched(javaPRNG *JavaUtilRandom, nums []int) bool {
    for i := 1; i < len(nums); i++ {
        if javaPRNG.NextInt(1000) != nums[i] {
            return false
        }
    }
    return true
}

func isLMatched(javaPRNG *JavaUtilRandom, nums []int) bool {
    for i := 1; i < len(nums); i++ {
        if javaPRNG.NextInt(1000)%8 != nums[i]%8 {
            return false
        }
    }
    return true
}

func isHMatched(javaPRNG *JavaUtilRandom, nums []int) bool {
    for i := 1; i < len(nums); i++ {
        if javaPRNG.NextInt(1000) != nums[i] {
            return false
        }
    }
    return true
}

Langkah 3: Kode Solusi Awal

Metode yang terpikirkan pertama kali adalah dengan melakukan enumerasi atau brute force. Enumerasi pertama untuk bagian high order bit di sebelah kiri dari bit yang telah diketahui. Selanjutnya di dalam enumerasi yang pertama dilakukan enumerasi yang kedua (nested loop). Pada enumerasi yang kedua dilakukan pencarian untuk low order bit. Baris kode yang dibuat berhasil untuk menemukan seed dan menebak random order selanjutnya yang keluar. Namun secara nilai kompleksitas algoritma yaitu O(4^N) serta waktu yang dibutuhkan masih sekitar 232 detik sehingga bila dilakukan submit akan menghasilkan time limit exceeded. Berikut potongan kode pertama dan hasil keluarannya.

// Guessing
segment1 := uint(nums[0])
found := false
for segment1 < ((1 << 32) - 1) {
    segment1 += 1000
    segment2 := uint(0)
    for segment2 < ((1 << 17) - 1) {
        currentSeed := ((segment1 << 17) | segment2)
        javaPRNG.SetSeedDirect(currentSeed)
        if isMatched(javaPRNG, nums) {
            found = true
        }
        if found {
            break
        }
        segment2++
    }
    if found {
        break
    }
}

Langkah 4: Optimasi Kode

Mikhail Egorov and Sergey Soldatov

Selanjutnya penulis mencari metode untuk mengoptimasi kode yang telah disusun sebelumnya. Penulis mendapatkan referensi dari sebuah konferensi *PHDays di tahun 2014. Dari salah satu sesi cracking disarankan untuk memisahkan pencarian. Pertama dilakukan pencarian low order bit terlebih dahulu. Baru setelahnya dilakukan enumerasi untuk high order bit*. Baris kode telah diubah memberikan nilai kompleksitas O(2^N) serta waktu yang dibutuhkan sekitar 280 ms. Optimasi yang dilakukan dapat meningkatkan performansi sehingga waktu yang dibutuhkan terpotong hingga per-1000 kali. Berikut potongan kode yang telah teroptimasi dan hasil keluarannya.

segment1 := uint(nums[0]) % 8
found := false
// Segment 2 - Low Order Bit
segment2 := uint(0)
for segment2 < ((1 << 17) - 1) {
    currentSeed := ((segment1 << 17) | segment2)
    javaPRNG.SetSeedDirect(currentSeed)
    if isLMatched(javaPRNG, nums) {
        break
    }
    segment2++
}
// Segment 1 - High Order Bit
segment1 = uint(nums[0])
for segment1 < ((1 << 32) - 1) {
    currentSeed := ((segment1 << 17) | segment2)
    javaPRNG.SetSeedDirect(currentSeed)
    if isHMatched(javaPRNG, nums) {
        found = true
    }
    if found {
        break
    }
    segment1 += 1000
}

Penutup

Saya ucapkan terima kasih bagi pembaca yang sabar membaca setiap kalimat hingga bagian ini. Kode dari dua solusi di atas dapat diakses di sini. Tetap semangat untuk belajar hal baru. Silahkan bila ada pandangan lain dari rekan pembaca dapat disampaikan di kolom komentar untuk dapat bersama-sama kita diskusikan.