How are SHACAL-2 ciphers calculated?

Question

I am trying to learn about the underlying functionality of the different hash functions (currently SHA) and I'm pretty stuck even after watching a Stanford video about it.

One method of hashing is by using Merkel-Damgård construction with the David Meyers function and SHACAL-2 block ciphers.

As far as I understand MD is the message divided into a chain of 64-bit blocks containing the previous block value or IV (initial vector defined by the hash function or a custom salt key). The block value or IV along with the current block value and some x bit key is after going through the SHACAL-2 function then the new cipher.

Is this correct understood? If it is: What happens inside the SHACAL function? What is math?

I found this but it doesn't really answer my question: SHACAL in SHA-256

Answer 1

The MD construction uses a compression function $C$ ($F$ in the figures) such that it has two inputs.

$$h_i = C(h_{i-1},m_i)$$

and the first $h_{-1} = IV$ and the last $H = h_{2^k-1}$ is the hash value.

The compression function can use a block cipher, where the message to the block cipher is the previous hash value and the key is the message. $h_i = E_{m}(h_{i-1})$

The first description of using a block cipher for compression function exists in Merkle's thesis on page 11. This construction is totally insecure since the existent block cipher directly chained and it can be shown that it has $\mathcal{O}(2^{n/2})$ second-preimage resistance instead of $\mathcal{O}(2^{n})$.

We don't want related key attacks as exist in some of the block-ciphers like AES and DES. This doesn't create a problem for encryption since the keys are chosen uniform randomly, however, the related keys can be used to attack the hash function. This is discussed extensively by Mannik and Preenel

We want large inputs due to the collision attacks on the compression functions [1] and therefore more rounds to process. So designers create a new block cipher for MD constructions instead of using existing ones. For SHA-1 it is called SHACAL and for SHA-2 it is called SHACAL-2.

The dividing value depends on the compression function, MD5, SHA-1, and SHA256 uses 512-bit message blocks, SHA512 is using 1024-bit message blocks. The messages are padded to be multiple of the block size with the message size is encoded at the end.

For example SHA-512 padding on NIST FIPS 180-4

Suppose that the length of the message, $M$, is $\ell$ bits. Append the bit 1 to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation $$\ell + 1 + k \equiv 896 \bmod 1024$$ Then append the 128-bit block that is equal to the number $\ell$ expressed using a binary representation

Formalize for arbitrary block size $b$ and $d$-bit encoded message size ( 64 for SHA-1 and SHA256, 128 for SHA512.

$$\ell + 1 + k \equiv b-d \bmod b$$

So the design criteria are having a block cipher with many rounds, SHACAL has 80, SHA-256 has 64, and SHA512 has 80 rounds while keeping the round function simple.

And the block cipher is used as Davies–Meyer to create a one-way compression function.

For example, the math for SHA256 is

• $\operatorname{Ch}(E,F,G) = (E \land F) \oplus (\neg E \land G)$
• $\operatorname{Ma}(A,B,C) = (A \land B) \oplus (A \land C) \oplus (B \land C)$
• $\Sigma_0(A) = (A\!\ggg\!2) \oplus (A\!\ggg\!13) \oplus (A\!\ggg\!22)$
• $\Sigma_1(E) = (E\!\ggg\!6) \oplus (E\!\ggg\!11) \oplus (E\!\ggg\!25)$

The bitwise rotation uses different constants for SHA-512. The given numbers are for SHA-256.
The red $\boxplus$ mean $ c = a + b \mod 2^{32}$, i.e. modulo addition.

As we can see, simple operations that CPUs can handle, light round function, with a little degraded unbalanced Feistel structure.

And we learned from the Tiny Encryption algorithm that, even simple rounds can be secure after 32 rounds.