期望熵：一種評估密碼強度嘅新指標

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," 載於 Proceedings of IEEE INFOCOM, 2010. （代表密碼強度方法調查）。
美國國家標準與技術研究院 (NIST)。 Entropy Estimation Suite. [在線]。可獲取：https://github.com/usnistgov/entropy-estimation
NIST特別出版物 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," 載於 Proceedings of CHES, 2015.
K. Reaz, G. Wunder, "ComPass: A Protocol for Secure and Usable Wi-Fi Device Provisioning," 載於 Proceedings of ACM WiSec, 2023. （根據上下文假設）。
C. E. Shannon, "A Mathematical Theory of Communication," The Bell System Technical Journal, 卷 27, 頁 379–423, 623–656, 1948.
R. V. L. Hartley, "Transmission of Information," The Bell System Technical Journal, 卷 7, 第 3 期, 頁 535–563, 1928.
J. Bonneau, "The Science of Guessing: Analyzing an Anonymized Corpus of 70 Million Passwords," 載於 Proceedings of IEEE Symposium on Security and Privacy, 2012.
J. L. Massey, "Guessing and Entropy," 載於 Proceedings of IEEE International Symposium on Information Theory (ISIT), 1994.
C. Cachin, Entropy Measures and Unconditional Security in Cryptography. 博士論文, 蘇黎世聯邦理工學院, 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," 載於 Proceedings of ACNS, 2019. （對抗性AI評估嘅外部參考）。