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

点击翻译按钮获取中文摘要

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.