I was writing in a document about the flaws of the MD construction which pushed cryptographers to create different and more robust constructions. However, I don't know why HAIFA and Sponge constructions don't suffer from this attack.


Sponge Construction

In sponge construction, the block size $b$ has two parts, $r$ is the rate and it is the written part and $c$ capacity is the untouched part by the input/output, $b= c+r$

enter image description here

The output is taken from $r$ in the squeezing stage. Therefore not all of the $b$ is the output. This prevents the length extension attack like in the truncations of SHA2, which are standardized after Keccak.

The idea is: when someone wants to extend a message $abc$ into $abcde$ they should be able to continue the hash output where it is left, the hash value. $h=H(IV,\text{"abc"})$ then using the $h$ as the IV for the $H' = H(h,\text{"df"})$ then the length extension is possible (here we did not consider the padding and not a big issue, either). Originally the length extension attack worked on MAC with $H(\text{secret}\mathbin\|\text{message})$ construction. Although the output will be different, the attacker can inject this with the new MAC tag, without the knowledge of the key, and the server will accept it. So. it works even the attacker cannot have the secret and the message. It doesn't work with HMAC, which is designed to be secure against this. On the other hand, KMAC based on SHA3 has much simpler design since SHA3's immunity.

The sponge constructions' two-stage design, that is absorbing and squeezing together with the $c$ prevents the length extension attack with a calculatable countermeasure.

Below is the capacity against the length extension attack of SHA-3.

\begin{array}{|c|c|c|c|c|}\hline \operatorname{SHA3}\text{ variant}\ & \text{output size} & \text{internal block size} & \text{rate } r& \text{Capacity against LEA} \\ \hline \operatorname{SHA3-224} & 224 & 1600 & 1152 & 448= 1600-1152\\ \hline \operatorname{SHA3-256} & 256 & 1600 & 1088 & 512 = 1600-1088 \\ \hline \operatorname{SHA3-384} & 384 & 1600 & 832 & 768 =1600-832\\ \hline \operatorname{SHA3-512} & 512 & 1600 & 576 & 1024 = 1600-576\\ \hline \end{array} LEA stands for Length Extension Attack.

HAIFA construction

The HAIFA construction is not mentioned about countermeasure about length extension, however, it can be designed/modified simply using a different salt in the last block as in BLAKE2 Is Blake2b vulnerable to length extension attacks?, like using $true$ for the last block and using $false$ for any other block. The HAIFA construction is simple 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.

enter image description here

  • $\begingroup$ I'm sorry, but I want to ask a very basic question which is not worth posting it. I have read many articles in addition to your answer and many other forums. But I think I am experiencing a flatline with my learning curve or it is just one of those days. $\endgroup$ – Hinton Zsh Aug 12 '20 at 11:55
  • $\begingroup$ Is the final hash value affected by the extension added by the attacker? I mean is it a completely different hash value or the same one, given the feature of the avalanche. $\endgroup$ – Hinton Zsh Aug 12 '20 at 11:55
  • $\begingroup$ Yes, it is a new different value. If you want to have the same value, you need lots of work for this (depend on the used hash function ) and that is infeasible. $\endgroup$ – kelalaka Aug 12 '20 at 12:07
  • $\begingroup$ What do you mean by capacity against length extension attack? What do those numbers represent? $\endgroup$ – Aman Grewal Aug 12 '20 at 12:38
  • $\begingroup$ They represent the bits, so you need to consider the attack time of LEA over 2. If you look carefully, it is $b-r$. $\endgroup$ – kelalaka Aug 12 '20 at 12:39

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.