Cryptology ePrint Archive: Report 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 better store the one-way hash of their clients’ passwords, rather than storing the password in the clear. This paper introduces Catena, a new one-way function for that purpose. Catena is memory-hard, which can hinder massively parallel attacks on cheap memory-constrained hardware, such as recent “graphical processing units”, GPUs. Furthermore, Catena has been designed to resist cache-timing attacks. This distinguishes Catena from scrypt, which may be sequentially memory-hard, but which we show to be vulnerable to cache-timing attacks. Additionally, 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).

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

Date: received 23 Aug 2013, last revised 9 Sep 2013

Contact author: christian forler at uni-weimar de, stefan lucks@uni-weimar de, jakob wenzel@uni-weimar de

Available format(s): PDF | BibTeX Citation

Version: 20130909:093116 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]