Paper 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.

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.