HAIFA (cryptological procedure)

This article or section needs to be revised. Details should be given on the talk page. Please help to improve it , and then remove this flag.

HAIFA (abbreviation for HA sh I terative F r A mework) is a construction method for iterative cryptological hash functions developed by Eli Biham and Orr Dunkelman . It was published in 2006 and has been used in many hash functions since then.

background

Iterative hash functions break the message to be hashed into blocks of equal length, which are processed step by step by a compression function (often a block cipher). The Merkle-Damgård construction is the most common mode of such an iteration and has been a quasi-standard for a long time. The collision safety of the underlying compression function is retained. Initially it was assumed this also applies to the (second) Preimage -resistance, but that is refuted in recent studies. As a result of these analyzes, attempts were made to further develop the Merkle-Damgård process, for example by HAIFA, or to replace it with another process.

Three out of 14 candidates in the second round in the SHA-3 selection process for a new hash function were based on the HAIFA construction (BLAKE, SHAvite-3, ECHO).

construction

HAIFA supplements the Merkle-Damgård construction with three new features: Firstly, additional data is entered into the compression function, which clearly designates the role and position of each step in the iteration sequence. This means that an attacker cannot omit or add additional steps, because the subsequent steps would then work differently. In particular, the last step (finalization) is clearly identified to prevent expansion attacks. Among other things, this should make offline phases of attacks and the successful fixed point attacks against the Merkle Damgård construction more difficult. Second, the compression function receives salt as an additional input. Third, the length of the hash value to be calculated for the compression function is also entered.

First, the message is expanded with the HAIFA padding scheme . In doing so, however, no information must be lost, i. H. the original message must be clearly reconstructable from the extended message. For this purpose, the message is supplemented by a 1, followed by a variable number of zeros. The length of the original message and the length of the hash value are added to this, each in a field of fixed width: ${\displaystyle M}$ ${\displaystyle |M|}$ ${\displaystyle m}$

${\displaystyle N=M\;\|\;10^{r}\;\|\;|M|\;\|\;m}$

The underlying compression function requires a certain message block length . The number of trailing zeros is therefore set to a number such that the length of the extended message is a multiple of . ${\displaystyle l}$ ${\displaystyle r\in \{0,1,\dots ,l-1\}}$ ${\displaystyle N}$ ${\displaystyle l}$

${\displaystyle N}$is divided into blocks of length bits. As with the Merkle-Damgård construction, these message blocks are iteratively processed by successive calls to a compression function : receives the previous output from and the respective next message block as input. In the HAIFA construction, two additional parameters are entered: the salt and the number of bits of the original message processed up to that point , including those in the current block: ${\displaystyle N_{1}\dots N_{n}}$ ${\displaystyle l}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle S}$ ${\displaystyle M}$

${\displaystyle x_{0}=C(IV,\,m,\,0,\,0)}$

${\displaystyle x_{i}=C(x_{i-1},\,N_{i},\,S,\,L(i)),\;\;i\in \{1,\dots n\}}$

With

${\displaystyle L(i)={\begin{cases}i\cdot l&{\text{wenn}}\;i\cdot l\leq |M|\\|M|&{\text{wenn}}\;|M|<i\cdot l<|M|+l\\0&{\text{wenn}}\;i\cdot l\geq |M|+l\end{cases}}}$

${\displaystyle x_{n}}$ (or part of it) is then the calculated hash value.

In the first iteration step, no message block is hashed, but the first concatenation value is formed from the length of the hash value to be calculated and a constant initialization vector IV . This calculation can be done in advance if it does not change; is then constant. In the last iteration step, the number of processed message bits is entered instead of if the last block no longer contains any bit of the original message. ${\displaystyle m}$ ${\displaystyle x_{0}}$ ${\displaystyle m}$ ${\displaystyle x_{0}}$ ${\displaystyle 0}$ ${\displaystyle N_{n}}$

From the input in the compression function it can always be clearly deduced which iteration step it is and whether it is already the last. In the first step, the input is formatted so that it always looks different from the input in the last. If with , it is a block full of bits of the original message and is the iteration number. If , then the block contains the last message bits, the number of which also indicates whether it is the last block . If so, it is the last block that contains the message length from which the iteration number results. ${\displaystyle m}$ ${\displaystyle N_{n}}$ ${\displaystyle L(i)\equiv 0{\pmod {l}}}$ ${\displaystyle L(i)>0}$ ${\displaystyle L(i)/l}$ ${\displaystyle L(i)\not \equiv 0{\pmod {l}}}$ ${\displaystyle L(i){\bmod {l}}}$ ${\displaystyle N_{n}}$ ${\displaystyle L(i)=0}$ ${\displaystyle |M|}$

The salt can consist of a fixed value or a different value for each hashed message. The recommended length is at least 64 bits, but if possible the salt should be half the length of the concatenation value. In cases where salt does not seem necessary, it can be used. ${\displaystyle x_{i}}$ ${\displaystyle S=0}$

properties

• In contrast, for example, to the also new Sponge construction, HAIFA is strongly based on the Merkle Damgård construction and can be regarded as a variation of or a supplement to it, similar to the wide pipe Merkle Damgård construction. Properties such as collision protection are retained.
• Compared to the Merkle Damgård construction, HAIFA offers improved protection against (second) pre-image attacks. The attacks known up to the time of development cannot be directly transferred to HAIFA. Charles Bouillaguet and Pierre-Alain Fouque were able to confirm HAIFA's assumed resistance to second pre-image attacks in 2010.
• The HAIFA construction can be combined with many other methods that are intended to improve the security properties of hash functions, such as RMX (randomized hashing according to Krawczyk and Halevi), enveloped Merkle-Damgård (according to Bellare and Ristenpart), RMC and ROX (according to Andreeva et al .).
• HAIFA supports hash values ​​with variable lengths.
• HAIFA offers the option of online hashing : Instead of the entire message, only a block of the message has to be kept in memory.

Alternative constructions to HAIFA

Also closely based on the Merkle-Damgård construction is the Wide-Pipe (Double-Pipe) -Merkle-Damgård construction. In 2005, Stefan Lucks presented a construction in which the internal status of the hash function is greater than the hash value. With a slightly higher memory requirement, a better second pre-image resistance can be achieved. Many modern hash functions such as Grøstl , Shabal, SIMD, Blue Midnight Wish are based on this construction.

Not based on the Merkle-Damgård construction, but also iterative, is the Sponge construction developed by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche in 2007 , which can be used in stream ciphers in addition to hash functions . Hash functions such as Keccak (SHA-3), JH , CubeHash, Fugue, Hamsi and Luffa are based on this construction.

Hash functions with HAIFA construction

• BLAKE
• SHAvite-3
• ECHO
• LAKE
• Sarmal
• SWIFFTX
• HNF-256
• The construction of Skein (the Unique Block Iteration ) also shows similarities with HAIFA.

Web links

• Eli Biham and Orr Dunkelman: A Framework for Iterative Hash Functions - HAIFA . 2007 (PDF).
• Eli Biham and Orr Dunkelman: The SHAvite-3 hash function. Tweaked version November 23, 2009 . P. 4–9 (short description of HAIFA) (PDF)
• Orr Dunkelman: Re-Visiting HAIFA and why you should visit too . 2008 (PDF).
• B. Denton, R. Adhami: Modern Hash Function Construction . International Conference on Security and Management. July 2011. (PDF)

Individual evidence

1. ↑ John Kelsey and Tadayoshi Kohno: Herding Hash Functions and the Nostradamus Attack . In: Eurocrypt 2006, Lecture Notes in Computer Science, Vol. 4004, pp. 183-200.
2. ^ Antoine Joux: Multicollisions in iterated hash functions. Application to cascaded construction. In: Advances in Cryptology - CRYPTO '04 Proceedings, Lecture Notes in Computer Science, Vol. 3152, Springer-Verlag, 2004, pp. 306-316.
3. ^ NIST: Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition . February 2011. (pdf)
4. ^ Richared D. Dean: Formal Aspects of Mobile Code Security . Dissertation, Princeton University, 1999.
5. ↑ Charles Bouillaguet, Pierre-Alain Fouque: Practical Hash Functions Constructions Resistant to Generic Second Preimage Attacks Beyond the Birthday Bound . 2010. Citeseer
6. ^ Stefan Lucks: A Failure-Friendly Design Principle for Hash Functions . In: ASIACRYPT'05, Vol. 3788 of Lecture Notes in Computer Science, Springer Verlag Berlin Heidelberg 2005. pp. 474–494.
7. ↑ Guido Bertoni1, Joan Daemen, Michaël Peeters, Gilles Van Assche: Cryptographic sponge functions . 2011. (pdf)
8. ↑ Eli Biham, Orr Dunkelman: The SHAvite-3 Hash Function . 2009. SHAvite-3: A hash function based on HAIFA
9. ↑ Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin: SHA-3 Proposal: ECHO (Version 2.0). July 20, 2010. (pdf)
10. ^ Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan: The Hash Function Family LAKE . In: Proceedings of FSE, LNCS 5086, Springer Berlin Heidelberg 2008. pp. 36-53. ISBN 978-3-540-71038-7
11. ↑ Harshvardhan Tiwari, Krishna Asawa: Building a 256-bit hash function on a stronger MD variant . In: Central European Journal of Computer Science, June 2014. pp. 67–85