Best Paper Award for IST Austria Cryptographers and their Collaborators

Postdoc Joël Alwen and Professor Krzysztof Pietrzak—together with their US collaborators—have been awarded the best paper award at the Eurocrypt ‘17 conference. Their prize-winning work proves the existence of “memory-hard” functions, cryptographic functions that are designed to be “egalitarian” in the sense that they can’t be computed at lower cost on dedicated hardware as compared to standard CPUs. These functions are crucial to securing password servers and have applications in the next generation of decentralized cryptocurrencies.

A server will usually not store a user’s password in the clear, but will instead apply a cryptographic hash function to it and store only the output, known as the hash value. This way a server can still verify a password by applying the hash function and checking if the output is the same as the stored value. However, if the password file is stolen—something “which unfortunately seems to happen pretty much constantly,” says Pietrzak—the passwords are not immediately compromised: To find the password corresponding to a hash value, the adversary must hash different password candidates until the hash matches the stored value. For a typical human-generated password this requires hashing in the order of a billion values. Unfortunately a billion is not really much, so to make the adversaries task even harder, one uses a “moderately hard” hash function, which is expensive, but not too expensive, to compute—this is not much of a burden for the server, who computes the function once per login attempt, but should make computing billions of hashes extremely costly for the adversary.

The classical approach towards constructing moderately hard functions is to simply iterate a standard hash function a few thousand times. Unfortunately, this does not gain nearly as much security as one might hope: while servers use standard CPUs, an adversary can use special-purpose hardware on which evaluating such functions is several orders of magnitude cheaper in terms of hardware and energy cost. Thus brute-forcing passwords was nowhere near as costly as anticipated!

To address this problem, in 2009, Colin Percival put forth the notion of “memory-hard” functions (MHFs)—moderately hard functions whose evaluation cost is dominated by memory cost. MHFs would be egalitarian: as memory cost is about the same over different hardware platforms, having special hardware would no longer benefit the adversary. Moreover, Percival also proposed a candidate MHF called scrypt, which became widely deployed.

A first formal definition capturing memory-hardness (called parallel cumulative memory complexity) was only given six years later, in 2015, by IST Austria postdoc Joël Alwen and Vladimir Serbinenko of ETH Zurich. A variety of candidate MHFs–including a winner of a two-year password-hashing competition–were shown to not meet this definition. The status of Percival’s original function scrypt, however, remained unresolved.

In 2016, the cryptography groups at IST Austria and the University of California Santa Barbara presented initial progress in this direction. Now, a year later, together with Leonid Reyzin of Boston University–who in 2016 spend a sabbatical at IST Austria–they have succeeded in making the final steps, and have finally proved that scrypt is memory-hard. 

Their result, which was presented in Paris at this year’s Eurocrypt conference—one of the two main cryptography conferences—enhances our understanding of memory-hard functions in general, and scrypt in particular. This not only increases our trust in using scrypt for password hashing, but also a variety of decentralized cryptocurrencies, such as Litecoin and Dogecoin, already make use of scrypt.

“This line of research still holds many exciting open problems that we are currently working on” says Pietrzak, “for example, the current models only capture hardware cost, but achieving egalitarianism in terms of energy cost is not yet well understood.”

Joël Alwen joined IST Austria as a postdoc in 2014, and has interests ranging from lattice-based cryptography to leakage resilience. He has also been involved a variety of programming projects, including the Netflix Challenge and designing attacks on password hashing functions. Professor Krzysztof Piertzak has headed the cryptography group at IST Austria since 2011, and explores a broad range of theoretical and practical aspects of cryptography, including memory-hard functions, cryptography for lightweight devices, symmetric cryptography, and sustainable cryptocurrencies.

»Download photo showing Leonid Reyzin (Boston University),  Joel Alwen (IST Austria), Binyi Chen (UC Santa Barbara ), Stefano Tessaro (UC Santa Barbara), Krzysztof Pietrzak (IST Austria). Image credit: Nigel Smart.

More information

Scrypt
Password Hashing Competition

Publication

“Scrypt is Maximally Memory-Hard”
Joel Alwen (IST Austria), Binyi Chen (UCSB), Krzysztof Pietrzak (IST Austria), Leonid Reyzin (Boston University), Stefano Tessaro (UCSB) https://eprint.iacr.org/2016/989