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

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

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.