International Association
for Cryptologic Research

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 sequentially memory-hard, which hinders 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 is also 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).