Apa yang membuat algoritma hashing “aman”?

Setelah membaca pertanyaan menarik ini , saya merasa memiliki ide bagus tentang algoritma hashing tidak aman yang akan saya gunakan jika saya membutuhkannya, tetapi tidak tahu mengapa saya mungkin menggunakan algoritma yang aman sebagai gantinya.

Jadi apa perbedaannya? Bukankah output hanya angka acak yang mewakili hash? Apa yang membuat beberapa algoritma hashing aman?

Ada tiga properti yang diinginkan dari setiap fungsi hash kriptografi H:

• resistensi preimage : Mengingat h, seharusnya sulit untuk menemukan nilai apa pun xdengan h = H(x).

• resistensi preimage kedua : Mengingat x1, itu harus sulit untuk menemukan x2 != x1dengan H(x1) = H(x2).

• resistensi tabrakan : Harus sulit untuk menemukan dua nilai x1 != x2dengan H(x1) = H(x2).

Dengan fungsi hash seperti yang digunakan dalam bahasa pemrograman umum untuk tabel hash (string), biasanya tidak ada yang diberikan, mereka hanya menyediakan untuk:

• resistensi tabrakan lemah : Untuk nilai yang dipilih secara acak (atau "biasanya") dari domain, kemungkinan tabrakan kecil. Ini tidak mengatakan apa-apa tentang penyerang yang sengaja mencoba membuat tabrakan, atau mencoba menemukan preimage.

Tiga properti di atas adalah (di antara) tujuan desain untuk setiap fungsi hash kriptografis. Untuk beberapa fungsi (seperti MD4, SHA-0, MD5) diketahui bahwa ini gagal (setidaknya sebagian). Generasi saat ini (SHA-2) diasumsikan aman, dan generasi berikutnya ("Secure Hash Algorithm 3") saat ini sedang dalam proses standar , setelah kompetisi .

Untuk beberapa penggunaan (seperti hashing kata sandi dan penurunan kunci dari kata sandi), domain nilai yang benar-benar digunakan xsangat kecil sehingga memaksa ruang ini menjadi layak dengan fungsi hash normal (cepat) yang aman, dan inilah saatnya kami juga ingin:

• eksekusi lambat : Diberikan x, dibutuhkan sejumlah sumber daya minimum (yang dapat dikonfigurasi) untuk menghitung nilai H(x).

Tetapi untuk sebagian besar kegunaan lain, ini tidak diinginkan, orang ingin:

• eksekusi cepat : Diberikan x, menghitung nilai H(x)secepat mungkin (sementara masih aman).

Ada beberapa konstruksi (seperti PBKDF2 dan scrypt) untuk membuat fungsi hash lambat dari yang cepat dengan sering mengulanginya.

Untuk lebih jelasnya, lihat tag hash di situs saudari kami Cryptography Stack Exchange.

Secure berarti seseorang yang ingin membuat Anda melakukan kesalahan dengan menggunakan tabrakan (yaitu fakta bahwa dua sumber di-hash dengan nilai yang sama) akan mengalami kesulitan.

Beberapa karakteristik:

• mengetahui hash, membangun file yang hash ke nilai itu sulit (varian, bagian dari file baru diberikan serta hash yang diinginkan)

• membangun dua file berbeda yang hash dengan nilai yang sama sulit (varian, bagian dari file diberikan)

Perbedaan utama cukup sederhana: hash normal dimaksudkan untuk meminimalkan jumlah tabrakan tidak disengaja, sejauh itu bisa tanpa memperlambat banyak proses.

Hash aman itu dimaksudkan untuk mencegah tabrakan, bahkan ketika seseorang melakukan yang terbaik untuk menyebabkannya. Anda biasanya tidak ingin perdagangan setiap kemungkinan tabrakan untuk operasi lebih cepat. Bahkan, membuat operasi yang sengaja lambat memiliki beberapa manfaat keamanan dalam dirinya sendiri, bahkan jika tidak membuat menemukan tabrakan lebih sulit.

Sebagai contoh dari yang terakhir: jika komputasi hash membutuhkan 50 ms, itu tidak akan memiliki pengaruh materi pada login normal pengguna (yaitu, sebagian besar pengguna tidak akan melihat perbedaan 50ms ketika mereka login). Pada saat yang sama, jika seorang penyerang ingin melakukan serangan kamus, bisa menghasilkan hanya 20 hash per detik adalah cacat serius . Dengan kata lain, dalam beberapa alasan, untuk hash yang aman, lebih lambat lebih baik.

Baca ini http://www.codinghorror.com/blog/2012/04/speed-hashing.html ini akan menjelaskan semuanya jauh lebih baik daripada yang pernah saya bisa menjelaskannya. Berikut adalah dua tajuk terpenting dalam artikel yang secara langsung menjawab pertanyaan Anda:

• Hash yang aman dirancang untuk menjadi tamper-proof
  • mengubah outputnya secara radikal dengan perubahan bit kecil ke data input
• Hash aman dirancang agar lambat

Bagian TL; DR-nya di akhir:

Jika Anda seorang pengguna:

Pastikan semua kata sandi Anda 12 karakter atau lebih, idealnya lebih banyak. Saya sarankan mengadopsi frase sandi, yang tidak hanya jauh lebih mudah diingat daripada kata sandi (jika tidak mengetik) tetapi juga sangat aman terhadap kekerasan memaksa murni karena panjangnya.

Jika Anda seorang pengembang:

Gunakan bcrypt atau PBKDF2 secara eksklusif untuk hash apapun yang Anda butuhkan agar aman. Hash baru ini dirancang khusus agar sulit diterapkan pada GPU. Jangan gunakan bentuk hash lainnya. Hampir setiap skema hashing populer lainnya rentan terhadap kekerasan dengan susunan GPU komoditas, yang hanya menjadi lebih cepat dan lebih paralel dan lebih mudah diprogram untuk setiap tahun.

Hash "aman" adalah hash yang diyakini sulit untuk "dipalsukan" dengan cara yang direproduksi secara formula tanpa pengetahuan sebelumnya tentang pesan yang digunakan untuk membuat hash. Karena informasi itu umumnya rahasia, maka kebutuhan untuk hash, ini adalah properti yang baik dari fungsi hashing yang dimaksudkan untuk digunakan dalam otentikasi.

Hash umumnya dianggap "aman" jika, diberi pesan M, fungsi hash hash (), dan nilai hash H yang dihasilkan oleh hash (M) dengan panjang dalam bit L, tidak ada yang berikut ini dapat dilakukan dalam waktu kurang dari O (2 ^L ) waktu:

• Diberikan hash () dan H, menghasilkan M. (resistensi preimage)
• Diberikan hash () dan M, menghasilkan M _{2 yang} berbeda sehingga hash (M ₂ ) == H. (resistensi tabrakan lemah)
• Diberikan hash (), hasilkan setiap M ₁ dan M ₂ sedemikian rupa sehingga hash (M ₁ ) == hash (M ₂ ). (resistensi tabrakan yang kuat)

Selain itu, hash "aman" harus memiliki panjang hash L sehingga 2 ^Lbukan jumlah langkah yang layak bagi komputer untuk melakukan perangkat keras saat ini. Hash integer 32-bit hanya dapat memiliki 2,1 miliar nilai; sementara serangan preimage (menemukan pesan yang menghasilkan hash H tertentu) akan memakan waktu cukup lama, itu tidak layak untuk banyak komputer, terutama yang ada di tangan lembaga pemerintah yang disewa dengan pemecahan kode. Selain itu, suatu algoritma yang membuat dan menyimpan pesan acak dan hash mereka akan, berdasarkan probabilitas, memiliki peluang 50% untuk menemukan hash duplikat dengan setiap pesan baru setelah mencoba hanya 77.000 pesan, dan akan memiliki peluang 75% untuk mencapai duplikat setelah hanya 110.000. Bahkan hash 64-bit masih memiliki peluang 50% untuk bertabrakan setelah mencoba hanya sekitar 5 miliar nilai. Itulah kekuatan serangan ulang tahun pada hash kecil. Sebaliknya,angka decillion (1,5 * 10 ³⁴ ).

Kebanyakan serangan yang didemonstrasikan pada hash kriptografi adalah serangan tabrakan, dan telah menunjukkan kemampuan untuk menghasilkan pesan bertabrakan dalam waktu kurang dari 2 ^L (sebagian besar masih eksponensial-waktu, tetapi mengurangi eksponen hingga setengahnya adalah pengurangan signifikan dalam kompleksitas karena membuat hash 256-bit semudah diselesaikan sebagai 128-bit, 128-bit semudah diselesaikan sebagai 64-bit, dll).

Selain ukuran hash kecil, faktor lain yang dapat membuat hash terbukti tidak aman adalah:

Low work - hash yang dirancang untuk digunakan oleh hashtable atau untuk tujuan "checksum" lainnya biasanya dirancang agar murah secara komputasi. Itu membuat serangan brute-force jauh lebih mudah.

"Sticky State" - Fungsi hashing rentan terhadap pola input di mana nilai hash saat ini dari semua input sejauh ini tidak berubah ketika diberi byte input tambahan tertentu. Memiliki "sticky state" membuat tabrakan mudah ditemukan, karena begitu Anda mengidentifikasi pesan yang menghasilkan hash "sticky state", itu sepele untuk menghasilkan pesan lain yang memiliki hash yang sama dengan menambahkan byte input yang menjaga hash dalam "sticky state" -nya ".

Difusi - Setiap byte input dari pesan harus didistribusikan di antara byte dari nilai hash dengan cara yang sama rumitnya. Fungsi hash tertentu membuat perubahan yang dapat diprediksi ke bit tertentu dalam hash. Ini sekali lagi membuat pembuatan tabrakan sepele; diberi pesan yang menghasilkan hash, tabrakan dapat dengan mudah dibuat dengan memperkenalkan nilai-nilai baru ke pesan yang hanya memengaruhi bit yang berubah yang dapat diprediksi.

Gunakan algoritma yang tepat untuk tugas yang dihadapi.

CRC digunakan untuk deteksi / koreksi kesalahan.

Intisari pesan kriptografis seperti SHA2 digunakan sebagai blok penyusun untuk konstruksi kriptografis (tanda tangan digital, MAC, fungsi derivasi kunci / kata sandi hashing) dan protokol keamanan.

Dalam tabel hash / kamus / peta menggunakan SipHash .

Apa yang Anda sebut algoritma hashing tidak aman tidak boleh digunakan dalam tabel hash , sebagaimana dibuktikan oleh entri CVE berikut: CVE-2003-0364, CVE-2011-4461, CVE-2011-4838, CVE-2011-4885, CVE-2011- 4462, CVE-2011-4815, CVE-2012-0840, CVE-2012-5371 , CVE-2012-5374, CVE-2012-5375