8
$\begingroup$

What is the importance of the $r$ and $c$ values?

Keccak[r=1600,c=0] is stated on a calculator on the Keccak website to be a checksum. But I figured if c=0, then there's only one possible output?

If C is 128, is there only 2^64 possible outputs, despite have infinite output length and an infinite number of inputs?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ C=128 has a security level of 64 bits against certain attacks, but the output size is still unlimited. $\endgroup$
    – CodesInChaos
    Commented Mar 18, 2014 at 18:07

1 Answer 1

Reset to default
9
$\begingroup$

Keccak is Sponge-based hash function:

Sponge Construction [Image taken from the official sponge page]

It has a large internal state, and iterates this with a permutation (that for theoretical proofs we model as an ideal permutation).

The total state of Keccak is $s=r+c$ bits. Because the user can only ever read from or input data into the $r$-section of this (the 'rate component of the state'), a user cannot directly modify the capacity component of the state. It turns out that the security of the construction boils down to avoiding internal collision on the capacity component (which is $c$-bits wide). That is, we require that the capacity component of the state never takes the same values twice and due to the birthday bound, this happens after around $2^{c/2}$ blocks.

So, for provable security, we need $c$ to be suitably large. However, the input and output is always at rate $r$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Okay. What does C do, and can you explain it like I'm five (not literally)? $\endgroup$
    – user3201068
    Commented Mar 18, 2014 at 20:44
  • 1
    $\begingroup$ Minor improvement, probably not sufficient tbh. Let me know if it makes sense now, otherwise I'll rewrite it some time $\endgroup$
    – Cryptographeur
    Commented Mar 18, 2014 at 22:36
  • $\begingroup$ I love that drawing, worth the proverbial thousand words! @user3201068: The state/water capacity of the sponge is $s=r+c$ bits. $r$ is the amount of entropy/water that enter/exit the sponge at each round/press of the sponge. $c$ bits are out of reach of the adversary/remain in the sponge when pressed, that is A) impossible to put in a particular state with odds better than random: B) unknown if the initial state is unknown as assumed in the Random Oracle model. $\endgroup$
    – fgrieu ♦
    Commented Mar 19, 2014 at 9:01

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.