Karena Pengumpulan Sampah adalah non-deterministik, mengapa tidak digunakan untuk pembuatan angka acak yang aman?

13

Saya mengerti bahwa / dev / random adalah sumber entropi yang bagus, dan biasanya digunakan - Seperti halnya saya membaca tentang GC, paling tidak di Jawa, tampaknya diterima bahwa daemon pengumpulan sampah dijalankan secara non-deterministik . Jika ini benar, mengapa kita tidak menggunakan waktu pengumpulan sampah sebagai sumber entropi alih-alih variabel / dev / acak?

random garbage-collection edthethird
sumber
7
lihat beberapa dokumen untuk fungsi rand () di C-library standar. Mereka secara khusus menyebut bahwa meskipun mereka memberi Anda apa yang tampak angka acak, mereka tidak dapat digunakan untuk keamanan. Pengumpul sampah tipikal Anda mungkin akan jatuh ke dalam kategori yang sama. Jika Anda akan menggunakannya untuk keamanan, Anda harus memastikan bahwa Anda menggunakan pengumpul sampah yang aman secara kriptografis.
DXM
15
sesuatu yang tidak deterministik masih bisa diprediksi
ratchet freak
7
Dalam hal ini "non-deterministik" adalah deskripsi yang buruk. Seorang pengumpul sampah adalah sistem yang sepenuhnya deterministik dan jika Anda memiliki pengetahuan penuh tentang keadaannya dan keadaan program yang menggunakannya, Anda dapat memprediksi hasil secara deterministik.
Gort the Robot
4
@DXM, apakah Anda tahu penerapan yang baik untuk pengumpul sampah yang aman secara kriptografis? ;)
AJMansfield
7
"Siapa pun yang menganggap metode aritmatika menghasilkan angka acak, tentu saja, dalam keadaan berdosa." - John von Neumann
Mark Adler

Jawaban:

58

"Tidak ditentukan" dan "acak" adalah dua konsep yang sama sekali berbeda.

Cara kerja yang tepat dari seorang pemulung tidak ditentukan dan tergantung pada pemungut sampah (biasanya diimplementasikan dengan semacam VM, tetapi tidak harus).

Karenanya, Anda tidak memiliki waktu yang ditentukan (yaitu deterministik) untuk mengumpulkan sampah.

Namun setiap implementasi yang diberikan akan mengikuti beberapa aturan dan ada kemungkinan besar bahwa dua program berikutnya dari program yang sama akan memiliki pola pengumpulan sampah yang sangat mirip.

Oleh karena itu entropi aktual yang disediakan oleh pengumpul sampah akan sangat rendah (dan mengetahui bagian mana yang benar-benar dapat Anda gunakan sebagai entropi akan menjadi rumit).

Sebagai perbandingan: A HashMapdi Jawa tidak menjamin urutan pengambilan untuk anggotanya (pada dasarnya karena menjamin itu akan menambah overhead yang tidak layak dibayar, sebagian besar waktu). Namun untuk diberikan implementasi dan diberikan set sisipan / kepindahan Anda dapat pasti menghitung urutan yang dihasilkan. Hanya karena tidak ada jaminan untuk pesanan yang diberikan, tidak berarti pesanan itu acak.

Joachim Sauer
sumber
20
Saya pikir itu akan menjadi pernyataan yang adil untuk mengatakan bahwa jika sebuah komputer pernah melakukan sesuatu yang sebenarnya non-deterministik, komputer itu rusak.
Schilcote
Non-deterministik juga bisa berarti bahwa ia bergantung pada beberapa keadaan eksternal untuk program yang sedang berjalan, yang itu sendiri mungkin bersifat deterministik, tetapi akan sama sekali tidak terkait dengan program itu sendiri sehingga dapat berbeda setiap kali program dijalankan.
penanggung jawab
@asmeurer Saya rasa saya tidak pernah mendengar istilah ini dalam konteks seperti itu. Bahkan, saya bahkan tidak yakin apa yang Anda maksud: Setiap program yang mengambil input eksternal (yaitu, program yang paling berguna) "bergantung pada beberapa keadaan eksternal", tetapi itu tidak membuatnya non-deterministik.
us2012
2
@Schilcote: Beberapa CPU modern menerapkan RNG yang non-deterministik (benar) dalam perangkat keras. Ini benar-benar non-deterministik hingga fisika tingkat kuantum.
MSalters
2
@Schilcote Bahkan tanpa instruksi RNG khusus (Intel RDRAND dan RDSEED) komputer tidak sepenuhnya deterministik. Beberapa pengaturan waktu tidak sepenuhnya ditentukan dan dapat bergantung pada faktor-faktor eksternal seperti suhu.
CodesInChaos
8

Pertama, kita harus berhati-hati untuk tidak jatuh ke dalam perangkap penalaran dengan memanipulasi kata-kata belaka. Sebagai contoh, kita bisa bertanya, karena NFA adalah "otomat terbatas hingga non-deterministik", mengapa kita tidak menggunakannya untuk mendapatkan angka acak? Dalam hal itu, itu karena bukan itu arti "non-deterministik" dalam NFA; pada kenyataannya, ketika kita mensimulasikan NFA, pada input yang diberikan, perilaku simulasi sangat menentukan.

"Deterministik" adalah frasa yang dimuat. Bagi seorang programmer komputer atau ilmuwan komputer, perilaku non-deterministik hanya berarti "menentukan perilaku yang tepat itu rumit untuk dipikirkan", dan tergantung pada terlalu banyak faktor, termasuk input program.

Namun, itu tidak berarti itu tidak deterministik bagi seseorang yang termotivasi untuk menyerang cryptosystem. Terkadang faktor lingkungan dan input dapat ditekankan, dan pola yang berulang muncul dari perilaku "non-deterministik".

Kaz
sumber