Im trying to implement a sponge in Java. The state starts out as an empty 200 byte array of all zeros. In the KMAC samples document from NIST, the following happens:
(black line is a pdf page break)
The way Im reading this is that a state with a bunch of zeros was sent into KECCAK, and then a state with apparently random data was returned. Does SHA3/KECCAK turn empty data into random data? Am I asking the right questions here? Any help is appreciated.
I personally find the Keccak.team Psuedo Code document very helpful to understand how Keccak-p works.
As DannyNiu said in the comments, most (all?) cryptographic permutation employ "round constants". These constants are somehow mixed in the Keccak state.
The pseudocode document gives the round constants as a table:
RC[0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[2] 0x800000000000808A RC[14] 0x8000000000008089
RC[3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[4] 0x000000000000808B RC[16] 0x8000000000008002
RC[5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[8] 0x000000000000008A RC[20] 0x8000000080008081
RC[9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008
and explains how they are used. In the iota-step of the $n^\text{th}$ Keccak-p round, the $n^\text{th}$ round constant $RC[n]$ gets introduced and gets XOR'd into the first word, first lane.
Apart from the round constants, the Keccak permutation has a very good diffusion: a single bit somewhere in the initial state will contribute significantly to many output bits.
The combination of both means that your Keccak permutation looks very random. It cannot, of course, turn zero entropy into random, since no finite algorithm can do that, but the goal of Keccak is to mix things about and make them appear random.
The Keccak permutation function would normally map the zero input (all bits are 0) onto zero output, if not for the iota-step, in which one word of the state is XORed wit a non-zero constant.
About three (of 24) rounds are sufficient for complete diffusion i. e. every bit of the state affects every other bit three rounds later. One could say, the permutation mixes the state eight times completely through. That means if only one bit is 1, it will diffuse quickly over the state so that 3 rounds later about half of the state bits are 1.
Let $R$ be the set of the state values which can reasonably be called "regular looking" (by whatever exact definition), e. g. all or almost all bits have the same value, or a short bit pattern repeats regularly. Among all the $2^{1600}$ states, those in $R$ are a very small fraction. It is very unlikely that any state in $R$ is mapped onto an output also in $R$. This holds as long as $|R| \ll 2^{800}$ (see "birthday paradox").
That would mean that there is no regular looking input that is mapped onto a regular looking output. And the probability for any given state to be mapped to an output in $R$ is negligible, i. e. the output will always look random, except someone deliberately constructs the input by calculating the inverse of the permutation.
