1
$\begingroup$

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.

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

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 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.

A picture can tell a thousand words

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, 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.


$\endgroup$
3
  • 1
    $\begingroup$ Thank you @Kelalaka! $\endgroup$
    – Hinton Zsh
    Aug 8 '20 at 6:21
  • $\begingroup$ could you please share the link/resource from which you found the design of the HAIFA? $\endgroup$
    – Hinton Zsh
    Aug 10 '20 at 6:33
  • $\begingroup$ I draw it. Need some cleanup, though $\endgroup$
    – kelalaka
    Aug 10 '20 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.