Keccak padding implementation, and bit ordering

Question

I am trying to implement Keccak in Java for my school work. And I am getting stuck in two places:

1. On the summary page the padding is shown as

   P = M || 0x01 || 0x00 || … || 0x00
   P = P xor (0x00 || … || 0x00 || 0x80)

   However on the specification page section 1.1.2 they mention the variable rate padding as 10*1.

   The way I read it, to prepare message for absorption phase, you cut your message into pieces of size r (bit rate). To get message length multiple of r you would append or concatenate the message with just, (for simplicity I am considering just bytes) in case just 1 byte padding required it will be 0x81. And if more than one byte required then it would be 0x80...0x01. So my padding implementation would be something like

   P = M || 0x80...01

   Where am I reading the specification in wrong way?

2. How is the placement of the bits in the state? I mean if I have a message of say 2 bits, then my bit goes to state position S[0][0][0], but then where should I place the next bit in the same row that is S[0][1][0] or in the same lane that is S[0][0][1]. I would have assumed to go with placing the bit in next cell in the row, and then when you are finished with bits from one slice, then you again start with [0][0] position in next slice. But the way most of the functions are defined with respect to slices, makes me think, it could be other way around. I am unable to find in specification, where they clearly mention this.

Please just point me to places in specification which can resolve my confusion. Thanks.

Answer 1

Both are correct, it is confusing because the summary page is discussing the state in terms of bytes, and the spec doc in terms of bits. The actual state for Keccak-1600 is built from 64-bit words.

During the transfer of the input message to the state, the bytes are essentially put into the words in reverse order, which now makes the summary page correct. This is related to the endianness of the specification and how the input message is placed into the state.

Here is an example of the first 576 bits of the input state of Keccak c=1024,r=576 AFTER padding for a simple message "test".

0000000174736574
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
8000000000000000

It can be seen that the 0x01 byte appended to the message precedes the message inside the first 64-bit word, and the final 0x80 byte occupies the highest bits of the final 64-bit word, exactly as how the 10*1 padding scheme says it should.

The resultant output digest after 24 rounds of permutation is:

1e2e9fc2002b002d75198b7503210c05a1baac4560916a3c6d93bcce3a50d7f00fd395bf1647b9abb8d1afcc9c76c289b0c9383ba386a956da4b38934417789e

I believe somewhere in the NIST submission document there is notation describing the bit/byte ordering, as NIST used a different bit ordering for the SHA-3 API.