Practical leakage-resilient pseudorandom generators
Practical leakage-resilient pseudorandom generators
复制标题
DOI：
10.1145/1866307.1866324
复制
发表时间：
2010-10
期刊：
影响因子：
--
通讯作者：
Yu Yu-Yu;François-Xavier Standaert;Olivier Pereira;M. Yung
中科院分区：
文献类型：
--
作者：
Yu Yu-Yu;François-Xavier Standaert;Olivier Pereira;M. Yung
加密系统和协议是许多互联网安全程序（例如SSL、SSH、IPSEC、DNSSEC、安全邮件等）的核心。所有密码函数的核心是一个良好的随机性来源，并且为了效率，伪随机发生器（PRG）的原语。PRG还可以用于流密码的设计，用于安全通信。如今，互联网由许多类型的设备组成，这些设备具有非常不同的硬件和软件特性。因此，在这样的开放环境中的问题之一是信息“泄漏”和通过所谓的“侧信道攻击”对其的利用。一个非常广泛和当前的研究方向是设计抵抗这种攻击的基本密码操作。最近的工作泄漏弹性PRG和流密码做了显着的进步，在标准的密码设置中的侧信道攻击的分析工具。但是，在缺乏一个完全可靠的泄漏模型的情况下，唯一可以证明安全的结构需要与物理直觉不一致的调整。例如，使用交替结构的构造，其中2n $的密钥位大小只能保证最多2^n $的安全性，已经为此目的而设计。在本文中，我们提供了两种方法的贡献，允许摆脱这些调整，或减少其对微不足道的性能开销的影响。首先，我们证明了一个自然的泄漏弹性，即符合工程经验，有状态的PRG可以证明基于随机预言机的假设。然后，我们讨论了这一假设的相关性，并认为它很好地捕捉了实际的侧信道攻击的现实。其次，我们提供了第一个没有交替结构的PRG结构，它利用密钥材料的全长，并可以证明在标准模型中的泄漏弹性。为此，我们只需要假设一个非自适应泄漏函数和一个小的公共存储器。我们还认为，这样的假设不仅是现实的，但必要的任何泄漏弹性原语，赠款对手（无状态）重新初始化能力。再加上对实际实现的较弱要求，这些贡献进一步缩小了物理可观察密码学理论与实践之间的差距。
Cryptographic systems and protocols are the core of many Internet security procedures (such as SSL, SSH, IPSEC, DNSSEC, secure mail, etc.). At the heart of all cryptographic functions is a good source of randomness, and for efficiency, the primitive of pseudorandom generator (PRG). PRG can also be used in the design of stream ciphers, for secure communications. The Internet is nowadays composed of many types of devices with very different hardware and software characteristics. Hence, one of the concerns in such open environments is the information "leakage" and its exploitation via the so-called "side channel attacks". A very extensive and current research direction is designing basic cryptographic operations that are resistant to such attacks. Recent works on leakage-resilient PRG and stream ciphers did significant progresses in providing tools for the analysis of side-channel attacks in the standard cryptographic setting. But in the absence of a completely sound model for the leakages, the only constructions that can be proven secure require tweaks that do not correspond to the physical intuition. For example, constructions using an alternating structure, in which a key bit-size of $2n$ can only guarantee a security of at most $2^n$, have been designed for this purpose. In this paper, we provide two methodological contributions, allowing to get rid of these tweaks, or to reduce their impact towards negligible performance overheads. First, we show that the leakage-resilience of a natural, i.e. conform to engineering experience, stateful PRG can be proven under a random oracle based assumption. We then discuss the relevance of this assumption, and argue that it nicely captures the reality of actual side-channel attacks. Second, we provide the first construction of a PRG without alternating structure, that exploits the keying material to its full length and that can be proven leakage-resilient in the standard model. For this purpose, we only need to assume a non adaptive leakage function and a small public memory. We also argue that such an assumption is not only realistic, but necessary for any leakage-resilient primitive that grants adversaries with a (stateless) reinitialization capability. Together with weaker requirements for practical implementations, these contributions further reduce the gap between the theory and practice of physically observable cryptography.