4
$\begingroup$

Wikipedia contains the following claim for $\text{Keccak-}f[25w]$:

It is defined for any power-of-two word size, $w = 2^ℓ$ bits.

Although all official descriptions of Keccak do not explicitly mention well-definedness of $\text{Keccak-}f[25n]$ for any $n$ above $64$.

So I have two related questions:

  1. Can we assume that $\text{Keccak-}f[25n]$ is a well-defined function for arbitrarily large $n$?
  2. What stops $\text{Keccak-}f[25n]$ from being a well-defined function even if the lane size $n$ is not a power-of-two number? In this case, we can simply calculate the required number of rounds as $$12 + 2\lceil \log_2 n \rceil,$$ where $\lceil x \rceil$ denotes a mathematical ceiling function. (Of course, round constants and rotation offsets will also be recalculated for the corresponding value of $n$.)
$\endgroup$

1 Answer 1

3
$\begingroup$

From a standardization point of view, $\text{Keccak-}f[25w]$ (i.e. $\text{Keccak-}p[25w, r]$ with $r = 12 + 2\lceil \log_2 w\rceil$) is simply not defined in FIPS PUB 202 when $w$ is not a power of two. Specifically, the Keccak permutation is only standardized for $w = 2^\ell$ with $\ell \in \{0, 1, \ldots, 6\}$. This means that, even if you can define the permutation for other values of $w$, it will be nonstandard.

That said, if $w$ is not a power of two the permutation will be less efficient (per bit). Ideally, your processor has instructions to operate on $w$ bits. In practice, one expects $\ell \ge 3$ for most applications. This is probably the main reason why the standard/original specification do not mention other values of $w$. Also, $w$ isn't allowed (in the standard) to be arbitrarily large because that would be overkill.

From a mathematical point of view, one could also define the permutation for $w$ not a power of two (despite the lack of a good reason). Let's consider each step separately:

  • $\theta$ just uses xors of bits and generalizes to all $w$, but as discussed below it is not necessarily invertible.
  • $\rho$ rotates each word. This works for any word length.
  • $\pi$ is a word permutation which clearly works for any $w$.
  • $\chi$ is bitwise along rows, so again no problem.
  • $\iota$ adds a constant to one of the lanes. This step requires more changes.

The problem with $\theta$ (thanks to poncho for pointing to this) is that it is not invertible for all values of $w$. In particular, if we represent the state as an element of the ring $\mathbb{F}_2[x, y, z] / \langle x^5 + 1, y^5 + 1, z^w + 1\rangle$ as in the reference, $\theta$ can be written as

$$\theta(\alpha) = p_\theta \alpha = (1 + (1 + y + y^2 + y^3 + y^4) (x + x^4 z))\alpha,$$

Hence, we must have $1/p_\theta \in \mathbb{F}_2[x, y, z] / \langle x^5 + 1, y^5 + 1, z^w + 1\rangle$ and this not true for all $w$.

The reason why the $\iota$ function does not immediately generalize is because it adds $\ell + 1$ round constant bits to bits $2^j - 1$, $j = 0, \ldots, \ell$. The natural generalization would be to do the same thing but with $\ell = \log_2 \lceil w\rceil$. The problem occurs when $\ell > 8$. The round constants are computed using an 8 bit LFSR. If you want more bits, you need a larger LFSR. For all $\ell \le 6$, the same LFSR is used but some output bits are ignored. So you will need to specify another LFSR... That said, it is not even essential that one uses an LFSR to generate round constants so you could argue that this isn't a major problem.

If $\ell$ is very large, I'm also not sure if $r = 12 + 2 \ell$ rounds would really be sufficient. I'm not going to make that analysis here, though.

$\endgroup$
6
  • 1
    $\begingroup$ I believe that if $w$ happens to be a multiple of 15, then the $\theta$ step will not be invertible (and hence you won't end up with a permutation) $\endgroup$
    – poncho
    Commented Dec 18, 2018 at 21:21
  • $\begingroup$ @poncho Ah, you're right. Thanks for pointing it out. I'll make some changes to take this into account. $\endgroup$
    – Aleph
    Commented Dec 18, 2018 at 21:36
  • $\begingroup$ I tend to believe that the values chosen for the $\rho$ operation (e.g. a maximum of 300) won't work well from a security standpoint when the lane size is extended to be significantly larger. $\endgroup$
    – Ruggero
    Commented Dec 19, 2018 at 10:42
  • $\begingroup$ @Ruggero I agree, that's the reason for my last paragraph. I took the question to be mostly about well-definedness (not security). $\endgroup$
    – Aleph
    Commented Dec 19, 2018 at 10:46
  • $\begingroup$ But if there does not exist an universal definition of this permutation for any power-of-two word size, then that quoted claim in Wikipedia is not correct? $\endgroup$ Commented Dec 22, 2018 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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