Serangan Denial of Service Ditemukan pada Algoritma Hash Ruby (CVE-2011-4815)

Ditulis oleh Urabe Shyouhei tanggal 2011-12-28
Diterjemahkan oleh catcyborg

Dampak

Hal ini terkait dengan kompleksitas komputasional. Seri String yang dibuat secara spesial yang saling menabrak nilai hash mereka secara sengaja telah ditemukan. Dengan urutan itu, penyerang dapat menyebabkan serangan denial of service dengan, contohnya, memberi mereka parameter POST dari permintaan HTTP untuk aplikasi Rails Anda.

Penjelasan Rinci

Situasi ini mirip dengan yang ditemukan pada Perl pada tahun 2003. Pada seri Ruby 1.8, kami menggunakan fungsi hash deterministik untuk meng-hash sebuah string. Dalah hal ini, "deterministik" berarti tidak ada informasi lain selain string itu sendiri untuk membuat sebuah nilai hash. Jadi, Anda dapat melakukan prekalkulasi nilai hash string sebelumnya. Dengan mengumpulkan seri string yang memiliki nilai hash sama, penyerang dapat membiarkan proses Ruby membentrokkan tabel hash (termasuk instance class Hash). Atribut amortisasi O(1) tabel hash bergantung pada keseragaman distribusi nilai hash. Dengan memberikan input yang dibuat sedemikian rupa, penyerang dapat membuat tabel hash jauh lebih lambat dari yang diharapkan (yaitu O(n2) untuk membuat tabel dengan n elemen dalam hal ini).

Versi yang Terkena Dampak

  • Ruby 1.8.7-p352 dan semua versi sebelumnya.

Semua seri Ruby 1.9 tidak terkena dampak serangan seperti ini. Mereka tidak berbagi implementasi hash dengan seri Ruby 1.8.

Solusi

Solusi kami adalah mengacak fungsi hash string dengan bit acak yang dibuat PRNG. Dengan melakukan itu, nilai hash string tidak lagi deterministik. Yakni, hasil String#hash konsisten untuk lifetime proses saat ini dan akan membuat angka yang berbeda pada boot selanjutnya. Untuk merusak situasi ini, penyerang harus membuat string yang dapat menangani pengacakan tersebut. Hal ini diyakini cukup sulit.

Harap upgrade ke ruby 1.8.7-p357.

Catatan

  • Ingat bahwa solusinya tidak berarti algoritma hash kami aman secara kriptografis. Dengan kata lain, kami memperbaiki tabel hash tetapi tidak memperbaiki kelemahan String#hash. Penyerang mungkin tetap mengeksploitasinya ketika ia mendapat sepasang string dan nilai hash yang dikembalikan String#hash. Anda tidak boleh memberi tahu keluaran String#hash. Jika Anda perlu melakukan hal itu, harap pertimbangkan penggunaan algoritma hash aman. Beberapa dari algoritma tersebut (seperti SHA256) disediakan di library standar Ruby.

  • Untuk yang mengetahui algoritma hash alternatif di dalam kode kami: kami tidak mendukungnya (kode itu dinonaktifkan secara default). Dengan memilih mereka, kami anggap Anda dapat membaca C, dan Anda dapat mengerti hal yang salah dengan yang default. Pastikan pilihan Anda aman untuk resiko Anda sendiri.

Ucapan Terima Kasih

Terima kasih kepada Alexander Klink alexander.klink@nruns.com dan Julian Waelde jwaelde@cdc.informatik.tu-darmstadt.de untuk melaporkan masalah ini.

PERBAIKAN beberapa tautan terkait:

  • CVE-2011-4815 ditetapkan pada masalah ini.
  • oCERT.org menerbitkan sebuah laporan tentang hal ini.
  • JRuby merilis versi 1.6.5.1 untuk memperbaiki masalah yang sama. Alternatif Ruby lain mungkin juga mendapat masalah yang sama.
  • Akun Twitter @hashDoS mengumpulkan informasi tentang serangan bentrok hash.