Why are the constants so simple in Keccak?

Question

Keccak, the construction selected for SHA-3 is very interesting. It seems unlike other primitives and has chosen very simple constants. (Keccak talk PDF)

The initial values of the state in Keccak is all zero, why?

The round constants have just a few bits set, why is this?

Previous primitives like SHA-2, use pseudorandom constants (for example derived from π).

/* Keccak round constants */
uint64_t RC[24] = {
    0x0000000000000001, 0x0000000000008082,
    0x800000000000808A, 0x8000000080008000,
    0x000000000000808B, 0x0000000080000001,
    0x8000000080008081, 0x8000000000008009,
    0x000000000000008A, 0x0000000000000088,
    0x0000000080008009, 0x000000008000000A,
    0x000000008000808B, 0x800000000000008B,
    0x8000000000008089, 0x8000000000008003,
    0x8000000000008002, 0x8000000000000080,
    0x000000000000800A, 0x800000008000000A,
    0x8000000080008081, 0x8000000000008080,
    0x0000000080000001, 0x8000000080008008,
};

Answer 1

As fgrieu pointed out, the constants are defined in terms of a binary Linear Feedback Shift Register. Because LFSRs can be represented very efficiently using standard logic gates they have been used for pseudorandom number generation computers for decades. They have fallen out of favor for use directly as secure stream ciphers due to advances in cryptanalysis. But the round constants for Keccak are not being relied upon to provide all the properties of a cryptographically secure pseudorandom generator.

By defining them in this way, the designers of Keccak achieve a few things:

1. NIST specifically asked for functions for which the number of rounds could be extended. This definition of round constants provides an unlimited supply should more rounds need to be added later.

2. The constants are efficient to implement as an LFSR in hardware. You don't have to embed a table in ROM with 2304 bits of square and cube roots like SHA-2.

3. Because the constants work out to be mostly zeroes, an fully unrolled pipeline implementation could possibly be even a bit more efficient than a LFSR for every stage. Super-linear scaling FTW.

4. The designers show that they have not hidden any subtle weaknesses into the choice of round constants because there is not enough information content there to conceal one. NIST has had problems with this in the past: http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115

5. The designers stake out the claim that the security of Keccak is not heavily dependent on having perfectly statistically unbiased round constants. This may sound petty, but saving your peer reviewers from needless unproductive discussions in advance seems to be a direct benefit to public cryptanalysis. It seems to have worked for Keccak anyway.

What's really fascinating is just how closely related all these reasons become under information theory. http://en.wikipedia.org/wiki/Algorithmic_information_theory

Answer 2

This is not a rationale, and I confess that I do not quite get how we go from that to the values, but I can at least point to how the constant are derived. Quoting the Keccak Reference:

The additions and multiplications between the terms are in $\mathrm{GF}(2)$. With the exception of the value of the round constants $\mathrm{RC}[i_r]$, these rounds are identical. The round constants are given by (with the first index denoting the round number): $$\mathrm{RC}[i_r][0][0][2^j-1] = \mathrm{rc}[j+7i_r] \text{ for all } 0\leq j \leq l,$$ and all other values of $\mathrm{RC}[i_r][x][y][z]$ are zero. The values $\mathrm{rc}[t]\in \mathrm{GF}(2)$ are defined as the output of a binary linear feedback shift register (LFSR): $$\mathrm{rc}[t]=\left( x^t \bmod x^8+x^6+x^5+x^4+1 \right) \bmod x \text{ in } \mathrm{GF}(2)[x].$$