3
$\begingroup$

I am implementing the SHA-3 algorithm in AVX2 assembly. The part where I am getting confused is that the padding with 10*1. Now my understanding is that the data message M first needs to be padded with a '01'bit sequence. So, N= M || '01'.

Next, for the moment, please assume that the implementation is for KECCAK[1024] which is sponge(KECCAK-p[1600,24],pad 10*1,576](n,d). This implies, all the packets P_{i} have to be 576 bits long (1600-1024).

Now, my confusion is when the incoming message M itself is of 573 bits length. Then, N=M || '01' becomes 575 bits length. Then, do I just pad a single bit '1'? This is not then 10*1. How does one handle this specific length message, please?

Any advice is welcome. Remain grateful.

$\endgroup$
3
$\begingroup$

10*1 padding does not mean pad with a "10", it means pad with a single bit, then as many 0 bits as is required to fill the rate, then set the last bit of the rate to 1. 10*1 padding needs at least 2 bits of padding, such as the case of 574 bits with a rate of 576, in that case you only have a single 0, which is then set to a 1 since it is the last bit.

If the message is 573 bits, you need 3 more bits, so you add your single bit, two 0s, then set the final bit to 1, which leaves you with a literal "101" padding.

You may also want to deal with the ambiguity of the digest size. Your specific parametrization specifically calls out a rate of 576, but KECCAK1024 strongly implies a 1024-bit digest size, but in this case it is your capacity. If you are using the capacity, you want it bracketed, like KECCAK[1024]

$\endgroup$
  • $\begingroup$ Thanks for the clarification.. Can u please also elaborate what happens when the message N is of size 575 bits ? $\endgroup$ – quasar66 Mar 12 '16 at 0:47
  • 1
    $\begingroup$ If N = 575 bits, you need 1 single 1 bit, 575 0 bits, then the final 1 bit $\endgroup$ – Richie Frame Mar 12 '16 at 0:49
  • $\begingroup$ Do you know why the padding ends with 1? ​ (rather than just being 10*) ​ ​ ​ ​ $\endgroup$ – user991 Mar 13 '16 at 3:39
  • 1
    $\begingroup$ @RickyDemer It has a security proof when used in a multi-rate sponge, the final 1 guarantees the final block of the rate is not all 0 $\endgroup$ – Richie Frame Mar 13 '16 at 8:20
1
$\begingroup$

According to section 5.1 on page number 19 (or 27 in the pdf) of the specification document, http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf, the padding algorithm returns the string 1 || 0^j || 1 where j indicates zero or more 0's such that the length of the resulting string is a multiple of the bit rate. Moreover by this definition the smallest possible output of the algorithm is 1 || 0^0 || 1 = 1 || 1 which is two bits long.

In the case you describe N would be: M (573 bits of your message) || 01 (2 bit domain) || 1 (start of 10*1 padding) || 0*(575 bits of 0) || 1 (end of 10*1 padding) which would be 2 blocks of 576 bits to absorb into the sponge.

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