it-swarm-id.com

Apa itu oracle kriptografi?

Saya menemukan istilah "kriptografi Oracle" dan meskipun sedikit googling, saya tidak dapat menemukan definisi yang jelas dan ringkas. Apa itu kriptografi Oracle dan apa fungsinya? Adakah yang bisa memberi contoh?

35
josh-cain

An Oracle adalah individu yang mengetahui nomor ponsel pribadi dewa. Ini memungkinkan dia (atau dia) untuk mendapatkan beberapa informasi yang biasanya dianggap di luar jangkauan manusia biasa, seperti sekilas masa depan. Dalam kriptografi, itu sama, kecuali bahwa tidak ada dewa yang terlibat: Oracle adalah sistem apa pun yang dapat memberikan beberapa informasi tambahan tentang suatu sistem, yang jika tidak maka tidak akan tersedia.

Sebagai contoh, pertimbangkan enkripsi asimetris dengan RSA . Tautan I standar untuk menyatakan bagaimana data harus dienkripsi dengan kunci publik. Secara khusus, enkripsi dimulai dengan operasi padding, di mana potongan data pertama kali diperluas dengan menambahkan header, sehingga panjang data yang empuk cocok dengan panjang kunci publik RSA. Header harus dimulai dengan dua byte 0x00 0x02, diikuti oleh setidaknya delapan byte non-nol acak, dan selanjutnya 0x00. Setelah data telah diisi, sekarang saatnya untuk menerapkan operasi matematika yang merupakan inti dari operasi RSA (eksponensial modular). Detail padding penting untuk keamanan.

Hasil enkripsi adalah modul integer RSA modulus, integer besar yang merupakan bagian dari kunci publik. Untuk kunci RSA 1024-bit, modulus n adalah nilai integer yang lebih besar dari 21023, tetapi lebih kecil dari 21024. Potongan data yang dienkripsi dengan benar, dengan RSA, menghasilkan nilai integer antara 1 dan n-1. Namun, padding menyiratkan beberapa struktur, seperti yang ditunjukkan di atas. Pihak dekripsi HARUS menemukan, setelah dekripsi, header PKCS # 1 yang terbentuk dengan benar, dimulai dengan 0x00 0x02 byte, diikuti oleh setidaknya delapan byte bukan nol, dan harus ada 0x00 yang menandai akhir header. Oleh karena itu, tidak semua bilangan bulat antara 1 dan n-1 adalah pesan terenkripsi RSA yang valid (kurang dari 1 setiap 65000 bilangan bulat seperti itu akan menghasilkan bantalan yang tepat saat didekripsi. ).

Mengetahui apakah modul integer yang diberikan n akan menghasilkan, setelah dekripsi, struktur pengisi yang valid, seharusnya tidak layak untuk siapa pun yang tidak mengetahui kunci privat. Pemilik kunci pribadi (dewa) memperoleh informasi itu, dan banyak lagi: jika dekripsi bekerja, pemilik kunci pribadi benar-benar mendapatkan pesan, yang merupakan titik dekripsi. Asumsikan bahwa ada adalah suatu entitas, di suatu tempat, yang dapat memberi tahu Anda apakah modulo integer yang diberikan n adalah data yang dienkripsi dengan RSA dengan valid; entitas itu tidak akan memberi Anda hasil dekripsi penuh, itu hanya akan memberi tahu Anda apakah dekripsi akan berfungsi atau tidak. Itu informasi satu-bit, pandangan sekilas tentang apa yang akan diperoleh dewa. Entitas adalah Oracle Anda: ia mengembalikan bagian dari informasi yang biasanya hanya tersedia untuk pemilik kunci pribadi.

Itu ternyata bahwa, dengan akses ke Oracle seperti itu, dimungkinkan untuk membangun kembali kunci pribadi, dengan mengirimkan bilangan bulat yang dibuat khusus modulo n (dibutuhkan satu juta atau jadi dari nilai-nilai tersebut, dan sedikit matematika, tetapi bisa dilakukan). Juga ternyata sebagian besar SSL/TLS implementasi saat itu (yaitu pada tahun 1999) secara tidak sengaja bertindak sebagai oracle: jika Anda mengirim, sebagai klien, pesan ClientKeyExchange yang dienkripsi RSA yang tidak valid, server merespons dengan pesan kesalahan tertentu ("duh, pesan ClientKeyExchange Anda bau"), sedangkan jika dekripsi bekerja, server tetap menggunakan protokol, menggunakan nilai apa pun yang didekripsi (biasanya tidak diketahui klien jika klien mengirim nilai acak , sehingga protokol gagal di kemudian hari, tetapi klien dapat melihat perbedaan antara bantalan yang valid dan tidak valid). Oleh karena itu, dengan implementasi seperti itu, penyerang dapat (setelah satu juta atau lebih koneksi gagal) membangun kembali kunci pribadi server, yang biasanya dianggap sebagai hal yang buruk.

Itulah yang dimaksud dengan: deskripsi matematis dari kebocoran data, untuk digunakan dalam bukti keamanan. Dalam kasus RSA, ini menunjukkan bahwa mengetahui apakah suatu nilai memiliki padding yang tepat atau tidak setara dengan mempelajari kunci privat (jika Anda tahu kunci privat Anda dapat mencoba dekripsi dan melihat padding untuk diri Anda sendiri; serangan Bleichenbacher menunjukkan bahwa itu juga bekerja sebaliknya).

67
Thomas Pornin

Oracle adalah sesuatu yang dapat segera (O(1)) memberi Anda jawaban untuk beberapa masalah, biasanya masalah yang tidak mungkin atau tidak mungkin. Sebagai contoh, a "Menghentikan masalah Oracle" dapat memberi tahu Anda segera apakah suatu program tertentu pada input tertentu berhenti atau tidak, meskipun masalah penghentian adalah tidak dapat dihitung bagi kami manusia biasa. Namun, kadang-kadang kita dapat membuktikan beberapa sifat yang berguna dengan berpura-pura bahwa ada oracle.

Dalam makalah kriptografi, misalnya, oracle paling sering digunakan untuk menunjukkan bahwa, bahkan jika penyerang kami memiliki akses ke beberapa Oracle yang tampaknya mustahil, mereka masih tidak akan memiliki keuntungan (signifikan) untuk menghancurkan keamanan kami. Misalnya, salah satu properti penting dari algoritma enkripsi (disebut resistensi terhadap serangan plaintext dikenal ) adalah bahwa jika seorang penyerang diberi pesan yang dienkripsi dengan kunci Anda m' dan mereka ingin mengetahui pesan asli m (atau mencari tahu kunci Anda) , kemudian memberi mereka pesan lain n dan enkripsinya dengan kunci Anda n' seharusnya tidak membantu mereka melakukannya dengan cara apa pun.

Mengambil ini secara ekstrim ( serangan plaintext yang dipilih ) : berikan penyerang sebuah Oracle yang dapat mengenkripsi atau mendekripsi sembarang pesan dengan kunci Anda kecuali untuk m dan m'. Bahkan di bawah kondisi ekstrem ini, kami ingin menunjukkan kepada enkripsi kami bahwa penyerang dengan Oracle tidak akan memiliki keuntungan dalam menemukan m (atau kunci Anda) dari penyerang tanpa Oracle. Ini berarti enkripsi kami aman dari serangan plaintext yang dipilih.


[Sunting]
Berikut adalah contoh praktis lain. Dalam pertanyaan Bisakah suatu program mengetahui apakah program lain bermain catur , kami menunjukkan bahwa tidak ada program seperti itu dengan terlebih dahulu mengasumsikan bahwa ada adalah deteksi-catur Oracle, kemudian menunjukkan keberadaannya mengarah pada ketidakmungkinan yang logis.

Oracle cryptographic adalah metode input/output kotak hitam.

Ini akan menanggapi setiap input dengan respons pseudo-acak tetapi akan selalu memberikan output yang sama untuk input tertentu.

Mereka umumnya digunakan untuk fungsi hash di mana keacakan penting untuk keamanan yang lebih tinggi.

Jelas masih akan ada masalah keamanan karena itu hanya fungsi matematika yang mengembalikan angka yang tampaknya pseudo-acak, tetapi mereka jelas lebih kuat daripada beberapa rekan mereka yang kurang acak.

Berikut ini adalah kertas padat tentang mereka dan desainnya - http://cseweb.ucsd.edu/users/mihir/papers/ro.pdf

1
doyler