Understanding the HAIFA (hash iterative framework) structure

Question

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.

Answer 1

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 Damgård (MD) construction. Interestingly, MD was invented by Ralph Merkle and Ivan Damgård independently and presented in the same main Cryptography Conference.

• R. Merkle. A certified digital signature, CRYPTO '89.
• I. Damgård. A design principle for hash functions, CRYPTO '89.

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

• fix-point of the compression function can be used in the second-pre-image attack by Dean.
• Kelsey, and Schneier same as above with the fixed point assumption is removed in Second Preimages on $n$-bit Hash Functions for Much Less than $2^n$ Work
• Chosen target pre-image attack by Kelsey, or known as Herding attack' Herding Hash Functions and the Nostradamus Attack
• The well-known length extension attack.
• Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions by Joux. Joux showed that finding multiple messages with the same hash value is almost the same as finding a single collision on iterated hash functions.

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

• BLAKE, BLAKE2 uses a simple design to eliminate the Length extension attack.
• SHAvite-3
• ECHO
• LAKE
• Sarmal
• SWIFFTX
• HNF-256

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

---