The Catena Password Scrambling-Framework

Catena is a novel and provably secure password-scrambling framework with cutting-edge properties. It supports flexible usage in multiple environments, it can also be used as a key-derivation function, as well as for proofs of work/space.

Catena is a finalist of the Password Hash Competition (PHC)

Current Version: catena-v3.3.pdf, Version 3.3 from  November 2, 2015.

Current reference implementation can be found on github

Catena-Variants is a modular framework that allows to easily exchange the components of Catena. This significantly simplifies benchmarking and verification of new components of Catena. It was developed by Sascha Schmidt within the scope of his master's thesis.

Current implementation of Catena-Variants can be found on github.


Previous versions of Catena:

Catena is flexible. An instantiation of Catena is defined by: (1) a cryptographic primitive H, e.g., BLAKE2b [5], (2) a “reduced” primitive H ′ (typically a reduced-round version of H, though H ′ = H is also possible), (3) an optional randomization layer Γ, to harden the memory initialization, and (4) a “memory-hard” function F , using both H and H ′ , and with some graph-driven data flow.

Catena has tunable parameters. The garlic defines time and memory requirements for Catena, increasing the pepper allows to increase the time without affecting the memory, and the salt size determines the defense against precomputation attacks. Catena supports a server relief protocol to shift the effort (both time and memory) for computing the password hash from the server to the client. Catena provides the client-independent update feature allowing the defender to increase the main security parameters (garlic and pepper ) at any time, even for inactive accounts.

Catena provides two default instantiations. Catena is a framework. The user can plug in any suitable H, H ′ , and F . This may be too much too choose from, for the less experienced users, and this lacks a fixed target for the cryptanalysts. Thus, we recommend two instantiations, with different choices for F . Catena-Butterfly runs in limited memory and maximizes the work for lower-memory adversaries, Catena-Dragonfly maximizes the amount of memory used.

Catena has a sound theoretical foundation. Both default instantiations have a sound and elegant design given by a simple and well-understood graph-based structure. The data flow in Catena-Butterfly is based on a stack of double-butterfly graphs, the data flow in Catena-Dragonfly is based on bit-reversal graphs. The time-memory tradeoff analysis follows the research from [30] and is based on the pebble game, which was – mostly in the 1970s and 1980s – extensively used to study time-memory tradeoffs.

Catena is secure. We claim the following security properties of Catena: preimage security (this important for most applications of password hashes), indistinguishability from random (important for key derivation), lower bounds on the time-memory tradeoffs (for high resilience against massively parallel attacks with constrained memory, such as, e.g., when using GPUs), and resistance to side-channel attacks, such as cache-timing and garbage collector attacks. Furthermore, Catena supports keyed password hashing, i.e., the output of the unkeyed version of Catena is encrypted by XORing it with a hash value generated from the userID, the memory cost parameter, and the secret key.