Tabrakan PBKDF2-HMAC

Question

Mencoba memahami properti umum tabrakan ini saat digunakan dengan SHA1, SHA256, dll. Di mana kunci yang diberikan lebih besar dari ukuran blok fungsi intisari. Dalam kasus ini tabrakan yang lebih kecil akan memiliki ukuran 20 karakter untuk SHA1 dan 32 untuk SHA256 (1/2 panjang intisari heksadesimal), jadi apakah ini berarti memaksa PBKDF2-HMAC-SHA1 penyerang hanya perlu mempertimbangkan frasa sandi 20 karakter atau kurang? Dan karenanya 32 atau kurang jika menggunakan SHA256? Apakah frasa sandi yang lebih panjang tidak berguna? Terima kasih.

Answer 1

"brute force a PBKDF2-HMAC-SHA1" bukan tentang tabrakan (setidaknya, jika ada satu hash yang ditargetkan, atau jika ada salt pada input hash sandi). Ini serangan preimage .

Output hash oleh SHA-1 adalah 160-bit. Itu 20 byte (bukan karakter; ini adalah pengertian yang berbeda, dan mengapa kami memiliki pengkodean karakter ). Ini bisa memakan waktu$2^{160}$nilai-nilai. Output dari PBKDF2-HMAC-SHA-1 memiliki ukuran parameterizable yang bisa lebih kecil (dengan pemotongan) atau lebih besar (pada dasarnya dengan menggabungkan hasil 20-byte), tetapi parameter sering diatur ke 20 byte, dan kami akan berasumsi bahwa .

Apakah ini berarti untuk memaksa PBKDF2-HMAC-SHA-1, penyerang hanya perlu mempertimbangkan frasa sandi yang terdiri dari 20 karakter atau kurang?

Tidak . Ini menyiratkan bahwa nilai acak ukuran hash memiliki probabilitas$2^{-160}$untuk mencocokkan hash yang diberikan. Konsekuensi praktisnya adalah bahwa mencoba secara acak menjadi sia-sia.

Kata sandi sering kali dibatasi pada subset ASCII dengan sekitar 95 karakter, jadi ada sekitar $2^{131.714}$kata sandi yang terdiri dari 20 karakter atau kurang (kebanyakan dari mereka persis 20 karakter). Jika PBKDF2 diparameterisasi untuk melakukan 1000 hash SHA-1 per PBKDF2 (yang merupakan parametriisasi terendah yang pernah dipertimbangkan menurut definisinya, dan menjadi sangat tidak mencukupi), hashing setengah dari kata sandi ini akan memerlukan lebih dari$2^{140}$ hashes, selesai $2^{40}$(satu juta juta) kali lebih banyak dari yang terbuang sejauh ini oleh penambangan bitcoin kemanusiaan. Itu bukan pilihan.

Pencarian kata sandi biasanya tidak mencoba semua kemungkinan kata sandi dengan lebih dari beberapa karakter; biasanya ≈6 di antara ≈70 karakter (hanya penyerang yang sangat kuat yang dapat menargetkan semua kombinasi 10 karakter bahkan jika ada peregangan sandi / kunci ringan ). Apa yang dilakukan pencarian kata sandi adalah mencoba kata sandi yang orang-orang dapat pilih secara masuk akal, kira-kira dalam mengurangi kemungkinan untuk dipilih.