Memprediksi output rand PHP ()

21

Saya telah membaca di banyak sumber bahwa output rand PHP () dapat diprediksi sebagai PRNG-nya, dan saya menerima itu sebagai fakta hanya karena saya melihatnya di banyak tempat.

Saya tertarik pada pembuktian konsep: bagaimana cara memprediksi hasil rand ()? Dari membaca artikel ini saya mengerti bahwa angka acak adalah angka yang dikembalikan dari daftar mulai dari pointer (seed) - tetapi saya tidak dapat membayangkan bagaimana hal ini dapat diprediksi.

Bisakah seseorang mencari tahu # acak apa yang dihasilkan melalui rand () pada saat tertentu dalam beberapa ribu tebakan? atau bahkan 10.000 tebakan? Bagaimana?

Ini muncul karena saya melihat perpustakaan auth yang menggunakan rand () untuk menghasilkan token untuk pengguna yang kehilangan kata sandi, dan saya berasumsi ini adalah celah keamanan potensial. Sejak itu saya mengganti metode dengan hashing campuran openssl_random_pseudo_bytes(), kata sandi hasign orignal, dan microtime. Setelah melakukan ini, saya menyadari bahwa jika saya berada di luar mencari, saya tidak tahu bagaimana menebak token, bahkan mengetahui itu adalah md5 dari rand ().

Erik
sumber
"tapi aku tidak bisa membayangkan bagaimana ini bisa diprediksi"? Anda perlu membaca dulu di " en.wikipedia.org/wiki/Linear_congruential_generator terlebih dahulu sehingga Anda dapat mulai membayangkan bagaimana hal itu dapat diprediksi. Kemudian Anda dapat merevisi pertanyaan Anda untuk menghilangkan keheranan dan beralih ke masalah yang lebih praktis tentang rekayasa ulang PHP. sumber fungsi rand untuk melihat cara kerjanya
S.Lott
"Saya menduga ini adalah lubang keamanan potensial"? Hanya jika Evil Hacker bisa mendapatkan kata sandi acak beberapa pengguna, gunakan tabel pelangi untuk membatalkan hash MD5 untuk memulihkan nilai asli (pra-hash) dan kemudian menjamin bahwa mereka membuat permintaan kata sandi berikutnya. Secara teoritis mungkin, saya kira. Tetapi hanya jika mereka memiliki meja pelangi yang berfungsi untuk angka acak.
S.Lott
@ S.Lott - ini bukan masalah kata sandi. Sistem ini memungkinkan Anda mengatur ulang kata sandi dan mengirimkan email kepada Anda token yang digunakan dalam URL. Token dihasilkan melalui MD5 (rand ()). Jika Anda dapat memprediksi output rand (), Anda dapat mengubah kata sandi siapa pun, tanpa memiliki hash untuk yang asli, atau mengetahui yang asli.
Erik
@Erik. Kanan. Ganti "kata sandi acak" dengan "token acak" jika itu membantu. Token hanya dapat disalahgunakan jika seseorang dapat melepaskan hash MD5 untuk memulihkan nomor acak DAN memastikan bahwa mereka akan mendapatkan nomor acak berikutnya. Memprediksi rand berikutnya hanya satu bagian kecil. Membatalkan MD5 adalah bagian yang sulit.
S.Lott
1
Perhatikan bahwa MD5 (rand ()) hanya memiliki keamanan yang sama dengan rand (). Sangat praktis untuk membangun tabel pencarian MD5 (rand ()) -> rand () untuk rangkaian angka yang sangat terbatas. Dengan domain terbatas rand (), Anda dapat mencoba brute force sederhana kecuali ada mekanisme untuk mencegah upaya berulang.
MZB

Jawaban:

28

Kemampuan untuk menebak nilai selanjutnya randterkait dengan kemampuan untuk menentukan apa srandyang dipanggil. Secara khusus, penyemaian sranddengan jumlah yang ditentukan menghasilkan hasil yang dapat diprediksi ! Dari prompt interaktif PHP:

[charles@charles-workstation ~]$ php -a
Interactive shell

php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > 

Ini bukan hanya kebetulan. Sebagian besar versi PHP * di sebagian besar platform ** akan menghasilkan urutan 97, 97, 39, 77, 93 saat srandmenggunakan 1024.

Untuk lebih jelasnya, ini bukan masalah dengan PHP, ini adalah masalah dengan implementasi randitu sendiri. Masalah yang sama muncul dalam bahasa lain yang menggunakan implementasi yang sama (atau serupa), termasuk Perl.

Kuncinya adalah bahwa setiap versi PHP waras akan memiliki pra-seeded sranddengan nilai "tidak diketahui". Oh, tapi itu tidak terlalu diketahui. Dari ext/standard/php_rand.h:

#define GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))

Jadi, ini adalah beberapa matematika dengan time(), PID, dan hasil php_combined_lcg, yang didefinisikan dalam ext/standard/lcg.c. Saya tidak akan tinggal di sini, karena mata saya berkaca-kaca dan saya memutuskan untuk berhenti berburu.

Sedikit Googling menunjukkan bahwa area lain dari PHP tidak memiliki properti generasi keacakan terbaik , dan panggilan untuk php_combined_lcgmenonjol di sini, terutama sedikit analisis ini:

Tidak hanya fungsi ini ( gettimeofday) memberikan kami stempel waktu server yang tepat pada plat perak, juga menambahkan output LCG jika kami meminta "lebih banyak entropi" (dari PHP uniqid).

Ya ituuniqid . Tampaknya nilai php_combined_lcgadalah apa yang kita lihat ketika kita melihat digit hex yang dihasilkan setelah memanggil uniqiddengan argumen kedua diatur ke nilai sebenarnya.

Sekarang, dimana kita?

Oh ya. srand.

Jadi, jika kode yang Anda coba prediksi dari nilai acak tidak menelepon srand, Anda harus menentukan nilai yang disediakan oleh php_combined_lcg, yang bisa Anda dapatkan (secara tidak langsung?) Melalui panggilan ke uniqid. Dengan nilai itu di tangan, layak untuk memaksa sisa nilai - time(), PID dan beberapa matematika. Masalah keamanan terkait adalah tentang sesi istirahat, tetapi teknik yang sama akan bekerja di sini. Sekali lagi, dari artikel:

Berikut ringkasan langkah-langkah serangan yang diuraikan di atas:
  • tunggu server untuk reboot
  • ambil nilai uniqid
  • brute memaksa benih RNG dari ini
  • polling status online untuk menunggu target muncul
  • interleave jajak pendapat status dengan jajak pendapat uniqid untuk melacak waktu server saat ini dan nilai RNG
  • ID sesi brute force terhadap server menggunakan interval waktu dan nilai RNG yang ditentukan dalam polling

Cukup ganti langkah terakhir seperti yang diminta.

(Masalah keamanan ini dilaporkan dalam versi PHP yang lebih lama (5.3.2) dari yang kita miliki saat ini (5.3.6), jadi ada kemungkinan bahwa perilaku uniqiddan / atau php_combined_lcgtelah berubah, sehingga teknik khusus ini mungkin tidak bisa diterapkan lagi. YMMV.)

Di sisi lain, jika kode Anda mencoba untuk produk panggilan srandsecara manual , maka kecuali mereka menggunakan sesuatu yang banyak kali lebih baik dari hasil php_combined_lcg, Anda mungkin akan memiliki banyak lebih mudah waktu menebak nilai dan penyemaian lokal Anda generator dengan nomor yang benar. Kebanyakan orang yang secara manual menelepon srandjuga tidak akan menyadari betapa mengerikannya ide ini, dan karenanya tidak mungkin menggunakan nilai yang lebih baik.

Perlu dicatat bahwa mt_randini juga diderita oleh masalah yang sama. Pembibitan mt_sranddengan nilai yang diketahui juga akan menghasilkan hasil yang dapat diprediksi. Mendasarkan entropi Anda openssl_random_pseudo_bytesmungkin adalah taruhan yang lebih aman.

tl; dr: Untuk hasil terbaik, jangan menabur pembuat angka acak PHP, dan demi kebaikan, jangan memaparkan uniqidkepada pengguna. Melakukan salah satu atau keduanya ini dapat menyebabkan angka acak Anda lebih mudah ditebak.


Pembaruan untuk PHP 7:

PHP 7.0 memperkenalkan random_bytesdan random_intsebagai fungsi inti. Mereka menggunakan implementasi sistem yang mendasari CSPRNG, membuat mereka bebas dari masalah yang dimiliki oleh generator nomor acak unggulan. Mereka mirip secara efektif openssl_random_pseudo_bytes, hanya tanpa memerlukan ekstensi untuk diinstal. Polyfill tersedia untuk PHP5 .


*: Patch keamanan Suhosin mengubah perilaku randdan mt_randsedemikian rupa sehingga mereka selalu mengunggah setiap panggilan. Suhosin disediakan oleh pihak ketiga. Beberapa distribusi Linux memasukkannya ke dalam paket PHP resmi mereka secara default, sementara yang lain menjadikannya pilihan, dan yang lain mengabaikannya sama sekali.

**: Bergantung pada platform dan panggilan pustaka yang mendasarinya sedang digunakan, urutan yang berbeda akan dihasilkan dari yang didokumentasikan di sini, tetapi hasilnya masih harus diulang kecuali patch Suhosin digunakan.

Charles
sumber
Terima kasih Charles - antara jawaban Anda dan membaca tautan tentang generator kongruensi linier dari Tangurena, saya merasa memiliki pemahaman yang lebih baik tentangnya. Saya sudah "tahu" bahwa menggunakan rand () dengan cara ini adalah ide yang buruk, tetapi saya tahu mengapa .
Erik
Wow, alat peraga untuk jawaban yang dijabarkan dengan seksama, terima kasih!
David Hobs
10

Untuk menggambarkan secara visual bagaimana non-acak rand()fungsi ini, berikut adalah gambar di mana semua piksel terbuat dari nilai-nilai merah, hijau dan biru "acak":

Nilai RGB acak

Biasanya tidak ada pola dalam gambar.

Saya sudah mencoba menelepon srand()dengan nilai yang berbeda, itu tidak mengubah seberapa dapat diprediksi fungsi ini.

Perhatikan bahwa keduanya tidak aman secara kriptografis dan menghasilkan hasil yang dapat diprediksi.

minipif
sumber
7

output dari PHP's rand () dapat diprediksi sebagai sebuah PRNG

Ini adalah generator kongruensi linier . Itu berarti Anda memiliki fungsi yang efektif: NEW_NUMBER = (A * OLD_NUMBER + B) MOD C. Jika Anda memetakan NEW_NUMBER vs OLD_NUMBER Anda akan mulai melihat garis diagonal. Beberapa catatan pada dokumentasi RAND PHP memberikan contoh bagaimana melakukannya.

Ini muncul karena saya melihat perpustakaan auth yang menggunakan rand () untuk menghasilkan token untuk pengguna yang kehilangan kata sandi, dan saya berasumsi ini adalah celah keamanan potensial.

Pada mesin windows, nilai maksimum RAND adalah 2 ^ 15. Ini memberi penyerang hanya 32.768 kemungkinan untuk diperiksa.

Bisakah seseorang mencari tahu # acak apa yang dihasilkan melalui rand () pada saat tertentu dalam beberapa ribu tebakan? atau bahkan 10.000 tebakan? Bagaimana?

Meskipun artikel ini bukan yang Anda cari, artikel ini menunjukkan bagaimana beberapa peneliti mengambil implementasi generator nomor acak yang ada dan menggunakannya untuk menghasilkan uang di Texas Holdem. Ada 52! deck yang mungkin dikocok, tetapi implementasinya menggunakan generator angka acak 32-bit (yang merupakan jumlah maksimum dari mt_getrandmax pada mesin windows), dan diunggulkan dengan waktu dalam milidetik sejak tengah malam. Ini mengurangi jumlah deck yang mungkin dikocok dari sekitar 2 ^ 226 menjadi sekitar 2 ^ 27 sehingga memungkinkan untuk mencari secara real time dan tahu apa yang telah ditangani.

Setelah melakukan ini, saya menyadari bahwa jika saya berada di luar mencari, saya tidak tahu bagaimana menebak token, bahkan mengetahui itu adalah md5 dari rand ().

Saya akan merekomendasikan menggunakan sesuatu dalam keluarga SHA-2 karena FB menganggap md5 rusak. Beberapa orang menggunakan google untuk mendekripsi hash md5 karena mereka sangat umum. Hanya hash sesuatu kemudian melemparkan hash ke pencarian google - pada dasarnya google telah menjadi meja pelangi raksasa .

Tangurena
sumber
1

Benar-benar lebih akurat untuk mengatakan bahwa mengingat angka yang dihasilkan secara acak, yang berikutnya relatif dapat diprediksi. Hanya ada begitu banyak angka. Tetapi itu tidak berarti bahwa Anda dapat menebaknya, lebih dari itu Anda dapat menulis sebuah program yang dapat melakukannya, cukup cepat.

pdr
sumber
1
Saya pikir angka selanjutnya sepenuhnya deterministik. Bukan "relatif" tetapi mutlak. Masalah dengan generator angka pseudo-acak adalah bahwa urutan akan lulus tes statistik. Dua angka yang berdekatan, walaupun sepenuhnya deterministik, akan memiliki sifat statistik yang sama dengan angka acak aktual.
S.Lott
1
Angka selanjutnya sepenuhnya deterministik. Itulah yang dimaksud dengan "pseudo" dalam generator angka pseudo-acak. Di sisi lain, informasi yang diperlukan untuk menentukan bahwa nomor berikutnya hampir mustahil diperoleh dalam praktiknya.
Rein Henrichs
@ S.Lott - Saya mendapat kesan bahwa suatu angka dapat muncul beberapa kali dalam 2 ^ 32 output yang mungkin dan bahwa setiap kali muncul dapat diikuti oleh nomor yang berbeda. Tetapi mengingat benih X, mengembalikan hasil Y, hasil selanjutnya akan selalu sama. Jadi, dalam praktiknya, mungkin ada beberapa angka yang mengikuti Y. Saya mungkin salah; sudah lama sejak saya benar-benar melihat PRNG.
pdr