2
$\begingroup$

I am reading up on SHA-2 algorithms and I came across this paper: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf

In section 5.2.1 it talks about the formula for padding a message. There is states there is congruence between:

$$\text{message length} + 1 + k$$ and $$896 \pmod{1024}$$

To calculate $k$ (the amount of zeroes) the following example is given for a message length of 24:

896-(24+1) = 871

I am wondering though why is $896 \pmod{1024}$ used when the outcome of this is always constant? Why not simply use the number 896?

$\endgroup$
2
$\begingroup$

We are given an $\ell$-bit message and we are trying to find the smallest nonnegative $k$ such that $\ell + 1 + k \equiv 896 \pmod{1024}$. This means we are trying to find $k$ such that $\ell + 1 + k$ is 896 plus an integer multiple of 1024: $\ell + 1 + k = 896 + n\cdot 1024$, for some $n$.

Suppose you have an 895-bit message, $\ell = 895$. A single bit of padding, with $k = 0$ zeros, makes its length a multiple of 1024 plus 896: $895 + 1 + 0 = 896 + 0\cdot 1024$.

Suppose you have an 897-bit message, $\ell = 897$. The smallest amount of padding you can add to make it a multiple of 1024 plus 896 is 1023 bits, with $k = 1022$ zeros: $897 + 1 + 1022 = 896 + 1\cdot 1024$.

Another way to phrase ‘a multiple of 1024 plus 896’ is ‘a multiple of 1024 minus 128’. The point is that we're adding the smallest amount of padding that will fill a 1024-bit block with room to append the length of the message as a 128-bit integer at the end. The complete padded input is $$m \mathbin\Vert 1 \mathbin\Vert 0^k \mathbin\Vert \operatorname{be128}(\ell)$$ where $\operatorname{be128}(\ell)$ is the 128-bit big-endian encoding of the integer $\ell$, and $0^k$ is as many zeros as you need to make this an exact multiple of 1024 bits long.

We want an exact integer multiple of 1024 bits in the padded message so that we can break it into blocks $b_1 \mathbin\Vert b_2 \mathbin\Vert \cdots \mathbin\Vert b_n$ to compute $$f(f(\dots f(f(\mathit{IV}, b_1), b_2)\dots), b_n),$$ where $f$ is the internal compression function defined on a 512-bit state and a 1024-bit block, and $\mathit{IV}$ is the standard initialization vector.

$\endgroup$

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.