Jaminan Kekerasan untuk AES

14

Banyak cryptosystem kunci publik memiliki beberapa jenis keamanan yang dapat dibuktikan. Sebagai contoh, cryptosystem Rabin terbukti sekeras pemfaktoran.

Saya bertanya-tanya apakah jenis keamanan yang terbukti seperti itu ada untuk cryptosystem kunci-rahasia, seperti AES. Jika tidak, apa bukti bahwa memecahkan cryptosystems seperti itu sulit? (selain resistensi terhadap serangan coba-coba)

Catatan: Saya kenal dengan operasi AES (AddRoundKey, SubBytes, ShiftRows, dan MixColumns). Tampaknya kekerasan AES berasal dari operasi MixColumns, yang pada gilirannya harus mewarisi kesulitannya dari beberapa masalah sulit di Galois Fields (dan dengan demikian, aljabar). Bahkan, saya dapat menyatakan kembali pertanyaan saya sebagai: " Masalah aljabar keras mana yang menjamin keamanan AES?"

cr.crypto-security algebra algebraic-complexity MS Dousti
sumber

Jawaban:

8

MIXCOLUMNS mencegah serangan yang hanya berfokus pada beberapa S-box, karena pencampuran kolom mengharuskan semua S-box untuk berpartisipasi dalam enkripsi. (Para desainer Rijndael menyebut ini "strategi jejak lebar.") Alasan analisis S-box sulit adalah karena penggunaan operasi inversi bidang yang terbatas. Pembalikan "memuluskan" tabel distribusi entri S-box, sehingga entri muncul (hampir) seragam, yaitu, tidak dapat dibedakan dari distribusi acak tanpa kunci. Kombinasi dari dua fitur itulah yang membuat Rijndael terbukti aman terhadap serangan yang diketahui.

Sebagai tambahan, buku The Design of Rijndael adalah bacaan yang sangat bagus, dan membahas teori dan filosofi kriptografi.

Aaron Sterling
sumber
1
Penjelasan yang bagus. Terima kasih. Sebenarnya, saya memiliki akses ke buku itu, tetapi tidak tahu bagian mana yang harus dibaca (mengenai pertanyaan saya). Apakah Anda menyarankan bab atau bagian khusus?
MS Dousti
3
Saya membacanya lebih dari dua tahun yang lalu, di luar perpustakaan, jadi saya tidak memiliki daftar isi di depan saya, dan saya tidak yakin saya bisa memberikan jawaban konkret untuk pertanyaan Anda, kecuali bahwa saya suka caranya mereka merancang S-box agar mudah diimplementasikan. Namun, satu hal yang dapat saya sarankan adalah penjelasan Stinson tentang AES dan jaringan substitusi-permutasi lainnya dalam Kriptografi: Teori dan Praktik. Ini Bab 3 dari edisi yang saya miliki, dan sepertinya Anda dapat mengunduh buku ini secara gratis di tautan ini: ebookee.com/…
Aaron Sterling
1
Terima kasih telah menyarankan buku Stinson. Bisakah Anda juga melihat Daftar Isi Desain Rijndael, dan melihat apakah itu mengingatkan sesuatu yang bermanfaat?
MS Dousti
2
Terima kasih untuk tautannya! :-) Ya, bagian 3.6 dan bab 5 sangat menarik bagi saya, karena mereka membahas "mengapa," bukan hanya "apa."
Aaron Sterling
10

Seperti yang dikatakan David, kami tidak memiliki pengurangan seperti itu untuk AES. Namun, ini tidak berarti bahwa kriptosistem Rabin atau RSA lebih aman daripada AES. Bahkan, saya akan mempercayai (setidaknya satu arah, mungkin juga pseudorandomess juga) keamanan cipher blok seperti AES / DES dll. (Mungkin dengan sedikit lebih banyak putaran daripada standar digunakan) lebih dari asumsi bahwa anjak piutang sulit, justru karena tidak ada struktur aljabar dan jadi lebih sulit untuk membayangkan bahwa akan ada semacam algoritma terobosan.

Seseorang dapat membuat cipher blok langsung dari fungsi satu arah, yang merupakan asumsi minimal untuk banyak kriptografi, tetapi konstruksi yang dihasilkan akan sangat tidak efisien dan karenanya tidak digunakan.

Boaz Barak
sumber
Terima kasih Boaz. Saya pikir konstruksi Luby-Rackoff adalah salah satu yang menyediakan pseudorandomess yang dapat dibuktikan berdasarkan struktur seperti DES, kan?
MS Dousti
3
Iya. Lebih tepatnya, Anda mulai dengan fungsi satu arah, mengubahnya menjadi generator pseudorandom menggunakan Hastad, Impagliazzo, Luby, Levin, lalu mengonversinya menjadi fungsi pseudorandom menggunakan Goldreich, Goldwasser, Micali, kemudian benar-benar menggunakan Luby-Rackoff untuk mengubahnya permutasi pseudorandom (yaitu, block ci pher)
Boaz Barak
6

Karena seseorang dapat mengubah skema enkripsi kunci publik apa pun menjadi skema kunci rahasia dengan cara yang umum, Anda dapat memperoleh skema kunci rahasia dengan jaminan keamanan yang dapat dibuktikan serupa.

Tetapi jawaban itu luar biasa: untuk blockcipher yang dikerahkan khas, kita tidak memiliki analisis keamanan yang dapat dibuktikan dalam pengertian masalah reduksi menjadi komputasi. Ada proposal untuk blockciphers dengan pengurangan keamanan, tetapi bagasi komputasi yang diperlukan untuk memfasilitasi pengurangan menjadikannya tidak kompetitif dengan skema yang lebih efisien seperti algoritma AES.

Yang menarik, komunitas keamanan yang dapat dibuktikan secara umum sepakat bahwa mengambil suara keamanan blockcipher (permutasi acak acak) sebagai asumsi, dan kemudian menguranginya ketika menganalisis protokol tingkat tinggi yang menggunakan blockcipher sebagai komponen. Yaitu, tidak seperti beberapa tantangan lain dalam desain protokol aman, tampaknya cukup untuk mempercayai intuisi cryptanalysts untuk keamanan ketika datang ke blockciphers.

David Cash
sumber