it-swarm-id.com

Mengapa AES tidak digunakan untuk hashing yang aman, bukan SHA-x?

Sejauh yang saya mengerti, AES diyakini sangat aman. (Saya telah membaca di suatu tempat bahwa itu pasti tidak akan rusak dalam 20 tahun ke depan, tetapi saya masih tidak yakin apakah penulisnya serius.)

DES masih tidak terlalu buruk untuk cypher lama, dan 3DES masih digunakan (mungkin tidak begitu banyak, tapi setidaknya saya melihat 3DES di about: config di Firefox).

Sepertinya cipher blok (baik) dipercaya oleh komunitas crypto.

OTOH, banyak masalah dengan fungsi hash kriptografi ditemukan.

Dari sudut pandang non-crypto-specialist: fungsi hashing dan cipher simetris adalah hal yang benar-benar sama: fungsi "acak" (dengan input dan output yang berbeda).

Jadi, mengapa tidak menggunakan hanya AES untuk hashing? Ini tampaknya hal-hal yang jelas dilakukan untuk mendapatkan keamanan AES yang kuat untuk hashing. Sebagai bonus, dapatkah implementasi perangkat keras AES membantu?

Apakah ada penjelasan sederhana tentang perbedaan nyata antara fungsi hash dan kode simetris?

46
curiousguy

Cipher blok memiliki kunci; kerahasiaan kunci adalah apa yang dibangun oleh keamanan sandi. Di sisi lain, fungsi hash tidak memiliki kunci sama sekali, dan tidak ada "data rahasia" di mana keamanan fungsi hash akan dibangun.

Block cipher adalah reversible: jika Anda tahu kuncinya, Anda dapat mendekripsi apa yang dienkripsi. Secara teknis, untuk kunci yang diberikan, cipher blok adalah permutasi ruang kemungkinan nilai blok. Fungsi hash dimaksudkan untuk menjadi non-reversibel, dan mereka tidak permutasi dengan cara apa pun.

Cipher blok beroperasi pada blok berukuran tetap (blok 128-bit untuk AES), baik untuk input maupun output. Fungsi hash memiliki output berukuran tetap, tetapi harus menerima input besar secara sewenang-wenang.

Jadi cipher blok dan fungsi hash adalah hewan yang sangat berbeda; Alih-alih mencoba untuk membedakan mereka, lebih mudah untuk melihat apa yang mereka miliki bersama: yaitu, bahwa orang-orang yang tahu cara merancang blok cipher juga cukup baik dalam merancang fungsi hash, karena alat analisis matematika mirip (cukup banyak fungsi aljabar linier dan boolean, sungguh).

Mari kita pergi untuk definisi yang lebih formal:

Cipher blok adalah keluarga permutasi yang dipilih oleh kunci. Kami menganggap spasi [~ # ~] b [~ # ~] dari n - blok bit untuk beberapa nilai tetap n; ukuran [~ # ~] b [~ # ~] kemudian 2n. Kunci adalah nilai dari spasi [~ # ~] k [~ # ~], biasanya spasi lain dari urutan m bit ( m tidak harus sama dengan n). Kunci k memilih permutasi di antara 2n! kemungkinan permutasi dari [~ # ~] b [~ # ~].

Block cipher dianggap aman selama komputasi tidak dapat dibedakan dari permutasi yang telah dipilih secara seragam dan acak di antara 2n! kemungkinan permutasi. Untuk memodelkan itu, bayangkan sebuah situasi di mana seorang penyerang diberi akses ke dua kotak hitam, satu mengimplementasikan cipher blok dengan kunci yang penyerang tidak tahu, dan yang lainnya menjadi permutasi yang benar-benar acak. Tujuan penyerang adalah untuk mengetahui yang mana. Dia dapat meminta setiap kotak mengenkripsi atau mendekripsi data apa pun yang dia inginkan. Pada serangan yang mungkin adalah untuk mencoba semua kunci yang mungkin (ada 2m kunci semacam itu) hanya satu yang ditemukan, yang menghasilkan nilai yang sama dari salah satu kotak; ini memiliki biaya rata-rata 2m-1 doa cipher. A secure block cipher adalah salah satu dari itu sehingga serangan generik ini adalah serangan terbaik.

AES didefinisikan lebih dari blok 128-bit ( n = 128) dan kunci 128-, 192- dan 256-bit.

Fungsi hash adalah fungsi tunggal, terdefinisi penuh, yang dihitung sebagai urutan bit input dengan panjang acak, dan nilai output dari panjang tetap r (misalnya r = 256 bit untuk SHA-256). Tidak ada kunci, tidak ada keluarga fungsi, hanya fungsi unik yang dapat dihitung siapa pun.

Fungsi hash h dianggap aman jika:

  • Secara komputasi tidak layak untuk menemukan preimage: diberi r - nilai bit x, tidak layak untuk menemukan m sedemikian rupa sehingga h (m) = x.
  • Secara komputasi tidak layak untuk menemukan preimage kedua: diberikan m, tidak layak untuk menemukan m ' berbeda dari m , sedemikian sehingga h (m) = h (m ').
  • Secara komputasi tidak layak untuk menemukan tabrakan: tidak layak untuk menemukan m dan m ', berbeda satu sama lain, sehingga h ( m) = h (m ').

Ada serangan umum yang dapat menemukan preimage, preimage kedua, atau collision, dengan biaya masing-masing, 2r, 2r, dan 2r/2. Jadi keamanan sebenarnya hanya dapat dicapai jika r cukup besar sehingga 2r/2 adalah biaya yang sangat besar. Dalam prakteknya, ini berarti bahwa r = 128 (fungsi hash 128-bit seperti MD5) adalah tidak cukup.

Secara informal, baik jika fungsi hash "terlihat seperti" telah dipilih secara acak dan seragam di antara fungsi-fungsi yang mungkin yang menerima input yang sama. Tetapi ini adalah properti yang tidak jelas karena kita berbicara tentang fungsi unik (probabilitas selalu secara implisit tentang rata-rata dan pengalaman berulang; Anda tidak dapat benar-benar memiliki probabilitas dengan satu fungsi tunggal). Juga, menjadi fungsi acak tidak persis sama dengan menjadi tahan terhadap tabrakan dan preimage; ini adalah perdebatan tentang Random Oracle Model .


Namun demikian, dimungkinkan untuk membangun fungsi hash dari cipher blok. Inilah yang konstruksi Merkle-Damgård lakukan. Ini mensyaratkan penggunaan pesan input sebagai key dari cipher blok; jadi cipher blok tidak digunakan sama sekali seperti yang seharusnya. Dengan AES, ini terbukti mengecewakan:

  • Ini menghasilkan fungsi hash dengan output 128-bit, yang terlalu kecil untuk keamanan terhadap teknologi yang tersedia pada 2011.
  • Keamanan fungsi hash kemudian bergantung pada tidak adanya serangan terkait kunci pada cipher blok. Serangan terkait kunci tidak benar-benar memiliki arti praktis pada cipher blok ketika digunakan untuk enkripsi; karenanya, AES tidak dirancang untuk menahan serangan seperti itu, dan, memang, AES telah a beberapa kelemahan dalam hal itu - bukan kekhawatiran untuk enkripsi, tetapi yang besar khawatir jika AES akan digunakan dalam konstruksi Merkle-Damgård.
  • Performa tidak akan baik.

Fungsi hash Whirlpool adalah desain yang dibangun di atas cipher blok terinspirasi dari AES - bukan yang asli. Block cipher itu memiliki jadwal kunci yang jauh lebih baik (dan lebih berat), yang menahan serangan terkait kunci dan membuatnya dapat digunakan sebagai inti dari fungsi hash. Juga, cipher blok itu berfungsi pada blok 512-bit, bukan blok 128-bit. Whirlpool diyakini aman. Whirlpool dikenal sangat lambat, jadi tidak ada yang menggunakannya.

Beberapa desain fungsi hash yang lebih baru telah mencoba untuk menggunakan kembali bagian dari AES - tepatnya, untuk menggunakan operasi internal yang memetakan dengan baik pada --- AES-NI petunjuk yang mana fitur prosesor Intel dan AMD baru-baru ini. Lihat misalnya ECHO dan SHAvite- ; kedua fungsi ini keduanya menerima sedikit eksposur sebagai bagian dari kompetisi SHA- dan diyakini "cukup aman". Ada yang sangat cepat pada prosesor Intel dan AMD terbaru. Pada arsitektur lain yang lebih lemah, jika kinerja fungsi hash memiliki beberapa peluang untuk benar-benar penting, fungsi-fungsi ini cukup lambat.

Ada konstruksi lain yang bisa membuat fungsi hash dari block cipher, mis. yang digunakan di Skein ; tetapi mereka juga cenderung membutuhkan blok yang lebih besar daripada yang didefinisikan AES.

Ringkasan: tidak hanya cipher blok dan fungsi hash yang sangat berbeda; tetapi gagasan membangun fungsi hash dari AES ternyata validitasnya dipertanyakan. Itu tidak mudah, dan ukuran blok AES yang terbatas adalah penghalang utama.

70
Thomas Pornin

Jawaban dasarnya adalah bahwa mereka adalah berbagai jenis algoritma. AES adalah algoritma kunci simetris. Anda tidak dapat menggunakannya dalam peran yang sama dengan RSA (algoritma kunci publik), atau SHA-256 (algoritma hashing). Mereka adalah sistem yang berbeda yang dirancang dengan sifat dan kelemahan yang sangat berbeda.

Namun, saya berhenti sejenak dan meskipun serius tentang ide ini untuk menjelaskannya selain hanya mengatakan, "Begini." Bagaimanapun, hash dalam arti universal adalah representasi data yang dapat diulang dalam ukuran tetap atau diperkecil. AES dapat menyediakannya melalui mode CBC. Namun, ada lebih banyak properti untuk hash yang aman daripada reduksi sederhana.

Algoritme hashing yang aman adalah sistem satu arah. AES mengenkripsi dan mendekripsi dengan cara yang sama (cipher simetris), dan Anda dapat membuat pemetaan 1-1 untuk setiap blok apa yang akan terjadi dengan kunci yang diberikan. Kecuali jika data dirantai dan dengan demikian bersifat lossy, Anda bisa mendekripsi "hash" AES ke sumber data.

Seseorang tidak dapat membalik proses SHA selain mencoba data input yang berbeda. Karena alasan Anda tidak dapat menggunakan SHA-x untuk mengenkripsi sesuatu, Anda tidak dapat menggunakan AES untuk hash sesuatu.

11
Jeff Ferland

Apakah ada penjelasan sederhana tentang perbedaan nyata antara fungsi hash dan kode simetris?

  • Sandi bersifat reversibel, fungsi hash tidak
  • Panjang output cipher tergantung pada panjang input; fungsi hash menghasilkan output panjang yang sama terlepas dari input
  • Perubahan bit tunggal di mana saja dalam fungsi hash kriptografi menghasilkan perubahan cascading (dramatis) dalam output hash. Sebagai aturan, ini tidak benar untuk cipher.
  • Cipher membutuhkan kunci, hash tidak

Desain dan tujuan keduanya secara fundamental berbeda dan mereka tidak dapat dipertukarkan.

9
tylerl

Anda pada dasarnya dapat mengubah blok cipher menjadi fungsi hash menggunakan konstruksi Merkle-Damgard dan pada dasarnya Anda dapat mengubah fungsi hash menjadi blok cipher menggunakan Feistel-networks jika Anda mendefinisikan fungsi F Feistel dengan cara berikut.

F(half_block, round_key) = hash(concatenate(half_block, round_key))

Tapi itu cukup tidak efisien (butuh waktu lama untuk menghitung), karena F sudah mahal untuk dihitung (ini adalah algoritma iteratif menggunakan e. 80 "putaran" internal dalam kasus SHA-512) dan untuk struktur Feistel, F sendiri diulang beberapa kali. Katakanlah Anda memiliki jaringan Feistel 20-tahap dengan fungsi putaran F 80-putaran, Anda melakukan 1600 SHA-2 "putaran" per blok. Ini juga mengarah pada ukuran blok yang agak besar (dua kali lipat dari ukuran fungsi hash), e. g. Blok cipher 1024-bit jika Anda menggunakan SHA-512 sebagai fungsi hash.

Tapi secara praktis, itu tidak selalu "tidak aman". Hanya saja "cipher blok" yang tersedia (bukan permutasi acak pseudorandom - bukan permutasi seperti dalam permutasi bit/byte, tetapi permutasi dalam arti pemetaan bijektif antara "semua blok input yang mungkin" dan "semua blok output yang mungkin") jauh lebih banyak efisien, lebih banyak digunakan dan karena itu lebih teliti dianalisis untuk sifat menjadi permutasi pseudorandom yang baik. Jika Anda memiliki daya komputasi untuk dihamburkan, gunakan SHA-512 dalam jaringan Feistel sebagai blok cipher. Kemungkinannya setidaknya itu tidak akan kurang aman daripada AES (asalkan Anda menambahkan jadwal kunci yang baik untuk menurunkan "kunci putaran"), namun itu akan membutuhkan banyak siklus CPU untuk memproses blok.

3
no.human.being

M. Abel benar. Contoh lain dari AES yang digunakan sebagai hash adalah AES-CBC atau AES-PCBC.

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_Cipher_Block_Chaining_.28PCBC.29

Jika CBC atau PCBC atau bahkan CFB dijalankan pada "file" dengan dan tanpa kesalahan, blok terakhir akan berbeda.

Ini tidak efisien, tetapi bisa dilakukan. Logikanya adalah: "Jika yang Anda miliki adalah palu, semuanya tampak seperti paku." Hal yang sama berlaku untuk AES. Mungkin ada cara yang lebih baik untuk hash, tetapi jika semua yang Anda miliki adalah AES. . .

0
aesuser