SEEDLab-伪随机数生成实验

在安全软件中，生成随机数是一项非常常见的任务。在许多情况下，加密密钥并不是由用户提供的，而是由软件在内部自动生成的。这些密钥的随机性非常重要；否则，攻击者就可能预测出加密密钥，从而破坏加密机制的安全性。 许多开发者根据自己以往的经验，知道如何生成随机数（例如用于蒙特卡洛模拟（Monte Carlo simulation））。因此，他们会使用类似的方法来生成用于安全目的的随机数。然而，一个随机数序列对于蒙特卡洛模拟来说可能是好的，但对于生成加密密钥来说却可能是不安全的。开发者需要了解如何生成安全的随机数，否则就很容易犯错误。类似的错误曾经出现在一些著名的软件产品中，例如Netscape和Kerberos。 在本实验中，学生将学习为什么常见的随机数生成方法并不适合用于生成秘密数据（例如加密密钥）。此外，学生还将学习一种用于安全目的的标准伪随机数生成方法。 本实验涵盖以下主题： • 伪随机数生成（Pseudo Random Number Generation） • 随机数生成中的常见错误 • 生成加密密钥 • /dev/random 和 /dev/urandom 设备文件

任务1 以错误方式生成加密密钥

为了生成高质量的伪随机数，我们需要从某个真正具有随机性的值开始。 清单1 生成一个128位加密密钥

printf("%lld\n", (long long) time(NULL));
srand (time(NULL)); ➀
for (i = 0; i< KEYSIZE; i++){
key[i] = rand()%256;
printf("%.2x", (unsigned char)key[i]);

库函数time()返回当前时间，其值表示自Epoch 1970-01-01 00:00:00 +0000 (UTC)以来经过的秒数。

如图1所示，因为时间是持续变化的，使用时间作为随机数种子生成的随机数是互不相同的。

如图2所示，将第➀行注释掉，再次运行程序，如果不使用srand进行种子的更新，那么每轮生成随机数都是相同的。

任务2 猜测密钥

2018年4月17日，Alice完成了她的报税表，并将该报税表（一个PDF文件）保存在自己的磁盘上。为了保护该文件，她使用任务1中程序生成的密钥对PDF文件进行了加密。她把这个密钥写在一本笔记本上，并把笔记本安全地存放在保险柜里。几个月后，Bob入侵了她的电脑，并获取了一份加密后的报税表副本。由于Alice是一家大公司的CEO，这个文件非常有价值。

Bob无法获得加密密钥，但在查看Alice的电脑时，他看到了密钥生成程序，并怀疑Alice的加密密钥可能就是由该程序生成的。他还注意到加密文件的时间戳是“2018-04-17 23:08:49“。他猜测密钥可能是在文件创建之前的两个小时内生成的。

由于该文件是PDF文件，而PDF文件有固定格式的文件头（header）。文件头的开头通常是版本号。在该文件创建的时间附近，PDF-1.5是最常见的版本，因此文件头通常以%PDF-1.5开头，这部分共有8个字节的数据。接下来的8个字节数据也比较容易预测。因此，Bob很容易得到前16个字节的明文。

根据加密文件的元数据（metadata），Bob知道该文件使用AES-128-CBC模式加密。由于AES是128位分组密码，16字节的明文正好是一个数据块。因此Bob已经知道了一块明文及其对应的密文。此外，Bob还可以从加密文件中得到初始向量（IV）（IV从不加密）。

Bob已知的信息如下：

Plaintext：255044462d312e350a25d0d4c5d80a34
Ciphertext：d06bf9d0dab8e8ef880660d2af65aa82
IV：09080706050403020100A2B2C2D2E2F2

因此可以找出Alice的加密密钥，从而解密整个文档。编写一个程序来尝试所有可能的密钥。

如图3所示，编写程序，从PDF文档加密时间的两小时之前开始枚举，将时间作为种子，对明文进行加密并与密文进行对比，如果相等即为成功找到密钥。

如图4所示，运行程序，成功找到了密钥95fa2030e73ed3f8da761b4eb805dfd7。

任务3 测量内核的熵（Entropy）

在虚拟世界中，很难真正产生随机性，也就是说仅靠软件很难生成真正的随机数。因此，大多数系统会从物理世界获取随机性。比如键盘按键之间的时间间隔、鼠标移动和鼠标中断的时间信息、中断发生的时间间隔收集随机数。 当然，并不是所有的中断都是好的随机来源。例如，定时器中断（timer interrupt）是可预测的，因此不是一个好的随机来源；而磁盘中断（disk interrupt）通常是更好的随机来源。最后一个函数则通过块设备请求完成的时间来收集随机性。随机性的多少通常用熵（entropy）来衡量。这里的“熵”与信息论中的熵含义不同。在这里，它只是表示系统当前拥有多少位随机数。 使用watch命令持续监控熵的变化。watch会周期性执行某个程序，并在全屏中显示输出。下面的命令每0.1秒执行一次cat：

watch -n .1 cat /proc/sys/kernel/random/entropy_avail

实验观察表明，移动鼠标是补充熵值最有效的方式，因为它产生高频且时间戳高度不规律的硬件中断；键盘输入效果其次，击键间隔的微秒级差异同样贡献可观的熵；点击鼠标和访问网站产生离散的中断事件，贡献中等程度的熵；而读取大文件的贡献最小，因为现代SSD的I/O完成时间差异极小。

任务4 从 /dev/random 获取伪随机数

Linux 会把从物理资源收集到的随机数据存储到一个随机池中，然后通过两个设备将这些随机性转换为伪随机数：/dev/random和/dev/urandom 这两个设备的行为是不同的。/dev/random是一个阻塞设备（blocking device）。也就是说，每当该设备输出一个随机数时，随机池中的熵值会减少。当熵值降到0时，/dev/random就会阻塞（block），直到系统重新收集到足够的随机性。我们可以设计一个实验来观察/dev/random的行为。使用cat命令持续从/dev/random读取伪随机数，并把输出通过hexdump进行格式化显示： cat /dev/random | hexdump 运行上述命令，同时使用watch命令监控系统的熵值（entropy）。如果你不移动鼠标也不输入任何内容，会发生什么？然后随机移动鼠标，看看是否能观察到任何变化。请在报告中描述并解释你的观察结果。

如图5所示，熵值会随着随机数的生成不断减少，当减少到一定程度后，设备阻塞。当移动鼠标后，随机熵增加，随机数又重新开始生成。 问题： 如果一个服务器使用/dev/random来为客户端生成随机的会话密钥，请描述攻击者如何对这样的服务器发起拒绝服务攻击（Denial-Of-Service, DOS）。

1. 攻击者大量发送连接请求，每个请求都触发服务器调用/dev/random生成一个会话密钥
2. 服务器的熵池被快速耗尽
3. 熵池归零后，/dev/random陷入阻塞，后续所有密钥生成操作挂起
4. 合法用户的连接请求全部卡在“等待生成会话密钥“阶段，服务实际上瘫痪

任务5 从/dev/urandom获取随机数

Linux还提供了另一种访问随机池的方法，即通过/dev/urandom设备。与/dev/random不同的是，这个设备不会阻塞（non-blocking）。/dev/random和/dev/urandom都使用随机池中的数据来生成伪随机数。当系统中的熵不足时： • /dev/random 会暂停（阻塞）等待新的随机性； • /dev/urandom 会继续生成新的随机数。 可以把随机池中的数据看作一个“种子（seed）”。正如我们所知道的，只要有一个种子，就可以生成任意数量的伪随机数。让我们观察/dev/urandom的行为。再次使用cat命令从该设备获取伪随机数。运行下面的命令，并描述移动鼠标是否会对结果产生影响。

cat /dev/urandom | hexdump

如图6所示，使用/dec/urandom生成随机数不会阻塞，且是否移动鼠标对其生成没有影响。 接下来，测量随机数的质量。我们可以使用一个叫ent的工具，该工具已经安装在我们的虚拟机中。从/dev/urandom生成1MB的伪随机数并保存到文件中，然后对该文件运行ent测试。 如图7所示，该1MB随机数样本的六项统计指标全部表现优异：熵值高达7.9998 bits/byte（几乎达到理论上限8.0），压缩率为0%，卡方检验结果落在理想区间，算术均值与理论值127.5的偏差仅0.011，蒙特卡洛估算π的误差只有0.12%，序列相关系数接近于0，说明字节间完全独立无规律。综合来看，这组数据的随机性接近完美，分布高度均匀、不可预测、无统计偏差，完全符合密码学级别随机数的质量要求。 从理论上讲，/dev/random设备更加安全，但在实际应用中，两者差别并不大，因为/dev/urandom使用的“种子”本身是随机且不可预测的。/dev/random的阻塞行为有一个很大的问题：阻塞可能会导致拒绝服务攻击。因此，在实践中通常推荐使用/dev/urandom来获取随机数。在程序中使用/dev/urandom非常简单，只需要直接从该设备文件读取数据即可。

如图8、9所示，直接从该设备文件读取数据，成功生成256位密钥并打印。