Security analysis of Spritz?

Question

Recently, a new cipher called Spritz has been released by Ronald L. Rivest and Jacob Schuldt. It should be a "drop-in replacement" for RC4.

There are many differences to RC4, Spritz is "spongy" and also has a complete different way to handle the key setup. But still there are many similarities to RC4 in generating the key stream or the whole structure of the cipher it self.

There are many results against RC4, so Spritz should be an interesting topic for analysis.

I have looked at some attacks on RC4 and be curious if some of them can be applied to Spritz as well. Does anybody else has analysed Spritz so far? Or is it far too early for results against Spritz?

From the performance viewpoint Spritz is really slow (compared to other related ciphers e.g. Keccak or Salsa20, SHA-256). Why didn't they go for performance? Nobody will use it if its that slow.

Answer 1

I have looked at some attacks on RC4 and be curious if some of them can be applied to Spritz as well. Does anybody else has analysed Spritz so far? Or is it far too early for results against Spritz?

No third party analysis. Probably way too early. (Even the paper you linked is unpublished.) The answer may of course change any time.

From the performance viewpoint Spritz is really slow (compared to other related ciphers e.g. Keccak or Salsa20, SHA-256). Why didn't they go for performance? Nobody will use it if its that slow.

They say in the paper that they were using "a simple and unoptimized implementation of Spritz". With the possible exception of Keccak, the implementations of those other algorithms may have seen years of optimization work.

Looking at the actual numbers, Spritz generates keystream at ~95 MB/s compared to 150+ for AES and 290+ for Salsa20 and RC4. So it's slower, but not by orders of magnitude. That sort of gap could realistically be closed with optimization work, if the implementation truly is poor. It also isn't necessarily that big a deal in many applications. Further, hardware performance might look completely different, although I don't see anything to suggest that it must.

The same question could be posed of AES: why are we using AES CTR if stream ciphers like Salsa20 have twice the performance? AES of course has the advantage of being an older design that has seen its share of cryptanalysis, but versatility may also play a role. As a block cipher, AES can be used for a variety of things, from MACs to disk encryption, whereas a stream cipher is basically only for encryption and requires a MAC to prevent malleability.

Similarly, due to being a sponge function, Spritz, like Keccak, could be seen as a more versatile primitive, offering not only encryption, but also a hash function and a MAC. This would allow you to rely on fewer moving parts, hopefully avoiding bugs and security weaknesses, possibly gaining back some performance too. Having a simple algorithm also helps.

However, the hash function performance of Spritz is more than an order of magnitude slower, so I'm not sure you'd really want to choose it over Keccak...

Answer 2

Unfortunately, there’s bad news.

According to Wikipedia, it’s alledgedly been broken; this paper appears to have details, but I prefer being a programmer, not an academic.

The summary of it boils down to (quoted from the citation):

Our attacks are able to distinguish a keystream of the full Spritz from a random sequence with samples of first two bytes produced by $2^{44.8}$ multiple key-IV pairs or $2^{60.8}$ keystream bytes produced by a single key-IV pair. These biases are also useful in the event of plaintext recovery in a broadcast attack.

In the second part of the paper, we look at a state recovery attack on Spritz, in a special situation when the cipher enters a class of weak states. We determine the probability of encountering such a state, and demonstrate a state recovery algorithm that betters the $2^{1400}$ step algorithm of Ankele et al. at Latincrypt 2015.

Unfortunately, while there’s now a lot of implementations of Spritz, search-engine indexed information is still rare, so the practical implications of this are still vague.

Effect on my plans

My main interest in Spritz is as PRNG, not as cipher, so feel free to ignore this section.

I had plans to replace aRC4 in arc4random(9) and arc4random(3) with Spritz, but it looks as if I can shelve those plans now; the sponge nature of Spritz was very appealing if you wish to mix new entropy in quickly.

There’s still the possibility of having one (long(er)-running) aRC4 (where state reinitialisation, due to the requirement of throwing away a lot of output at first, is very expensive) state in parallel to a Spritz state (sponge, so this is where input goes) and XORing the output bytes to produce the final (hopefully) CSPRNG stream. This will reduce throughput compared to using only one of them, but increase ease of (and reduce cost of) mixing in new pseudo-random bytes from one source (using the kernel /dev/[u]random as source for aRC4 (which is a known and mastered technology by now, even if OpenBSD switched to DJB’s algorithms) as before, and “other inputs” (which can be something less/untrusted like network packets/statistics; here, the STOP symbol’s niceties come into play) as source for Spritz, the latter having been initialised from /dev/urandom at first) and, also not unimportantly, increase the size of the pool (by having two). It is known that XORing PRNG output together is safe when they are unrelated, which they are not likely to stay over the runtime of the OS, but if the inputs are only mildly related and the algorithms differ, I have hopes.