You are looking at a specific version 20161212:100651 of this paper. See the latest version.

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.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
password hashingmemory-hardcache-timing attack
Contact author(s)
jakob wenzel @ uni-weimar de
History
2016-12-12: last of 12 revisions
2013-08-30: received
See all versions
Short URL
https://ia.cr/2013/525
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.