Sha-512 understanding padding problem

Question

I don't understand how to append the length of 128 bits exactly? First, we pad bits to make the length ($n*1024-128$) but then I need to append 128 bit of the plain text length. I find the problem to append 128 bits.

Answer 1

NIST FIPS 180-4 on page 13 defines the padding scheme for SHA-512 as;

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

So you first append 1, then calculate the number of the zeroes by the formula, append the zeroes, then append the 128-bit binary-encoded length.

For example: If your message size is $\ell =49$ than

$$49 + 1 + k \equiv 896 \bmod 1024$$ solving for minimal $k = 896-49-1 = 846$. Therefore the padded message is

$$ \text{padded message } = \overbrace{M}^{49-bit} \mathbin\| \overbrace{1}^{1-bit} \mathbin\| \overbrace{000\cdots 000}^{846-bit\; 0s} \mathbin\| \overbrace{00000000\cdots00110001}^{128-\text{bit binary encoded length } \ell} $$

Like all uniquely removable padding schemes this padding scheme also uniquely removable, usually called unpad. Get the last 128-bit, then remove all trailing zeros and the first 1 from the end. The rest will be the message and check the message size to ensure that it matches.

The length encoding in the NIST standard sets an upper limit for the size of the message to be hashed. One can hash at most $2^{128}$-bit-sized input messages. Before the upper limit, one has limited by the current technology.

SHA512, like all Merkle–Damgård constructions SHA512 has also vulnerable to length extension attack. Instead of SHA512 using SHA3 or Blake2 series are preferable. After SHA3, the stripped versions SHA512-384 and SHA512-256 are designed to have resistance to length extension attack. They have also different initial values that provide the domain separation from SHA512.

Answer 2

Here's your development brief

---

First, you pad until you have 16 bytes left, using 0x80 for the first byte, bytes valued 0x00 after that.

If you run out of space (you need 17 bytes minimum) then you pad until you reach the end of the block, and continue padding with 0x00 in the next block until you have 16 bytes left for the length.

In most implementations you hash each block once it is filled, so then you have pad, hash block, pad some more and then continue to the next step.

---

Secondly you insert the number of bits in the message as 128 bit big endian number.

That means that you pad the number itself with 0x00 bytes to the left, then come the most significant bytes and you end with the lowest significant bytes to the right.

Notes:

• If your platform doesn't support 128 bit numbers then you may decide to only support messages up to $2^{64} - 1$ in bits / $2^{61} - 1$ in bytes, and leave the first 8 bytes set to 0x00. You could also perform addition using two 64 bit integers to calculate the length, or even by using addition over bytes.
• If your platform only supports little endian then you need to reverse the byte order yourself.
• Don't forget to multiply with 8 if you counted bytes instead of bits.