3
$\begingroup$

From this answer, I see that from a mathematical point of view, one could define the $\text{Keccak-}f[25w]$ permutation for an arbitrary value of $w$.

I am interested in the following question: disregarding all properties of the resulting function except the invertibility (because $\text{Keccak-}f[25w]$ is required to be a permutation), is it true that if the value of $w$ is a multiple of $8$ and not a multiple of $5$, the corresponding $\text{Keccak-}f[25w]$ function is invertible (and bijective)? If the answer is “No”, then how to determine whether a particular $w$ is suitable (assuming that $w$ is required to be a multiple of $8$)?

$\endgroup$
-2
$\begingroup$

Regarding Keccak-f[25w] I’m assuming that you’re referring to changing the total number of lanes (25 as outlined in the standard) and not changing the 64-bit lanes size. Changing the lane count, as stated in the previous answer regarding a change in the lane size, would also result in a non-standard version of Keccak. To the extent that modification of the source code would be required to execute the function.

Your question is directed specifically at the viability of inversion given a deviation from the 25 lane standard.

Is it true that if the value of w is a multiple of 8 and not a multiple of 5, the corresponding Keccak-f[25w] function is invertible?

The above statement is false. If the total lane count is a multiple of 5 Keccak-f[25w] will be invertible, with the understanding that arbitrary constants can be added at the pi, rho, and iota steps. Essentially a total lane count being a multiple of 5 is required to maintain continuity with steps theta and chi. If the total lane count is even there might be some issues with pi, because rotational symmetry might be broken.

Issues will be caused when there is a total lane count that is NOT a multiple of 5. If the total lane count is prime the s-box definition of chi will need to extend to the full lane count. I would probably write a test for the largest factor that isn’t equal to the total lane count. How this affects the statistical properties of chi after considering state truncation would require further analysis. With theta things started getting interesting. An arbitrary lane count change could be added to theta without affecting its forward derivation. By the bit-twisting definition of theta applied with the extension of the 1:11 indexing relationship. In the reverse direction you will encounter the same issue if the lane count is prime. Now even if the lane count is NOT prime and you leverage the largest factor not including itself, there will be a computational resource issue as a result of the nature with which theta is inverted. Then again my theta inversion implementation could be a black boxed version of something glaringly simple. And always remember the print() statement is not necessarily truth.

Addressing below comment:

Keccak can be inverted as long a the lane width is an even number so w=8,16,48,64... are all viable sizes assuming you're comfortable throwing in some random bits to account for the reduced size of iota. I however wouldn't be able to invert Keccak when w > 1000.

$\endgroup$
  • 1
    $\begingroup$ > I’m assuming that you’re referring to changing the total number of lanes ($25$ as outlined in the standard) and not changing the 64-bit lanes size < No, the symbol $w$ denotes the lane size, and this question is about the invertibility of Keccak functions when $w=8, 16, 24, 32, 48, \ldots$, which corresponds to $\text{Keccak-}200, \text{Keccak-}400, \text{Keccak-}600, \text{Keccak-}800, \text{Keccak-}1200, \ldots$ The number of lanes is always the same ($25$). $\endgroup$ – lyrically wicked Feb 6 at 8:04
  • $\begingroup$ > Keccak can be inverted as long a the lane width is an even number < According to this answer, the function is invertible if $w$ is not a multiple of $15$. But, for example, $w=120$ is even, it is a multiple of $8$, and it is a multiple of $15$. Is the function invertible if |x| = 5, |y| = 5, |z| = 120? $\endgroup$ – lyrically wicked Feb 13 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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