期望熵：一种用于评估密码强度的新指标

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模型（类似于GANs用于攻击其他安全领域的方式）进行验证。这个概念很有前景，但其操作实用性取决于在机器生成密码的受控环境之外，进行透明、同行评审的验证。

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} $$ 这将使均匀分布（完美随机性）在 $N$ 增大时映射到 $H_E \to 1$，而高度可预测的密码（$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. 应用前景与未来方向

直接应用：

实时密码强度计： 将期望熵集成到Web和应用程序的注册流程中，为用户提供直观的、基于百分比的强度指示器。
安全策略强制执行： 组织可以设置最低期望熵阈值（例如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）。熵估计套件。 [在线]。可用：https://github.com/usnistgov/entropy-estimation
NIST特别出版物800-90B。用于随机比特生成的熵源建议。
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. 博士论文，苏黎世联邦理工学院，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评估的外部参考文献）。