Skip to content

Padding-kk-bit state machine

The 136-byte output of the Padding-KK SM must first be translated to bits before it can be used as the Keccak-F SM’s input.

This is where the Padding-KK-Bit state machine comes into the picture.

The Padding-KK-Bit SM play the role of converting bytes to bits in both directions. It also serves as a bridge between the bit-wise operating Keccak-F SM and the byte-wise operating Padding-KK SM.

The Padding-KK-Bit SM is in charge of validating each action connected to the inputs and outputs of the Keccak-F permutation blocks in addition to being a two-way bytes-to-bits converter.

Design strategy

Here’s how this state machine facilitates operations between the Padding-KK SM and the Keccak-F SM.

A block of 136 rows of bytes in the Padding-KK SM corresponds to 1993 rows in the Padding-KK-Bit SM. The picture below, displays the correspondence, also shows three subdivisions of the 1993 rows (corresponding to 1224+512+256+1).

Figure 1: Padding-KK block vs. Padding-KK-Bit's 3 subdivisions

First subdivision: Consists of 9136=1224 rows, where each of the 136 byte-rows has been expanded into 9 rows (i.e., 8 rows for the 8 bits plus 1 row for the byte that represents the 8 bits). The decomposition of the bytes into the 8 bits (with an extra row, just for the byte), is done for easy implementation in PIL. This subdivision of 1224 rows represents the bitrate of the KECCAK-F permutation. Therefore, a strategy to ensure that the bits are accurately and correctly provided, as input to the KECCAK-F SM, needs to be derived.

Second subdivision: Consists of the 512 rows, and represents the capacity input-bits in the 1600-bit state of the KECCAK-F SM. Within the KECCAK-F state machine, unlike the bits in the first subdivision of 1224 rows, the capacity bits are not affected by any exterior bits.

Third subdivision: Consists of 256+1 rows represents the 256 bits of the intermediate hash value produced by the KECCAK-F permutation. At the end of hashing each 1088 bits (136-byte) string, this intermediate hash value actually coincides with the final hash of the KECCAK-256 hash function. Each hash value, the final digest, is packed into eight 32-bit registers at the final row of this subdivision.

Bytes to bits correspondence

This section elaborates how the Padding-KK-Bit SM handles the correspondence of bytes between state machines, and correct positioning of bits with respect to the powers of 2.

Starting with the first subdivision, the 1224 rows related to the bit decomposition of each byte, the following registers are utilised:

  • The Padding-KK-Bit state machine has a column named rBit, which records all the bits associated with the decomposition of each of the bytes of the Padding-KK SM.

  • In order to relate the byte to its bit decomposition between the two states machines, a register called r8Id is added in both state machines as a bit-to-parent-byte identifier.

  • Also, another register called r8, is added for the sole purpose of sequentially constructing each byte from the bits.

  • A factor register Fr8 is used to correctly place each bit in the parent, with respect to the powers of 2.

  • Therefore, each complete byte is recorded at the last row of such a 9-row byte block of the r8 register. This row is flagged with a “1” in the same row of another register called latchR8. This ensures that latchR8 is 0 in all rows except the last row of a 9-row byte block.

Example: Representation of two bytes

Here’s an example of how two bytes, 0xa1 and 0xfe, from the Padding-KK SM look like in the Padding-KK-Bit SM. The horizontal lines mark the end of a byte block.

aFreeInr8Id0xa110xfe2rBitr8Idr8Fr8latchR811010010b120010b01220010b001230010b0001240110b00001250010b100001260110b0100001270X10b101000010102010120b020120b10220120b110230120b1110240120b11110250120b111110260120b1111110270X10b1111111001

Note that latchR8 is equal to 1 in the last row of each byte block, and this is the same row where the corresponding complete byte is found in the r8 column.

The following constraint applies to the r8 column,

r8=r8(1latchR8)+rBit·Fr8

It is very important for Fr8 to be “0” when latchR8 is “1”. If this is not the case, then there is no guarantee that the r8 register will reset to 0 in the next block.

It is also necessary to ensure that rBit is binary, by using the next constraint,

rBit(1rBit)=0

Validating transitions of bits

The challenge of breaking down bytes into bits has been the main focus up to this point. Here, it is intended to verify the bit transitions following the KECCAK-F operation, which is carried out for each block of 136 bytes. For this, a few columns are introduced.

  • sInBit: This register stores the input bit of the current KECCAK-F permutation block.

  • sOutBit: This register stores the output bit of the current KECCAK-F permutation block.

  • connected: The same idea as in the Padding-KK state machine applies here. The connected register is constant within a block, and reflects that the output of the previous permutation KECCAK-F is connected to the current one. That is, it indicates that the previous 136-byte block belongs to the same string as the current block.

  • latchSOut: This register records “1” in the very last row of each of the 1993-row block corresponding to a 136-byte block of the Padding-KK SM, and 0 everywhere else.

Below figure depicts a schema of how to relate the above columns with the KECCAK-F sponge construction.

A schema relating Padding-KK-Bit to KECCAK-F Sponge Construction

Constraints for bit transitions

These constraints are needed to ensure correct transition between rows.

There is a need to make sure the connected register is constant in each block. Hence, the following constraint should be added,

connected(1latchSOut)=connected·(1latchSOut)

It is also mandatory to test whether connected and sOutBit are binary. For these two checks, the following equations are used,

connected(1connected)=0,sOutBit(1sOutBit)=0 

The register sInBit is actually computed from sOutBit, connected and rBit columns. Recall that, at the first block of the sponge function, the input bits to the KECCAK-F permutation actually coincide with rBit. However, after the first block, an XOR of sOutBit and rBit must be performed, as seen in the above figure.

Therefore, sInBit is computed using an auxiliary register aux_sInBit as follows,

aux_sInBit=sOutBit2sOutBitrBit,  sInBit=connectedaux_sInBit+rBit

A quick analysis shows the following,

  1. If connected is 0, then sInBit equals rBit, which is precisely what needs to happen in the first KECCAK-F permutation block.

  2. But if connected is 1, then sInBit equals sOutBit2sOutBitrBit+rBit, which is actually the XOR of sOutBit and rBit.

Below table shows all the cases of the above computation.

connectedsOutBitrBitsInBit00000011010001111000101111011110

Capacity connection in the 512 rows

The second subdivision of the Padding-KK-Bit SM’s 1993-row block consists of the 512 rows, corresponding to KECCAK-F SM’s capacity bits. It is mandatory to ensure these capacity bits (the middle subdivision of each 1993-row block) are not affected by any exterior bit.

First, a new register called rBitValid is added, and it is defined such that it records 1 in each of the rows corresponding to the capacity bits, and 0 everywhere else. Hence, the following relationship is added.

(1rBitValid)rBit=0

This ensures that in each 1993-row block, rBit is 0 everywhere in the rows corresponding to the capacity bits. This results in XOR-ing sOutBit with a 0. And thus, for the rows corresponding to the capacity bits, computing sInBit=sOutBitrBit, amounts to sInBit=sOutBit.

Therefore, these equations guarantee that the capacity bits are not modified by any exterior bits.

Output calculations in the (256 + 1) rows

Now, the last part of the Padding-KK-Bit SM is to keep track of the last subdivision of each 1993-row block. Recall that this third subdivision consists of 256+1 rows, and it is in charge of storing each bit of the intermediate hashes of the KECCAK-F permutation blocks. The 256 bits of the KECCAK-F permutation output are sequentially and cumulatively stored in eight 32-bit registers {sOuti| 0i7}. In a similar method used for the read operations in the Padding-KK SM, eight (8) factor columns {FSOuti| 0i7} are used to ensure correct positioning (of each of the 32 bits in sOuti) with respect to powers of 2.

Example: Storing 256-bit intermediate hash outputs

Consider the 256 bits, 0b|101100111010||1111|0110101101|, where “|” separates every set of 32 bits. The table below displays how the 256+1 rows of a 1993-block are stored in the registers {sOuti| 0i7}.

sOutBitsOut0sOut1sOut7FSOut0FSOut1FSOut7latchSOut      10b10b00b01000  00b010b00b02000  10b1010b00b022000  10b11010b00b023000  00b011010b00b024000  10b1011010b00b025000  00b01011010b00b026000  10b101011010b00b027000      10b1101011010b00b0230000  00b01101011010b00b0231000  10b01101011010b10b00100  10b01101011010b110b00200      10b01101011010b1110b0023000  10b01101011010b11110b0023100          00b01101011010b11110b00010  10b01101011010b11110b100020  00b01101011010b11110b01000220  10b01101011010b11110b101000230      00b01101011010b11110b01100111010002300  10b01101011010b11110b101100111010002311

Observe how factors {FSOuti| 0i7}, in the above table, are used to construct the 32-bit registers {sOuti| 0i7}. Note that the last row contains the complete set of the 256 bits. These columns fulfil the following relations,

sOuti=sOuti(1latchSOut)+sOutBitFSOuti

where 0i7.

The latchSOut register ensures that sOutBit is not constrained at the very beginning of each 1993-block, but only until the third subdivision is reached, where the FSOuti begin to attain non-zero values.

This concludes our design for creating the Padding-KK-Bit SM. What is left to be done is to connect both states machines and check the validity of the last hash.

Padding-KK SM and Padding-KK-Bit SM connection

This section describes how these two state machines, the Padding-KK SM and the Padding-KK-Bit SM, connect via Plookup.

First of all, observe that there’s a need to check whether the bytes received in one state machine are the same as those in the other. Also, corresponding sequential order of these bytes should be checked. The identifier register r8Id is added in both states machines for the very reason. In addition, each byte should have the same value in connected register. Hence, the following Plookup is added in the Padding-KK state machine,

r8valid { aFreeIn,r8Id,connected} in  {PaddingKKBit.r8,PaddingKKBit.r8Id,PaddingKKBit.connected  }; 

The Padding-KK state machine has the {hashi} registers while the Padding-KK-Bit state machine has the {sOuti} registers, which must be related to some point during the execution. Yet, up this point, the order of the hashes has not been checked in any way. Hence, as previously done, an sOutId register is added in both machines in order to identify each of these hashes.

In particular, sOutId is an increasing sequence of integers which increases by one at each processed block. That is, in the Padding-KK state machine, sOutId increases by one in each block of 136 rows, whilst in the Padding-KK-Bit state machine, it increases by one in each block of 1993 rows. This is because a single block of 136 rows in the Padding-KK SM corresponds to a single block of 1993 rows in the Padding-KK-Bit SM.

Hence, the following Plookup is added:

lastHashLatch {hash0,hash1, hash2,hash3, hash4,hash5, hash6,hash7,\quad sOutId} in  {PaddingKKBit.sOut0,PaddingKKBit.sOut1,PaddingKKBit.sOut2,PaddingKKBit.sOut3,PaddingKKBit.sOut4,PaddingKKBit.sOut5,PaddingKKBit.sOut6,PaddingKKBit.sOut7,PaddingKKBit.sOutId  };