Kapan itu berbahaya untuk hash

Fungsi hash kriptografi yang andal mengubah plaintext menjadi teks dengan panjang tertentu. Ini memastikan "ketekunan": kesulitan dalam memulihkan prototipe pertama dan kedua. Atau, dalam bahasa sederhana tentang properti pertama, kesulitan mendapatkan teks seperti itu, nilai fungsi hash yang akan sama dengan yang ditentukan.

Kompleksitas pemulihan dipahami sebagai fakta bahwa untuk menemukan prototipe pertama [fungsi hash kriptografi yang dapat diandalkan], diperlukan untuk menyelesaikan rata-rata setidaknya $$$2 ^ {n-1}$operasi hash di mana $$$n$- jumlah bit dalam output dari fungsi hash kriptografi. Mengambil fungsi hash modern dengan ukuran output yang besar (mulai dari 256 bit), pengembang sistem informasi yakin bahwa tidak mungkin untuk mengembalikan data asli dari nilai fungsi hash. Paling sering dia benar.

Tetapi ada satu set kasus yang penting ketika, terlepas dari keandalan fungsi hash, mengembalikan gambar terbalik atau bahkan teks sumber tidak menjadi masalah. Ini adalah kasus ketika menggunakan fungsi hash tidak ada gunanya. Ini adalah kasus ketika jumlah varian dari teks sumber dapat dicari .

Contoh: nomor telepon . Nomor telepon berbeda dengan awalan "+7" dan 10 digit $$$10 ^ {10} \ sekitar 2 ^ {33}$. Perangkat modern yang dioptimalkan untuk beralih lebih dari nilai hash memilah jutaan hash per detik. Ini berarti bahwa penghitungan nilai fungsi hash untuk semua kemungkinan nomor telepon dengan awalan tidak lebih dari beberapa detik.

Contoh: nomor kartu kredit (PAN, nomor kartu pembayaran ). Seringkali nomor kartu ditutup, mengungkapkan 4 (6) pertama dan / atau 4 digit terakhir, sambil menyembunyikan sisanya. Ada 16 digit pada kartu. Mungkinkah untuk hash nomor kartu untuk menyembunyikannya dari penyerang? Tidak. Jika penyerang menerima 8 digit dari 16 (4 pertama dan 4 terakhir), serta nilai fungsi hash dari nomor kartu penuh, maka ia dapat memulihkan angka penuh dalam waktu kurang dari satu detik. Untuk melakukan ini, ia perlu memilah semuanya $$$10 ^ {8} \ sekitar 2 ^ {26}$opsi nomor.

Contoh yang menarik dengan alamat email . Tampaknya dengan nilai fungsi hash yang dapat diandalkan, tidak mungkin untuk mengembalikan alamat asli. Jumlah varian berbeda dari 8 huruf Latin dan 10 digit sudah memberikan $$$36 ^ 8 \ sekitar 2 ^ {41}$opsi untuk nama kotak surat tanpa memperhitungkan domain layanan email yang berbeda ( @mail.ru , @gmail.com , dll.). Jika Anda mengambil karakter lain yang diizinkan, serta memperpanjang alamat, bahkan ada lebih banyak opsi. Tapi ... Hingga 2006, proyek Blue Frog (Blue Frog) berhasil, yang menawarkan perlindungan anti-spam kepada penggunanya. Dia menggunakan pemberitahuan otomatis penyedia tentang spam yang dikirim dari server mereka, yang memaksa pengiklan untuk menolak mengirim spam ke setidaknya alamat-alamat yang merupakan peserta dalam proyek. Untuk memahami apakah kotak itu milik peserta atau tidak, file didistribusikan dengan daftar nilai fungsi hash kriptografis dari masing-masing alamat kotak surat anggota.

Diasumsikan bahwa spammer akan memeriksa setiap alamat mereka untuk mengirim iklan pada daftar ini dan mengecualikan kecocokan yang ditemukan. Namun, keberadaan file dengan nilai-nilai fungsi hash memungkinkan penyerang untuk melakukan hal yang sebaliknya: mengidentifikasi peserta proyek dan mengirim aliran pesan yang tidak berarti yang diperkuat kepada mereka untuk menolak menggunakan proyek Blue Frog. Beberapa waktu setelah serangan ini (dan juga yang lain, termasuk serangan DDoS pada server), proyek menghentikan pekerjaannya.

Seperti sebelumnya, penggunaan garam apa pun yang datang dengan nilai fungsi hash tidak mempengaruhi waktu enumerasi (tetapi masih melindungi terhadap serangan kamus).

Kemungkinan solusi untuk kasus yang dijelaskan.

1. Hash bukan nilai-nilai itu sendiri, tetapi gabungan dari nilai asli dan beberapa rahasia disimpan secara terpisah. Misalnya, tidak dalam tabel database (bersama dengan nilai-nilai fungsi hash), tetapi dalam konfigurasi server aplikasi. Dengan kesuksesan yang sama, alih-alih hashing, Anda dapat menggunakan fungsi enkripsi blok pada beberapa kunci rahasia.
2. Gunakan fungsi hash yang tidak hanya andal, tetapi juga lambat dalam komputasi. Baik untuk cryptanalyst dan untuk pengguna legal. Contoh dari fungsi-fungsi tersebut adalah PBKDF2, bcrypt, scrypt, Argon2, yang ketika memanggil fungsi, kami juga menunjukkan jumlah iterasi hash. Namun, jika meningkatkan panjang output dari fungsi hash dengan hanya satu bit (dari 256 atau 512) meningkatkan kompleksitas serangan cryptanalyst dengan urutan biner (dengan faktor dua), maka meningkatkan jumlah iterasi untuk fungsi hash PBKDF2 akan menggandakan kompleksitas serangan hanya dengan dua kali. Artinya, mendapatkan nilai hash bahkan oleh pengguna legal menjadi mahal dalam hal sumber daya komputasi dan energi yang dikeluarkan.