隱私保護密碼破解：安全雜湊復原協定

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. 分析框架範例案例

情境： 一位自由接案的滲透測試員（Client）從客戶的系統中取得一個 NTLM 雜湊值。已知密碼政策為：9字元的英數字混合。該測試員缺乏足夠的 GPU 運算能力來及時破解。

3PC 協定應用：

客戶端設定： 測試者設定一個隱私參數，例如 $k=100$。真實的 NTLM 雜湊值是 $H_{real}$。客戶端軟體會生成 99 個密碼學上可信的誘餌 NTLM 雜湊值，從而建立匿名集合 $S$。
伺服器參與： 測試者將 $S$ 發送至商業破解服務（伺服器），請求使用字典及規則破解所有雜湊，目標為9位英數密碼。
伺服器處理： 伺服器執行其破解工具。針對每個生成的候選密碼，它會計算其NTLM雜湊值，並透過批次操作檢查是否與$S$中的所有100個雜湊值匹配。
結果返回： 伺服器返回所有匹配成功的密碼列表任何雜湊值位於 $S$ 中，但未指明是哪一個雜湊值匹配。
客戶端過濾： 測試者知道原始雜湊值 $H_{real}$。他們計算每個返回密碼的雜湊值，以識別與 $H_{real}$ 匹配的那一個，從而恢復目標密碼。其他返回的密碼對應已破解的誘餌密碼，將被丟棄。

伺服器僅得知 100 個雜湊值中有一個屬於測試者，但不知道是哪一個，並且看到許多已破解的密碼，但不知道它們的相關性。

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 這類混合網路將訊息來源隱藏在群體之中的做法。

Logical Flow: 邏輯本身是嚴謹的，但取決於一個關鍵且常被忽略的假設：生成 完全無法區分的誘餌的能力。若伺服器能透過統計方法區分真實雜湊與誘餌（例如，根據先前資料外洩的頻率或雜湊生成的模式），則 $k$-匿名模型便會崩潰。該論文將謂詞加密延伸至雜湊函數的做法是新穎的，但實際的安全性更取決於誘餌生成演算法的品質，而非謂詞函數本身。

Strengths & Flaws: 其優勢在於能直接應用於一個真實且服務不足的利基市場（注重隱私的滲透測試者），且客戶端的加密開銷相對較輕。與許多隱私保護系統一樣，其主要缺陷在於 trust-but-verify 悖論。客戶端必須信任伺服器能正確執行協議，且不會竄改流程（例如透過記錄中間狀態來關聯時間戳記）。與完全同態加密（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.

目錄