Algoritma hashing kata sandi yang umum digunakan bekerja seperti ini hari ini: Garam kata sandi dan beri makan ke dalam KDF. Misalnya, menggunakan PBKDF2-HMAC-SHA1, proses hashing kata sandi adalah DK = PBKDF2(HMAC, Password, Salt, ...). Karena HMAC adalah hashing 2 putaran dengan kunci empuk, dan SHA1 serangkaian permutasi, shift, rotasi, dan operasi bitwise, pada dasarnya, seluruh proses adalah beberapa operasi dasar yang diatur dengan cara tertentu. Tidak jelas, secara mendasar, betapa sulitnya mereka untuk menghitung. Itu mungkin mengapa fungsi satu arah masih menjadi kepercayaan dan kami telah melihat beberapa fungsi hash kriptografis yang penting secara historis menjadi tidak aman dan usang.

Saya bertanya-tanya apakah mungkin untuk memanfaatkan masalah lengkap NP untuk kata sandi hash dengan cara baru, berharap untuk memberikan landasan teoritis yang lebih solid. Ide kuncinya adalah, misalkan P! = NP (jika P == NP maka tidak ada OWF sehingga skema saat ini pecah juga), menjadi masalah NPC berarti jawabannya mudah diverifikasi tetapi sulit untuk dihitung. Properti ini sangat cocok dengan persyaratan hashing kata sandi. Jika kami melihat kata sandi sebagai jawaban untuk masalah NPC, maka kami dapat menyimpan masalah NPC sebagai hash kata sandi untuk melawan serangan offline: Mudah untuk memverifikasi kata sandi, tetapi sulit untuk dipecahkan.

Peringatan adalah, kata sandi yang sama dapat dipetakan ke beberapa contoh masalah NPC, mungkin tidak semuanya sulit dipecahkan. Sebagai langkah pertama dalam penelitian ini, saya mencoba menafsirkan string biner sebagai jawaban untuk masalah 3-SAT, dan untuk membangun contoh masalah 3-SAT di mana string biner adalah solusi. Dalam bentuknya yang paling sederhana, string biner memiliki 3 bit: x_0, x_1, x_2. Lalu ada 2 ^ 3 == 8 klausa:

000 (    (x_0) v    (x_1) v    (x_2) )
--------------------------------------
001 (    (x_0) v    (x_1) v NOT(x_2) )
010 (    (x_0) v NOT(x_1) v    (x_2) )
011 (    (x_0) v NOT(x_1) v NOT(x_2) )
100 ( NOT(x_0) v    (x_1) v    (x_2) )
101 ( NOT(x_0) v    (x_1) v NOT(x_2) )
110 ( NOT(x_0) v NOT(x_1) v    (x_2) )
111 ( NOT(x_0) v NOT(x_1) v NOT(x_2) )

Misalkan string biner adalah 000. Maka hanya 1 dari 8 klausa yang salah (yang pertama). Jika kita membuang klausa pertama dan DAN 7 klausa yang tersisa, maka 000 adalah solusi dari formula yang dihasilkan. Jadi jika kita menyimpan formula, maka kita dapat memverifikasi 000.

Masalahnya adalah, untuk string 3-bit, jika Anda melihat 7 klausa yang berbeda di sana, maka Anda langsung tahu mana yang hilang, dan itu akan mengungkapkan bit.

Jadi, kemudian saya memutuskan untuk membuang 3 dari mereka, hanya menjaga 4 ditandai dengan 001, 010, 100 dan 111. Ini kadang-kadang menimbulkan tabrakan tetapi membuat penyelesaian masalah menjadi kurang sepele. Tabrakan tidak selalu terjadi, tetapi apakah mereka pasti akan menghilang ketika input memiliki lebih banyak bit belum diketahui.

Edit. Dalam kasus umum di mana string biner bisa berupa (000, 001, ..., 111), masih ada 8 klausa di mana 7 benar dan 1 salah. Pilih 4 klausa yang memberikan nilai kebenaran (001, 010, 100, 111). Ini tercermin dalam implementasi prototipe di bawah ini.

Edit. Seperti jawaban yang ditunjukkan oleh @DW di bawah ini, metode pemilihan klausa ini mungkin masih menghasilkan terlalu banyak klausa pada serangkaian variabel tertentu yang memungkinkan untuk dengan cepat mempersempit nilainya. Ada metode alternatif untuk memilih klausa di antara total 7 * C (n, 3) klausa. Misalnya: Pilih sejumlah klausa yang berbeda dari serangkaian variabel tertentu, dan lakukan itu hanya untuk variabel yang berdekatan ((x_0, x_1, x_2), (x_1, x_2, x_3), (x_2, x_3, x_4), .. .) dan dengan demikian membentuk sebuah siklus, bukan sebuah klik. Metode ini kemungkinan tidak berfungsi juga karena secara intuitif Anda dapat mencoba tugas menggunakan induksi untuk menguji apakah semua klausa dapat dipenuhi. Jadi untuk membuatnya mudah menjelaskan keseluruhan struktur mari kita gunakan metode saat ini.

Jumlah klausa untuk string n-bit adalah 4 * C (n, 3) = 4 * n * (n - 1) * (n - 2) / 6 = O (n ^ 3), yang berarti ukuran dari hash adalah polinomial ukuran kata sandi.

Ada implementasi prototipe di Python di sini . Ini menghasilkan contoh masalah 3-SAT dari string biner input pengguna.

Setelah perkenalan yang panjang ini, akhirnya pertanyaan saya:

1. Apakah konstruksi di atas (seperti yang diterapkan dalam prototipe) berfungsi sebagai hashing kata sandi aman, atau setidaknya terlihat menjanjikan, dapat direvisi, dll.? Jika tidak, di mana gagal?

2. Karena kita memiliki 7 * C (n, 3) klausa untuk dipilih, apakah mungkin menemukan cara lain untuk membangun instance 3-SAT aman yang cocok untuk digunakan sebagai hash kata sandi, mungkin dengan bantuan pengacakan?

3. Apakah ada pekerjaan serupa yang mencoba memanfaatkan kelengkapan NP untuk merancang skema hashing password yang terbukti aman, dan sudah mendapatkan beberapa hasil (baik positif atau negatif)? Beberapa pengantar dan tautan akan sangat disambut.

Edit. Saya akan menerima jawaban di bawah ini oleh @DW, yang merupakan orang pertama yang membalas dan memberikan wawasan besar tentang struktur masalah serta sumber daya yang bermanfaat. Skema pemilihan klausa naif yang diperkenalkan di sini (seperti yang diterapkan dalam prototipe Python) tampaknya tidak berfungsi karena mungkin untuk dengan cepat mempersempit penugasan variabel dalam kelompok kecil. Namun, masalahnya tetap terbuka karena saya belum melihat bukti formal yang menunjukkan pengurangan NPC-ke-PasswordHashing seperti itu tidak akan berfungsi sama sekali. Bahkan untuk masalah pengurangan 3-SAT khusus ini, mungkin ada berbagai cara memilih klausa yang tidak ingin saya sebutkan di sini. Jadi setiap pembaruan dan diskusi masih sangat disambut baik.

Sayangnya, ini tampaknya tidak berhasil (lihat di bawah untuk perincian), dan tampaknya sulit menemukan cara untuk membuat ide semacam ini menghasilkan skema yang terbukti aman.

Masalah dengan ide umum Anda

Anda bukan orang pertama yang memikirkan ide mencoba mendasarkan kriptografi pada masalah NP-complete. Masalahnya adalah bahwa kekerasan NP hanya menjamin kekerasan kasus terburuk, tetapi kriptografi membutuhkan kekerasan kasus rata-rata. Ada beberapa upaya untuk mendasarkan kriptografi pada masalah NP-lengkap (misalnya, kriptografi knapsack), tetapi mereka belum bernasib baik. Biasanya yang terjadi adalah orang menemukan algoritma yang sering efektif rata-rata (atau dengan probabilitas non-sepele), meskipun dalam kasus terburuk mereka bersifat eksponensial; ini cukup untuk memecahkan crypto, meskipun itu tidak bertentangan dengan kekerasan NP.

$\ne$

Saya sarankan membaca lebih lanjut tentang subjek ini. Anda dapat menemukan beberapa titik awal yang berguna di Pentingnya Masalah NP-Hard dalam Kriptografi , kompleksitas kasus rata-rata membuka masalah selain fungsi satu arah , Status Dunia Impagliazzo? , Kasus terburuk hingga pengurangan kasus rata-rata .

Masalah dengan skema khusus Anda

Proposal spesifik Anda tidak sepenuhnya ditentukan. Untuk menganalisis suatu skema, Anda perlu menentukan sepenuhnya bagaimana skema bekerja. Dalam kasus Anda, tidak jelas bagaimana Anda memilih 4 dari 7 klausa dalam contoh umum. (Dan satu contoh bukan pengganti untuk spesifikasi yang menjelaskan bagaimana Anda melakukannya secara umum.)

$x_0,x_1,x_2,x_3,x_4$$2^5$kemungkinan penugasan ke 5 variabel tersebut, jadi cobalah semuanya dan buang semua penugasan yang dilanggar oleh salah satu dari 40 klausa. Saya memperkirakan bahwa ini hanya akan meninggalkan Anda dengan satu tugas yang konsisten dengan semua klausa.

$1/2$$1/2^{10}$$2^5-1$$7/8$$(7/8)^{40} \approx 2^{-7.7}$$(2^5-1) \times 2^{-7.7} \approx 0.15$

Ini dapat diulang untuk setiap kelompok yang terdiri dari 5 variabel, secara unik memulihkan penugasan unik yang memuaskan untuk masing-masing. Jika ada ambiguitas, penugasan kandidat dapat diperiksa terhadap klausa lain.

Dengan cara ini, kami melihat bahwa ada algoritma efisien yang biasanya akan menyelesaikan kelas instance 3SAT yang dihasilkan oleh prosedur Anda. Itu tidak akan menyelesaikan semua instance 3SAT, tetapi instance yang Anda hasilkan memiliki struktur khusus, dan itu memecahkan instance dengan struktur khusus itu secara efektif. Ini menggambarkan hal ini dengan baik: beberapa contoh 3SAT lebih mudah daripada yang lain, dan kekerasan 3SAT (dalam kompleksitas kasus terburuk) mengatakan sedikit atau tidak sama sekali tentang kekerasan contoh khusus yang Anda hasilkan atau kekerasan contoh 3SAT rata-rata.