# Understanding the HAIFA (hash iterative framework) structure

Unfortunately, this structure doesn't even have a full Wikipedia on it. I'm struggling to understand it. There are no Youtube videos, Lectures, or any educational video on it. I want to understand how the structure works, and I don't care about the maths behind the hash iterative framework. I would also like if someone can provide me with an outline to the structure or any useful links to better understand it.

• What are the points on HAIFA that you fail to grasp? Aug 7, 2020 at 19:28
• @ kelalaka can you provide me with a link to the paper or any resource that I can use? Aug 7, 2020 at 19:33
• I wrote a small answer, something is missing let me know. Aug 7, 2020 at 20:27
• Look for citations inline and references at the bottom of the Wikipedia page would usually lead you to original sources. Jul 5, 2021 at 4:38

## 1 Answer

HAsh Iterative FrAmework (HAIFA) proposed by Biham and Dunkelman, in 2005-2007. The main idea of the work is to fix the flaws of Merkle and Damgård (MD) construction. Interestingly, MD was invented by Ralph Merkle and Ivan Damgård independently and presented in the same main Cryptography Conference.

Flaws in MD constructions are found even if the underlying compression function is secure. In MD, the iteration maintains the collision resistance of the compression function proved by both Merkle and Damgård. Over time, it is shown that it is not enough;

MD construction problems

HAIFA is designed with these goals

• simplicity: this is important since the simple design gives a better understanding to analyze.
• maintaining the collision resistance of the compression function
• increasing the security of iterative hash functions against (second) pre-image attacks, and
• the prevention of easy-to-use fix-points of the compression function. HAIFA also supports variable hash size.

Previous MD modifications

There are patches for MD before HAIFA, and actually, HAFAI can use all.

• Randomized hashing scheme: They reduced the collision-resistant requirement of the compression function. They randomized the inputs of the compression function so that, the collision of the compression function can be masked.

• Enveloped MD construction: This method preserves the compression function's collision resistance and pseudorandom and the pseudorandom family properties. This construction can be very useful in the case of a hash function is designed for MACs, since the pseudorandom properties of the compression function are preserved.

• Wide pipe: This method uses a larger internal state than the output size. This construction results in finding internal collisions as hard as finding the pre-image of the hash function itself.

HAIFA design

The compression function of HAIFA is designed as

$$C:\{0,1\}^{m_c} \times \{0,1\}^n \times \{0,1\}^b \times \{0,1\}^s \to \{0,1\}^{m_c}$$ or

$$h_i = C(h_{i-1}, M_i, \#bits, salt)$$ $$\#bits$$ is the number of bits hashed, $$h_0 = IV$$, and $$salt$$ is the usual salt value.

The padding scheme

It is bit padding, add 1 then and as many as 0 then the length encoded in $$t$$ bits, then the digest size encoded in $$r$$ bits. Therefore the added 0 is $$\equiv n - (t+r-1) \mod n$$

Security

• Collision resistance: Similarly to MD, they have proved that if the underlying compression function is collision resistance the HAIFA construction, too.

• Fixed point countermeasure: the inclusion of the number of bits hashed so far prevents the fixed point attacks.

• Randomized hashing is achieved by the salt.

• Multi-collision attack: The attack still works, however, the inclusion of the salt prevents pre-computation

• The Hearding attack: The precomputation is infeasible if the salt is unknown.

Hash Algorithm Based on HAIFA

The first three are in the second round of the SHA-3 competition of NIST.

• Thank you @Kelalaka! Aug 8, 2020 at 6:21
• could you please share the link/resource from which you found the design of the HAIFA? Aug 10, 2020 at 6:33
• I draw it. Need some cleanup, though Aug 10, 2020 at 7:38