Can somebody help me understand RC4 Spritz? (Three Questions)

Question

So ever since I first took a stab at understanding stream Ciphers, not one stood out more than RC4, because it's so fantastically simple. As most people reading this will know, with its fantastic simplicity comes with easily done cryptanalysis and RC4 has certainly been subject to plenty of it (leading to RC4's total failure, more or less).

Now, when breezing over the wikipedia article on alternative constructions of the PRGA stage of RC4, we get this rather neat little alteration, dubbed spritz:

#// All arithmetic is performed modulo 256
while GeneratingOutput:
    i := i + w
    j := k + S[j + S[i]]
    k := k + i + S[j]
    swap values of S[i] and S[j]
    output z := S[j + S[i + S[z + k]]]
endwhile

Now a bunch of things spring to mind about this alteration (that is seemingly far stronger, albeit, unfortunately much slower) but what's at the forefront of my mind is:

THREE Specific questions I'd like to know the answer to are:

• Can we safely assume that from any given setup of S[], we can get to another set up of s[]? Or does it follow, that there will be some impossible states, like the Finney States of RC4?

• Can anybody actually link me to any paper attempting any cryptanalysis of spritz, being as a DRBG, Stream Cipher or Cryptographically Secure Hash?

• Finally: I know the question should be more specific: But given it's similarity to RC4? How many problems from RC4 could we expect to pop-up in Spritz?

There's a few questions here, the reality is I'd be grateful to get an answer on any of these, as papers on this algorithm, don't seem to be an easy google search away... but my own limited tests (and thought experiments), make me think we're certainly onto a better version the PRGA for RC4 (apart from the fact, it's 40-50% of the speed).

All input appreciated!

(edit: I removed the question about what values of W can we use: the answer is 1..3..5..7, up to 255, presuming the range of S, is 256)

Answer 1

The reference definition of Spritz seems to be: Ronald L. Rivest and Jacob C. N. Schuldt, Spritz - a spongy RC4-like stream cipher and hash function, presented at Charles River Crypto Day (2014).

The code snippet of the question shows how the state of Spritz repeatedly used in DBRG output mode is updated and its next output byte $z$ produced; the state being permutation $S$ coded as $N=2^8$ distinct bytes, and byte variables $i$, $j$, $k$, $z$  (in the context $w$ is a constant odd byte depending on input of the DBRG).

It seems highly unlikely that this code snippet cycles over all the $256!\times2^{4\times 8}\lesssim2^{1716}$ states, or even the $256!\times\lesssim2^{1684}$ values of permutation $S$, for the expected maximum cycle length of an iterated random mapping of a set of size $s$ is $\approx0.7825\sqrt s$. This however is not a proof.

The above leaves entirely open the possibility of analogs to Finney states of RC4 (states that would give RC4 a very short period). It seems quite plausible that there exists such short cycles, and that (contrary to Finney states for RC4) they could be reached for some inputs to Spritz used in DBRG mode. However the design of Spritz strives to make it computationally impossible to reach a desired state, thus exhibiting a state giving a short or moderate cycle (which seems quite possible) would not by itself qualify as a break of Spritz.

I found two reports of cryptanalytic attempts, but neither claims to be even close to practical for the full Spritz, or even practical for a drastically reduced version (with $N=32$ instead of $N=256$ , that is $\approx2^{320}$ potential states instead of $\approx2^{1716}$ ).

• Bartosz Zoltak, Statistical weakness in Spritz against VMPC-R: in search for the RC4 replacement (IACR Cryptology ePrint Archive, 2014-12); this claims a distinguisher for a reduced Spritz with $N=16$  (that is, $\approx2^{60.25}$ states) using $\approx2^{41.4}$ bits of output. The attack is not claimed to break the full Spritz ( $N=256$ ) better than the distinguisher for $\approx2^{89}$ output bits acknowledged by the designers.
• Ralph Ankele, Stefan Koelbl and Christian Rechberger, State-recovery analysis of Spritz (IACR Cryptology ePrint Archive, 2015-08); the attack is acknowledged to be entirely impractical for the full Spritz (time $2^{1400}$, reducing to $2^{99}$ for $N=32$ ).

Spritz is designed with the intend to fix the known issues in RC4, and I know knew no reason why the techniques used towards that goal would fail.

Update: there is now a true attack on Spritz: Subhadeep Banik and Takanori Isobe, Cryptanalysis of the Full Spritz Stream Cipher, in proceedings of FSE 2016.