1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Note: this is answer was written to extend poncho's answer in detail. $\endgroup$ – kelalaka Jun 28 '20 at 7:15

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.