一個無感知的密碼破解伺服器：結合 Hellman 表格與 PIR 協定

目錄

• 1. 簡介
• 2. 基礎知識
  • 2.1 雜湊反查表格
  • 2.2 私有資訊擷取
• 3. 解決方案概述
• 4. 技術細節與演算法建構
• 5. PIR 協定與複雜度分析
• 6. 實驗結果
• 7. 結論與未來工作
• 8. 原創分析與專家評論
• 9. 技術細節與數學公式
• 10. 分析框架與案例研究
• 11. 未來應用與方向
• 12. 參考文獻

1. 簡介

本文探討攻擊性資安作業中的一個關鍵隱私挑戰：透過第三方伺服器執行密碼破解，同時不洩露目標雜湊值。情境涉及一位本地資源有限（例如智慧型手機）的滲透測試人員，需要遠端查詢大型預先計算的雜湊表格（如彩虹表或 Hellman 表格）。核心問題在於建構一個無感知的密碼破解伺服器，使伺服器無法得知客戶端正嘗試破解哪些密碼-雜湊對，從而保護作業機密性。

2. 基礎知識

2.1 雜湊反查表格

密碼系統通常儲存密碼學雜湊值。攻擊者使用預先計算的表格來反查這些雜湊值。主要方法包括：

• Hellman 表格 (1980)： 一種時間-記憶體權衡方法，使用雜湊與密碼的鏈條，僅儲存鏈條的起點與終點。
• Rivest 的顯著點 (1982)： 一種最佳化方法，使用特殊的「顯著」雜湊值作為鏈條終點，以減少查詢次數。
• 彩虹表 (Oeschlin, 2003)： 在鏈條的每一步使用不同的還原函數，通常速度更快，但較不適合本文提出的基於 PIR 的查詢模型。

本文認為，對於此特定應用，Hellman 表格（或使用顯著點的變體）比彩虹表更適合與 PIR 協定結合。

2.2 私有資訊擷取

私有資訊擷取允許客戶端從資料庫中擷取項目，而伺服器無法得知存取的是哪個項目。對於儲存 n 位元字串的單一資料庫，PIR 方案涉及：

1. 查詢生成（客戶端）
2. 查詢傳輸
3. 查詢處理（伺服器）
4. 回應傳輸
5. 回應解碼（客戶端）

複雜度以 $O_C$（客戶端處理）、$O_S$（伺服器處理）和 $O_T$（傳輸）衡量。一個基本的下限是 $O_S$ 必須至少為 $O(n)$ 以確保隱私，這意味著伺服器必須執行與資料庫大小成比例的工作量。

3. 解決方案概述

所提出的解決方案巧妙地結合了Hellman 表格（或顯著點表格）與單一資料庫 PIR 協定。伺服器儲存預先計算的破解表格。當客戶端想要破解一個雜湊值時，它使用 PIR 查詢，從 Hellman 表格中對應於潛在鏈條匹配的特定位置，私下擷取必要資訊，而不洩露查詢索引。

4. 技術細節與演算法建構

此建構的重點在於調整 Hellman 表格以適應 PIR。Hellman 表格由一個密碼學雜湊函數 $H$ 和一個還原函數 $R$ 定義。一條鏈條以明文 $SP_i$ 開始，迭代計算：$X_0 = SP_i$，$X_{j+1} = H(R(X_j))$，僅儲存 $(SP_i, EP_i)$，其中 $EP_i$ 是經過 $t$ 步後的最終值。為了檢查一個雜湊值 $h$，客戶端從 $h$ 開始計算一條長度為 $t$ 的鏈條，在每一步檢查中間值是否與儲存的終點匹配。PIR 協定用於從伺服器的表格中私下獲取這些終點比較結果。

5. PIR 協定與複雜度分析

本文分析了計算與通訊的開銷。使用標準的計算型 PIR 協定（例如基於二次剩餘假設），伺服器端的處理成本 $O_S$ 隨表格大小而變化。客戶端成本 $O_C$ 和通訊成本 $O_T$ 顯著較低，但仍不可忽視。分析顯示，雖然與明文查詢相比，PIR 引入了開銷，但這是為強查詢隱私所必須付出的代價。選擇 Hellman 表格而非彩虹表的理由在於，彩虹表需要使用不同的還原函數檢查多個欄位，導致更多的 PIR 查詢和更高的總體成本。

6. 實驗結果

使用 Python 實作了一個原型。實驗證明了該方法的可行性。關鍵指標包括：

• 查詢時間： 一次無感知破解嘗試的端到端時間，考慮了 PIR 計算和通訊延遲。
• 伺服器負載： 伺服器每次查詢的計算負載，確認了 $O(n)$ 的理論下限。
• 成功率： 在給定表格覆蓋率下成功破解雜湊值的機率，與標準 Hellman 表格的成功機率一致。

結果驗證了系統可行，但也突顯了效能權衡：與非隱私服務相比，隱私保護的代價是每次查詢增加了伺服器計算量。

7. 結論與未來工作

本文成功展示了一種新穎的無感知密碼破解伺服器架構。未來的工作方向包括：

• 探索更有效率的 PIR 協定以降低 $O_S$ 和 $O_T$。
• 研究使用可信執行環境作為密碼學 PIR 的替代或補充方案。
• 將模型擴展到分散式或多伺服器 PIR 設定，以潛在提升效能。

8. 原創分析與專家評論

核心洞見： 本文的重點不在於更快地破解密碼，而在於更隱密地破解。作者們發現了攻擊性資安中一個明顯的作業缺口：數位足跡。當紅隊成員查詢雲端破解服務時，該查詢的中繼資料本身就是一種風險。這項工作提議使用 PIR 來加密意圖本身，使伺服器變得「無感知」。這是一個將先進密碼學理論應用於現實世界資安問題的經典範例。其重要性類似於針對機器學習 API 的模型反轉攻擊或成員推論攻擊中的隱私考量，其中查詢本身就可能洩露敏感資訊。

邏輯流程： 論證邏輯嚴謹。1) 定義威脅模型：一個不可信的第三方伺服器。2) 選擇合適的密碼學原語：單一資料庫計算型 PIR，這是此非共謀單一伺服器情境下唯一可行的選擇。3) 調整破解原語：選擇 Hellman 表格而非彩虹表，因為其結構在每次破解嘗試中需要更少、更確定的 PIR 查詢。這是一個至關重要的工程決策，顯示了深厚的領域知識。從問題到密碼學工具再到系統整合的流程連貫一致。

優點與缺點： 主要優點是新穎性和直接適用性。原型證明了概念可行性。然而，缺點是實用性。PIR 的效能開銷巨大。正如作者所指出的，伺服器工作量是 $O(n)$。對於大型表格（TB 級），這對商業服務來說是難以承受的。這是一個優先考慮完美隱私而非任何效率表象的解決方案。此外，它僅保護查詢本身。伺服器仍然知道客戶端正在執行破解操作，這在某些司法管轄區可能足以觸發警報。與新興的全同態加密方法相比，這種基於 PIR 的方法更簡單，但靈活性遠不如前者。

可行建議： 對於資安從業者，這是一個高保證、隱私保護型攻擊工具的藍圖。對於研究人員，它開啟了關於高效、可用的 PIR 的研究方向。立即的下一步是將其與基於 TEE 的方法進行基準測試。TEE 將以潛在低於密碼學 PIR 的開銷私下處理計算，儘管它引入了對硬體供應商的信任。長遠願景應是混合模型：使用 PIR 進行初始、最敏感的索引查詢，並可能使用可信硬體進行後續步驟，在信任假設和效能之間取得平衡。這項工作，如同創造性地結合網路進行非配對影像翻譯的基礎 CycleGAN 論文一樣，展示了如何結合兩種成熟的技術來為一個小眾但重要的問題創造新穎的解決方案。

9. 技術細節與數學公式

對於雜湊函數 $H$ 和還原函數 $R$，Hellman 鏈條的核心是迭代定義的。給定起始明文 $P_0$： $$X_0 = P_0$$ $$X_{k+1} = H(R(X_k)) \quad \text{for } k = 0, 1, ..., t-1$$ 鏈條終點是 $X_t$。表格儲存對 $(P_0, X_t)$。為了反轉一個雜湊值 $h$，需要從 $h$ 計算一條試驗鏈條：$Y_0 = h$，$Y_1 = H(R(Y_0))$，...，$Y_t = H(R(Y_{t-1}))$。在每一步 $j$，檢查 $R(Y_j)$ 是否為顯著點，或者 $Y_j$ 是否與儲存的終點 $X_t$ 匹配，從而觸發鏈條重新生成以找到原像。在適應 PIR 的版本中，對伺服器儲存的終點列表的檢查，是透過對應於 $R(Y_j)$ 或 $Y_j$ 的索引進行 PIR 查詢來完成的。

10. 分析框架與案例研究

案例研究：安全滲透測試即服務
設想一個提供密碼稽核的雲端 PTaaS 平台。一家客戶公司上傳其自身系統的密碼雜湊列表進行安全稽核。使用標準服務，雲端供應商會得知該公司密碼對應的具體雜湊值，這可能造成潛在的資料外洩。使用無感知伺服器框架：

1. 客戶端的稽核工具預處理每個目標雜湊值 $h$。
2. 對於每個 $h$，它在本地計算供應商 Hellman 表格中必要的索引 $i_1, i_2, ... i_k$。
3. 它使用 PIR 協定為這些索引生成加密查詢，並將其發送給 PTaaS 伺服器。
4. 伺服器處理所有查詢（對其整個資料庫執行工作）並返回加密的資料區塊。
5. 客戶端解密回應並在本地處理，查看是否找到任何鏈條匹配，從而恢復明文密碼。

在整個過程中，PTaaS 供應商僅看到加密的、看似隨機的查詢，無法得知客戶端正在測試哪些雜湊值，從而保護了客戶內部密碼集的機密性。

11. 未來應用與方向

本研究原則的應用可延伸至密碼破解之外：

• 隱私保護型威脅情報查詢： 從共享資料庫查詢入侵指標，而不洩露自身資產。
• 機密 DNA 序列比對： 醫院可以查詢基因組資料庫以尋找疾病標記，而不暴露患者的完整基因組。
• 日誌分析中的私有過濾： 在共享的安全日誌中搜尋攻擊模式，而不洩露您的組織易受攻擊的特定模式。
• 與全同態加密的融合是一個關鍵方向。雖然 PIR 隱藏了存取模式，但 FHE 可以讓伺服器在加密資料上執行整個破解計算，僅返回加密結果。像 Microsoft 的 SEAL 和 OpenFHE 這樣的專案正使其變得更實用。
• 與差分隱私整合可以增加一層統計隱私，確保即使查詢的成功或失敗也不會洩露太多資訊。

12. 參考文獻

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). (被引用為創造性技術組合的類似範例)。
7. Microsoft Research. (n.d.). Microsoft SEAL (Simple Encrypted Arithmetic Library). Retrieved from https://www.microsoft.com/en-us/research/project/microsoft-seal/