使用openssl生成弱密钥要注意什么？ （低熵）

#1 楼

我会回答考虑Linux OS，它是最受欢迎的类Unix操作系统之一（介于urandom的操作系统之间）。如果您需要其他操作系统，请通知我。
我还将使用Linux 3.3.3内核中random.c驱动程序的源代码进行回答，因为它是/dev/random机制的最佳文档之一。另一个是论文：Linux随机数生成器分析，Gutterman，2006年，086.pdf-检查第4-6页和图2.1（幻灯片）。然后，您可以查看《 Linux伪随机数生成器再版》，Lacharme 2012，251.pdf。

Linux中有几个随机池：

512个字节（128个4字节的单词）的主池；将传入的熵添加到其中；
128个字节的辅助池为/dev/random生成随机数

随机池（或另一个辅助池）/dev/urandom生成128个字节


所有三个池都有单独的熵计数器，但是通常主池的计数器是平均值。 “可用”计数器来自主池。

当您请求随机数据时，一部分熵是从相应的辅助池中提取的（使用涉及SHA1的单向函数），然后将其部分添加（混入）到游泳池中。提取的数据的一部分提供给随机数据的使用者。用户和内核都消耗熵，例如启用ASLR后（在大多数发行版中启用），内核使用API​​随机驱动程序来启动进程。有一个有趣的例子，当做几个cat /proc/sys/kernel/random/entropy_avail会偷走大多数熵，也许也是你的情况，这是StackOverflow的证明。要监视entropy_avail，应使用一些守护程序或简单的C程序，这些程序将多次重读池而无需重新启动进程。

当辅助池的熵较低时，将从主池中提取一部分熵（再次使用加密的单向函数），然后将其一部分重新混回到主池中，再将其一部分混合到消耗池中。 />

1）熵必须达到多低才具有危险性？如果我运行cat / proc / sys / kernel / random / entropy_avail，我会得到大约130到几千的任何东西。而且它似乎起伏很快。当没有熵时，entropy_avail仅给出高质量的位和块，而/dev/random给出任何质量的位。当熵高时，/dev/urandom提供高质量的比特，但是当熵为零时，它给出（可能）密码伪随机数序列（几乎在所有其他流行的OS中都有这样的CSPRNG生成器的更好的例子：FreeBsd / OpenBSD，MacOS ，多发性硬化症）。但是251.pdf（第16页的第4.3部分）说：“因此，如果内部状态没有受到损害并且如果三个池都由未知值初始化，则没有熵输入的Linux PRNG被认为是安全的。”
这里对Linux熵估计背后的数学进行了分析（对软件工程师没有什么用，只需要对数字进行加法和减法即可）。

有urandom和/dev/random驱动程序的源代码：http：/ /lxr.linux.no/linux+v3.3.3/drivers/char/random.c#L261（您可以打开/dev/urandom来查看随机驱动程序的实际工作）

 /*
  * Configuration information
  */
 #define INPUT_POOL_WORDS 128
 #define OUTPUT_POOL_WORDS 32
 #define SEC_XFER_SIZE 512
 #define EXTRACT_SIZE 10  --- 10 bytes to be extracted from secondary pools


 /*
  * The minimum number of bits of entropy before we wake up a read on
  * /dev/random.  Should be enough to do a significant reseed.
  */
 static int random_read_wakeup_thresh = 64;

如果DEBUG_ENT低于64位，则不会从available_entropy中读取任何内容。因此，这是极低的值，较小的值将阻止正在阅读/dev/random的每个人。

如果/dev/random低于128位，并且有一些好人可以从用户空间为我们提供更多的熵，请尝试让他们这样做。因此，即使是128位熵，我们也不是最好的形式，也不愿意寻求帮助。

 /*
  * If the entropy count falls under this number of bits, then we
  * should wake up processes which are selecting or polling on write
  * access to /dev/random.
  */
 static int random_write_wakeup_thresh = 128;

如果有128 * 28 = 3584位以上，我们拒绝添加来自外部来源的所有可用熵（但是某些“样本”仍将混入主要池中）；当可用熵很多时，会将一些传入的熵添加到辅助池中（而不是urandom池中）。


1a）攻击在130可行吗？它必须走（50，10，1，0）？我还没有看到任何硬数字。攻击只是理论上的，还是要在实践中破解它需要花费多少工作？池。请参阅http://eprint.iacr.org/2006/086.pdf-初始化中的第2.2部分。主池最初是在系统启动时填充的，攻击者想预测，初始化方式（使用了哪些随机源以及输入的数据是什么）。这在嵌入式设备或无人值守服务器或虚拟服务器中可能会出现问题，因为这些设备的熵源数量很少。主要来源是：用户生成的（键盘，鼠标），外围设备（例如，来自网络的中断），响应时间难以预测的设备（硬盘）。

大多数嵌入式设备将没有硬盘，外围设备数量将很少（并且都是该型号的标准配置），没有任何用户坐在启动PC的前面，并且在无法预料的时刻移动鼠标并按下键。而且它们可能具有劣质的定时资源（来自外部源的熵数据是32位时间戳和32位属性；如果只能根据32kHz石英测量时间戳，则情况很糟，更好的方法是使用时钟滴答计数器或现代的Intel / AMD CPU（3 GHz，具有一些难以预测的变化）。

嵌入式设备具有使用标准闪存映像的标准化设置（通常不会在设备整个实时运行时更新），并且某些设备或只读可启动媒体（Knoppix，OpenWRT）在以下情况下错误地保存/恢复了熵开机/关机。正确的实现是在关机时将512个字节从某些随机存储保存到永久存储，并在启动时提早将它们反馈回available_entropy（Linux来源中也有注释：确保系统启动时不可预测； SysV-era启动系统中的/dev/random脚本） 。

有一些嵌入式问题的新概述，以及在哪里可以找到好的随机性：http://cseweb.ucsd.edu/users/swanson/papers/Oakland2013EarlyEntropy.pdf工作结论：“随机性是一项基本的系统服务。除非已准备好为应用程序提供高熵随机性，否则不能说系统已成功启动。”

我认为最危险的事情是在高度嵌入式设备上的已知时间启动后，在它们启动后及早生成一些密钥。为了破解密钥，需要黑客对所有熵源进行反向预测，并在生成密钥时对主要池状态和次要池状态进行建模。这个任务很艰辛，但是有时候攻击密钥本身会更容易。我现在无法显示urandom攻击的示例，但我认为某些脆弱的安装中存在这些示例。

我还认为debian版本的openSSL比糟糕的随机质量更致命：http://www.schneier.com/blog/archives/2008/05/random_number_b.html http://xkcd.com/221 /每个固定的RSA密钥大小只有大约数十万个密钥，因为禁用了urandom输入，并且openssl唯一且最佳的熵输入是进程ID或PID，通常限制为32-65在Linux上成千上万。


2）openssl是否会阻塞，直到有足够的熵来生成密钥？我的理解是/ dev / urandom不会阻止，并且是默认设置，但/ dev / random会阻止。由于性能/一致性原因，我假设/ dev / random不是默认值？


openssl不会阻塞（我认为，没有检查现代版本），因为没有明确的方法可用于检测urandom的熵过低并转换为-完全PRNG模式。 / dev / urandom上只有几个ioctl可以读取avaliable_entropy。 openssl仅尝试使用自己的PRNG，该PRNG由当前时间，openssl的pid和来自urandom或RANDFILE的数据来播种。 /char/random.c#L109

 /*
  * When the input pool goes over trickle_thresh, start dropping most
  * samples to avoid wasting CPU time and reduce lock contention.
  */

 static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;

因此，正如所说的随机和urandom的来源一样，您不应从/etc/rc.d/init.d/random生成长期密钥，但仍然可以使用它来生成用于执行不重要操作的会话密钥（例如，用于SSL的会话密钥到Facebook以与猫一起查看更多图像）。是要生成的密钥。如果它是TLS的会话密钥，并且您在服务器上，则使用urandom将限制可以连接的客户端数量（没有那么多的熵，/dev/random将会阻止，我认为这是在openSSL中使用urandom的原因之一） 。

但是，当您为20年的SSL证书生成一些4096位RSA密钥时，您希望使用具有良好外部熵源的计算机，在重新启动后正确保存/恢复熵，并且该机制已被人类使用了一段时间。

实际上，当真正的硬件随机源可用（而不是Linux LRNG-PRNG）可用时，最好生成更多有价值的密钥，例如一些平衡的热噪声测量方案（仅采用Analog的最低精度位） -数字转换器-ADC）。即使在现代的Intel CPU中（也可能在VIA的cpus中，也不了解AMD或ARM），也存在良好的硬件随机源（带有输出AES的逆变器回路的热噪声），请检查服务器上的/dev/random设备。更新某些HW RNG（论文2013）中可能存在一些缺陷，这些缺陷很难检查，因为有缺陷的随机数据是由设备制造商的私钥加密的。

并且是唯一正确的处理方法高价值密钥-用于在经过认证的HSM（硬件安全模块）中生成它们，并仅在防篡改HSM内将它们保留为完整版本（完整私钥）（尝试打开此类HSM盒，或取出电池并您的私钥将消失。有趣的情况是，当该密钥是某个银行中最主要的密钥时-数百万个PIN码可能会在一瞬间丢失。只能以拆分形式提取私钥-当在安全管理人员周围散布N个密钥（每个部分都可以在安全员的密钥下加密）并且需要K个部分来重建原始密钥（例如，通过Shamir方案）。

主要规则是估计信息的价值（例如，您的私人照片花费约数十万美元；但是Google或Facebook的SSL证书花费数十亿美元），信息应保存多长时间以及应保存多少被投入破坏您的信息。例如。设置橡胶软管密码分析可能会花费大约100-500,000美元（窃取某人或知道/可以访问该机密的人/包含机密的东西，并应用车库扳手/散热装置/电烙铁来获取机密-烙铁应只能用于从闪存卡上拆下闪存芯片，而不能用于其他事物），因此HSM和密钥的拆分备份是银行和IT巨头的有价值的密钥的唯一变体。 > 2b）openssl中是否有标志或选项，您可以在其中选择使用/ dev / random来确定自己的身份？使用来自/ dev / random的数据：http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=88728

 109 * The two other interfaces are two character devices /dev/random and
 110 * /dev/urandom.  /dev/random is suitable for use when very high
 111 * quality randomness is desired (for example, for key generation or
 112 * one-time pads), as it will only return a maximum of the number of
 113 * bits of randomness (as estimated by the random number generator)
 114 * contained in the entropy pool.
 115 *
 116 * The /dev/urandom device does not have this limit, and will return
 117 * as many bytes as are requested.  As more and more random bytes are
 118 * requested without giving time for the entropy pool to recharge,
 119 * this will result in random numbers that are merely cryptographically
 120 * strong.  For many applications, however, this is acceptable.

（您可以验证使用strace的openssl实际上打开了“文件名”以使其随机而没有打开/ dev / urandom）


3）在共享框上，邻居是否有任何方法可以耗尽所有资源系统的随机性，迫使您生成弱密钥？似乎直到有足够的熵才能解决上面的问题（＃3）。


有一种方法可以减少大多数随机性（甚至通过TCP-syn cookie生成来远程消除，请参见086论文的3.4节；保留约64-128位仅可用于/ dev / random，第251页，第18页。 ）。但是即使耗尽，邻居也无法仅通过听/dev/hwrng和urandom来通过urandom加密弱点预测您生成的密钥。你们两个都将获得池SHA1的不同部分的部分SHA1-s（每个都被主池中的SHA1的部分重新填充），而且你们中的任何人都不能重建主池的状态。最糟糕的情况是使用urandom时，可用的熵为0（这可能很难实现）。即使在这种情况下，您将获得具有未知种子的加密伪随机生成器。攻击者被迫破解递归SHA1并精确猜测种子（如果熵被耗尽，则为128字节的随机信息；在非耗尽情况下，则为512字节的主池）。即使系统中只有一个用户专门获得了urandom的所有输出（如果他有时仍然没有主池内容），也无法解决此任务。

共享计算机的根可以做所有事情：编写内核模块以转储主/备用池的状态；模拟有1600万比特的可用熵，而/dev/random将循环输出类似/dev/random的东西;窃取您的openssl进程的内存转储以转储密钥；读取您存储在fs私钥上的内容；截取从您发送到“您的” openssl的按键，作为密码短语，以解密安全存储的私钥。而聪明的邻居，如果他是穿着羊皮的狼，将尝试获得root权限来获取您的密钥。

共享计算机上的聪明攻击者可能会尝试对您的加密库和加密算法进行侧信道攻击，并且存在实际的攻击，例如使用精确的缓存度量（Bernstein 2005：“对AES的缓存定时攻击”），即使他居住在其他虚拟机中也是如此。这是例如将AES加密作为独立的硬件块移动到Intel CPU内，不易于缓存侧通道泄漏。


4）给定您已经生成的公钥/私钥，有什么方法可以证明它是低生成的？熵？


我认为不可以，如果正确初始化了池，并且其内容保持安全（没有root攻击者）。

在一些非常差劲的嵌入式安装中，没有计时功能（设备启动到1970年），没有保存/恢复池（或在读入urandom之后恢复得太晚，例如在某些ubuntus中），之前没有任何随机输入密钥已生成；当密钥由某个启动脚本生成时；然后攻击者可以对池的状态进行建模并重新生成相同的密钥。 /files/conference/usenixsecurity12/sec12-final228.pdf“挖掘P和Q：检测网络设备中普遍存在的弱密钥”。他们通过扫描数百万个设备并比较它们的密钥来检测到错误的密钥：


对于TLS，至少有5.23％的主机使用制造商的默认密钥，这些默认密钥所有者从未更改过，另外0.34％似乎由于随机数生成器发生故障而与一个或多个其他主机生成了相同的密钥。


并且通过检查密钥中的弱点；再次-通过比较许多扫描的密钥，对于RSA，他们发现了许多模块N1和N2，其中N1 = p1 * q1和N2 = p1 * q2。我了解这种情况，因为存在弱键，但是您无法区分弱键和好键。但是，如果密钥是从固定的低熵设备状态（首次引导，早期生成）生成的，则很有可能找到另一设备（与HW平台相同）与第一设备生成相同的p或q（如果两者相同，则N相同）。


更令人震惊的是，我们能够为64,000（0.50％）个TLS主机和108,000（1.06％）的SSH主机计算私有密钥仅在随机性不足的情况下，利用RSA和DSA的已知弱点单独扫描数据。在RSA的情况下，恰好共享一个素数的不同模数将导致公共密钥看起来不同，但其私钥可以通过计算最大公因数（GCD）来有效地计算。 > DSA要求生成具有大量熵的“短暂密钥k”。 k不应针对不同的消息重复，但有些k相同。


几乎所有（脆弱的主机）提供的信息都将其标识为无头或嵌入式系统，包括路由器，服务器管理卡，防火墙，以及其他网络设备。此类设备通常会在首次启动时自动生成密钥，并且与传统PC相比，其熵源可能有限。

.. Linux的随机数生成器（RNG）可能会出现启动时的熵孔，从而导致产生urandom。在无头和嵌入式设备中可能发生的条件下确定输出。