Spritz cipher sponge function capacity

Question

Rivest and Shuldt proposed a new sponge like cipher algorithm called Spritz:

http://people.csail.mit.edu/rivest/pubs/RS14.pdf

In this paper they say that the strength of the cipher is related to the bit-capacity of its sponge-like internal function. They calculate this as 936 bits from 5 8-bit registers and 112 bytes of an internal state space. That gives (112+5)*8 = 936 bits.

However the 112 bytes of the internal state space are all different, thus they represent one of (256!)/((256-112)!) permutations. This number of permutations can be represented in 855 bits which with the 5 registers makes for 895 bits which is 81 bits less than claimed.

My question is, is the effective strength of the sponge function 936 bits as stated by Rivest and Shuldt, or, given it can be entirely represented in only 895 bits, "just" 895?

Answer 1

The relationship between Spritz's security and the capacity of the internal function, Shuffle, is based on the fact that any generic attack must use on the order of $2^{c/2}$ queries to Shuffle in order to have a non-negligible success probability, where $c$ is Shuffle's capacity. A generic attack does not use any details about Shuffle, meaning the attack holds if you replace Shuffle with any other function. This does not say anything about attacks against Spritz in general, and if you're able to find a special property about Shuffle which is useful for an attack, such as a more efficient description of Shuffle, then you can beat the $2^{c/2}$ minimum requirement on the amount of Shuffle queries for a successful attack.

So the fact that Shuffle can be described more compactly will not change Rivest and Schuldt's security claim since their claim only depends on Shuffle's explicit capacity. In fact, Spritz's effective security could be significantly worse than what they claim, but you'll have to find an attack against Spritz to show this.