it-swarm-id.com

Mengapa fungsi hash satu arah? Jika saya mengetahui algoritma, mengapa saya tidak bisa menghitung input dari itu?

Mengapa hash kata sandi tidak dapat direkayasa ulang?

Saya telah melihat ini sejak lama dan telah membaca banyak tentang itu, tetapi saya tidak dapat menemukan penjelasan mengapa hal itu tidak dapat dilakukan. Sebuah contoh akan membuatnya lebih mudah untuk memahami pertanyaan saya dan untuk membuat hal-hal sederhana kita akan mendasarkannya pada algoritma hashing yang tidak menggunakan garam ( LanMan ).

Katakan kata sandi saya adalah "Kata Sandi". LanMan akan hash ini dan menyimpannya di database. Program-program crack dapat memaksa ini dengan hashing menebak kata sandi yang Anda berikan. Kemudian membandingkan hash yang dihasilkan dengan hash dalam database. Jika ada kecocokan, itu berhasil kata sandi.

Mengapa, jika cracker kata sandi mengetahui algoritma untuk mengubah kata sandi teks menjadi hash, tidak bisakah itu membalikkan proses untuk menghitung kata sandi dari hash?

Pertanyaan ini adalah Pertanyaan Keamanan IT Minggu Ini.
Baca tanggal 24 Feb 2012 entri blog untuk lebih jelasnya atau kirim milik Anda sendiri Pertanyaan dalam Pekan.

231
Mucker

Biarkan saya menemukan "algoritma hashing kata sandi" sederhana untuk menunjukkan kepada Anda cara kerjanya. Berbeda dengan contoh lain di utas ini, ini sebenarnya layak, jika Anda dapat hidup dengan beberapa batasan kata sandi yang aneh. Kata sandi Anda adalah dua bilangan prima besar, x dan y. Misalnya :

x = 48112959837082048697
y = 54673257461630679457

Anda dapat dengan mudah menulis program komputer untuk menghitung xy dalam O ( [~ # ~] n [~ # ~ ] ^ 2) waktu, di mana [~ # ~] n [~ # ~] adalah jumlah digit di x dan y. (Pada dasarnya itu berarti dibutuhkan empat kali asalkan angkanya dua kali lebih panjang. Ada algoritma yang lebih cepat, tetapi itu tidak relevan.) Simpan xy di basis data kata sandi.

x*y = 2630492240413883318777134293253671517529

Seorang anak di kelas lima, diberi kertas goresan yang cukup, bisa mengetahui jawabannya. Tetapi bagaimana Anda membalikkannya? Ada banyak algoritma yang dirancang orang untuk memfaktorkan sejumlah besar, tetapi bahkan algoritma terbaik pun lambat dibandingkan dengan seberapa cepat Anda dapat mengalikan x dengan y. Dan tidak ada algoritma yang dapat dilakukan oleh siswa kelas lima, kecuali angkanya sangat kecil (misalnya, x = 3, y = 5).

Itulah properti kunci: perhitungannya jauh lebih mudah daripada maju. Untuk banyak masalah, Anda harus menemukan algoritma yang sama sekali baru untuk membalikkan perhitungan.

Ini tidak ada hubungannya dengan fungsi injeksi atau bijective. Ketika Anda meretas kata sandi, seringkali tidak masalah jika Anda mendapatkan kata sandi yang sama atau jika Anda mendapatkan kata sandi yang berbeda dengan hash yang sama. Fungsi hash dirancang sehingga sulit untuk membalikkannya dan mendapatkan jawaban apa pun, bahkan kata sandi yang berbeda dengan hash yang sama. Dalam crypto-speak: fungsi hash yang rentan terhadap serangan preimage sama sekali tidak berharga. (Algoritma hashing kata sandi di atas adalah injeksi jika Anda memiliki aturan yang x < y. )

Apa yang dilakukan ahli kriptografi? Kadang-kadang, mereka mencoba mencari algoritma baru untuk membalikkan fungsi hash (pra-gambar). Mereka melakukan persis apa yang Anda katakan: menganalisis algoritme dan mencoba untuk membaliknya. Beberapa algoritma telah dibalik sebelumnya, lainnya tidak.

Latihan untuk pembaca: Misalkan database kata sandi berisi entri berikut:

3521851118865011044136429217528930691441965435121409905222808922963363310303627

Apa passwordnya? (Yang ini sebenarnya tidak terlalu sulit untuk komputer.)

Catatan Kaki: Karena sedikitnya jumlah kata sandi yang dipilih orang dalam praktiknya, hash kata sandi yang baik tidak hanya sulit untuk dihitung mundur tetapi juga memakan waktu untuk menghitung ke depan, untuk memperlambat serangan kamus. Sebagai lapisan perlindungan lainnya, garam acak mencegah penggunaan tabel serangan yang dikomputasi sebelumnya (seperti "Tabel pelangi").

Catatan Kaki 2: Bagaimana kita tahu bahwa sulit untuk membalik fungsi hash? Sayangnya, kami tidak melakukannya. Kami hanya tidak tahu cara mudah untuk membalikkan fungsi hash. Membuat fungsi hash yang terbukti sulit untuk dibalik adalah grail suci desain fungsi hash, dan itu belum tercapai (mungkin itu tidak akan pernah terjadi).

235
Dietrich Epp

Nah, itu pertanyaan yang bagus.

Pertama-tama kita harus memberikan presisi: banyak fungsi satu arah, khususnya fungsi hash seperti yang biasa digunakan dalam kriptografi, menerima input dari ruang yang jauh lebih besar daripada ruang nilai output. Sebagai contoh, SHA-256 didefinisikan untuk input yang terdiri dari string hingga 18446744073709551615 bit; ada 218446744073709551616-1 input yang mungkin, tetapi karena output selalu merupakan urutan 256 bit, hanya ada 2256 kemungkinan keluaran untuk SHA-256. Seharusnya, beberapa input berbeda menghasilkan output yang sama. Oleh karena itu, untuk output yang diberikan SHA-256, tidak mungkin untuk memulihkan secara ambigu input yang digunakan, tetapi, mungkin, dimungkinkan untuk menghitung input yang menghasilkan nilai output yang diberikan. Preimage resistance adalah tentang itu: kesulitan menemukan input yang cocok untuk suatu output (terlepas dari bagaimana output itu diperoleh di tempat pertama).

Jadi kita berbicara tentang fungsi yang semua orang dapat hitung dari input apa pun (menggunakan program yang diketahui publik, tidak ada nilai rahasia yang terlibat - kita tidak berbicara tentang enkripsi).


Apa kata akademisi

Tidak jelas apakah fungsi satu arah dapat benar-benar ada. Saat ini, kami memiliki banyak fungsi yang tidak ada yang tahu cara membalikkannya; tetapi ini tidak berarti bahwa mereka tidak mungkin untuk membalikkan, dalam pengertian matematika. Perhatikan, meskipun, tidak terbukti bahwa fungsi satu arah tidak dapat ada, jadi harapan tetap ada. Beberapa orang menduga bahwa apakah fungsi satu arah mungkin ada atau tidak bisa menjadi salah satu dari pernyataan matematika yang menjengkelkan ini yang tidak dapat dibuktikan atau dibantah ( teorema Gödel membuktikan bahwa hal-hal seperti itu harus ada). Tetapi tidak ada bukti untuk itu.

Oleh karena itu, tidak ada bukti bahwa fungsi hash yang diberikan benar-benar tahan terhadap preimage.

Ada beberapa fungsi yang dapat dihubungkan dengan masalah-masalah sulit yang terkenal. Misalnya, jika n adalah produk dari dua bilangan prima besar, maka fungsi x x2 mod n sulit untuk dibalikkan: mampu menghitung akar kuadrat modulo bilangan bulat non-prime n ( secara umum) setara dengan mampu faktor n , dan masalah itu diketahui sulit. Tidak terbukti sulit, ingatlah; hanya bahwa matematikawan telah mencoba untuk faktor faktor bilangan bulat besar efisien (setidaknya) 2500 tahun terakhir, dan meskipun beberapa kemajuan telah dibuat, tidak ada orang pintar ini yang menemukan algoritma yang benar-benar mematikan untuk itu. Rekor dunia untuk faktorisasi "RSA modulus" (produk dari dua bilangan prima besar yang dipilih secara acak dengan panjang yang sama) adalah bilangan bulat 768-bit .

Beberapa fungsi hash berdasarkan "masalah sulit" seperti itu telah diusulkan; lihat misalnya MASH-1 dan MASH-2 (pada masalah RSA ) dan ECOH ( dengan kurva elips). Hanya beberapa fungsi yang ada, karena:

  • Mengubah "masalah sulit" menjadi fungsi hash yang aman tidaklah mudah; ada banyak masalah rumit. Sebagai contoh, saat mengekstraksi modulo akar kuadrat yang non-prime n adalah biasanya keras, ada nilai yang ekstraksi akar kuadratnya adalah mudah.

  • Kinerja fungsi hash seperti itu cenderung, katakanlah, kurang optimal. Seperti 100x lebih lambat dari SHA-1 yang lebih umum digunakan.

Cara yang lebih "standar" untuk membangun fungsi hash adalah mengumpulkan kriptografer dan mengunyah beberapa desain yang diusulkan; fungsi yang bertahan dari upaya cryptanalytic selama beberapa tahun kemudian dianggap "mungkin kuat". Kompetisi SHA- adalah upaya seperti itu; pemenang harus diumumkan akhir tahun ini. Pada 51 kandidat (mereka yang berhasil dalam langkah administrasi), 14 dipertahankan untuk "putaran 2" dan 14 ini relatif telah diamati dengan cermat oleh banyak kriptografer, dan tidak satupun dari mereka menemukan sesuatu yang benar-benar layak dikatakan tentang fungsi. Daftar ini telah dikurangi menjadi 5 dan selanjutnya akan dikurangi menjadi 1 "segera", tetapi tidak untuk alasan keamanan (sebagian besar data aktual adalah tentang kinerja, bukan perlawanan).


Apa yang membuat MD5 sulit untuk dibalik

Karena kita tidak tahu bagaimana cara membuktikan bahwa suatu fungsi sulit untuk dibalik, yang terbaik yang bisa kita lakukan adalah mencobanya pada fungsi tertentu, sehingga mendapat " intuisi "tentang bagaimana fungsi mencapai resistensi yang nyata.

Saya memilih MD5 , yang terkenal. Ya, MD5 adalah "rusak" , tapi itu untuk tabrakan, bukan preimage. Ada adalah diketahui serangan preimage yang, setidaknya secara teoritis, lebih cepat daripada cara generik ("cara generik" adalah "keberuntungan", yaitu mencoba masukan sampai kecocokan ditemukan, dengan biaya rata-rata 2128 evaluasi karena MD5 memiliki output 128-bit; the serangan Sasaki-Aoki memiliki biaya 2123.4, yang lebih rendah, tetapi masih terlalu tinggi untuk benar-benar dicoba, sehingga hasilnya masih teoritis). Tetapi MD5 relatif sederhana dan telah menahan serangan cukup lama, jadi ini adalah contoh yang menarik.

MD5 terdiri dari sejumlah evaluasi "fungsi kompresi" pada blok data. Pesan input pertama kali diisi, sehingga panjangnya menjadi kelipatan 512 bit. Ini kemudian dibagi menjadi blok-blok 512-bit. Kondisi berjalan 128-bit (ditahan dalam empat variabel 32-bit yang disebut [~ # ~] a [~ # ~] , [~ # ~ ] b [~ # ~] , [~ # ~] c [~ # ~] dan [~ # ~] d [~ # ~] ) diinisialisasi ke nilai konvensional, kemudian diproses dengan fungsi kompresi . Fungsi kompresi mengambil status running dan satu blok pesan 512-bit, dan mencampurkannya ke nilai baru untuk status running. Ketika semua blok pesan telah diproses, nilai akhir dari status yang sedang berjalan adalah output hash.

Jadi mari kita berkonsentrasi pada fungsi kompresi. Ini berfungsi seperti ini:

  • Input: keadaan berjalan ( ABC D) dan blok pesan [~ # ~] m [~ # ~] . Blok pesan adalah 512 bit, kami membaginya menjadi 16 kata 32-bit M, M1, M2, ... M15.
  • Output: nilai status menjalankan baru.
  • Pengolahan:

    1. Simpan status saat ini dalam beberapa variabel: A → A ', B → B' , C → C ' dan D → D'
    2. Lakukan 64 putaran yang terlihat seperti ini:
      • Hitung T = B + ((A + fsaya(B, C, D) + Mk + Xsaya) <<< ssaya) . Ini berbunyi seperti ini: kita menghitung fungsi yang diberikan fsaya (fungsi bitwise sederhana, yang tergantung pada angka bulat i ) di atas [~ # ~] b [~ # ~] , [~ # ~] c [~ # ~] , dan [~ # ~] d [~ # ~] . Tambahkan ke nilai [~ # ~] a [~ # ~] , satu pesan Word Mk dan konstanta Xsaya (penambahan dilakukan modulo 232). Putar hasilnya ke kiri oleh beberapa bit (jumlah shift juga tergantung pada putaran). Akhirnya, tambahkan [~ # ~] b [~ # ~] : hasilnya adalah [~ # ~] t [~ # ~] .
      • Putar kata-kata keadaan: D → A , C → D , B → C , T → B .
    3. Tambahkan nilai status yang disimpan ke variabel status saat ini: A + A '→ A , B + B' → B , C + C '→ C , D + D' → D .

Poin penting adalah bahwa ada 64 putaran, tetapi hanya 16 kata pesan. Ini berarti bahwa setiap pesan Word memasuki pemrosesan empat kali . Saya menulisnya dalam huruf tebal karena itu adalah poin utama; resistensi terhadap preimage berasal dari karakteristik itu. Pesan mana yang digunakan Word dalam setiap putaran dijelaskan dalam spesifikasi MD5 (RFC 1321); spesifikasi juga menjelaskan fungsi fsaya, jumlah rotate ssaya dan konstanta 32-bit Xsaya.

Sekarang anggaplah Anda mencoba untuk "membalikkan" MD5; Anda mulai dari output dan bekerja perlahan ke atas fungsi kompresi. Pertama, Anda harus memutuskan output dari putaran 64. Memang, output dari fungsi kompresi adalah jumlah dari output dari putaran 64, dan status yang disimpan (the Nilai A 'B' C 'D' ). Anda tidak memiliki keduanya, jadi Anda harus memilih. Harapan Anda adalah bahwa Anda akan dapat menemukan nilai untuk kata-kata pesan yang akan memungkinkan Anda untuk mendapatkan input dari putaran 1 beberapa nilai yang koheren dengan keputusan sewenang-wenang Anda pada A ' dan saudara-saudaranya.

Mari kita lihat bagaimana hal-hal terlihat ketika Anda menjalankan fungsi kompresi mundur. Anda memiliki output dari sebuah putaran (variabel [~ # ~] a [~ # ~] , [~ # ~] b [~ # ~] , [~ # ~] c [~ # ~] dan [~ # ~] d [~ # ~] setelah putaran) dan Anda ingin menghitung ulang input dari putaran itu. Anda sudah mengetahui nilai sebelumnya dari [~ # ~] b [~ # ~] , [~ # ~] c [~ # ~] dan [~ # ~] d [~ # ~] , tetapi untuk [~ # ~] a [~ # ~] dan Mk Anda memiliki banyak pilihan: setiap nilai 32-bit dimungkinkan untuk [~ # ~] a [~ # ~] , dan masing-masing memiliki yang sesuai Mk. Pada awalnya, Anda senang akan hal itu; siapa yang akan menolak kebebasan seperti itu? Cukup pilih secara acak Mk, dan ini menghasilkan yang sesuai [~ # ~] a [~ # ~] hanya dengan beberapa operasi (coba saja!).

Tetapi setelah Anda membalikkan itu 16 putaran (putaran 49 hingga 64, karena Anda bekerja mundur), kebebasan menghilang. Anda telah "memilih" nilai-nilai dari semua kata pesan. Saat mencoba membalikkan babak 48, Anda ingin menghitung ulang nilai [~ # ~] a [~ # ~] sebelum putaran itu; sesuai spesifikasi MD5, pesan Word M2 digunakan di babak 48, dan Anda telah memilih nilai M2 (saat membalikkan putaran 63). Jadi hanya ada satu pilihan untuk [~ # ~] a [~ # ~] . Jadi apa yang akan Anda katakan? Satu pilihan sudah cukup untuk melanjutkan perjalanan mundur. Jadi kamu melanjutkan.

Sekarang, Anda berada di awal fungsi kompresi. Ingatlah bahwa, pada awalnya, Anda membuat pilihan nilai A 'B' C 'D' yang sewenang-wenang: ini memungkinkan Anda untuk menghitung output dari putaran 64, dan mulai mundur berjalan. Sekarang Anda telah mendapatkan input dari ronde 1, yang harus identik dengan A 'B' C 'D' ... dan tidak cocok. Itu cukup normal: Anda memilih A 'B' C 'D' secara sewenang-wenang, dan Anda juga memilih kata-kata pesan Mk sewenang-wenang, sehingga dapat diharapkan bahwa sebagian besar waktunya tidak akan berfungsi. Jadi Anda mencoba memperbaiki perhitungan , dengan mengubah secara retrospektif pilihan awal Anda dari A 'B' C 'D' , atau satu atau beberapa pilihan acak untuk Mk. Tetapi setiap modifikasi pada sembarang Mk menyiratkan modifikasi di tempat lain, karena masing-masing Mk digunakan empat kali. Jadi, Anda perlu modifikasi lain untuk membatalkan yang lain, dan seterusnya ...

Pada saat itu Anda mulai memahami masalah pembalik MD5: setiap kali Anda menyentuh sedikit pun, itu memicu banyak sekali modifikasi di seluruh algoritme, yang harus Anda batalkan dengan menyentuh bit lain, dan ada terlalu banyak interaksi . Pada dasarnya, Anda menyulap dengan 2128 Bola pada saat yang sama, dan itu terlalu banyak untuk melacak semuanya.

Jika setiap blok pesan memiliki panjang 2048-bit, dipecah menjadi 64 kata, dan setiap pesan Word hanya digunakan sekali dalam MD5, maka Anda dapat membalikkannya dengan mudah. Anda lakukan seperti di atas: pemilihan arbitrer dari A 'B' C 'D' , pemilihan kata pesan yang berubah-ubah untuk putaran 64 hingga 5; dan untuk empat putaran pertama, Anda hanya mempertimbangkan nilai yang ingin Anda peroleh untuk input putaran (nilai yang cocok dengan pilihan sewenang-wenang Anda dari A ', B ', C' atau D ') dan mengerjakan pesan Word yang sesuai. Mudah seperti pai. Tetapi MD5 tidak memproses data dengan blok 2048-bit, tetapi dengan blok 512-bit, dan setiap pesan Word digunakan empat kali.


Beberapa tikungan tambahan

Struktur fungsi kompresi MD5 sebenarnya adalah generalisasi dari Feistel cipher . Dalam cipher Feistel, data dibagi menjadi dua bagian, dan, untuk setiap putaran, kami mengubah satu setengah dengan menambahkan/xoring ke nilai menengah yang dihitung dari setengah lainnya dan dari kunci; dan kemudian kita bertukar dua bagian. Perpanjang skema ini ke perpecahan empat bagian, dan Anda mendapatkan struktur yang sama dari putaran MD5 - dengan putaran 90º: MD5 terlihat seperti enkripsi kondisi saat ini saat ini menggunakan blok pesan sebagai kunci (dan ada tambahan tambahan dari output putaran 64 dengan status tersimpan, yang meninggalkan MD5 dari cipher yang diputar).

Jadi mungkin kita bisa membangun fungsi hash dari cipher blok? Memang kita bisa: itulah --- Whirlpool . Fungsi hash dibangun di atas cipher blok yang diputar (blok pesan adalah kuncinya); cipher blok Whirlpool adalah "W", turunan dari Rijndael, lebih dikenal sebagai AES . Tetapi W memiliki blok yang lebih besar (512 bit, bukan 128 bit) dan jadwal kunci yang telah di-reforg.

Ketika Anda membuat fungsi hash dari blok cipher yang diputar, maka serangan preimage pada fungsi hash agak setara dengan serangan rekonstruksi kunci pada blok cipher; jadi ada beberapa harapan bahwa jika cipher blok aman, maka demikian juga fungsi hash. Di sana lagi, ada detail-detail aneh. Juga, untuk struktur seperti itu, collisions pada fungsi hash seperti serangan terkait kunci pada cipher blok; serangan terkait kunci biasanya dianggap tidak fatal, dan sering diabaikan (misalnya, mereka bukan bagian dari kriteria evaluasi untuk kompetisi AES, dan Rijndael dianggap agak lemah dalam hal itu, itulah sebabnya W memiliki kunci baru susunan acara).

Beberapa desain yang lebih baru dibangun di atas cipher blok yang tidak diputar , sehingga keamanan fungsi hash dapat diturunkan lebih langsung dari keamanan cipher blok; lihat misalnya kandidat SHA-3 Skein , didefinisikan pada cipher blok yang disebut Threefish.

Sebaliknya, orang dapat mencoba membuat blok cipher dari fungsi hash. Lihat misalnya SHACAL , yaitu SHA-1 "set upright". Dan, sesuai petunjuk, SHACAL memiliki beberapa kelemahan terkait kunci yang sangat mirip dengan kelemahan SHA-1 yang diketahui berkaitan dengan tabrakan (tidak ada tabrakan aktual yang dihitung, tetapi kami memiliki metode yang seharusnya hampir sejuta kali lebih cepat daripada algoritma pencarian tabrakan generik).

Oleh karena itu, bertentangan dengan apa yang saya katakan di pengantar tulisan ini, kita telah berbicara tentang enkripsi selama ini . Masih banyak yang bisa ditemukan dan dipelajari tentang hubungan antara fungsi hash dan enkripsi simetris.


TL; DR: tidak ada TL; DR untuk pesan ini. Baca seluruhnya, atau pergilah.

128
Thomas Pornin

Langkah pertama menuju jawaban di sini adalah melihat contoh-contoh, seperti yang bagus dari @Dietrich, fungsi yang jauh lebih sulit untuk dijalankan dalam satu arah daripada terbalik, dan telah menolak banyak upaya untuk menemukan terobosan kecepatan. Tetapi masalahnya rumit, jadi saya akan mencoba untuk mengatasinya lagi.

Banyak orang tampaknya jatuh ke dalam perangkap (heh) berpikir bahwa fungsi hash sebenarnya entah bagaimana ajaib - bahwa mereka benar-benar mutlak "fungsi satu arah" yang secara matematis tidak dapat dijalankan mundur sama sekali, hanya karena mereka disebut hash. Ini bukan cara yang sehat untuk memikirkannya di forum keamanan. Ini sering salah dalam praktik. Dan selalu salah dalam teori, mengingat definisi matematika dasar dari fungsi sebagai pemetaan dari domain ke gambar .

Semua hash dapat dibalik, pada prinsipnya. Ini mungkin berantakan dan brutal (seperti dalam brute-force), mungkin butuh waktu yang lama tidak praktis dengan perangkat keras saat ini, dan bahkan mungkin bertahan dalam jangka panjang, tetapi secara matematis itu hanya masalah waktu. Seperti yang dicatat @mucker, semua informasi ada untuk menemukan kata sandi asli, (atau, setidaknya, kata sandi yang berfungsi). Jika kita lupa itu, kita lupa bahaya heuristik pintar untuk mengambil kata sandi kemungkinan ceri, yang membuat berita secara teratur. Hashing adalah masalah teknik dan tantangan utamanya adalah efisiensi - bagaimana membuatnya mahal untuk menemukan kata sandi yang diberikan hash. Salah satu hasil prinsip pemikiran semacam itu adalah pentingnya membuat hash kata sandi lambat

Dan sains dan matematika hashing lambat laun menjadi lebih baik. Sebenarnya tidak ada bukti bahwa hash benar-benar keras. @ Dietrich menjawab adalah cara yang bagus untuk menggambarkan bagaimana fungsi hash ideal mungkin dimungkinkan. Tapi lihat saja para ahli nyata yang menggambarkan bagaimana kita tidak memiliki bukti untuk salah satu algoritma kripto terbaik: Apa model matematika di balik klaim keamanan cipher simetris dan algoritma digest?

Fakta bahwa LanMan dikutip dalam pertanyaan tersebut adalah lebih banyak bukti bahwa kita perlu menghindari hash yang ideal. LanMan adalah fungsi hash yang ideal, mudah dikalahkan dengan kombinasi sedikit analisis dan sedikit kekerasan. Untuk contoh populer lain dari fungsi hash mengerikan lihat MySQL OLD_PASSWORD cryptanalysis? .

Jadi kembalikan dirimu dari perangkap - jatuh ke dalamnya tidak harus merupakan perjalanan satu arah. Ketahuilah bahwa hash bersifat reversibel, dan jaga agar pola pikir keamanan yang terpercaya tetap aktif saat Anda mencari cara terbaik untuk membalikkannya. Itu sering kali merupakan cara terbaik untuk menemukan yang benar-benar sulit untuk dibalik. Saya tidak mencoba memberikan aspersi pada praktik terbaik di luar sana, seperti bcrypt atau PBKDF2 atau scrypt. Tetapi buktinya jelas bahwa bahkan programmer yang baik pun sering salah. jadi berhati-hatilah dengan cara Anda menggunakannya dan jangan mencoba untuk membuat sendiri.

17
nealmcb

Karena begitulah fungsi Cryptographic Hash Functions, mereka adalah fungsi matematika satu arah (dari biasa ke hash). Algoritma dibuat dan diuji secara khusus untuk menghindari itu, dan juga menghindari tabrakan (2 teks biasa menghasilkan hash yang sama).

Anda dapat membaca lebih banyak di wikipedia , tetapi poin utama dari artikel ini adalah:

Fungsi hash kriptografi yang ideal memiliki empat sifat utama atau signifikan:

  • mudah (tetapi tidak harus cepat) untuk menghitung nilai hash untuk setiap pesan yang diberikan
  • itu tidak layak untuk menghasilkan pesan yang memiliki hash yang diberikan
  • itu tidak layak untuk memodifikasi pesan tanpa mengubah hash
  • tidak mungkin menemukan dua pesan berbeda dengan hash yang sama

Sebagian besar serangan pada fungsi hash didasarkan pada menemukan tabrakan (jadi 2 teks biasa berbeda akan cocok dengan hash yang sama) atau pra-menghasilkan jutaan hash dan membandingkannya hingga Anda menemukan dataran yang menghasilkannya.

Singkat sejarah panjang: jika algoritma hash adalah reverse-engineerable atau dapat diserang seperti itu, itu bukan algoritma hash yang baik.

Untuk kata sandi, menyelidiki menggunakan BCrypt, posting ini memiliki banyak info tentangnya.

12
coredump

Bayangkan fungsi hash yang menggunakan bit tunggal untuk hash. Jadi hash Anda bisa 0 atau 1.

Dan katakanlah fungsi hash menambahkan setiap byte data dan jika datanya genap, nilai hash adalah 0. Jika data itu ganjil, hash adalah 1.

Apakah Anda melihat mengapa Anda tidak dapat memulihkan data Anda dengan merekayasa balik fungsi hash itu?

Itu sama untuk algoritma hash yang sebenarnya, hanya formula secara signifikan lebih baik daripada fungsi yang baru saja saya jelaskan.

Kesulitan Anda mungkin karena Anda mempertimbangkan hash sejauh penggunaannya untuk kata sandi. Tidak jelas mengapa Anda tidak dapat memulihkan kata sandi 8 karakter dari hash 128 bit. Tetapi fungsi hash yang Anda gunakan untuk kata sandi juga dapat digunakan untuk menghitung hash dari seluruh terabyte data, dan hash masih akan mengambil data hanya 128 bit. Jelas, Anda tidak dapat melakukan reverse engineering hash 128 bit dan memulihkan terabyte data Anda.

Juga, dengan asumsi Anda memiliki setiap permutasi yang mungkin dari satu terabyte data, akan ada sejumlah besar data yang berbeda yang menghasilkan hash yang sama. Lagi pula, jika Anda memiliki lebih dari 2 ^ 127 permutasi data yang berbeda, Anda akan cenderung menemukan dua data berbeda yang memiliki hash yang sama.

8
user1068775

Ada algoritma yang secara inheren tidak dapat dibalik; mereka mengubah input A menjadi output B sedemikian rupa sehingga bahkan jika Anda tahu langkah-langkah algoritma yang tepat, Anda tidak dapat memulihkan A dari B.

Contoh yang sangat sederhana: konversi setiap karakter dalam kata sandi menjadi nilai ASCII dan jumlahkan semua nilai. Tidak mungkin Anda dapat memulihkan kata sandi asli dari hasilnya.

4
Massimo

Ada satu aspek dari masalah yang hilang pada jawaban sebelumnya. Itulah sifat fungsi hash yang banyak-ke-satu. Karena (sebagian besar) fungsi hash adalah output panjang tetap (mis., 256 bit), secara teknis ada banyak string yang semuanya memiliki hash dengan nilai yang sama.

Sebagai contoh, jika Anda mengambil semua string 512 bit (yang ada 2 ^ 512). Hanya ada 2 ^ 256 output dari fungsi hash. Jadi, untuk setiap output dari fungsi hash, ada kira-kira 2 ^ 256 512 bit string yang hash ke nilai itu. Saya katakan kasar karena kita tidak tahu apakah fungsi hash sebenarnya adalah fungsi acak, itu bisa memiliki sedikit bias.

Jadi, mengingat intisari, ada banyak string yang hash dengan nilai yang sama. Oleh karena itu, jika Anda mendefinisikan "membalikkan fungsi hash" sebagai mengeluarkan kata sandi pengguna, bagaimana fungsi membalikkan Anda akan berurusan dengan jumlah string yang berpotensi tak terbatas yang menghasilkan intisari yang diberikan?

2
mikeazo

Anda bertanya "mengapa penting bahwa fungsi hash menjadi satu arah?" Ini properti keamanan.

Ada dua jenis "hash" (atau "pesan intisari" sebagaimana mereka dipanggil) yang umum digunakan saat ini. Salah satunya adalah intisari pesan sederhana, yang mungkin Anda kenal sebagai algoritma checksum, seperti CRC32. Algoritma dirancang sedemikian rupa sehingga perubahan bit tunggal pada input akan menghasilkan nilai intisari yang berbeda. Tujuan utama ini adalah untuk memastikan bahwa pesan tidak rusak oleh kecelakaan. Checksum CRC32 hadir pada setiap paket TCP/IP, dan mis-match menghasilkan pengiriman ulang untuk memperbaiki kesalahan.

Intisari pesan sering digunakan dalam kriptografi sebagai bagian dari "menandatangani" pesan. Pesan dienkripsi oleh pengirim dengan kunci pribadinya, dan siapa saja dapat menggunakan kunci publik untuk memvalidasi bahwa itu dienkripsi hanya oleh pengirim. Tetapi kriptografi kunci publik RSA hanya dapat mengenkripsi pesan yang lebih kecil dari ukuran kunci (256 byte), yang jauh lebih pendek daripada pesan yang paling berguna. Algoritma digest pesan menghasilkan nilai yang lebih kecil dari kunci RSA. Jadi dengan mengenkripsi intisari alih-alih pesan, tanda tangan RSA dapat digunakan pada pesan ukuran apa pun.

Tapi intisari pesan biasa tidak aman terhadap penyerang. Pertimbangkan checksum yang sangat sederhana yang hanya menjumlahkan nilai-nilai karakter. Jika Anda menandatangani checksum seperti itu, saya bisa menukar pesan lain yang menghasilkan checksum yang sama, dan tanda tangan akan cocok, membodohi korban.

Penggunaan lain yang umum untuk pencernaan pesan adalah perlindungan kata sandi selama penyimpanan. Jika Anda mengenkripsi kata sandi sebelum menyimpannya dalam sistem, administrator sistem yang mengetahui kunci dapat mendekripsi semuanya. (Anda mungkin telah memperhatikan masalah ini baru-baru ini ketika beberapa situs web diretas.)

Untuk menghindari masalah ini, dibutuhkan jenis hash yang berbeda, hash yang "aman secara kriptografis." Algoritme hash aman memiliki dua properti tambahan, resistensi tabrakan, dan non-reversibilitas.

Resistensi tabrakan berarti bahwa saya seharusnya tidak dapat menemukan pesan yang menghasilkan intisari yang sama. Dengan begitu saya tidak bisa menukar pesan jahat saya dengan pesan baik Anda.

Properti non-reversibilitas berarti bahwa saya tidak dapat mengubah intisari kembali menjadi teks biasa sehingga saya tidak dapat mendekripsi pesan aslinya, seperti kata sandi pengguna.

Membuat intisari adalah masalah yang sangat mirip dengan enkripsi, karena Anda harus mengacak data sedemikian rupa sehingga tidak bocor informasi tentang data asli. Ini bahkan lebih sulit, karena matematika yang sama harus tidak memberikan petunjuk tentang cara membuat tabrakan berhasil.

1
John Deters

Saya pikir ada banyak alasan, tetapi satu yang jelas: intisari yang dihasilkan oleh fungsi hash tidak akan pernah mengandung informasi yang tak terbatas, karena intisari memiliki bit yang terbatas. Tetapi fungsi hash dapat digunakan untuk input hash dari informasi yang tak terbatas. Masukan sebenarnya bisa apa saja.

Kesulitan untuk menemukan tabrakan bukanlah jawabannya. Kesulitan sebenarnya adalah membuktikan data asli Anda sebenarnya satu-satunya input yang mungkin cocok dengan intisari tertentu. Saya pikir Anda mungkin tidak pernah menghitung satu input dan mengklaim itu adalah satu-satunya jawaban untuk intisari.

0

Yang lain telah menjelaskan mengapa fungsi hash kriptografi yang baik sulit untuk dibalik - tetapi menurut artikel Wikipedia ini , LanMan dirancang dengan buruk dan dapat dibalik relatif mudah:

Meskipun didasarkan pada DES, block cipher yang dipelajari dengan baik, hash LM bukanlah fungsi satu arah yang benar karena kata sandi dapat ditentukan dari hash karena beberapa kelemahan dalam implementasinya ... Dengan memasang serangan brute force pada setiap setengahnya secara terpisah, mesin desktop modern dapat memecahkan hash LM alfanumerik dalam beberapa jam ... Pada tahun 2003, Ophcrack, sebuah implementasi dari teknik tabel Rainbow, diterbitkan. Ini secara khusus menargetkan kelemahan enkripsi LM, dan termasuk data pra-komputasi yang cukup untuk memecahkan hampir semua hash alfanumerik LM dalam beberapa detik.

0
James