一种基于伪随机数生成器（PRNG）的安全密码生成器

目录

1. 引言

网站账户和密码泄露事件的持续报道，凸显了信息安全和密码安全的至关重要性。虽然网站漏洞是一个因素，但密码本身的内在安全性才是关键。常见的不安全密码实践包括基于关键词的密码、使用流行短语、包含个人信息以及密码复用。人工智能和大语言模型的兴起，进一步增强了攻击者猜测密码的能力。

本研究提出了一种基于密码学安全伪随机数生成器（PRNG）的安全密码生成器。它使用基于密钥的哈希消息认证码（HMAC）、基于密码的消息认证码（CMAC）或KECCAK消息认证码（KMAC）来构建PRNG，以生成安全的随机数，进而用于生成密码。生成数字的随机性通过熵和独立同分布（IID）测试，依据NIST SP 800-90B标准进行验证。

主要贡献：

• 构建了基于HMAC、CMAC和KMAC的安全PRNG用于密码生成。
• 分析了不同字符集和长度约束下密码的安全性，并与AES-128/256进行了比较。
• 使用NIST SP 800-90B熵和IID测试进行了实证验证。

2. 文献综述

2.1. 基于线性同余生成器的PRNG

线性同余生成器（LCG）在C和Java等语言中常用，它使用线性递推关系生成数字序列。给定种子 $k$，初始值 $f_0(k)$ 计算为 $f_0(k) \equiv a \oplus k \ (\text{mod} \ m)$。后续数字通过 $f_i(k) \equiv a \times f_{i-1}(k) + c \ (\text{mod} \ m)$ 生成。然而，LCG是不安全的，因为其状态可以通过 $f_{i-1}(k) \equiv (f_i(k) - c) \times a^{-1} \ (\text{mod} \ m)$ 进行逆向推导，从而暴露种子和整个序列。

2.2. 安全伪随机数生成器

为了解决LCG的漏洞，密码学安全的PRNG至关重要。本文重点介绍三种NIST推荐的构造方法。

2.2.1. 基于HMAC的PRNG

其安全性依赖于哈希函数（例如SHA2、SHA3）的单向特性。对于密钥 $k$ 和消息 $M$，HMAC的计算公式为 $r_{hmac}(k, M) = h((k \oplus opad) \ || \ h((k \oplus ipad) \ || \ M))$，其中 $ipad$ 和 $opad$ 是常量。为了生成长比特流，使用计数器模式：$M_i = i \ || \ KDF \ || \ 0x00 \ || \ M \ || \ L$，产生输出 $r_{hmac,i}$。

2.2.2. 基于CMAC的PRNG

其安全性基于高级加密标准（AES）。使用密钥 $k$ 的密码块链接（CBC）模式，将消息 $M$ 分割为块 $M'_1, M'_2, ...$。密文通过迭代计算：$c_{i+1} = AES(k, c_i \oplus M'_{i+1})$，其中 $c_0 = Pad0(0)$。最终输出 $r_{cmac}$ 从最后一个块派生。

2.2.3. 基于KMAC的PRNG

基于SHA-3（KECCAK）哈希函数，KMAC提供可变长度输出，被认为是后量子密码学的有力候选者。其构造遵循类似的认证哈希原理，提供了很高的安全保障。

2.3. 随机性验证方法

NIST SP 800-90B标准提供了评估随机数生成器质量的方法。主要评估两个方面：

• 熵验证： 衡量数据中每比特的不可预测性或“随机性”。高熵对于安全密码至关重要。
• IID（独立同分布）验证： 测试生成的序列在统计上是否独立且遵循相同的分布，确保不存在任何模式或相关性。

3. 提出的安全密码生成器

系统架构包含两个主要阶段：

1. 安全随机数生成： 用户可以选择性地提供一个待哈希消息（TBHM）。该消息与一个密码学密钥一起，由选定的安全PRNG（基于HMAC/CMAC/KMAC）处理，以产生密码学强度的随机比特序列。
2. 密码生成： 将随机比特映射到用户定义或系统定义的字符集（例如，字母数字加符号）上，生成指定长度的最终文本密码。结合字符集大小和密码长度提供的熵，分析其相对于AES-128/256的安全强度。

4. 实验与结果

4.1. 实验设置

进行实验以验证PRNG输出的随机性。测试套件实现了NIST SP 800-90B评估程序，对所有三种PRNG类型生成的大量随机数样本进行熵估计和IID测试。

4.2. 随机性验证结果

结果摘要： 提出的基于HMAC、CMAC和KMAC的PRNG均成功通过了NIST SP 800-90B的熵和IID验证测试。生成的序列在统计上没有显示出与真正随机性的显著偏差，证实了它们适用于密码学密码生成。

图表描述（设想）： 一个条形图，比较了三种PRNG类型的最小熵估计值（单位：比特/比特）与NIST通过阈值。所有三个条形都将显著高于阈值线，其中KMAC可能显示最高值，紧随其后的是HMAC-SHA3和CMAC-AES256。

4.3. 性能分析

对计算效率（例如，每秒生成次数）进行了比较分析。基于CMAC的生成器（使用AES-NI硬件加速）通常显示出最高的吞吐量，其次是基于HMAC的（SHA2/SHA3），而KMAC计算量更大，但提供了强大的后量子安全特性。

5. 结论与未来工作

本研究成功设计并验证了一种基于密码学安全PRNG（HMAC、CMAC、KMAC）的安全密码生成器。生成的密码的安全性源于这些底层密码学原语的已证实的鲁棒性以及PRNG输出经过验证的高随机性。未来的工作包括将生成器集成到浏览器扩展或密码管理器中，探索其在生成密码之外的密码学密钥方面的应用，以及对完整系统进行侧信道攻击抵抗性分析。

6. 原创分析与专家点评

核心见解： 本文是对网络安全中长期存在的薄弱环节——人为选择密码——的一种务实、以工程为中心的回应。其核心价值不在于新颖的密码学，而在于将现有、久经考验的构造（HMAC、CMAC、KMAC）正确应用和严格验证于一个特定的、高影响力的用例。它正确地指出，将密码生成从用户大脑转移到经过验证的密码学过程，是一项根本性的安全升级，类似于密钥交换从对称加密转向非对称加密。

逻辑流程： 逻辑清晰合理，遵循经典的应用研究模式：问题定义（弱密码）→ 对常见解决方案的批判（不安全的LCG）→ 提出稳健的解决方案（基于CSPRNG的生成器）→ 实证验证（NIST测试）。选择NIST SP 800-90B作为验证基准非常出色，因为它是评估密码学环境中随机性的事实标准，为结果提供了即时可信度。

优势与不足：
优势： 本文最大的优势在于其实践验证。许多提案停留在设计阶段。通过将输出提交给NIST的严格测试，作者提供了安全性的具体证据，这对于采用至关重要。包含基于SHA-3的KMAC，显示出对后量子考量的远见，正如NIST正在进行的后量子密码学标准化进程中所指出的那样。
不足/遗漏： 分析有些孤立。一个显著的不足是缺乏对种子管理的讨论。如果PRNG的种子是可预测的或泄露的，那么任何PRNG的安全性都会崩溃。系统如何生成、存储和保护HMAC/CMAC/KMAC的初始密码学密钥？这与算法本身同样关键。此外，虽然将密码强度与AES进行比较是有用的，但更直接地与现有密码生成器（如KeePass或1Password中的）及其底层PRNG（例如使用ChaCha20）进行比较，将能更好地说明其竞争优势。

可操作的见解： 对于安全从业者而言，本文可作为一个蓝图。行动1： 立即弃用任何将LCG或类似非密码学RNG（如`rand()`）用于安全敏感任务的做法。行动2： 在构建或审计密码生成器时，主要检查清单应包括：1）使用CSPRNG（来自NIST SP 800-90A的HMAC_DRBG、CTR_DRBG，或本文的构造），2）使用类似NIST SP 800-90B或Dieharder的套件验证其输出，以及3）从高熵源（例如Linux上的`getrandom()`）实现稳健的种子生成。本文成功地聚焦于第2点，但第1点和第3点同样是完整图景中同等重要的部分。

7. 技术细节与数学公式

所提出生成器的安全性取决于底层密码学函数。关键的数学运算包括：

• HMAC： $r_{hmac}(k, M) = h((k \oplus opad) \ || \ h((k \oplus ipad) \ || \ M))$
• CMAC（CBC-MAC）： $c_{i+1} = E(k, c_i \oplus M_{i+1})$，其中 $E$ 是分组密码（AES）。
• 密码熵： 生成密码的熵 $H$ 为 $H = L \cdot \log_2(N)$，其中 $L$ 是密码长度，$N$ 是字符集大小。对于一个来自94个字符集的16位密码，$H \approx 16 \cdot \log_2(94) \approx 105$ 比特。

8. 分析框架与案例示例

案例示例：审计Web应用的密码重置功能
场景： 一个Web应用为点击“忘记密码”的用户生成临时密码。
框架应用：

1. 识别RNG： 检查服务器端代码。如果发现`Math.random()`（JavaScript）或PHP中的简单LCG，则是一个严重缺陷。
2. 评估熵源： PRNG是如何被种子的？它是否使用系统熵（`/dev/urandom`、`CryptGenRandom`）？
3. 映射到提出的解决方案： 建议将有缺陷的RNG替换为实现本文设计的模块——例如，一个使用`hmac.new`（SHA256）并从`os.urandom(32)`获取种子的Python函数。
4. 验证输出（实施后）： 生成100万个临时密码样本，转换为比特流，并运行NIST STS套件（一个相关的测试套件）以确保随机性。

9. 未来应用与方向

该核心技术可应用于用户密码生成之外：

• API密钥与令牌生成： 为微服务架构生成安全、随机的API密钥和会话令牌。
• 安全默认凭证： 将此生成器嵌入物联网设备固件中，为每个设备创建唯一、强大的默认密码，以缓解基于常见默认设置的广泛攻击。
• 密码学种子生成： 其高质量输出可用于为其他密码学系统提供种子，或生成随机数和初始化向量（IV）。
• 与密码管理器集成： 该算法可以作为开源密码管理器的核心引擎集成，提供透明且可审计的随机性来源。
• 后量子准备： 进一步探索和优化基于KMAC的生成器，与NIST的FIPS 202和SP 800-185标准保持一致，为后量子计算时代做准备。

10. 参考文献

1. M. Bishop，《计算机安全：艺术与科学》，Addison-Wesley，2003年。
2. NIST，《特别出版物 800-63B：数字身份指南》，2017年。
3. NIST，《特别出版物 800-90A：使用确定性随机比特生成器生成随机数的建议》，2015年。
4. NIST，《特别出版物 800-90B：用于随机比特生成的熵源建议》，2018年。
5. J. Kelsey, B. Schneier, D. Wagner，《低熵密钥的安全应用》，ISW '97。
6. D. D. Hwang, B. B. Gupta，《密码安全及其影响研究》，JIS，2019年。
7. NIST，《FIPS 202：SHA-3标准：基于置换的哈希和可扩展输出函数》，2015年。
8. NIST，《SP 800-185：SHA-3派生函数：cSHAKE、KMAC、TupleHash和ParallelHash》，2016年。
9. M. S. Turan, E. Barker, J. Kelsey，《随机比特生成器（RBG）构造建议》，NIST SP 800-90C，2016年。
10. P. G. Neumann，《计算机系统及相关技术使用中对公众的说明性风险》，ACM SIGSOFT，1995年。