Paper 2013/525

Catena: A Memory-Consuming Password Scrambler

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. Therefore, we introduce a novel and provably secure password-scrambling framework called Catena and derive an instantiation Catena-$\lambda$, which is based on a memory-consuming one-way function called $\lambda-$bit-reversal graph ($\lambda$-BRG). It is characterized by its $\lambda$-memory hardness. Thus, Catena-$\lambda$ excellently thwarts massively parallel attacks on cheap memory-constrained hardware, such as recent graphical processing units (GPUs). Additionally, we show that Catena-$\lambda$ 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 the $\lambda$-BRG is password-independent and therefore resistance against cache-timing attacks. Moreover, Catena 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)~a 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).