Pilih Bahasa

Pelayan Pecahan Kata Laluan Tanpa Kesedaran: Menggabungkan Jadual Hellman dan Protokol PIR

Analisis pelayan pecahan kata laluan yang memelihara privasi menggunakan jadual Hellman dan protokol PIR untuk melindungi kerahsiaan pertanyaan.
strongpassword.org | PDF Size: 0.2 MB
Penilaian: 4.5/5
★ ★ ★ ★ ★
Penilaian Anda
Anda sudah menilai dokumen ini
Sampul Dokumen PDF - Pelayan Pecahan Kata Laluan Tanpa Kesedaran: Menggabungkan Jadual Hellman dan Protokol PIR
Lihat Dokumen PDF Muat Turun PDF Terjemah PDF
Laman Utama » Dokumentasi » Pelayan Pecahan Kata Laluan Tanpa Kesedaran: Menggabungkan Jadual Hellman dan Protokol PIR

Kandungan

1. Pengenalan

Kertas kerja ini membincangkan satu cabaran privasi kritikal dalam operasi keselamatan ofensif: melaksanakan pecahan kata laluan melalui pelayan pihak ketiga tanpa mendedahkan hash sasaran. Senario ini melibatkan seorang penguji penembusan dengan sumber tempatan yang terhad (contohnya, telefon pintar) yang perlu membuat pertanyaan terhadap jadual hash prakiraan yang besar (seperti jadual Rainbow atau Hellman) yang dihoskan dari jauh. Masalah terasnya adalah membina pelayan pecahan kata laluan tanpa kesedaran di mana pelayan tidak dapat mengetahui pasangan kata laluan-hash mana yang cuba dipecahkan oleh klien, sekali gus mengekalkan kerahsiaan operasi.

2. Asas-asas

2.1 Jadual Penyongsangan Hash

Sistem kata laluan selalunya menyimpan hash kriptografi. Penyerang menggunakan jadual prakiraan untuk menyongsangkan hash ini. Kaedah utama termasuk:

  • Jadual Hellman (1980): Pertukaran masa-memori menggunakan rantai hash dan kata laluan, hanya menyimpan titik permulaan dan penghujung rantai.
  • Titik Terpilih Rivest (1982): Pengoptimuman menggunakan nilai hash "terpilih" khas sebagai titik penghujung rantai untuk mengurangkan pencarian.
  • Jadual Rainbow (Oeschlin, 2003): Menggunakan fungsi pengecilan yang berbeza pada setiap langkah rantai, secara amnya lebih pantas tetapi kurang sesuai untuk model pertanyaan berasaskan PIR yang dicadangkan.

Kertas kerja ini berhujah bahawa jadual Hellman (atau varian dengan titik terpilih) adalah lebih serasi dengan protokol PIR berbanding jadual Rainbow untuk aplikasi khusus ini.

2.2 Pengambilan Maklumat Peribadi (PIR)

Pengambilan Maklumat Peribadi (PIR) membolehkan klien mengambil item dari pangkalan data tanpa pelayan mengetahui item mana yang diakses. Untuk pangkalan data tunggal yang menyimpan rentetan n-bit, skim PIR melibatkan:

  1. Penjanaan Pertanyaan (Klien)
  2. Penghantaran Pertanyaan
  3. Pemprosesan Pertanyaan (Pelayan)
  4. Penghantaran Respons
  5. Penyahkodan Respons (Klien)

Kerumitan diukur sebagai $O_C$ (pemprosesan klien), $O_S$ (pemprosesan pelayan), dan $O_T$ (pemindahan). Satu batas bawah asas ialah $O_S$ mestilah sekurang-kurangnya $O(n)$ untuk memastikan privasi, bermakna pelayan mesti melakukan kerja berkadar dengan saiz pangkalan data.

3. Gambaran Keseluruhan Penyelesaian

Penyelesaian yang dicadangkan menggabungkan jadual Hellman (atau jadual titik terpilih) dengan protokol PIR pangkalan data tunggal secara bijak. Pelayan menyimpan jadual pecahan prakiraan. Apabila klien ingin memecahkan hash, ia menggunakan pertanyaan PIR untuk mengambil maklumat yang diperlukan secara peribadi dari lokasi tertentu dalam jadual Hellman yang sepadan dengan padanan rantai yang berpotensi, tanpa mendedahkan indeks pencarian.

4. Butiran Teknikal & Pembinaan Algoritma

Pembinaan ini memberi tumpuan kepada menyesuaikan jadual Hellman untuk PIR. Jadual Hellman ditakrifkan oleh fungsi hash kriptografi $H$ dan fungsi pengecilan $R$. Satu rantai bermula dengan teks biasa $SP_i$, dan secara berulang mengira: $X_0 = SP_i$, $X_{j+1} = H(R(X_j))$, hanya menyimpan $(SP_i, EP_i)$ di mana $EP_i$ ialah nilai akhir selepas $t$ langkah. Untuk menyemak hash $h$, klien mengira rantai panjang $t$ bermula dari $h$, menyemak pada setiap langkah jika nilai perantaraan sepadan dengan titik penghujung yang disimpan. Protokol PIR digunakan untuk mengambil perbandingan titik penghujung ini dari jadual pelayan secara peribadi.

5. Protokol PIR & Analisis Kerumitan

Kertas kerja ini menganalisis beban pengiraan dan komunikasi. Menggunakan protokol PIR pengiraan standard (contohnya, berdasarkan andaian residu kuadratik), kos pemprosesan sebelah pelayan $O_S$ berskala dengan saiz jadual. Kos klien $O_C$ dan komunikasi $O_T$ adalah jauh lebih rendah tetapi tidak remeh. Analisis menunjukkan bahawa walaupun PIR memperkenalkan beban berbanding pertanyaan teks biasa, ia adalah harga yang perlu dibayar untuk privasi pertanyaan yang kuat. Pemilihan jadual Hellman berbanding Rainbow dibenarkan di sini kerana jadual Rainbow memerlukan penyemakan berbilang lajur dengan fungsi pengecilan yang berbeza, membawa kepada lebih banyak pertanyaan PIR dan kos keseluruhan yang lebih tinggi.

6. Keputusan Eksperimen

Satu prototaip telah dilaksanakan dalam Python. Eksperimen menunjukkan kebolehgunaan pendekatan ini. Metrik utama termasuk:

  • Masa Pertanyaan: Masa dari awal hingga akhir untuk percubaan pecahan tanpa kesedaran, mengambil kira pengiraan PIR dan kependaman komunikasi.
  • Beban Pelayan: Beban pengiraan pada pelayan bagi setiap pertanyaan, mengesahkan batas teori $O(n)$.
  • Kadar Kejayaan: Kebarangkalian berjaya memecahkan hash berdasarkan liputan jadual, yang selaras dengan kebarangkalian kejayaan jadual Hellman standard.

Keputusan mengesahkan bahawa sistem ini berfungsi tetapi menonjolkan pertukaran prestasi: privasi datang dengan kos peningkatan pengiraan pelayan bagi setiap pertanyaan berbanding perkhidmatan bukan peribadi.

7. Kesimpulan & Kerja Masa Depan

Kertas kerja ini berjaya menunjukkan seni bina novel untuk pelayan pecahan kata laluan tanpa kesedaran. Hala tuju kerja masa depan termasuk:

  • Meneroka protokol PIR yang lebih cekap untuk mengurangkan $O_S$ dan $O_T$.
  • Menyiasat penggunaan Persekitaran Pelaksanaan Dipercayai (TEE) seperti Intel SGX sebagai alternatif atau pelengkap kepada PIR kriptografi.
  • Memperluaskan model kepada tetapan PIR teragih atau berbilang pelayan untuk berpotensi meningkatkan prestasi.

8. Analisis Asal & Ulasan Pakar

Pandangan Teras: Kertas kerja ini bukan tentang memecahkan kata laluan dengan lebih pantas; ia tentang memecahkannya dengan lebih senyap. Penulis telah mengenal pasti jurang operasi yang ketara dalam keselamatan ofensif: jejak kaki digital. Apabila ahli pasukan merah membuat pertanyaan kepada perkhidmatan pecahan berasaskan awan, metadata pertanyaan itu adalah satu liabiliti. Kerja ini mencadangkan untuk menyulitkan niat itu sendiri menggunakan PIR, menjadikan pelayan "tanpa kesedaran". Ia adalah contoh klasik menggunakan teori kriptografi lanjutan (PIR) kepada masalah infosec dunia sebenar yang sukar. Kepentingannya adalah setara dengan pertimbangan privasi dalam serangan penyongsangan model atau serangan inferens keahlian terhadap API pembelajaran mesin, di mana pertanyaan itu sendiri boleh membocorkan maklumat sensitif.

Aliran Logik: Hujah ini adalah logik dan kukuh. 1) Takrifkan model ancaman: pelayan pihak ketiga yang tidak dipercayai. 2) Pilih primitif kriptografi yang sesuai: PIR pengiraan pangkalan data tunggal, yang merupakan satu-satunya pilihan yang boleh dilaksanakan untuk senario pelayan tunggal yang tidak bekerjasama ini. 3) Sesuaikan primitif pecahan: Pilih jadual Hellman berbanding Rainbow kerana strukturnya memerlukan lebih sedikit pertanyaan PIR yang lebih deterministik bagi setiap percubaan pecahan. Ini adalah keputusan kejuruteraan penting yang menunjukkan pengetahuan domain yang mendalam. Aliran dari masalah ke alat kriptografi ke integrasi sistem adalah koheren.

Kekuatan & Kelemahan: Kekuatan utama ialah kebaharuan dan kebolehgunaan langsung. Prototaip membuktikan kebolehgunaan konsep. Walau bagaimanapun, kelemahannya adalah praktikal. Beban prestasi PIR adalah besar. Seperti yang dinyatakan penulis, kerja pelayan adalah $O(n)$. Untuk jadual besar (terabait), ini adalah menghalang untuk perkhidmatan komersial. Ia adalah penyelesaian yang mengutamakan privasi sempurna berbanding sebarang bayangan kecekapan. Tambahan pula, ia hanya melindungi pertanyaan. Pelayan masih tahu klien sedang melakukan operasi pecahan, yang mungkin cukup untuk menaikkan penggera di sesetengah bidang kuasa. Berbanding pendekatan penyulitan homomorfik penuh (FHE) yang sedang muncul, kaedah berasaskan PIR ini lebih mudah tetapi jauh kurang fleksibel.

Pandangan Boleh Tindak: Untuk pengamal keselamatan, ini adalah pelan untuk alat ofensif pemelihara privasi jaminan tinggi. Untuk penyelidik, ia membuka satu bidang kerja mengenai PIR yang cekap dan boleh digunakan. Langkah seterusnya segera ialah membuat penanda aras ini berbanding pendekatan berasaskan TEE (contohnya, menjalankan logik pecahan di dalam enklaf SGX). TEE akan mengendalikan pengiraan secara peribadi dengan beban yang berpotensi kurang daripada PIR kriptografi, walaupun ia memperkenalkan kepercayaan kepada pembekal perkakasan. Visi jangka panjang sepatutnya model hibrid: gunakan PIR untuk pencarian indeks awal yang paling sensitif, dan mungkin perkakasan dipercayai untuk langkah seterusnya, mengimbangi andaian kepercayaan dan prestasi. Kerja ini, seperti kertas kerja CycleGAN asas yang menggabungkan rangkaian secara kreatif untuk terjemahan imej tidak berpasangan, menunjukkan bagaimana menggabungkan dua teknologi matang (jadual Hellman dan PIR) boleh mencipta penyelesaian novel untuk masalah niche tetapi penting.

9. Butiran Teknikal & Rumusan Matematik

Teras rantai Hellman untuk fungsi hash $H$ dan fungsi pengecilan $R$ ditakrifkan secara berulang. Diberi teks biasa permulaan $P_0$: $$X_0 = P_0$$ $$X_{k+1} = H(R(X_k)) \quad \text{untuk } k = 0, 1, ..., t-1$$ Titik penghujung rantai ialah $X_t$. Jadual menyimpan pasangan $(P_0, X_t)$. Untuk menyongsangkan hash $h$, seseorang mengira rantai percubaan dari $h$: $Y_0 = h$, $Y_1 = H(R(Y_0))$, ..., $Y_t = H(R(Y_{t-1}))$. Pada setiap langkah $j$, seseorang menyemak jika $R(Y_j)$ adalah titik terpilih atau jika $Y_j$ sepadan dengan titik penghujung yang disimpan $X_t$, mencetuskan penjanaan semula rantai untuk mencari praimej. Dalam versi yang disesuaikan PIR, semakan terhadap senarai titik penghujung yang disimpan pelayan dilakukan melalui pertanyaan PIR pada indeks yang sepadan dengan $R(Y_j)$ atau $Y_j$.

10. Kerangka Analisis & Kajian Kes

Kajian Kes: Pengujian Penembusan Selamat sebagai Perkhidmatan (PTaaS)
Bayangkan platform PTaaS berasaskan awan yang menawarkan audit kata laluan. Sebuah syarikat klien memuat naik senarai hash kata laluan dari sistem mereka sendiri untuk audit keselamatan. Menggunakan perkhidmatan standard, pembekal awan mengetahui hash khusus mana yang sepadan dengan kata laluan syarikat, satu potensi pelanggaran. Menggunakan rangka kerja pelayan tanpa kesedaran:

  1. Alat audit klien memproses awal setiap hash sasaran $h$.
  2. Untuk setiap $h$, ia mengira indeks yang diperlukan $i_1, i_2, ... i_k$ ke dalam jadual Hellman pembekal secara tempatan.
  3. Ia menggunakan protokol PIR untuk menjana pertanyaan tersulit untuk indeks ini dan menghantarnya ke pelayan PTaaS.
  4. Pelayan memproses semua pertanyaan (melakukan kerja pada keseluruhan pangkalan datanya) dan mengembalikan blok data yang disulitkan.
  5. Klien menyahsulit respons dan memprosesnya secara tempatan untuk melihat jika sebarang padanan rantai ditemui, memulihkan kata laluan teks biasa.

Sepanjang proses ini, pembekal PTaaS hanya melihat pertanyaan tersulit yang kelihatan rawak dan tidak mengetahui apa-apa tentang hash mana yang diuji oleh klien, sekali gus mengekalkan kerahsiaan set kata laluan dalaman klien.

11. Aplikasi & Hala Tuju Masa Depan

Prinsip penyelidikan ini melangkaui pecahan kata laluan:

  • Pencarian Perisikan Ancaman Pemelihara Privasi: Membuat pertanyaan tentang penunjuk kompromi (IOC) dari pangkalan data kongsi tanpa mendedahkan aset sendiri.
  • Pemadanan Jujukan DNA Sulit: Sebuah hospital boleh membuat pertanyaan pangkalan data genomik untuk penanda penyakit tanpa mendedahkan genom penuh pesakit.
  • Penapisan Peribadi dalam Analisis Log: Mencari melalui log keselamatan kongsi untuk corak serangan tanpa mendedahkan corak khusus yang organisasi anda terdedah kepadanya.
  • Pertemuan dengan Penyulitan Homomorfik Penuh (FHE) adalah hala tuju utama. Walaupun PIR menyembunyikan corak akses, FHE boleh membolehkan pelayan melakukan keseluruhan pengiraan pecahan pada data yang disulitkan, hanya mengembalikan keputusan yang disulitkan. Projek seperti SEAL Microsoft dan OpenFHE menjadikan ini lebih praktikal.
  • Integrasi dengan privasi kebezaan boleh menambah lapisan privasi statistik, memastikan bahawa kejayaan atau kegagalan pertanyaan pun tidak membocorkan terlalu banyak maklumat.

12. Rujukan

  1. Calvo, A., Futoransky, A., & Sarraute, C. (2013). An Oblivious Password Cracking Server. arXiv preprint arXiv:1307.8186.
  2. Hellman, M. (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory, 26(4), 401-406.
  3. Rivest, R. L. (1982). How to reuse a "write-once" memory. (MIT Laboratory for Computer Science Technical Report).
  4. Oechslin, P. (2003). Making a faster cryptanalytic time-memory trade-off. Advances in Cryptology - CRYPTO 2003 (pp. 617-630). Springer.
  5. Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (1995). Private information retrieval. Proceedings of IEEE 36th Annual Symposium on Foundations of Computer Science (pp. 41-50). IEEE.
  6. Zhu, J. Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired image-to-image translation using cycle-consistent adversarial networks. Proceedings of the IEEE international conference on computer vision (pp. 2223-2232). (Dirujuk sebagai contoh analog gabungan teknologi kreatif).
  7. Microsoft Research. (n.d.). Microsoft SEAL (Simple Encrypted Arithmetic Library). Diambil dari https://www.microsoft.com/en-us/research/project/microsoft-seal/