以下是一些想法。如果你不耐烦,请跳到最后的结论。
1.什么是安全种子?
Security is defined only relatively to an attack model. We want here a sequence of n bits, that has n bits of entropy with regards to the attacker: in plain words, that any of the possible 2n values for that sequence are equally probable from the attacker point of view.
这是一个与以下相关的模型信息可供攻击者使用。生成和使用种子的应用程序(通常在 PRNG 中)知道确切的种子;种子是否“安全”并不是种子的绝对属性,甚至不是种子生成过程的绝对属性。重要的是攻击者掌握的有关生成过程的信息量。该信息级别根据情况的不同而有很大差异;例如在多用户系统上(例如类 Unix,具有硬件强制的应用程序分离),内存访问的精确计时可以揭示名义上受保护的进程如何读取内存的信息。即使是远程攻击者也可以获得此类信息;这已经是证明了(在实验室条件下)关于 AES 加密(典型的 AES 实现使用内部表,其访问模式取决于密钥;攻击者强制缓存未命中,并通过服务器响应的精确计时来检测它们)。
必须考虑种子的寿命。只要攻击者不知道种子,它就是安全的;此属性必须在之后成立。特别是,不可能从后续 PRNG 输出的摘录中恢复种子。理想情况下,即使在某个时刻获得完整的 PRNG 状态,也不应该提供有关 PRNG 事先生成的任何位的线索。
我想在这里指出的一点是,只有在可以保持安全的上下文中使用种子时,种子才是“安全的”,这或多或少意味着加密安全的 PRNG 和一些防篡改存储。如果这样的存储可用,那么最安全的种子就是生成的种子once,很久以前,并用于由防篡改硬件托管的安全 PRNG 中。
不幸的是,这样的硬件很昂贵(它被称为 HSM,花费几百或几千美元),而且这种成本通常很难证明是合理的(坏种子不会阻止系统运行;这是不可测试性的常见问题)的安全)。因此,通常会选择“主要是软件”的解决方案。由于软件不擅长提供长期的机密存储,因此种子的生命周期被任意缩短:定期获得新的种子。在Fortuna,这样的重新播种应该在生成的伪随机数据的每兆字节中至少发生一次。
总而言之,在没有 HSM 的设置中,使用攻击者无法收集的数据可以相对容易地获得安全种子(因为我们会经常这样做)。
2. 混合
随机数据源不会产生良好的统一位(每个位的值为 1 的概率完全一致)0.5,并且位值彼此独立)。相反,随机源会在特定于源的集合中生成值。这些值可以被编码为位序列,但你的钱并没有物有所值:n熵位,您必须拥有在编码时使用的值远多于n bits.
这里使用的加密工具是PRF它接受任意长度的输入,并产生一个n位输出。这种加密安全的 PRF 被建模为随机预言机:简而言之,在不尝试的情况下预测给定输入的预言机输出的任何内容在计算上是不可行的。
现在,我们有散列函数。哈希函数必须满足一些安全属性,即抵抗原像、第二原像和碰撞。我们通常通过尝试了解它们如何偏离随机预言模型来分析哈希函数。这里有一个重要的点:遵循随机预言模型的 PRF 将是一个很好的哈希函数,但也可以存在良好的哈希函数(在抵抗原像和碰撞的意义上),尽管如此,这些函数很容易与随机预言区分开来。特别是,SHA-2函数(SHA-256、SHA-512...)被认为是安全的,但由于“长度扩展攻击”而偏离了随机预言模型(给定h(m),可以计算出h(米 || 米')对于部分受限的消息m'不知道m)。长度扩展攻击似乎没有为创建原像或冲突提供任何捷径,但它表明这些哈希函数不是随机预言。为了SHA-3 竞赛,NIST表示候选人不应允许这种“长度扩展”。
因此,混合步骤并不容易。现在最好的选择仍然是使用 SHA-256 或 SHA-512,并在选择后切换到 SHA-3(这应该在 2012 年中期左右发生)。
3. 来源
计算机是一台确定性机器。为了获得一些随机性,你必须混合物理世界的一些测量结果。
哲学提示:在某些时候,你必须信任一些聪明的人,他们可能穿着实验室外套或获得报酬进行基础研究。当您使用诸如 SHA-256 之类的哈希函数时,您实际上是在信任一群密码学家,当他们告诉您:我们花了很多年努力寻找缺陷,但一无所获。当你用盖革计数器使用一点正在衰变的放射性物质时,你就相信了一些物理学家的说法:我们非常努力地寻找预测下一个原子内核何时爆炸的方法,但我们没有找到。请注意,在这种特定情况下,“物理学家”包括像贝克勒尔、卢瑟福、玻尔或爱因斯坦这样的人,而“真正的困难”意味着“一个多世纪的积累研究”,所以你在这里并不完全处于未涉足的领域。然而,人们对安全仍然抱有一点信心。
一些计算机已经包含生成随机数据的硬件(即使用和测量物理过程,据物理学家所知,该物理过程是足够随机的)。 VIA C3(一系列 x86 兼容 CPU)就有这样的硬件。奇怪的是,30 年前的家用电脑 Commodore 64 也有一个硬件 RNG(或者是这么说的)维基百科, 至少)。
除非有特殊的硬件,否则您必须使用可能获得的任何物理事件。通常,您会使用击键、传入的以太网数据包、鼠标移动、硬盘访问……每个事件都带有一些数据,并且发生在可测量的瞬间(由于周期计数器,现代处理器具有非常准确的时钟)。这些时刻和事件数据内容可以作为熵源进行累积。对于操作系统本身(可以直接访问硬件)来说,这比对于应用程序来说要容易得多,因此收集种子的正常方法是询问操作系统(在 Linux 上,这称为/dev/random
or /dev/urandom
【各有利弊,选择你的毒药】;在 Windows 上,调用CryptGenRandom()
).
一个极端的情况是 1.2 之前的 Java 小程序,在添加之前java.security.SecureRandom
;由于 Java 在将应用程序代码与硬件隔离方面非常有效,因此获取随机种子是一项艰巨的挑战。通常的解决方案是让两个或三个线程同时运行并疯狂地进行线程切换,这样每秒的线程切换数量就有些随机(实际上,这试图通过操作系统调度程序操作的计时来提取随机性,这取决于计算机上也发生的事件,包括与硬件相关的事件)。这是非常不令人满意的。
时间相关措施的一个问题是攻击者也知道当前时间。如果攻击者具有对机器的应用访问权限,那么他也可以读取周期计数器。
有些人建议通过将放大器设置为最大来使用声卡作为“白噪声”源(现在甚至服务器也有音频)。其他人则主张打开网络摄像头的电源(我们知道网络摄像头视频是“嘈杂的”,这有利于随机性,即使网络摄像头面向墙壁);但带有网络摄像头的服务器并不常见。您还可以 ping 外部网络服务器(例如www.google.com
)并查看返回需要多长时间(但这可以被监视网络的攻击者观察到)。
使用哈希函数进行混合步骤的优点在于,熵只能累积;添加数据没有什么坏处,即使该数据不是那么随机。通过哈希函数尽可能多地填充。哈希函数非常快(良好的 SHA-512 实现在使用单核的典型 PC 上处理速度超过 150 MB/s),并且播种不会经常发生。
4。结论
Use a HSM。它们要花费几百或几千美元,但你的秘密难道不值钱得多吗? HSM包括RNG硬件,运行PRNG算法,并存储防篡改的种子。此外,大多数 HSM 已获得各种国家法规的认证(例如美国的 FIPS 140 和欧洲的 EAL 级别)。
如果你太便宜而不会购买 HSM,或者如果你想保护实际上不太值得的数据,那么使用通过哈希获得的种子构建一个加密安全的 PRNGlots的物理措施。来自某些硬件的任何内容都应该进行哈希处理,以及获取该数据的时刻(读取“周期计数器”)。您应该在此处按兆字节对数据进行哈希处理。或者,更好的是,做not这样做:只需使用操作系统提供的功能即可,其中已经包含此类代码。