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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\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]

Improve this answer
$\endgroup$
4
  • $\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, 2016 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, 2016 at 0:49
  • $\begingroup$ Do you know why the padding ends with 1? ​ (rather than just being 10*) ​ ​ ​ ​ $\endgroup$
    – user991
    Mar 13, 2016 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, 2016 at 8:20
2
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.