65.9K
CodeProject 正在变化。 阅读更多。
Home

Fortuna - 加密安全的伪随机数生成器

citadel
starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.63/5 (12投票s)

2004年3月4日

17分钟阅读

viewsIcon

101259

downloadIcon

3510

一个 C++ 组件，用于使用 Fortuna 算法生成加密安全的伪随机数

Fortuna Generator

Fortuna Pools

Fortuna Sources

引言

伪随机数生成器 (PRNG) 在许多加密操作中都有使用。最重要的加密操作之一是生成加密密钥。如果攻击者能够攻破您的（伪）随机数生成器，他们也可能能够攻破您的加密密钥。这很糟糕；如果攻击者知道用于加密您数据的密钥，他们就可以解密您加密的内容。因此，一个好的 PRNG 必须生成难以预测的“随机”数字，并且 PRNG 本身的状态必须难以被攻破。尽管 Fortuna 是新的（密码学家从不信任任何新事物），但它在设计时就考虑了这两个目标。Fortuna 由密码学/安全领域两位经验丰富的知名人士设计。

Fortuna 是由 Bruce Schneier 和 Niels Ferguson 在他们的著作《实用密码学》中开发的一个随机数生成器。Fortuna 解决了他们之前的 PRNG Yarrow 的一些缺点。实现 Yarrow 的最大挑战是 Yarrow 需要熵估计。Fortuna 通过移除熵估计器来克服这个问题。除了移除熵估计器外，最大的设计改变是 Fortuna 有 32 个池用于收集熵。

我的 Fortuna 实现由 4 部分组成。有一个生成实际伪随机数据的生成器。有一个由 32 个熵源数据池组成的累加器。有一个源管理器来管理数据源。还有一个种子文件，用于维护池状态的副本，并确保 Fortuna 即使在计算机刚重启后也能生成伪随机数据。Fortuna 通过使用 32 个熵池来避免要求准确估计熵的问题。熵池用于定期重新播种生成器。因此，如果一个池或一个伪随机数流被攻破，下次重新播种时，生成器将使用新的种子，从而未来的 PRN 不会被攻破。

作者为 Fortuna 提供了许多实现细节。我大部分时间都遵循了他们的建议，但也做了一些修改。有关更完整的信息，请访问 www.citadelsoftware.ca/fortuna。例如，作者建议不要使用 C 或 C++ 编写安全软件，而这是一个 C++ 组件。我将尝试在过程中指出我偏离他们建议的地方。

设计目标

此 Fortuna 实现的主要设计目标是开发一个适合在 Web 服务器上使用的 PRNG。Web 服务器的一个显著特点是通常没有太多来自键盘或鼠标的输入。因此，此 Fortuna 实现使用 Windows 可用的信息作为生成器的“熵”源。请注意，这种类型的生成器比“伪随机”更准确地称为“混沌确定性”，因为源并非真正随机。此 Fortuna 实现的一些熵来自于使用高性能计时器来计时操作系统调用。我知道计时数据不是真正的熵，因为它是确定性的。我将在下面详细介绍高性能计数器。而无法预测 PRNG 的结果是我们希望具备的主要属性。

此 Fortuna 实现的另一个设计目标是使 PRNG 难以被成功攻击。这是通过以下方式实现的：

  • 有大量数据被输入熵池，有些具有高熵，有些具有低熵。由于数据量大，攻击者很难攻破单个池的状态。
  • 使用来自 Windows 注册表的数据，以便您的环境特定的应用程序数据作为（低）熵源包含在累加器中。
  • 每个进程的状态信息（页面错误、内存、I/O 读取和写入）被用作熵源。
  • 大量使用高精度计时器作为熵源。
  • 避免将关键随机数据简单地存储在连续的内存区域中，以避免内存扫描攻击。
  • 在不需要宝贵的随机数据时，谨慎地将其在内存中随机化。

请注意，真正的“熵”源需要物理源；有关硬件 RNG，请参阅 ComScire（我与该公司无关，但从我读到的所有信息来看，他们似乎是一家受人尊敬、信誉良好的公司，产品质量很好）。

如果您

  • 信任您的网络安全
  • 确信攻击者无法访问整个注册表，并且可以监控您机器上所有正在运行的进程的状态
  • 确信攻击者无法在您的机器上运行自己的软件来尝试确定 32 个数据池的内容并攻破生成器
我相信这个 PRNG 可能非常适合您。

为了攻破 Fortuna 的这个实现，攻击者将需要访问整个注册表、进行进程监控等。攻击者需要严重攻破一台机器才能做到这一点。因此，我认为 Fortuna 的这个实现对于许多基于 Web 的应用程序来说是可以接受的。下面我列出了用于填充数据池的所有数据源。请注意，我说的是“数据池”，而不是“熵池”。这是因为使用的一些源的熵并不高。例如，我使用整个注册表作为池的源。现在，注册表中并没有多少熵，但是攻击者要了解整个注册表需要整个机器都被攻破。如果发生这种情况，您将面临很多问题，而不仅仅是您的 PRNG 可能被攻破。

类设计

Fortuna 的这个实现是高度多线程的。每个数据源都在自己的线程上运行，每个数据池也都在自己的线程上运行。每个数据源循环遍历所有池，以轮询方式将一个字节分发给每个池。每个池对象都有一个互斥锁来保护池数据。由于每个源将其数据分布到每个池中，这为源数据在池中的分布增加了另一层“确定性混沌”。当两个不同的源同时访问一个池时，线程调度程序决定哪个线程首先获得访问权限。虽然线程调度程序不是随机的，但考虑到有 32 个池（每个池都在自己的线程上）和超过 32 个源（每个源都在自己的线程上），预测哪个源字节会最终进入哪个池会变得难以处理。

所有这些线程都不会给您的应用程序增加太多开销，因为它们大部分时间都在等待。每个源都调用 'WaitForSingleObject' 来确定组件是否正在关闭。

Fortuna 实现的 UML 图可以在我的网站 这里 找到。

熵源

熵源（此处“熵”一词的使用是松散的，如上所述，它们更适合描述为数据源）分布在各个熵池中。在《实用密码学》一书中，每个源事件只添加到_一个_池（参见书中 10.5.6）。在此实现中，每个源事件中的每个字节都以轮询方式分发给各个池。每个字节的数据都附带一个字节，该字节指定该源字节的熵位数。这允许池跟踪池中熵的位数。

每个源都必须提供此虚拟方法来提供一些“混沌数据”（我知道，我知道，这是一个俗气的名字）。

  // derived classes must implement this to return their data
  // pair - unsigned char, this is the chaotic data
  // pair - int,      this is the number of bits of 
  // entropy in the associated byte
  virtual bool GetChaoticData(std::vector<std::pair<unsigned char, 
    int> > vData)=0;

高分辨率性能计数器

现在大多数新计算机都配备了高分辨率性能计数器。计数器的频率可以通过 API 函数获得。

  BOOL QueryPerformanceFrequency(LARGE_INTEGER* lpFrequency);

如果没有高性能计时器，则返回值为 0。在我 2.2GHZ 的笔记本电脑上，高性能计时器的频率是 3,579,545。请注意，频率与 CPU 频率不同。高分辨率性能计数器的值通过以下方式获得：

  BOOL QueryPerformanceCounter(LARGE_INTEGER* lpPerformanceCount);

使用高性能计数器获取计时数据时，计时器中每改变一个字节，池中就会增加一比特熵。

我进行了一些关于高性能计数器的实验，以确定通过使用高性能计数器来计时 Sleep 1ms 的调用，可以声称有多少比特的熵。我为此测试编写了一个单独的程序。我使用高性能计时器来获取 Sleep 函数周围的高性能计数，如下所示：

  hpTimer.Start();
  Sleep(dwSleep);
  hpTimer.Stop();

  diff = hpTimer.m_stopTime.LowPart - hpTimer.m_startTime.LowPart;

  // subtract the number of counts to sleep
  diff -= dwFreq/1000*dwSleep;

其中 hpTimer 是包装高性能计时器的简单类。然后，我将时间差的最低有效位添加到我自己编写的位向量（称为 BitBucket）中（成员 m_bitbucket，类型为 BitBucket）。我需要互斥锁，因为我使用了 200 个线程来加速比特生成，并且有一个单独的线程负责提取累积的最低有效位并将其写入文件。文件写入线程在提取每个比特生成线程的比特后会休眠 100 毫秒。

  uc = (unsigned char)(diff & 0x01); // extract the lsb
  m_mutex.Wait(INFINITE);
  m_bitbucket.Add(uc);
  m_mutex.Release();

我累积了所有最低有效位，将大约 60MB 的数据写入一个文件，然后运行了 DieHard 随机性测试。数据通过了大多数 diehard 测试。如果您对更多细节感兴趣，可以在我的网站 www.citadelsoftware.ca/hptimer 上找到。

Windows 注册表

Windows 注册表是一个庞大的数据存储库。这是用于填充数据池的数据源之一。同样，这不是随机数据，但重现这些数据需要攻击者能够访问整个注册表。处理注册表进行此类应用程序时的一个挑战是确保打开的每个注册表项句柄都能被正确关闭。为了使此 PRNG 能够在服务器上运行数周或数月而不重启，绝不能有资源泄漏。我已通过使用 RegCloseKey() 在不再需要句柄时关闭注册表项句柄来确保这一点。此外，注册表项以 KEY_ENUMERATE_SUB_KEYS | KEY_QUERY_VALUE 打开，因此只请求读取权限。

注册表中的任何数据都不会被认为会为池增加熵，除了 CLSID。同样，这是一个非常保守的方法。使用注册表并有四个不同的源线程将数据分布到池中，这大大增加了攻击者的工作难度。

注册表是系统范围的资源。几乎所有应用程序都会在某个时候使用注册表。FortunaCSI PRNG 必须小心，不要对注册表施加过多的负载。为此，每个源线程的线程优先级都会降低。这是通过以下方式实现的：

BOOL m_bSetThreadPriority = SetThreadPriority(hThreadId, 
  THREAD_PRIORITY_BELOW_NORMAL);

此外，在每次访问注册表后，每个遍历注册表的源线程都会休眠一段时间。休眠时间通常为 3-10 毫秒。实际休眠时间是线程 ID、“this”指针以及从注册表中提取的数据的函数。这使得攻击者更难确定来自注册表的数据最终会进入哪个 32 个池中的哪个。

代码中也正确处理了具有访问限制的键的情况。尝试打开注册表键可能会导致错误代码 ERROR_ACCESS_DENIED。发生这种情况时，将放弃子键，并继续处理具有访问限制的键的父键。

我通过编写一个包含注册表中每个键和值的日志文件来测试注册表遍历逻辑。这暴露了许多问题，特别是当我没有正确处理没有读取权限的键时。

HKEY_CLASSES_ROOT\CLSID

此 Fortuna 实现的一个源线程循环遍历 HKCR\CLSID 列表中的所有 GUID。这是机器上安装的每个 COM 对象的每个 GUID 的列表。在我一台使用了大约一年的 2.2 Ghz Windows/XP 笔记本电脑上，此列表中大约有 5600 个 GUID，并且遍历这些 GUID 的每个周期大约需要 1 分钟。

在将 GUID 的字节添加到数据池时，我只为每个字节与前一个 GUID 不同的字节计算 1 比特的熵。这使得“熵”的估计量非常保守。避免过于频繁地重新播种生成器很重要。

在我机器上读取所有 CLSID 一次大约需要 30 分钟。

HKEY_CLASSES_ROOT

处理 HKCR 在我的机器上大约需要 2.5 小时。

HKEY_CURRENT_USER

HKCU\Software 是应用程序在注册表中存储应用程序特定数据的地方。例如，您的文本编辑器很可能会在此处列出您最近使用的文件。每个应用程序包含大量此类数据，以及 GUI 数据，如您的背景颜色等。在我的 Win/XP 笔记本电脑上，一个专用线程需要大约 8 分钟才能遍历所有这些注册表数据。导出键名和仅 ASCII 数据的结果是一个约 270K 的文件。

在我的机器上，遍历 HKCU 大约需要 30 分钟。

HKEY_LOCAL_MACHINE

HKLM 是注册表最大的存储库。在我的机器上，处理它大约需要 5 小时。

进程信息

每个进程都有大量信息可用。如果您查看任务管理器，“查看”->“选择列”，您可以看到一些可用信息的示例：
  • 进程名称
  • 进程 ID
  • 内存使用
  • 页面错误
  • 句柄
  • 线程
  • I/O 读取
  • I/O 读取字节
  • I/O 写入
  • I/O 写入字节
  • I/O 其他
  • I/O 其他字节

上述每个数量都可以通过不同的 Win32 API 调用获得。以下是一些方法以及可用的数据。有关具体函数的更多信息，请参阅 MSDN。

来自以下结构的所有非零字节将被添加到数据池。当某个字节与上一次调用中同一进程的值不同时，该字节将被标记为包含一个比特熵。否则，数据将被添加到池中，但不声明熵。

GetProcessIOCounters

此方法填充 IO_COUNTERS 结构。这提供了以下信息：

typedef struct _IO_COUNTERS
{ ULONGLONG ReadOperationCount;
  ULONGLONG WriteOperationCount;
  ULONGLONG OtherOperationCount;
  ULONGLONG ReadTransferCount;
  ULONGLONG WriteTransferCount;
  ULONGLONG OtherTransferCount;
} IO_COUNTERS, *PIO_COUNTERS;

GetProcessTimes

此方法提供每个进程的内核时间和用户时间。

GetProcessMemoryInfo

此方法填充 PROCESS_MEMORY_COUNTERS 结构。这提供了以下信息：

typedef struct _PROCESS_MEMORY_COUNTERS {
  DWORD cb;
  DWORD PageFaultCount;
  SIZE_T PeakWorkingSetSize;
  SIZE_T WorkingSetSize;
  SIZE_T QuotaPeakPagedPoolUsage;
  SIZE_T QuotaPagedPoolUsage;
  SIZE_T QuotaPeakNonPagedPoolUsage;
  SIZE_T QuotaNonPagedPoolUsage;
  SIZE_T PagefileUsage;
  SIZE_T PeakPagefileUsage;
} PROCESS_MEMORY_COUNTERS;

GetPerformanceInfo

此方法填充 PERFORMACE_INFORMATION （请注意 psapi.h 中的代码拼写错误）结构。这提供了以下信息：

typedef struct _PERFORMACE_INFORMATION {
  DWORD cb;
  SIZE_T CommitTotal;
  SIZE_T CommitLimit;
  SIZE_T CommitPeak;
  SIZE_T PhysicalTotal;
  SIZE_T PhysicalAvailable;
  SIZE_T SystemCache;
  SIZE_T KernelTotal;
  SIZE_T KernelPaged;
  SIZE_T KernelNonpaged;
  SIZE_T PageSize;
  DWORD HandleCount;
  DWORD ProcessCount;
  DWORD ThreadCount;
} PERFORMACE_INFORMATION, *PPERFORMACE_INFORMATION;

QueryWorkingSet

Win32 API 提供 QueryWorkingSet 来访问进程当前加载的内存页的工作集。我找到了一篇有些过时的文章，提供了更多关于工作集的信息。如果您有兴趣，这里是 Matt Pietrek 的文章 Matt Pietrek，其中提供了更多关于工作集的信息（如果您知道有更近期的文章，我很乐意提供引用）。

每次获得进程的工作集时，都会将字节与前一个工作集的字节进行比较。如果大小不同，则每个非零字节添加一个比特熵。如果字节数相同，则每个不同的字节添加一个比特熵。与前一个工作集相同的字节会被添加到池中，但不会声明熵。这使得熵估计量非常保守。

一些工作集可能非常大，超过 10MB 的数据。因此，我决定将考虑的工作集限制在 1MB 以下。以下是一些具有大型工作集的应用程序：

  • svchost.exe, 22MB
  • Windows Explorer, 21MB
  • Yahoo Pager, 18MB
  • Visual Studio 7, 45MB
  • Internet Explorer, 30MB

我惊讶于 Yahoo Pager 的工作集如此之大。在我开始过滤掉大型工作集之前，Fortuna 使用了大量的内存并产生了大量的页面错误。移除大型工作集后，PRNG 的系统资源使用更加合理。

Microsoft Crypto API

Microsoft 引入了一个加密 API，他们声称该 API 适用于加密目的。不幸的是，关于 Crypto API 的内部机制没有任何公开信息。因此，出于隐私考虑，有些人对使用它感到不安。此外，考虑到过去微软的一些安全实践，很难知道 Crypto API 应该信任到什么程度。

我的方法是使用 Crypto API 作为“随机”数据的一个来源。为什么不呢？它增加了攻击者的工作量；现在攻击者必须攻破 Microsoft Crypto API 以及其他使用的数据源。Crypto API 每 100 毫秒生成 32 字节的随机数据。这些字节使用每字节“随机”数据 1 比特的熵估计值分布到所有数据池中。这显然是一个保守的估计，因为 Crypto API 的内部机制是未公开的。

Ping

Ping 是一个网络命令，用于确定网络传输时间。我使用高分辨率计时器来计时执行 Ping 的各种调用。即使 Ping 超时，计时数据仍然具有用于播种 PRNG 池的有用随机性。Ping 计时数据压缩率仅为 2% 左右。我无法从 Ping 收集到足够多的计时数据来使用 Diehard 进行分析。

种子文件

我实现的种子文件与《实用密码学》的作者有所不同。如果我理解正确的话，他们只写出了生成器的状态。所以，每次 PRNG 重启时，池中的所有熵都会丢失。

在我的实现中，我写出了 32 个熵池中每一个的状态。我还写出了生成器的密钥以及生成器使用的计数器。一些熵池仅在很少的重新播种时使用，并在生成器状态被攻破的重新播种期间提供安全性。因此，在我看来，熵池的状态值得保存在种子文件中。

我使用 AES 256 位密钥以 CTR 模式加密种子文件。密钥是用户提供的种子文件密码与盐值连接的 SHA256 哈希值。

围绕种子文件使用的一个问题是确保永不重复使用相同的种子文件。为了避免使用相同种子文件两次可能出现的重复值（请参见本书中关于此情况可能发生的良好讨论），在读取种子文件并允许 Fortuna PRNG 返回伪随机字节之前，会向池熵的哈希值添加更多数据。这些数据包括当前所有进程快照的哈希值、时间信息以及其他可用数据。有关详细信息，请参阅 FortunaUtils.cpp 中的 GetMachineSignature() 函数。

使用代码

关于如何使用文章或代码的简要说明。类名、方法和属性，任何技巧或窍门。

使用代码非常简单。所有复杂性都对用户隐藏。以下是如何设置 Fortuna PRNG。

 Fortuna* pFortuna = new Fortuna();

 std::string sFileName("FortunaCSI.bin");
 std::string sPassword("MtNorquay~246");
 bStatus = pFortuna->SetSeedFile(sFileName, sPassword);
 if (!bStatus)
 {
  printf("Set Seed File Failed\n");
  assert(0);
 }

 bool bReadSeedFile = false;
 if (bReadSeedFile)
 {
  CitadelSoftwareInc::Fortuna::FortunaErrors fError = 
    CitadelSoftwareInc::Fortuna::eNoErrors;
  bStatus = pFortuna->ReadSeedFile(fError);

  if (!bStatus)
  {
   printf("Failed to read seed file");
   assert(0);
  }
 }

 pFortuna->StartThreads();

请注意，种子文件的使用是可选的。StartThreads() 方法是开始收集数据、遍历注册表、监控进程等的必要条件。

设置完成后，计算随机数就非常简单了。

 unsigned int uint = 0;
 bool bStatus = pFortuna->GetRandomInt(uint);
 if (!bStatus)
   printf("Fortuna PRNG is not ready yet\n");
 else
   ...

还有一个方法可以获取任意长度的随机字节数组。

  bool GetRandomBytes(unsigned char* pData, unsigned int numBytes);

关注点

编写服务器应用程序需要广泛的测试。添加新功能后，我通常会测试程序运行 8 到 12 小时，每 1 到 10 秒请求一个随机数。在添加 QueryWorkingSet 数据源并运行 8 小时后，我发现（从任务管理器中）使用了大约 24000 个句柄 - 哎呀。我很快发现了问题并修复了它。GetPerformanceInfo 函数返回句柄的数量；也许应该监控该值，并在该值超过某个阈值时将问题指示写入日志文件。

为了演示 PRNG 的使用，我编写了一个小型 MFC 应用程序来生成密码。CodeProject 页面顶部的屏幕截图显示了我添加的 Fortuna 监视器。这是一个 MFC 对话框，用于监视生成器以及源和池对象的状态。“Sources”的“Peek”编辑框显示了当前选定的源正在馈送到池中的实际数据。

如果您对我的 Fortuna 实现有任何问题或意见，我很乐意倾听。我的电子邮件地址是 ron at citadelsoftware dot ca。祝您一切顺利！

历史

  • 修订 1.0
© . All rights reserved.