Cryptology ePrint Archive: Report 2013/525

Catena: A Memory-Consuming Password-Scrambling Framework

Christian Forler and Stefan Lucks and Jakob Wenzel

Abstract: It is a common wisdom that servers should store the one-way hash of their clients’ passwords, rather than storing the password in the clear. In this paper we introduce a set of functional properties a key-derivation function (password scrambler) should have. Unfortunately, none of the existing algorithms satisfies our requirements and therefore, we introduce a novel and provably secure password scrambling framework (PSF) called Catena. Furthermore, we introduce two instantiations of Catena based on a memory-consuming one-way functions. Thus, Catena excellently thwarts massively parallel attacks on cheap memory-constrained hardware, such as recent graphical processing units (GPUs). Additionally, we show that Catena is also a good key-derivation function, since – in the random oracle model – it is indistinguishable from a random function. Furthermore, the memory-access pattern of both instantiations is password-independent and therefore, Catena provides resistance against cache-timing attacks. Moreover, Catena is the first PSF which naturally supports (1) client-independent updates (the server can increase the security parameters and update the password hash without user interaction or knowing the password), (2) an optional server relief protocol (saving the server’s resources at the cost of the client), and (3) a variant Catena-KG for secure key derivation (to securely generate many cryptographic keys of arbitrary lengths such that compromising some keys does not help to break others). We denote a password scrambler as a PSF with a certain instantiation.

Category / Keywords: password hashing, memory-hard, cache-timing attack

Date: received 23 Aug 2013, last revised 12 Dec 2016

Contact author: jakob wenzel at uni-weimar de

Available format(s): PDF | BibTeX Citation

Note: Biryukov and Khovratovich have shown that stacking more than one bit-reversal graph only adds some linear factor to the quadratic time-memory tradeoff.

Version: 20161212:100651 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]