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

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

• Thanks for the clarification.. Can u please also elaborate what happens when the message N is of size 575 bits ? – quasar66 Mar 12 '16 at 0:47
• If N = 575 bits, you need 1 single 1 bit, 575 0 bits, then the final 1 bit – Richie Frame Mar 12 '16 at 0:49
• Do you know why the padding ends with 1? ​ (rather than just being 10*) ​ ​ ​ ​ – user991 Mar 13 '16 at 3:39
• @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 – Richie Frame Mar 13 '16 at 8:20

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.