Catena (hash function)

from Wikipedia, the free encyclopedia

Catena is a basic structure ( framework ) for hashing of passwords . It is suitable for secure authentication (saving passwords), as a password-based key derivation function and as a proof-of-work process. Catena was developed in 2013 by Christian Forler, Stefan Lucks and Jakob Wenzel and took part as a candidate in the Password Hashing Competition . The name Catena is derived from the Latin word for chain.

history

Catena was first presented in 2013 as an alternative to the password hash function Scrypt . Catena took part as a candidate in the Password Hashing Competition and was modified several times in the course of the competition. With version v2, Catena is no longer a concrete algorithm ( password scrambler ), but a framework that can be instantiated by various algorithms. The presented instances in version v3 are Catena-Dragonfly and Catena-Butterfly . In 2015, Catena was recognized by the Password Hashing Competition as one of four proposals alongside the winner Argon2 with special recognition for its agile framework and its resistance to side-channel attacks .

Criticism of Scrypt

The development of Catena was motivated by the criticism of the Scrypt function, whose basic idea ( memory intensity) was taken up. The listed criticisms were:

  • Complexity: Scrypt uses two different cryptographic primitives ( Salsa20 / 8 and SHA-256 ) and four other operations (ROMix, BlockMix, PBKDF2 , HMAC )
  • Vulnerability to cache timing attacks : The addresses for data access in the ROMix function depend on the password
  • Vulnerability to garbage-collector attack : memory fragments can be used to simplify trying out passwords

structure

The Catena framework is defined by:

  1. a cryptographic hash function : the latest reference implementation includes Blake 2b as the only function. In versions v1 and v2, SHA-512 was implemented in addition to Blake2b , but in version v3 only mentioned as a possibility. In theory, any hash function with a length of 64 bytes can be used.
  2. a reduced variant of this hash function: Version v3 uses the hash function Blake2b, which was reduced from 12 to one round.
  3. an optional function Γ (gamma) as a randomization layer (random access layer ): The function Γ should also secure the memory requirement. In order to prevent time-memory trade-offs , the memory-intensive vector (the status) is modified depending on the salt . The saltMix function, which is based on a Xorshift generator, is currently used for all the instances presented . However, the Catena team explains that this function can in principle also be replaced.
  4. a memory-intensive function F, which accesses a vector with a graph-controlled data flow: The function F is characterized by a cache-time-constant execution. Starting with version v2, two variants are presented: Catena-BRG ( bit reversalt graph ) and Catena-DBG ( double butterfly graph ).

parameter

Catena allows passwords and salts of any length. In addition, another argument can be entered, for example a cryptographic key or a personal string . Safety can mainly be set using three parameters:

  • keep the salt or parts of it secret ( Pepper )
  • Increase the memory requirement using the garlic parameter: The recommended value for Catena Butterfly is 16, for Catena-Butterfly-Full 14, for Catena-Dragonfly 21, for Catena-Dragonfly-FULL 18. If Catena is used as a key derivation function, the recommended value is increased Value to 22 (Dragonfly) or 17 (Butterfly).
  • Increase the computational effort through the depth of the graph using the parameter λ (lambda): The recommended value for Catena-Dragonfly is 2, for Catena-Butterfly 4.

properties

Client-independent setting ( client-independent update )

With the first version of Catena, a mechanism was presented for the first time, with which the security settings for authentication can be changed on the server side. In this way, the security parameters can also be adapted to new requirements for inactive or rarely used accounts - without interaction with the user and without knowing the password. This mechanism was subsequently adopted by other password hashing methods.

Server relief

The server relief allows a large part of the authentication process to be outsourced from the server to the client : the server first sends the salt to the client. The time-consuming and memory-intensive function F is carried out on the client side, the server then only calculates an efficient hash function.

Key derivation function Catena-KG

Catena can be executed in a special mode as a key derivation function and as such allows the efficient calculation of extremely long keys as well as the generation of several, independent keys.

Proof of work

Catena has its own mode for a proof-of-work scenario. This mode is intended, for example, for cryptocurrencies and to make it more difficult for email providers to send spam.

Concrete instances

With version v2 Catena was as a framework ( framework described) with two different instances: Catena BRG and Catena DBG. In version v3 these were slightly changed, made more concrete and presented as Catena-Dragonfly and Catena-Butterfly . Both instances can be executed with a round-reduced and a full hash function.

The selection of the instance depends on the system requirements, the application scenario and the expected attack.

Catena Dragonfly

Catena-Dragonfly and Catena-Dragonfly-FULL are based on the bit reversal graph for the F-function and the hash function Blake2b. In the “FULL” variant, the hash function is carried out completely, in the other variant only one round. Catena-Dragonfly-FULL corresponds in most respects to the original version of Catena as a password scrambler and is an instance of the variant Catena-BRG presented in version v2. Catena-Dragenfly was first presented in January 2015 in version v3 as an instance of the framework during the Password Hashing Competition .

Catena-Dragonfly is recommended for applications in which sufficient RAM is available and an attacker with a high budget (availability of ASICs ) is to be fended off. Typical use cases are key derivation functions and proof-of-work scenarios.

Catena butterfly

Catena-Butterfly and Catena-Butterfly-FULL are based on the double butterfly graph for the F-function and like Catena-Dragenfly on the complete or round-reduced hash function Blake2b. Catena-Butterfly is an instance of the variant Catena-DBG presented in version v2 and was also listed for the first time in version v3 from January 2015.

Catena-Butterfly is recommended for applications with limited RAM and when attackers with a low budget (only availability of GPUs and FPGAs ) are expected. A typical use case is authentication on a server.

Other variants

In December 2015 Jakob Wenzel presented four other instances of Catena at the “Passwords15” congress in Cambridge, each targeting a specific security feature.

Web links

Individual evidence

  1. ↑ Password Hashing Competition: Candidates ( Memento from August 11, 2015 in the Internet Archive ) .
  2. ↑ Christian Forler, Stefan Lucks, Jacob Wenzel: The Catena Password scrambling Framework. 2nd Round of the Password Hashing Competition (PHC) . P. 27 (pdf)
  3. ↑ Christian Forler, Stefan Lucks, Jacob Wenzel: The Catena Password scrambling Framework. 2nd Round of the Password Hashing Competition (PHC) . P. 31 (pdf)
  4. ↑ Christian Forler, Stefan Lucks, Jacob Wenzel: Catena: A Memory-Consuming Password Scrambler. (pdf, 308 KiB) August 23, 2013, p. 6 , accessed on October 26, 2015 (English).
  5. ↑ Christian Forler, Stefan Lucks, Jacob Wenzel: The Catena Password scrambling Framework. (PDF, 669 KiB) Version 3.2. September 29, 2015, p. 45 , accessed on October 26, 2015 (English).
  6. ↑ Stefan Lucks, Jakob Wenzel: Catena Variants - Different Instantiations for an Extremely Flexible Password-Hashing Framework ( Memento of the original from April 21, 2016 in the Internet Archive ) Info: The archive link was inserted automatically and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. (Presentation as pdf)  @1@ 2Template: Webachiv / IABot / passwordscon.org