Implementation details of the π step of the Keccak round function

Question

In the official Keccak implementation overview, there is a section discussing different ways to organise the internal Keccak-f state -- namely section 1.2, Bit and byte numbering conventions -- and at https://keccak.team/software.html, you can find a reference software implementation as well as a list of third-party ones. At least two of the third-party C implementations, however, refer to an array of 24 integer constants that are evidently used in the π step of the Keccak-f permutation, but they are not mentioned in the specification. In the keccak-tiny-unrolled.c file from David Gil's implementation, for example, the array is defined as follows:

static const uint8_t pi[24] = \
  {10,  7, 11, 17, 18, 3,
    5, 16,  8, 21, 24, 4,
   15, 23, 19, 13, 12, 2,
   20, 14, 22,  9, 6,  1};

In the π step, 24 out of all the 25 lanes comprising the internal Keccak state are moved to different positions. It's a simple 'bijective' mapping, but the order in which the lanes are processed by David Gil's program isn't obvious because the state array is flattened to one dimension and the π step is combined with the 'chronologically first' ρ mapping in which each lane is bitwise rotated by a fixed number of positions. All the rotation offsets as defined in section 1.1 are given below (note the indices):

The corresponding rho array from the above-mentioned file looks like this (zero skipped as idempotent, rho and pi arrays' sizes equal):

static const uint8_t rho[24] = \
  { 1,  3,  6, 10, 15, 21,
   28, 36, 45, 55,  2, 14,
   27, 41, 56,  8, 25, 43,
   62, 18, 39, 61, 20, 44};

I don't want to say something blatantly wrong, but now, given this array, numbering the state lanes in the row-major scheme (starting from zero) and knowing that in the actual code (see the keccakf() function) its elements are taken in the order defined in that same array, we can conclude that the first element of the pi array is just an index of the 1-dimensional state array element (a single lane) which should be replaced with the lane rotated by rho[i] positions. The order of lanes in the a array from the keccakf() function then becomes as follows (i - lane stored in a[i]):

0 - 12     7 - 9    14 -  1    21 - 18
1 - 13     8 - 5    15 - 22    22 - 19
2 - 14     9 - 6    16 - 23    23 - 15
3 - 10    10 - 2    17 - 24    24 - 16
4 - 11    11 - 3    18 - 20
5 - 7     12 - 4    19 - 21
6 - 8     13 - 0    20 - 17

For example, the 13th lane rotated by rho[0] = 1 position to the left should take the place of the second one, so a[pi[0]=10] = 2. Similarly, the second lane rotated by rho[1] = 3 positions should replace the ninth one, so a[pi[1]=7] must be the ninth lane.

I'd like to know where these constants come from and why the state is organised in such a way. I've read the linked overview briefly, but it says nothing about any explicit formula for the π constants and I haven't found anything really helpful elsewhere either. Could you please help me?

Answer 1

From my implementation code, the indexes for the pi array are calculated as follows:

For x = 0 To 4
    For y = 0 To 4
        State[(0 * x) + (1 * y), (2 * x) + (3 * y)] = tempState[x, y]
    Next y
Next x

From the Keccak specification:

The mapping $π$ is a transposition of the lanes that provides dispersion aimed at long-term diffusion. Without it, Keccak-f would exhibit periodic trails of low weight... For $π$ we have chosen a matrix that defines a permutation of the axes where they are in a single cycle of length 6.

The mapping $ρ$ consists of translations within the lanes aimed at providing inter-slice dispersion. Without it, diffusion between the slices would be very slow. It is translation-invariant in the z-direction.

For rho offset calculation:

x = 1
y = 0

For t = 0 To KECCAK_LANES - 2
    RhoOffsets[(5 * y) + x] = ((t + 1) * (t + 2) / 2) Mod KECCAK_LANELENGTH
    newX = ((0 * x) + (1 * y)) Mod 5
    newY = ((2 * x) + (3 * y)) Mod 5
    x = newX
    y = newY
Next t

You may notice that the multiplication constants for x and y are identical to pi, and the actual computed constants are a simple geometric sequence [0,1,3,6,10,15,21,...,300] modulo 64, or whatever the lane length happens to be for smaller Keccak instances.

The reason keccak-tiny seems to use a completely different order for the rho offsets is because both pi and rho are linear and can be done in reverse order as long as the order of the offsets is changed, and that is exactly what they did. Because the order of rho is basically the inverse of pi, the fact that they switched the order makes their rho offset order identical to the geometric sequence.

So how do we see the relation between the rho offset order and the pi order? Looking at the x,y table of rho values, the 0th element (0) in the 0th position (0,0), the 1st element (1) is in the 5th position (1,0), the 2nd element (3) is in the 2nd position (0,2), the 3rd element (6) is in the 11th position (2,1), and so on, with the final element (44) in the 6th position (1,1).

Following those element positions in the sequence of the pi values within the state (x+5y), the 0th pi value is 0, the 5th value is 10, the 2nd value is 7, the 11th value is 11, and so on, with the final value being 1, matching the pi sequence table. You can calculate the pi value from the x,y position of the sequential element in the rho table, $π_{x,y}$ = $5*((2x+3y) \mod 5 )+y$

Since pi mixes the entire state by repositioning lanes, and rho rotates the bits within each lane, they are combined as a single gate free operation in hardware. The final positions of lanes within the state follows pi only.