期望熵：一種用於評估密碼強度的新穎指標

1. 引言與動機

本文介紹期望熵，這是一種新穎的指標，旨在評估隨機或類隨機密碼的強度。其動機源自現有密碼強度評估工具中的實際落差。基於古典組合數學的公式（例如，$\log_2(\text{字元空間}^{\text{長度}})$）會輸出數十位元的結果，而業界標準的NIST熵估計套件則提供一個介於0到1之間的標準化最小熵分數。這種差異使得直接比較和直觀解釋變得困難。期望熵透過提供與NIST工具相同的0-1尺度上的強度估計來彌合這一落差，例如，值為0.4表示攻擊者必須窮舉至少40%的可能猜測才能找到密碼。

這項工作置於「PHY2APP」專案的背景下，該專案專注於使用實體層安全方法為Wi-Fi設備配置（ComPass協定）生成強對稱密碼，突顯了對一個穩健、可擴展的強度指標的需求。

2. 熵的各種定義

熵衡量無序性、隨機性或不確定性。不同的定義對密碼強度的適用性各不相同。

2.1 最小熵

定義為 $H_{\infty} = -\log_2(\max(p_i))$，其中 $p_i$ 是某個元素的機率。它代表最壞情況，衡量猜測最可能結果的難度。這是NIST套件輸出的基礎。

2.2 夏農熵

定義為 $H_1 = -\sum_{i=1}^{N} p_i \log_2 p_i$。它提供了資訊內容的平均度量，但在密碼破解情境中，因其與實際猜測難度無關而受到批評，因為它忽略了密碼長度和攻擊者的最佳策略。

2.3 哈特利熵

定義為 $H_0 = \log_2 N$，它僅衡量分佈的大小（字母表大小），完全忽略字元機率。

2.4 猜測熵

定義為 $G = \sum_{i=1}^{N} p_i \cdot i$，其中猜測按機率遞減排序。這衡量了最優攻擊者所需的期望猜測次數。它更直接地與實際破解時間相關，但未經標準化。

3. 期望熵

3.1 定義與公式

期望熵建立在猜測熵的概念之上，但標準化到 [0, 1] 尺度。其核心思想是從單一密碼的組成來估計強度。它考慮了互斥的字元集：小寫字母 $L$ (|L|=26)、大寫字母 $U$ (26)、數字 $D$ (10) 和符號 $S$ (32)，對於英文而言，形成了一個總大小為94的字元空間 $K$。

雖然單一密碼的完整數學推導在提供的摘錄中有所暗示但未完全明確，但該指標本質上是將最優攻擊者所需的工作量相對於總搜尋空間進行標準化。如果 $G$ 是猜測熵，$N$ 是可能密碼的總數（例如，完整空間的 $94^{\text{長度}}$），則標準化形式在概念上可能與 $E \approx G / N_{eff}$ 相關，其中 $N_{eff}$ 是考慮密碼組成的有效搜尋空間大小。

3.2 解釋與尺度

其關鍵創新在於其可解釋的尺度。期望熵值為 $\alpha$（其中 $0 \le \alpha \le 1$）意味著攻擊者必須執行至少 $\alpha$ 比例的總猜測次數（以最優順序）才能破解密碼。值為1表示理想的隨機性，攻擊者必須進行完整的暴力搜尋。這與NIST最小熵尺度直觀地保持一致，便於系統設計者進行比較和決策。

4. 核心洞見與分析師觀點

核心洞見： Reaz和Wunder不僅僅是提出另一個熵指標；他們正試圖解決安全工程中一個關鍵的可用性和可解釋性落差。真正的問題不在於缺乏複雜性度量，而在於當組合數學工具大喊「80位元！」而NIST低語「0.7」時產生的認知摩擦。期望熵是一個務實的翻譯器，將密碼學強度轉換為統一儀表板上可操作的、機率性的風險分數。

邏輯流程： 論證優雅而簡單：1) 現有指標存在於不同的星球（位元 vs. 標準化分數），導致混淆。2) 猜測熵 ($G$) 更接近攻擊者的現實，但沒有界限。3) 因此，將 $G$ 相對於有效搜尋空間進行標準化，以創建一個0-1分數，直接映射到攻擊者所需的工作量百分比。這橋接了理論（NIST的最小熵）與實務（密碼破解者的工作量）。

優點與缺陷： 其優點在於優雅的簡單性和即時的可解釋性——對政策制定者和系統架構師來說是天賜之物。然而，魔鬼藏在分佈假設中。該指標的準確性在很大程度上取決於正確地對單一密碼樣本內的字元機率分佈 $p_i$ 進行建模，這是一個眾所周知困難的統計問題。與NIST測試長位元流的套件不同，將其應用於一個短的16字元密碼需要穩健的估計器，而這些估計器可能對偏差敏感。從摘錄來看，論文並未完全詳細說明單一實例的這個估計過程，這是其致命弱點。

可操作的洞見： 對於安全團隊，此指標可以整合到密碼創建API或Active Directory外掛程式中，以提供即時、直觀的強度回饋（「您的密碼需要破解60%的猜測」）。對於研究人員，下一步必須是針對真實世界的破解工具（如Hashcat或John the Ripper）進行嚴謹、大規模的實證驗證，以校準模型。期望熵0.8是否真的意味著80%的搜尋空間？這需要對抗性AI模型（類似於GAN用於攻擊其他安全領域的方式）的證明。這個概念很有前景，但其操作實用性取決於在機器生成密碼的受控環境之外，進行透明、經過同行評審的驗證。

5. 技術細節與數學公式

基於概述的概念，可以概念性地構建密碼的期望熵 $H_E$。假設一個長度為 $l$ 的密碼從字母表 $\mathcal{A}$ 中抽取，每個字元位置都有一個相關的機率分佈（可以從密碼本身或參考語料庫估計）。

有序機率向量： 對於大小為 $N = |\mathcal{A}|^l$ 的整個密碼空間，理論上可以根據被選擇的機率（根據生成模型）對所有可能的密碼進行降序排序。
猜測熵： 最優攻擊者的期望猜測次數為 $G = \sum_{i=1}^{N} p_i \cdot i$，其中 $p_i$ 是第 $i$ 個最可能密碼的機率。
標準化： 均勻分佈的最大可能 $G$ 為 $(N+1)/2$。工作量的標準化度量可以定義為： $$ H_E \approx \frac{2 \cdot G - 1}{N} $$ 這會將均勻分佈（完美隨機性）映射到 $H_E \to 1$（當 $N$ 很大時），而將高度可預測的密碼（$G$ 很小）映射到接近0的值。
實務估計： 對於單一密碼，必須估計其「排名」或所有比它更可能的密碼的累積機率。如果一個密碼到其排名的累積機率質量為 $\alpha$，則 $H_E \approx 1 - \alpha$。這與論文的描述一致，即值0.4意味著搜尋40%的空間。

從單一樣本中估計此值的精確、高效演算法是作者所暗示的核心技術貢獻。

6. 實驗結果與圖表說明

註：提供的PDF摘錄未包含具體的實驗結果或圖表。以下是基於對此類指標進行典型驗證研究可能涉及的內容描述。

對期望熵的全面評估可能涉及以下圖表：

圖表1：指標比較散點圖。 此圖表將密碼繪製在兩個軸上：X軸顯示經典位元強度（例如，$\log_2(94^l)$），Y軸顯示期望熵（0-1）。點的雲圖將揭示兩種度量之間的相關性（或缺乏相關性），突顯那些長度長（高位元強度）但可預測（低期望熵）的密碼。
圖表2：抗破解能力曲線。 此圖將顯示攻擊者（使用像Hashcat這樣的工具進行基於規則的攻擊）為破解按期望熵分數分箱的密碼（例如，0.0-0.1, 0.1-0.2...）所必須遍歷的實際搜尋空間比例。理想的指標將顯示一條完美的對角線，其中預測工作量（熵）等於實際工作量。偏離對角線表示估計誤差。
圖表3：分數分佈圖。 一個直方圖，顯示不同密碼類型的期望熵分數：機器生成的（例如，來自ComPass協定）、有規則的人為生成和無規則的人為生成。這將視覺化展示該指標區分不同密碼生成方法的能力。

需要驗證的關鍵結果是聲明：「擁有某個值的期望熵，例如0.4，意味著攻擊者必須窮舉至少40%的總猜測次數。」這需要實證攻擊模擬。

7. 分析框架：範例案例

情境： 評估一個使用94字元可列印ASCII空間的系統中的兩個12字元密碼。

密碼A（人為選擇）： Summer2024!
密碼B（機器生成）： k9$Lp@2W#r1Z

經典位元強度： 兩者具有相同的理論最大值：$\log_2(94^{12}) \approx 78.7$ 位元。

期望熵分析：

密碼A： 結構很常見：一個字典單字（"Summer"）、一個可預測的年份（"2024"）和一個常見的後綴符號（"!"）。一個機率模型（如在洩露密碼上訓練的馬可夫鏈）會為這種模式分配高機率。它在可能密碼有序列表中的排名會非常低，意味著更可能密碼的累積機率很高。因此，其期望熵將是低的（例如，0.05-0.2），表示攻擊者很可能在最優猜測順序的前5-20%內找到它。
密碼B： 它看起來是隨機的，沒有明顯的模式，每個位置混合了字元集。一個機率模型會為這個特定序列分配一個非常低、大致均勻的機率。它的排名會非常高（接近有序列表的中間/末尾）。因此，其期望熵將是高的（例如，0.7-0.95），表示攻擊者必須搜尋大部分空間。

這個範例展示了期望熵如何提供比經典公式得出的相同位元強度更細緻、更現實的風險評估。

8. 應用展望與未來方向

立即應用：

即時密碼強度計： 將期望熵整合到網站和應用程式的註冊流程中，為使用者提供直觀的、基於百分比的強度指示器。
安全政策強制執行： 組織可以設定最低期望熵閾值（例如，0.6），而不僅僅是複雜性規則，直接將政策與估計的破解工作量掛鉤。
自動化系統稽核： 掃描現有密碼資料庫（雜湊值）以估計集體期望熵分佈，並識別具有極弱密碼的帳戶。

未來研究方向：

穩健的單一樣本估計器： 開發和比較統計方法（例如，使用神經語言模型、n-gram模型或布隆過濾器），以準確估計從中推導出 $H_E$ 的單一密碼的機率/排名。
對抗性評估： 針對最先進的密碼破解工具和AI模型（例如，PassGAN，一種適用於密碼的生成對抗網路框架改編版）測試該指標，以查看預測工作量是否與實際破解時間相符。
超越密碼： 將標準化的「工作量分數」概念應用於其他秘密，例如密碼學金鑰（其中位元是標準）或生物特徵模板，以創建跨不同身份驗證因素的統一強度指標。
標準化努力： 向像NIST這樣的機構提議期望熵或其原則，以納入未來數位身份指南（例如，SP 800-63B）的修訂中。

9. 參考文獻

德國聯邦教育與研究部 (BMBF)。PHY2APP專案資助詳情。
M. Dell'Amico, P. Michiardi, Y. Roudier, "Password Strength: An Empirical Analysis," in Proceedings of IEEE INFOCOM, 2010. （代表密碼強度方法調查）。
美國國家標準與技術研究院 (NIST). Entropy Estimation Suite. [線上]. 可取得：https://github.com/usnistgov/entropy-estimation
NIST Special Publication 800-90B. Recommendation for the Entropy Sources Used for Random Bit Generation.
J. Kelsey, K. A. McKay, M. Turan, "Predictive Models for Min-Entropy Estimation," in Proceedings of CHES, 2015.
K. Reaz, G. Wunder, "ComPass: A Protocol for Secure and Usable Wi-Fi Device Provisioning," in Proceedings of ACM WiSec, 2023. （根據上下文假設）。
C. E. Shannon, "A Mathematical Theory of Communication," The Bell System Technical Journal, vol. 27, pp. 379–423, 623–656, 1948.
R. V. L. Hartley, "Transmission of Information," The Bell System Technical Journal, vol. 7, no. 3, pp. 535–563, 1928.
J. Bonneau, "The Science of Guessing: Analyzing an Anonymized Corpus of 70 Million Passwords," in Proceedings of IEEE Symposium on Security and Privacy, 2012.
J. L. Massey, "Guessing and Entropy," in Proceedings of IEEE International Symposium on Information Theory (ISIT), 1994.
C. Cachin, Entropy Measures and Unconditional Security in Cryptography. PhD Thesis, ETH Zurich, 1997.
J. O. Pliam, "The Disparity between Work and Entropy in Cryptology," 1998. [線上]. 可取得：https://eprint.iacr.org/1998/024
B. Hitaj, P. Gasti, G. Ateniese, F. Perez-Cruz, "PassGAN: A Deep Learning Approach for Password Guessing," in Proceedings of ACNS, 2019. （用於對抗性AI評估的外部參考）。