Bagaimana sistem operasi membuat entropi untuk benih acak?

Di Linux, file /dev/randomdan/dev/urandom file adalah sumber pseudo-random byte yang memblokir dan non-blocking.

Mereka dapat dibaca sebagai file normal:

$ hexdump /dev/random
0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa
0000010 5652 1f08 ccb8 9ee2 d85c 7c6b ddb2 bcbe
0000020 f841 bd90 9e7c 5be2 eecc e395 5971 ab7f
0000030 864f d402 74dd 1aa8 925d 8a80 de75 a0e3
0000040 cb64 4422 02f7 0c50 6174 f725 0653 2444
...

Banyak varian unix lainnya menyediakan /dev/randomdan /dev/urandomjuga, tanpa perbedaan pemblokiran / non-pemblokiran.

Setara Windows adalah CryptGenRandom()fungsinya .

Bagaimana sistem operasi menghasilkan pseudo-randomness?

Judul dan isi pertanyaan Anda mengajukan dua pertanyaan berbeda: bagaimana OS menciptakan entropi (ini harus benar-benar diperoleh entropi), dan bagaimana ia menghasilkan pseudo-randomness dari entropi ini. Saya akan mulai dengan menjelaskan perbedaannya.

Dari mana asal keacakan?

Random number generator (RNG) terdiri dari dua jenis:

• Pseudo-random number generator (PRNG), juga disebut generator bit acak deterministik (DRBG) atau kombinasinya, adalah algoritma deterministik yang mempertahankan keadaan internal variabel ukuran-tetap dan menghitung outputnya dari keadaan itu.
• Hardware number number generator (HRNG), juga disebut generator nomor acak "benar", didasarkan pada fenomena fisik. "Benar" sedikit keliru, karena tidak ada sumber informasi yang diketahui benar-benar acak , hanya sumber informasi yang tidak diketahui dapat diprediksi.

Beberapa aplikasi, seperti simulasi fenomena fisik, dapat berupa konten dengan angka acak yang lulus tes statistik. Aplikasi lain, seperti pembuatan kunci kriptografi, membutuhkan properti yang lebih kuat: tidak dapat diprediksi . Ketidakpastian adalah properti keamanan, bukan (hanya) properti statistik: itu berarti bahwa musuh tidak dapat menebak output dari generator nomor acak. (Lebih tepatnya, Anda dapat mengukur kualitas RNG dengan mengukur probabilitas musuh untuk menebak setiap bit dari output RNG. Jika probabilitasnya berbeda dari 1/2, RNG buruk.)

Ada fenomena fisik yang menghasilkan data acak dengan sifat statistik yang baik - misalnya, peluruhan radioaktif, atau beberapa pengamatan astronomi dari kebisingan latar belakang, atau fluktuasi pasar saham. Pengukuran fisik semacam itu perlu dikondisikan ( memutihkan ), untuk mengubah distribusi probabilitas yang bias menjadi distribusi probabilitas yang seragam. Pengukuran fisik yang diketahui semua orang tidak baik untuk kriptografi: fluktuasi pasar saham mungkin bagus untuk geohashing , tetapi Anda tidak dapat menggunakannya untuk menghasilkan kunci rahasia .

Kriptografi membutuhkan kerahasiaan : musuh tidak harus bisa mengetahui data yang masuk ke pengkondisian. Ada generator nomor acak pseudo-acak aman (CSPRNG): algoritma PRNG yang outputnya cocok untuk digunakan dalam aplikasi kriptografi, selain memiliki sifat statistik yang baik . Salah satu properti yang membuat CSPRNG aman secara kriptografis adalah bahwa outputnya tidak memungkinkan musuh untuk merekonstruksi keadaan internal (mengetahui semua bit tetapi yang dihasilkan oleh CSPRNG tidak membantu menemukan bit yang hilang). Saya tidak akan membahas cara membuat CSPRNG karena itu bagian yang mudah - Anda dapat mengikuti resep yang diberikan oleh kriptografer profesional (gunakan standaralgoritma, seperti Hash_DRBG, HMAC_DRBG atau CTR_DRBG dari NIST SP 800-90A ) atau ANSI X9.31 PRNG . CSPRNG membutuhkan dua properti dari negaranya agar aman:

• Negara harus dirahasiakan dari awal dan setiap saat (meskipun paparan negara tidak akan mengungkapkan hasil masa lalu).
• Status harus linier: RNG tidak boleh dimulai dua kali dari status yang sama.

Arsitektur generator angka acak

Dalam praktiknya, hampir semua generator angka acak yang baik menggabungkan CSPRNG dengan satu atau lebih sumber entropi . Singkatnya, entropi adalah ukuran dari ketidakpastian sumber data. Mendasarkan generator nomor acak murni pada perangkat keras RNG sulit:

• Data fisik mentah kemungkinan membutuhkan pengkondisian, untuk mengubah data probabilistik menjadi distribusi yang seragam.
• Keluaran dari sumber keacakan harus dirahasiakan.
• Sumber entropi seringkali lambat dibandingkan dengan permintaan.

Jadi RNG dalam sistem operasi hampir selalu berfungsi seperti ini :

1. Akumulasi entropi yang cukup untuk membangun keadaan internal yang tidak dapat diprediksi.
2. Jalankan CSPRNG , menggunakan entropi terakumulasi sebagai benih, yaitu sebagai nilai awal dari kondisi internal.
3. Secara opsional, campurkan entropi tambahan ke dalam kondisi internal secara berkala. (Ini tidak sepenuhnya diperlukan, karena entropi tidak "dikonsumsi" pada tingkat yang terukur . Ini membantu melawan ancaman tertentu yang membocorkan kondisi RNG tanpa membahayakan keseluruhan sistem.)

Layanan pembuatan bilangan acak adalah bagian dari pekerjaan sistem operasi, karena pengumpulan entropi memerlukan akses ke perangkat keras, dan sumber entropi merupakan sumber daya bersama: sistem operasi harus mengumpulkannya dan mendapatkan output dari mereka yang sesuai dengan aplikasi. Pengondisian semu acak dari sumber entropi diperlukan dalam sistem operasi; itu mungkin juga aman secara kriptografis, karena ini pada dasarnya tidak lebih sulit (dan diperlukan pada sistem operasi di mana aplikasi tidak saling percaya; pada sistem yang sepenuhnya kooperatif, setiap aplikasi harus menjalankan CSPRNG sendiri secara internal jika sistem operasinya toh tidak menyediakannya).

Sebagian besar sistem dengan penyimpanan persisten akan memuat seed RNG dari disk (saya akan menggunakan "disk" sebagai singkatan untuk segala jenis penyimpanan persisten) ketika mereka boot, dan menimpa seed dengan beberapa data pseudo-acak segar yang dihasilkan dari seed itu, atau jika tersedia dengan data acak yang dihasilkan dari seed tersebut ditambah sumber entropi lain. Dengan cara ini, bahkan jika entropi tidak tersedia setelah reboot, entropi dari sesi sebelumnya digunakan kembali.

Harus berhati-hati tentang negara yang diselamatkan. Ingat bagaimana saya mengatakan negara harus linier? Jika Anda mem-boot dua kali dari kondisi disk yang sama, Anda akan mendapatkan output RNG yang sama. Jika ini kemungkinan di lingkungan Anda, Anda perlu sumber entropi lain. Berhati-hatilah saat memulihkan dari cadangan, atau saat mengkloning mesin virtual . Salah satu teknik untuk kloning adalah mencampur entropi yang disimpan dengan beberapa data lingkungan yang dapat diprediksi tetapi unik (misalnya waktu dan alamat MAC); berhati-hatilah bahwa jika data lingkungan dapat diprediksi, siapa pun yang memiliki keadaan VM yang disimpan dapat merekonstruksi benih instance VM bercabang dua.

Sumber entropi

Menemukan (dan menggunakan dengan benar) sumber entropi adalah bagian yang paling menantang dari pembuatan bilangan acak dalam sistem operasi. Sumber entropi yang tersedia tentu akan tergantung pada perangkat keras dan di lingkungan mana perangkat keras berjalan.

Jika Anda beruntung, perangkat keras Anda menyediakan periferal yang dapat digunakan sebagai sumber entropi: generator nomor acak perangkat keras , baik yang berdedikasi maupun dengan tujuan sampingan. Sebagai contoh:

• kebisingan termal
• kebisingan longsor dari kebisingan longsor
• berbagai jenis (kombinasi) osilator , seperti cincin osilator
• peluruhan radioaktif
• berbagai fenomena kuantum yang tidak bisa saya jelaskan
• kebisingan akustik
• kebisingan kamera

NIST SP800-90B menyediakan pedoman desain untuk perangkat keras RNG. Mengevaluasi perangkat keras RNG sulit . Perangkat keras RNG biasanya adalah binatang yang halus, yang perlu digunakan dengan hati-hati: banyak jenis memerlukan waktu setelah boot dan beberapa waktu di antara bacaan agar tidak stabil, mereka sering peka terhadap kondisi lingkungan seperti suhu, dll.

Prosesor Intel x86-64 berbasis pada arsitektur Ivy Bridge memberikan RdRandinstruksi yang menyediakan output dari CSPRNG yang diunggulkan oleh noise termal . Sebagian besar prosesor smartphone menyertakan sumber entropi perangkat keras, meskipun Android tidak selalu menggunakannya.

Sistem yang tidak memiliki sumber entropi yang kuat harus dilakukan dengan menggabungkan sumber entropi yang lemah dan berharap ( memastikan kata yang terlalu kuat) bahwa mereka sudah cukup. Pergerakan mouse acak sangat populer untuk mesin klien, dan Anda mungkin telah melihat acara keamanan oleh program kriptografi tertentu yang meminta Anda untuk memindahkan mouse (meskipun pada sistem operasi PC abad ke-21 OS akan memiliki akumulasi entropi tanpa aplikasi yang perlu repot ).

Jika Anda ingin melihat contoh, Anda dapat melihat Linux, tetapi berhati-hatilah karena itu tidak sempurna . Secara khusus, /dev/randomblok terlalu sering (karena blok sampai cukup entropi tersedia, dengan gagasan entropi yang terlalu konservatif), sedangkan /dev/urandomhampir selalu baik kecuali pada boot pertama tetapi tidak memberikan indikasi ketika tidak memiliki cukup entropi. Linux memiliki driver untuk banyak perangkat HRNG , dan mengakumulasi entropi dari berbagai perangkat (termasuk perangkat input ) dan timing disk .

Jika Anda memiliki penyimpanan persisten (rahasia), Anda dapat menggunakannya untuk menyimpan entropi dari satu boot ke boot berikutnya, seperti yang ditunjukkan di atas. The boot pertama adalah waktu yang halus: sistem mungkin dalam keadaan yang cukup diprediksi pada saat itu, terutama pada perangkat yang diproduksi secara massal yang pada dasarnya beroperasi dari pabrik dengan cara yang sama. Beberapa perangkat tertanam yang memiliki penyimpanan persisten dilengkapi dengan benih awal di pabrik (diproduksi oleh RNG yang berjalan pada komputer di pabrik). Dalam lingkungan server yang tervirtualisasi, entropi awal dapat ditentukan ketika membuat mesin virtual dari host atau dari server entropi.

Perangkat yang tidak diunggulkan adalah masalah yang tersebar luas dalam praktiknya - sebuah studi tentang kunci RSA publik menemukan bahwa banyak server dan perangkat memiliki kunci yang dihasilkan dengan RNG yang buruk, kemungkinan besar PRNG yang baik yang tidak diunggulkan secara kurang memadai. Sebagai perancang OS, Anda tidak dapat menyelesaikan masalah ini sendiri: itu adalah tugas entitas yang mengendalikan rantai penyebaran untuk memastikan bahwa RNG akan diunggulkan dengan benar saat boot pertama. Tugas Anda sebagai perancang OS adalah untuk menyediakan RNG yang tepat, termasuk antarmuka untuk menyediakan unggulan pertama, dan untuk memastikan pensinyalan kesalahan yang tepat jika RNG digunakan sebelum diunggulkan dengan benar.

Selain jawaban Gilles, interupsi juga dapat digunakan untuk membangun entropi. Di Linux misalnya, saat menambahkan interrupt handler, Anda dapat menentukan apakah terjadinya interupsi ini harus digunakan sebagai kontribusi ke kumpulan entropi kernel.

Tentu saja ini seharusnya tidak menjadi kasus dengan interupsi yang penyerang mungkin dapat menentukan. Sebagai contoh, sekilas lalu lintas jaringan (yaitu interupsi yang dihasilkannya) tampaknya menjadi sumber keacakan yang baik. Namun, penyerang mungkin dapat memanipulasi traffic Anda sedemikian rupa sehingga ia kemudian dapat memprediksi keacakan yang Anda butuhkan untuk beberapa operasi.