目錄
1. 引言
儘管業界力推無密碼解決方案，密碼仍然係用戶身份驗證嘅主流形式。儲存密碼哈希值係標準做法，但透過破解嚟測試其強度需要大量資源。將呢項任務外判俾第三方伺服器會帶嚟重大私隱風險，因為哈希摘要同還原嘅明文都會外洩。本文介紹「私隱保護密碼破解（3PC）」協議，允許客戶端利用第三方嘅計算能力進行哈希破解，同時唔會洩露目標哈希值或破解出嚟嘅密碼。
2. The 3PC Protocol
3PC協議旨在解決外判密碼破解中的信任問題。其核心創新在於允許第三方執行計算密集型工作，同時對客戶的實際數據一無所知。
2.1 Core Mechanism & Predicate Function
該協議基於謂詞加密的概念構建，並針對哈希函數進行了調整。客戶端不會直接發送目標哈希值 $H(p)$，而是發送一個 匿名集 包含真實的哈希值，並混入 $k-1$ 個精心構造的誘餌哈希值。第三方伺服器的角色是破解 所有 使用提供嘅密碼字典或規則集嚟破解呢組哈希值。
關鍵係 謂詞函數 $f$。伺服器會將候選密碼 $p'$ 同匿名集中嘅每個哈希值進行比對。函數定義為：若且唯若 $H(p')$ 同集中嘅哈希值 $H_i$ 匹配，則 $f(H(p'), H_i) = 1$。伺服器會返回滿足 $f=1$ 嘅候選密碼集合。 任何 集合中的雜湊值，而無需知道匹配到的是哪個特定雜湊值（真實的或誘餌的）。
2.2 Decoy Hash Generation & Anonymity Set
生成可信嘅誘餌對安全至關重要。誘餌哈希必須令伺服器無法將其與真實哈希區分開。論文提出從符合目標哈希函數（例如NTLM、SHA-256）輸出空間嘅分佈中生成誘餌。咁樣可以確保真實哈希嘅$k$-匿名性。客戶端保持 合理否認性，因為即使客戶端喺提交集合後，亦無法從密碼學上證明邊個哈希先係原始目標。
Key Insights
- 集合中的隱晦保密： 安全性源於將真實哈希值隱藏於誘餌之中，而非來自對哈希值本身的傳統加密。
- 計算負擔的轉移： 客戶端的開銷在於生成匿名集；暴力破解/字典攻擊的重任完全外判。
- 恒定時間查找承諾： 該協議聲稱允許查找時間獨立於匿名集大小 $k$，僅受伺服器 IOPS 限制。
3. Technical Implementation & Analysis
3.1 數學基礎
該協議的安全性可以概率模型進行分析。設 $S$ 為大小為 $k$ 的匿名集，其中包含一個真實哈希值 $H_r$ 和 $k-1$ 個誘餌哈希值 $H_{d1}...H_{d(k-1)}$。假設誘餌完美無瑕，伺服器在觀察該集合及破解結果後，正確猜中真實哈希值的概率最多為 $1/k$。
對伺服器嘅信息洩漏 $\mathcal{L}$ 可以用最小熵量化：$\mathcal{L} \leq -\log_2(1/k) = \log_2(k)$ 位元。客戶端可以通過調整 $k$ 控制洩漏。對候選值 $p'$ 喺所有 $k$ 個哈希上嘅謂詞函數評估可以表示為向量：$\vec{R} = [f(H(p'), H_1), f(H(p'), H_2), ..., f(H(p'), H_k)]$。匹配到 任何 位置會將 $p'$ 傳回客戶端。
3.2 Performance & Scalability
論文指出，主要瓶頸並非密碼學運算，而是伺服器破解裝置（例如GPU/FPGA記憶體頻寬）的每秒輸入/輸出操作次數（IOPS）。由於伺服器必須針對所有 $k$ 個雜湊值測試每個候選密碼，理論上工作量因子會呈線性增長（$O(k)$）。然而，透過在平行硬體上進行高效批次處理，可將實際減速效應降至最低，從而在實際的 $k$ 值下接近所宣稱的「常數時間」查找。
4. Experimental Results & Chart Description
作者在FPGA架構上實現了概念驗證。雖然提供的摘錄未詳述具體性能數據，但論文聲稱展示了該協議的可行性。
假設性能圖表（基於協議描述）： 折線圖嘅Y軸可能會顯示「有效破解速度」（例如：哈希值/秒），而X軸就係「匿名集大小（k）」。一條代表 傳統攻擊 單一哈希上會顯示為一條高而平的線。該曲線對於 3PC protocol 會隨著k值增加而顯示下降趨勢，但由於在FPGA/GPU上進行了優化的批量處理，其斜率會比簡單的線性預測更為平緩。第三條線可能代表「理論上限（IOPS限制）」，作為3PC曲線的漸近線。
5. 分析框架示例案例
情境： 一名自由職業滲透測試員（客戶）從客戶系統中取得一個NTLM雜湊。已知密碼政策為：9位字母數字混合。該測試員缺乏足夠的GPU運算能力進行及時破解。
3PC 協議應用：
- 客戶端設定： 測試人員設定一個私隱參數，例如 $k=100$。真實的 NTLM 雜湊值是 $H_{real}$。客戶端軟件會生成 99 個密碼學上合理的誘餌 NTLM 雜湊值，從而建立匿名集合 $S$。
- 伺服器參與： 測試者將 $S$ 發送至商業破解服務（伺服器），並要求使用字典及規則破解所有雜湊值，目標為9位英數字密碼。
- 伺服器處理： 伺服器執行其破解工具。對於每個生成的候選密碼，它會計算其NTLM雜湊值，並透過批次操作檢查是否與$S$中所有100個雜湊值匹配。
- 結果返回： 伺服器返回所有匹配的密碼列表 任何 喺$S$入面嘅hash。佢冇指明係邊個hash匹配到。
- 客戶端過濾： 測試者知道原本嘅hash $H_{real}$。佢哋會計算每個返嚟嘅密碼嘅hash，從而識別出同$H_{real}$匹配嗰個，咁樣就可以搵返目標密碼。其他返嚟嘅密碼對應已破解嘅誘餌，會被丟棄。
6. Core Insight & Analyst's Perspective
核心洞察： The 3PC protocol is a clever, pragmatic hack that turns a fundamental limitation of cryptography—the one-way nature of hash functions—into a privacy feature. It recognizes that in password cracking, the goal isn't to hide the 進程 但係要隱藏 目標 同埋 結果 喺過程固有嘅噪音之內。呢個唔係追求「無法破解」嘅加密，而係更關乎策略性嘅信息混淆，其精神類似於Tor呢類混合網絡，將訊息嘅來源隱藏喺人群之中。
邏輯流程： 邏輯本身合理，但取決於一個關鍵且常被忽略的假設：生成 完全無法區分的誘餌的能力。若伺服器能從統計上區分真實哈希值與誘餌（例如，根據先前數據洩露中的出現頻率，或哈希生成的模式），則 $k$-匿名模型便會崩潰。該論文將謂詞加密擴展至哈希函數的做法新穎，但實際安全性更取決於誘餌生成算法的質量，而非謂詞函數本身。
Strengths & Flaws: 其優點在於能直接應用於一個真實且服務不足的利基市場（注重私隱的滲透測試人員），且客戶端的加密開銷相對較輕。與許多私隱保護系統一樣，其主要缺點在於 trust-but-verify paradox。客戶必須信任伺服器會正確執行協議，並且不會干擾過程（例如透過記錄中間狀態來關聯時間點）。與完全同態加密（FHE）等高級加密協議不同——後者提供了更強的理論保證，但速度慢得不切實際（正如Gentry開創性工作等早期實現所見）——三方計算（3PC）以犧牲絕對的密碼學安全性來換取實際效率。這是一個合理的工程權衡，但必須清晰傳達。
可行動的洞察： 對於安全團隊而言，此協議是進行安全密碼審計的可行工具，尤其是在合規要求（如GDPR）限制共享敏感哈希值時。當前的步驟是實施並審計誘餌生成模組。對於研究人員而言，下一個前沿方向是強化協議以抵禦主動的伺服器攻擊，並將其與其他隱私增強技術（PETs）整合。未來不僅在於使破解過程私有化，更在於構建一套隱私保護的安全操作體系，就像身份驗證協議從簡單加密發展到零知識證明一樣。對於攻擊性安全領域，三方計算（3PC）是朝著該方向邁出的充滿希望的第一步。
7. Future Applications & Research Directions
- 合規驅動安全審計： 讓受監管行業（金融、醫療）能夠在從不暴露密碼哈希值（即使對內部審計團隊）的情況下，對員工帳戶進行嚴格的密碼強度測試，以協助符合GDPR/CCPA規範。
- 聯邦哈希分析： 多個組織可以協作參與針對共同威脅行為者（例如勒索軟件組織）的密碼庫破解工作，而無需任何參與者透露其內部雜湊值或查看他人的雜湊值。
- 與密碼外洩警示服務整合： 用戶可以向「Have I Been Pwned」等服務提交從其密碼雜湊衍生的匿名集合，而無需透露實際雜湊值，從而增強外洩檢查的私隱保護。
- 研究方向 - 後量子韌性： 在後量子語境下研究該協議的安全性。雖然哈希函數本身可能具備抗量子性，但誘餌生成與謂詞函數機制需針對量子對抗模型進行分析。
- 研究方向 - 主動對抗模型： 將安全模型擴展至考慮偏離協議（例如透過引入側信道）的主動惡意伺服器，對於實際應用至關重要。
8. References
- Bonneau, J., Herley, C., van Oorschot, P. C., & Stajano, F. (2012). The quest to replace passwords: A framework for comparative evaluation of web authentication schemes. IEEE Symposium on Security and Privacy.
- FIDO Alliance. (2022). FIDO: The Future of Fast, Secure, Passwordless Sign-Ins. https://fidoalliance.org/
- Gentry, C. (2009). A fully homomorphic encryption scheme （博士論文，史丹福大學）。（用於計算隱私技術之比較）。
- NIST. (2020). Digital Identity Guidelines (NIST Special Publication 800-63B).
- Weir, M., Aggarwal, S., de Medeiros, B., & Glodek, B. (2009). Password cracking using probabilistic context-free grammars. IEEE Symposium on Security and Privacy.
- Zhao, F., & Halderman, J. A. (2019). 測量密碼強度對猜測攻擊嘅影響. USENIX Security Symposium.