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 '20 at 19:28
• @ kelalaka can you provide me with a link to the paper or any resource that I can use? Aug 7 '20 at 19:33
• I wrote a small answer, something is missing let me know. Aug 7 '20 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 '21 at 4:38

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 is invented by Ralph Merkle and Ivan Damgård independently and presented in the same main Cryptography Conference.

Flaws in MD constructions are found even 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 not enough;

MD construction problems

HAIFA is designed with these goals

• simplicity: this is important since the simple design a better understanding to analyze.
• maintaining the collision resistance of the compressions 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 collision resistance, the pseudorandom and the pseudorandom family properties of the compression function. This construction can be very useful like the case of a hash function is designed for MACs, since the pseudorandom properties of the compression function is 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. 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, the 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 fix-ed 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

• 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 '20 at 6:21
• could you please share the link/resource from which you found the design of the HAIFA? Aug 10 '20 at 6:33
• I draw it. Need some cleanup, though Aug 10 '20 at 7:38