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 17 Dec 2014

Contact author: christian forler 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: 20141217:092527 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]