SaTC: CORE: Small: On the Power of Preprocessing and Non-Uniformity

今天，散列函数无处不在，因为它们被广泛用于几乎所有的密码应用程序。因此，准确分析它们的安全性是至关重要的。遗憾的是，传统的散列函数分析没有考虑攻击者执行(可能代价高昂但仅一次)预处理攻击的能力，这可能会显著加快重复实时攻击相应应用程序的时间。例如，著名的彩虹表预处理攻击是破解密码的最成功和最实用的方法。受这一严重缺陷的启发，本项目提出了一种新的理论来评估哈希函数在这种强大的预处理攻击下的安全性，并设计了严格而实用的对抗措施。更具体地说，使用散列函数的应用程序的传统分析是在所谓的随机Oracle模型(ROM)中完成的，其中散列函数被建模为真正随机的。相反，这个项目研究了传统只读存储器的一个扩展，其中允许攻击者获得一些关于所讨论的散列函数的任意但有限制的信息。该扩展被称为具有辅助输入的随机Oracle模型(AI-ROM)。这一新模型中的安全边界可以有效地防御比传统的只读存储器更广泛的复杂攻击者，包括预处理攻击。该项目为AI-ROM奠定了坚实的理论基础，包括：(1)为哈希函数的各种重要应用推导出严格的AI-ROM安全界；(2)研究常见的针对预处理的对策的效果，如盐渍和硬度放大；(3)开发AI-ROM的新应用，如空间证明；(4)将辅助输入模型扩展到其他理想化的安全模型，如理想密码模型、随机置换模型和一般组模型。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Today, hash functions are ubiquitous in that they are widely used in almost every cryptographic application. Thus, accurately analyzing their security is of paramount importance. Unfortunately, traditional analyses of hash functions do not take into account the ability of the attacker to perform (possibly expensive but only one-time) preprocessing attacks, which might dramatically speed up the time to repeatedly attack the respective application in real time. For example, the famous rainbow tables preprocessing attack is the most successful and practical approach to crack passwords. Motivated by this serious shortcoming, this project develops a novel theory of how to assess security of hash functions against such powerful preprocessing attacks, and designs rigorous yet practical counter-measures against them. More specifically, traditional analyses of applications utilizing hash functions are done in the so called Random Oracle Model (ROM), where the hash function is modeled as truly random. In contrast, this project studies an extension of the traditional ROM where the attacker is allowed to obtain some arbitrary but bounded information about the hash function in question. This extension is referred to as Random Oracle Model with Auxiliary Input (AI-ROM). Security bounds in this new model provably protect against a much wider class of sophisticated attackers than the traditional ROM, including preprocessing attacks. This project develops a firm theoretical foundation of AI-ROM, including: (1) deriving tight AI-ROM security bounds for a variety of important applications of hash functions; (2) studying the effects of common countermeasures against preprocessing, such as salting and hardness amplification; (3) developing novel applications for AI-ROM, such as proofs of space; (4) extending the auxiliary-input model to other idealized models of security, such as the ideal-cipher, the random-permutation and the generic group models.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.