How to Eat Your Entropy and Have it Too: Optimal Recovery Strategies for Compromised RNGs
How to Eat Your Entropy and Have it Too: Optimal Recovery Strategies for Compromised RNGs
复制标题
如何吃掉你的熵并拥有它：受损 RNG 的最佳恢复策略
作者：
Y. Dodis;A. Shamir;Noah Stephens;Daniel Wichs
随机数生成器（RNG）在许多密码体制和协议中起着至关重要的作用，但其安全性证明通常假设其内部状态是用真正的随机种子初始化的，并且始终保持秘密。然而，在许多实际情况下，这些都是不切实际的假设：种子通常是在低熵外部事件（例如手动按键的时间）重置/重启后收集的，并且状态可以通过侧信道或渗透攻击在未知的时间点受到损害。通常的补救措施（用于所有主要的操作系统，包括Windows，Linux，FreeBSD，MacOS，iOS等）是通过辅助输入定期补充内部状态，并从环境中获取额外的随机性。然而，从这样的攻击中恢复可证明是正确的和计算上最优的方式仍然是一个未解决的挑战至今，在本文中，我们形式化的问题，设计一个有效的恢复机制，从状态妥协，考虑它作为一个在线优化问题。如果我们知道最后一次妥协的时间和从那时起收集的熵的量，我们就可以停止产生任何输出，直到状态再次变得真正随机。然而，我们面临的挑战是，即使在最困难的情况下，（和最现实的）情况，其中（a）我们对最后一个状态妥协的定时以及从那时起注入状态的新熵的量一无所知，以及（B）任何过早的输出产生导致RNG使用的所有增加的熵的总损失，因为攻击者可以使用蛮力来枚举所有可能的低熵状态。换句话说，我们面临的挑战是制定恢复机制，保证在我们甚至不知道的妥协之后尽快挽救局面。我们面临的困境是，任何过早使用的熵将丢失，而任何未使用的熵将延迟recovery.After发展我们的正式定义框架的RNG输入，我们展示了如何构建一个接近最优的RNG，这是在我们的模型是安全的。我们的技术受到了福图纳RNG设计的启发（这是一种启发式RNG构造，目前由Windows使用，没有任何正式分析），但我们对它进行了非平凡的调整，以适应我们更强大的对抗环境。沿着这条路，我们对福图纳的正式处理使我们能够将其熵效率提高几乎两倍，并通过证明在我们非常一般的问题模型中任何恢复机制的可能效率的严格下限来证明我们的改进结构本质上是紧密的。
Random number generators (RNGs) play a crucial role in many cryptographic schemes and protocols, but their security proof usually assumes that their internal state is initialized with truly random seeds and remains secret at all times. However, in many practical situations these are unrealistic assumptions: The seed is often gathered after a reset/reboot from low entropy external events such as the timing of manual key presses, and the state can be compromised at unknown points in time via side channels or penetration attacks. The usual remedy (used by all the major operating systems, including Windows, Linux, FreeBSD, MacOS, iOS, etc.) is to periodically replenish the internal state through an auxiliary input with additional randomness harvested from the environment. However, recovering from such attacks in a provably correct and computationally optimal way had remained an unsolved challenge so far.In this paper we formalize the problem of designing an efficient recovery mechanism from state compromise, by considering it as an online optimization problem. If we knew the timing of the last compromise and the amount of entropy gathered since then, we could stop producing any outputs until the state becomes truly random again. However, our challenge is to recover within a time proportional to this optimal solution even in the hardest (and most realistic) case in which (a) we know nothing about the timing of the last state compromise, and the amount of new entropy injected since then into the state, and (b) any premature production of outputs leads to the total loss of all the added entropy used by the RNG, since the attacker can use brute force to enumerate all the possible low-entropy states. In other words, the challenge is to develop recovery mechanisms which are guaranteed to save the day as quickly as possible after a compromise we are not even aware of. The dilemma that we face is that any entropy used prematurely will be lost, and any entropy which is kept unused will delay the recovery.After developing our formal definitional framework for RNGs with inputs, we show how to construct a nearly optimal RNG which is secure in our model. Our technique is inspired by the design of the Fortuna RNG (which is a heuristic RNG construction that is currently used by Windows and comes without any formal analysis), but we non-trivially adapt it to our much stronger adversarial setting. Along the way, our formal treatment of Fortuna enables us to improve its entropy efficiency by almost a factor of two, and to show that our improved construction is essentially tight, by proving a rigorous lower bound on the possible efficiency of any recovery mechanism in our very general model of the problem.