Padding of SHA-3

Question

SHA-3 uses Padding, so the original message has a certain length.

In the case of SHA-3-512 each block has the size of 576, so any message must be padded, such that it is a multiple of the blocksize 576.

I know the rule that the padding is done via the formula

p(m)=P10*1

where P is a predetermined bit-String and the * is a placeholder, where an amount of 0 is inserted, such that the condition is met.

Now here comes the question: What happens, when we want to put a message of 575 bit into the algorithm? Obviously we are 1 bit short of the required length, and the padding rule is at least 3 bit long. What happens in that case?

Answer 1

What happens, when we want to put a message of 575 bit into the algorithm? Obviously we are 1 bit short of the required length, and the padding rule is at least 3 bit long. What happens in that case?

In that case, we just extends padding until it hits the next multiple-of-576 boundary; in this case, this means the padding is 577 bits long (and crosses the block boundary).

Answer 2

From the FIPS 202 defines the padding. Multi-rate padding :

The padding rule $pad10*1$, whose output is a $1$, followed by a (possibly empty) string of $0$s, followed by a $1$.

The padding rule, pad, is a function that produces padding, i.e., a string with an appropriate length to append to another string. In general, given a positive integer $x$ and a non-negative integer $m$, the output $pad(x, m)$ is a string with the property that $m + len(pad(x, m))$ is a positive multiple of $x$. Within the sponge construction, $x = r$ and $m = len(N)$, so that the padded input string can be partitioned into a sequence of $r-bit$ strings.

Where $r$ is the block size or the rate. The $r$ can be calculated by $r = 1600 - 2\cdot r$

The below algorithm is the padding algorithm of SHA3 and internally determines the number of required zeros.

Algorithm 9: pad10*1(x, m)

• Input: positive integer $x$; non-negative integer $m$.
• Output: string $P$ such that $m + len(P)$ is a positive multiple of $x$.
• Steps:
  1. Let $j = (– m – 2) \bmod x$.
  2. Return $P = 1 \mathbin\| 0^j \mathbin\| 1$.

---

• A message with 575-bit size;

What happens, when we want to put a message of 575 bit into the algorithm? Obviously we are 1 bit short of the required length, and the padding rule is at least 3 bit long. What happens in that case?

Call the algorithm pad10*1(x, m) with 575 ( pad10*1(576, 575) ), then $$j = (-575 -2) \bmod 576 =575$$ So the number of 0's is 575.

The padded message is $$m\mathbin\|1\,\underbrace{00\ldots00}_{575-zeroes}\,1$$

The total padding size is 577 which requires an extra block since the $r=576$.