Essentially all cryptographic applications crucially rely on secret keys that are chosen randomly and are unknown to an attacker. Unfortunately, the process of deriving secret keys in practice is often difficult, error-prone and riddled with security vulnerabilities and pitfalls. Indeed, badly generated keys offer a prevalent source of attacks that render complex cryptographic applications completely insecure despite their sophisticated design and rigorous mathematical security analysis. Given the central role that key derivation plays in the security landscape, it receives surprisingly little formal study within the cryptographic community, which has correspondingly had surprisingly little influence on the process of key derivation in practice. The major goal of this project is to examine several different scenarios for key derivation, including the use of random number generators (RNGs), passwords and biometrics. In all these cases, we develop a thorough theoretical foundations and formal understanding of the required security properties and propose new methods that provide improved security with provable guarantees.

We concentrate on the following areas:

(1) System Random Number Generators (RNGs). RNGs are an important and complex system component whose goal is to gather entropy from various sources (e.g., the timing of system calls), carefully manage the gathered pools of entropy over time, and periodically use them to output arbitrarily long strings of seemingly random bits, which can be used as cryptographic secret keys.

As part of our research, we found practical attacks on the Linux's RNG /dev/random, and showed the first theoretical analysis (and improvements) of Windows 8 RNG Fortuna. In addition to attacking/analyzing these existing RNG constructions, we also designed a new theoretical framework for building and rigorously analyzing RNGs, and designed several new and provably secure RNGs in our framework, which provide both qualitative and quantitative security and efficiency improvements to known RNG constructions.


(2) Key Derivation minimizing Entropy Loss. The problem of key derivation is a fundamental cryptographic problem of how to convert an imperfect entropy source such as password into the longest possible nearly uniform cryptographic key. Previous solutions to this problem achieved this task, but at the expense of extracting a key which was noticeably shorter than the entropy of the source. In fact, some prior work even suggested that such non-trivial entropy loss is inherent to the problem. In a very surprising result, we showed that this intuition is wrong, by designing the first provably secure key derivation functions (for a large collection of cryptographic applications) which achieve almost no entropy loss. Given that many entropy sources have very little entropy to begin with, we hope that our work will likely have a significant impact in practice.

(3) Key Derivation from passwords. One of the main challenges of generating keys from passwords is the issue of offline dictionary attacks where an attacker searches over all possible passwords in a small dictionary. We propose new solutions that reduce the effectiveness of such attacks. One of our ideas is to introduce a semi-trusted online entity ("helper") that can help users derive strong cryptographic keys from passwords and prevent offline dictionary attacks, but cannot hurt the user's security if it is ever compromised. We want this helper to be able to identify incorrect password attempts without being able to mount an offline dictionary attack. We achieve this by giving the helper only a single bit of information about the password which is sufficient to identify each incorrect password guess with probability 1/2 and therefore detect if too many such guesses are made.  

(4) Random Oracle with Auxiliary Input. Most practical methods for key derivation rely on the "random oracle model" - a framework that allows for rigorous security analysis including analyzing quantitative levels of security. However, the concrete security bounds that the random oracle promises are overly optimistic when we consider realistic attacks that may involve large amount of "pre-computation" before attacking a specific instance . In our work, we propose a variant of the random oracle model that takes such pre-computation into account and allows us to analyze the security level of various primitives in such settings. 

Beyond the scientific impact, we believe this project will have a broader impact on society. The poor security of current key-derivation schemes is one of the most common targets of real-world attacks. We expect the results of this research to be useful in significantly improving the security landscape for companies and individuals. On a more direct level, much of the research for this project involved the participation of PhD students and postdocs and included a large mentoring and career-development component. We emphasized diversity and inclusion of under-represented minorities. The participants include a female PhD student and two female postdocs who are continuing on to a research career in academia.

Last Modified: 10/26/2018
Modified by: Daniel Wichs