Cryptanalysis of the Full Spritz Stream Cipher

Abstract

Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on a short-term bias in the first two bytes of a keystream and a long-term bias in the first two bytes of every cycle of N keystream bytes, where N is the size of the internal permutation. 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.

1 Introduction

RC4, designed by Rivest in 1987, is still one of most widely used stream ciphers in the world. It is adopted in many software applications and standard protocols such as SSL/TLS, WEP, Microsoft Lotus and Oracle secure SQL. After the disclosure of its algorithm in 1994, RC4 has attracted intensive cryptanalytic efforts over past 20 years. Finally, in 2013, practical plaintext recovery attacks on RC4 in SSL/TLS were proposed by AlFardan et al. [1] and Isobe et al. [9]. In the response to these results, usage of RC4 has drastically decreased, especially in TLS, and major companies such as Google, Microsoft, and Mozilla announced that they will officially remove the RC4 from web browsers by early 2016.

At the same time, there has been extensive research in recent years to come up with RC4-like stream ciphers that while marginally slower in software, would wipe out the known shortcomings of RC4. Many such ciphers like RC4A [17], NGG [14], GGHN [8], Quad-RC4 [16], RC4+ [10] and VMPC [24] have been proposed to fulfil this objective. However, all the aforementioned ciphers have had distinguishing attacks reported against them [3–5, 12, 18, 20, 21]. Spritz [19] is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. The authors intended Spritz to be a replacement for RC4, and hence the design for Spritz was chosen meticulously, with special attention given to the fact that known weaknesses of RC4 [11, 13] do not carry over. The authors automatically examined many thousands of candidates to obtain cryptographically secure update functions and an estimated 5 “core-months” of CPU time were used in the statistical experiments performed by them. Their experiments suggested that $2^{81}$ samples were required to distinguish the output of Spritz from random.

1.1 Description of Spritz

Spritz consists of a permutation S over the set $\{0,1,2,\ldots ,N-1\}$ (default value of N is 256) and six pointers i, j, k, w, a, z, where i, j, k are index pointers, w gives the step distance for i, a is a nibble counter, and z stores the output byte. The design specifies a number of modules that are executed for producing a keystream as defined in Fig. 1. The authors specify a number of modes of operation using the Spritz structure like a stream cipher, hash function, MAC etc. In the stream cipher mode of operation the keystream is produced in the following manner. First the permutation is initialized using the INITIALIZESTATE(N) routine. The secret key K is then absorbed into the state using the ABSORB(K) module. Additionally, if an IV is to be used, then the ABSORBSTOP() module is invoked and the IV is absorbed by calling the ABSORB(IV) function. Thereafter, the SQUEEZE module is invoked to produce keystream bytes.

Fig. 1.

Modules for Spritz. When N is a power of 2, the last two lines of WHIP are equivalent to $w = w + 2$.

1.2 Previous Work

The only published work on cryptanalysis of Spritz is presented in [2]. The authors tackle the problem of state recovery using three different approaches. The best algorithm they propose theoretically recovers the internal permutation used in Spritz in $2^{1400}$ steps. Additionally, in [23], the author proposed a distinguisher for a scaled down version of Spritz ($N =8$). It was observed that the event $Z_i=Z_{i+2}$ was biased. However, the bias was not theoretically proven and no analogous result for the full Spritz ($N = 256$) was proposed.

1.3 Our Contribution and Organization

In this paper, we first show a short-term bias which is present in the first two bytes of a keystream and a long-term bias which appears in the first two bytes of every cycle of N keystream bytes. We theoretically prove that these biases exist in a keystream of Spritz regardless of the value of N. Based on these biases, we propose distinguishing attacks on the full Spritz ($N = 256$). 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 applicable to a plaintext recovery attack in a broadcast setting and multi-session setting in SSL/TLS.

Thereafter we show that under certain conditions, Spritz enters a weak class of states, during which, the odd and even elements of the permutation are never swapped with each other. In this case, the sequence constructed with the last bit of every keystream byte becomes periodic with period equal to 4. We show that in such an event, a state recovery attack on Spritz is more efficient and improves upon the $2^{1400}$ step algorithm proposed in [2]. Table 1 shows the summary of our results.

In Sect. 2, we will present the distinguisher on Spritz and study a few of its implications. In Sect. 3, we will present our state recovery attack on Spritz. Section 4 concludes the paper.

Table 1. Summary of results on Spritz

2 Distinguishing Attacks on Spritz

Before we proceed to outline the details of the distinguisher, let us present a few observations on how the various index pointers are used when Spritz is operated in the stream cipher mode. Note that when Spritz is used in the stream cipher mode: the sequence of execution of modules is

A. ABSORB(K)

B. ABSORBSTOP(), ABSORB(IV) (optional, only if IV is used)

C. SQUEEZE().

• 1. In the ABSORB(K) (and also ABSORB(IV)) phase, the internal permutation is swapped according to the nibble values of the key (IV). During this phase the index a is used only to keep track of the number of nibbles currently absorbed in the permutation. After the ABSORB phase, the index a plays no further role in the SQUEEZE phase when the cipher starts producing keystream bytes.

• 2. The index w, which is used to increment the index i, is constant during the SQUEEZE phase. The value of this index does not depend on the secret key, and hence is not secret. Its value can be deduced from the length of the secret key and IV. If the length of key is limited to bytes, and no IV is used, then the SHUFFLE procedure is executed only once. In that case, the value of w during the SQUEEZE phase is 7.

• 3. If the length of the Key is more than bytes the value of w can be deduced by examining the number of times the SHUFFLE module has been called during the ABSORB phases. For example, if $N=256$, and a Key of size 80 bytes, the SHUFFLE procedure gets called twice, at the end of the 64th byte and at the beginning of SQUEEZE. Each SHUFFLE call increases the value of w by 6 and so the value of w during the keystream generation is $1+6+6=13$.

• 4. The value of the index i at the beginning of the SQUEEZE phase is always 0, whatever be the the size of the Key and IV used in the ABSORB phases. This is because whenever bytes get absorbed, the value of the pointers i, j, k are altered by call to the SHUFFLE module. Each SHUFFLE module calls the WHIP(2N) module thrice. Each WHIP module in turn updates i using the rule $i=i+w$ a total of 2N times. Whatever be the actual value of w, at the end of the any call to the WHIP module, the updated value of $i=0+2wN \equiv 0 \bmod N$. And so the value of i remains 0 going in and out of the WHIP executions and hence also the SHUFFLE module.

• 5. The only indices that change during the SQUEEZE phase is i, j, k, z.

• 6. The sequence of updates during the SQUEEZE phase is therefore given as:

  • (a) $i=i+w$

  • (b) $j=k+S[j+S[i]]$

  • (c) $k=k+i+S[j]$

  • (d) SWAP (S[i], S[j])

  • (e) return $z= S[j+S[i+S[z+k]]]$

2.1 Bias in First Two Output Bytes of a Keystream

We first prove that the first two output bytes produced by the Spritz stream cipher are biased towards the tuple $(-w,-w)$. For example, if $N=256$, and if a 64 byte key is used, then $w=7$, and then the first 2 bytes are biased towards the value (249, 249).

Theorem 1

The first two output bytes $Z_1$ and $Z_2$ produced by the Spritz stream cipher are biased towards $(-w,-w)$. The probability of this event is given by $\mathsf{Pr}[Z_1=Z_2= -w] = \frac{1}{N^2} + \frac{3}{N^4}$.

Proof

We outline three mutually exclusive events I, II and III, each of which occurs with probability $\frac{1}{N^4}$, that guarantees that the first two output bytes produced by the cipher are both equal to $-w$. Each of the three events are denoted by the states of the permutation and the values of the index pointers before the beginning of the SQUEEZE phase.

• I. $S[w]=-w,~ S[2w]=0, k=0, S[j-w] = 2w$

• II. $k=2w ,~ S[j+S[w]]=-2w,~ S[2w]=w, S[0]=-w$

• III. $k+S[j-w]=2w, ~ k+S[2w]=0,~ S[w-k]=0,~S[w]=-w$

For example, when I occurs in the first round we have the following changes: $1.~ i\leftarrow i+w=w$

$2.~j\leftarrow 0 + S[j +S[w]] = S[j-w] = 2w$

$3.~k\leftarrow k+ i +S[j]=0+w+S[2w]=0+w+0=w$

$4.~S[w]\leftarrow 0,~S[2w]\leftarrow -w$ after SWAP

$5.~z\leftarrow S[j+S[i+S[z+k]]] = S[ 2w +S[w+S[w]]] = S[2w+S[w]]=S[2w]=-w$

Similarly in the second round we have the following changes:

$1.~ i\leftarrow i+w=2w$,

$2.~j\leftarrow w + S[2w +S[2w]] = w+S[w] = w$

$3.~k\leftarrow k+ i +S[j]=w+2w+S[w]=3w+0=3w$

$4.~S[w]\leftarrow -w,~S[2w]\leftarrow 0$ after SWAP

$5.~z\leftarrow S[ w +S[2w+S[3w-w]]] = S[w+S[2w+S[2w]]]=S[w]=-w$

We get similar results when we analyze II and III. Let us now denote by E the union of the events I, II and III. We have $\mathsf{Pr}[\mathsf{E}]=\frac{3}{N^4}$, and $\mathsf{Pr}[Z_1=Z_2=-w|\mathsf{E}]=1$. We assume that when E does not occur $\mathsf{Pr}[Z_1=Z_2=-w|\mathsf{E}^c]=\frac{1}{N^2}$, and is more or less uniformly random. We were able to verify the assumption by running computer simulations. Therefore by Bayes theorem, we have:

$$\begin{aligned} \mathsf{Pr}[Z_1=Z_2=-w]=&~ \mathsf{Pr}[Z_1=Z_2=-w|\mathsf{E}]\cdot \mathsf{Pr}[\mathsf{E}] + \mathsf{Pr}[Z_1=Z_2=-w|\mathsf{E}^c]\cdot \mathsf{Pr}[\mathsf{E}^c] \\ =&~1\cdot \frac{3}{N^4} + \frac{1}{N^2} \cdot \left[ 1-\frac{3}{N^4}\right] \approx \frac{1}{N^2} + \frac{3}{N^4}\\ \end{aligned}$$

   $\square$

Experimental Results: By performing extensive computer simulations with (a) one billion random keys, and (b) a fixed key with one billion random IVs, the probability $\mathsf{Pr}[Z_1=Z_2=-w]$ was found to be around $\frac{1}{N^2}+\frac{2.9}{N^4}$ for $N=16$ and $N=32$. In Figs. 2 and 3, we plot $\left[ \mathsf{Pr}[(Z_1,Z_2)=x]-\frac{1}{N^2}\right] \cdot N^4$ for all values of x when $N=16$ and 32 respectively with $w=7$. The x-axis is marked as $NZ_1+Z_2$. We can see a sharp peak at the x-axis mark corresponding to $(-7,-7)$ (i.e. $9*16+9=153$ for $N=16$ and $25*32+25=825$ for $N=32$). The plot is not uniform and there seems to be some bias for other values of x too, but the most significant bias exists at the point corresponding to $(-w,-w)$.

Fig. 2.

$\left[ \mathsf{Pr}[(Z_1,Z_2)=x]-\frac{1}{N^2}\right] \cdot N^4$ (for $N=16$)

Fig. 3.

$\left[ \mathsf{Pr}[(Z_1,Z_2)=x]-\frac{1}{N^2}\right] \cdot N^4$ (for $N=32$)

2.2 Distinguishing Attack with Multiple Key-IV Pairs Based on a Short-Term Bias

We now state the following theorem from [11], which outlines the number of output samples required to distinguish two distributions X and Y.

Theorem 2

(Mantin-Shamir [11]) Let X, Y be distributions, and suppose that the event e happens in X with probability p and in Y with probability $p(1 + q)$. Then for small p and q, $O\left( \frac{1}{pq^2}\right)$ samples suffice to distinguish X from Y with a constant probability of success.

Let X be the probability distribution of $Z_1$ and $Z_2$ in an ideal random stream, and let Y be the probability distribution of $Z_1$ and $Z_2$ in streams produced by Spritz for randomly chosen keys. Let the event e denote $Z_1=Z_2=-w$, which occurs with probability of $\frac{1}{N^2}$ in X and $\frac{1}{N^2}+\frac{3}{N^4}= \frac{1}{N^2}\cdot \left( 1 + \frac{3}{N^2}\right)$ in Y. By using the Theorem 2 with $p = \frac{1}{N^2}$ and $q= \frac{3}{N^2}$, we can conclude that we need about $\frac{1}{pq^2}= \frac{N^6}{9} \approx 2^{44.8}$ output samples to reliably distinguish the two distributions.

Therefore, we can mount a distinguishing attack with multiple key-IV pairs, if output samples of $Z_1$ and $Z_2$ produced by $2^{44.8}$ distinct key-IV pairs are available. In the single key setting, it requires samples of first two bytes $Z_1$ and $Z_2$ generated by $2^{44.8}$ different IVs.

2.3 Distinguishing Attack with a Single Key-IV Pair Based on a Long-Term Bias

The distinguishing attack on Spritz described in Theorem 1 requires that i and z are both zero at the beginning of the SQUEEZE phase. In general, during the production of a single stream of keystream bytes from any key or key/IV pair i and z are not both zero at the beginning of each round. This is why although the result in Theorem 1, holds for distinguishing the first 2 output bytes produced by multiple key/IV pairs, the same result can not be translated for a single keystream byte sequence using the event $Z_t=Z_{t+1}=-w$.

However i becomes 0 after every N rounds, and so in order to distinguish a single sequence of keystream bytes, one could look at the event $Z_{mN+1}=Z_{mN+2}=-w$ (for all integers $m\ge 0$) i.e. the first two of every cycle of N keystream bytes. However we still need $Z_{mN}=0$ for the initial conditions of the distinguisher to be fulfilled and so we should really look at the event $\mathsf{Pr}[Z_{mN+1}=Z_{mN+2}=-w|Z_{mN}=0]$. For the reasons outlined in Theorem 1, we also have

$$\mathsf{Pr}[Z_{mN+1}=Z_{mN+2}=-w|Z_{mN}=0]=\frac{1}{N^2}+\frac{3}{N^4}$$

where the probability this time is calculated over several integral values of m. Note that we will need $T=\mathcal {O}(\frac{N^6}{9})\approx 2^{44.8}$ samples to reliably distinguish the stream. However for this we need $T\cdot N$ cycle of keystream bytes (as $Z_{mN}=0$ will on average occur once every N cycle) and hence $T\cdot N^2=\mathcal {O}(\frac{N^8}{9})\approx 2^{60.8}$ keystream bytes. The distinguishing attack was verified for 100 random keys for $N=16,32$.

2.4 Plaintext Recovery Attacks in the Broadcast Setting

These short- and long-term biases are also used for plaintext recovery attacks in the broadcast setting where the same plaintext is encrypted with different keys or/and IV in the same manner of previous attacks [1, 9, 11, 15]. Note that the broadcast setting is converted into the multi-session setting where the target plaintext block are repeatedly sent in the same position in the plaintexts in multiple SSL/TLS sessions. According to Theorem 2, given $\frac{1}{pq^2}$ ciphertexts, we can distinguish the distribution of correct candidates of plaintext bytes (the biased distribution) from the distribution of wrong candidates of plaintext bytes (a random distribution) with a constant probability. It can be considered as the lower bound of the required number of ciphertexts for recovering biased bytes of a plaintext in this setting as mentioned in [11]. Recent statistical methods to detect a correct plaintext e.g. likelihood calculations of techniques [1, 22] and Bayesian analysis [7] might help to reduce the required number of ciphertexts when mounting an actual attack.

3 State Recovery Attack on Spritz

We first look at a class of special states of the Spritz stream cipher that occurs just before the beginning of the SQUEEZE phase.

Definition 1

Define a Spritz state as the 3-tuple (S, j, k) just at the beginning of the SQUEEZE phase. A Spritz state is called a SPECIAL state if all the following conditions hold simultaneously.

• 1. $S[t] \equiv 0 \bmod 2, \text { if } t\equiv 1\bmod 2$,

• 2. $S[t] \equiv 1 \bmod 2, \text { if } t\equiv 0\bmod 2$,

• 3. $j\equiv 0 \bmod 2$ and $k\equiv 0 \bmod 2$

In other words a SPECIAL state occurs when all the even indexed positions of the S array hold odd values, all the odd indexed positions hold even values and additionally j and k are even. We will now show that if the state at the beginning of the SQUEEZE phase is a SPECIAL state, then the sequence $Z_t \bmod 2, ~t =0,1,2,3,\ldots$ is periodic with period equal to 4.

Lemma 1

If the state at the beginning of the SQUEEZE phase is a SPECIAL state then the following hold (assuming N is even):

• (a) The state after every four iterations is a SPECIAL state.

• (b) In every iteration, the updated values of i and j are equal modulo 2. Hence no SWAP between odd and even values occur. And so, even and odd indexed positions of the S array will continue to hold odd and even values respectively.

• (c) $Z_t\equiv Z_{t+4} \bmod 2$, for all values of t.

Proof

Note that i and z are 0 at the beginning of the SQUEEZE phase and so both are even to begin with. If N is even, the design of the WHIP module ensures that the value of w is odd, whatever be the length of key/IV. Thereafter, all the above claims can be verified by running four iterations of the UPDATE function. We summarize the modulo 2 values of the various indices over 4 iterations in Table 2. Note that the updated values of i, j in each round is either both odd or both even, which means that the odd and even values are never swapped during the SQUEEZE phase. At the end of round 4, i, j, k, z become even again and so the modulo values of the above indices will repeat every 4 cycles. And therefore, the sequence of the modulo 2 values of the keystream byte z becomes periodic with period 4: $0,1,1,0,~0,1,1,0,~0,1,1,0 \ldots$    $\square$

Table 2. The modulo 2 values of the various indices through 4 iterations. The ones marked with are used in the State recovery process in Algorithm 1

Probability of a SPECIAL state: Combinatorially, it is easy to see that the total number of SPECIAL states is $\left( \frac{N}{2}\right) ^2 \cdot \left[ \left( \frac{N}{2}\right) !\right] ^2$. Therefore, if carry out the key/IV Setup operation with different keys/ single key and different IVs, then the probability that the state at the beginning of the SQUEEZE state is SPECIAL is given by

$$\begin{aligned} \rho = \frac{\left( \frac{N}{2}\right) ^2 \cdot \left[ \left( \frac{N}{2}\right) !\right] ^2}{ N^2\cdot (N!)} \end{aligned}$$

For $N=256$, $\rho \approx 2^{-253.7}$. So if one employs an IV of length more than 254 bits, it is likely that a SPECIAL state will be encountered in $\rho ^{-1}$ attempts. Using this, a state recovery attack can be mounted in a Multiple IV mode as follows:

• 1. For a fixed key, and Multiple IVs collect keystream of around $10*N$ bytes and inspect the sequence $Z_t \bmod 2$.

• 2. If the sequence is $0,1,1,0,~0,1,1,0,~0,1,1,0 \ldots$ i.e. periodic with period 4, then the attacker can conclude with high probability that he has encountered a SPECIAL state and he proceeds according to Algorithm 1.

• 3. The above technique is likely to succeed once in $\rho ^{-1}$ attempts.

3.1 State Recovery of SPECIAL states

Once the attacker is sure that he has encountered a SPECIAL state, he has the task of recovering a much simpler state and he proceeds in the same manner as in [2, Algorithm 1]. However, there a few differences as given in Algorithm 1.

The algorithm can be summarized in the following words: In each round, the attacker guesses the value of some of the elements of the internal permutation to determine the value of all the five indices required in the state update operation, each time making sure that odd indices get even values and vice versa. He then inspects the keystream byte produced in the round and tries to determine if the intermediate guessed permutation is consistent with the keystream byte observed. The attacker computes the index $d = j+S[i+S[z+k]]$ with the guessed values of the permutation and then performs the Verification step: Depending on the comparison between S[d] and the current keystream byte $Z_r$ he makes the following transitions:

$$\begin{aligned} \begin{array}{l@{\quad }lll} \mathbf {If} &{} S[d]= \textsf {NULL}\,\, \textsf {and}\,\, Z_r \not \in S \,&{}\rightarrow &{} \text { Assign } S[d]=Z_r, \text {Go to next round } r+1\\ \mathbf {If} &{} S[d]= \textsf {NULL} \,\, \textsf {and}\,\, Z_r \in S \,&{}\rightarrow &{} \text {Contradiction!!} \,\,\,\,\,\text {Try another assignment} \\ \mathbf {If} &{} S[d]\ne \textsf {NULL} \,\, \textsf {and} \,\,Z_r \ne S[d]&{}\rightarrow &{} \text {Contradiction!!}\,\,\,\, \text {Try another assignment} \\ \mathbf {If} &{} S[d]\ne \textsf {NULL} \,\, \textsf {and} \,\, Z_r = S[d]&{}\rightarrow &{} \text {Go to next round } r+1 \\ \end{array} \end{aligned}$$

3.2 Complexity of the Algorithm

The complexity is given by the number of guesses or assignments made, until a solution is found. As in [2], we compute the complexity by splitting the algorithm in several cases $c_i(x)$ to which we assign probabilities according to the occurrence of each case. Note that we can view the above internal state recovery algorithm, as two modules each working to recover exactly one half of the elements of the permutation. This is true since, the odd and the even indices never swap among each other. Let us denote by $\mathcal {T}_1,\mathcal {T}_2$ as the average number of assignments that would made in recovering the odd/even indexed elements of the permutation, if they were operating independent of the other. Since for every assignment in $\mathcal {T}_1$ we would need $\mathcal {T}_2$ assignments to verify the correctness of the solution, the total complexity of our algorithm is $\mathcal {T}=\mathcal {T}_1\cdot \mathcal {T}_2$.

To estimate $\mathcal {T}_1$, we have to note the parity of the the odd indices assigned in every cycle. We already know that the parity of all the indices will repeat after every 4 rounds, so observing the first 4 cycles is sufficient. As per Algorithm 1, the five indices that are used in the assignment process are $i_{next},a,j_{next},b,c$, and the index used in the verification process is d. It is easy to see that these correspond to $i,j+S[i], j, z+k, i+S[z+k]$ and $j+S[i+S[z+k]]$ respectively. A quick look at Table 2, tells us four of the assignment indices and the only verification index are odd in the first round. Thereafter the second and third rounds have one and two assignment indices odd. The fourth round has one assignment and one verification index odd. This means that there are four assignments followed by a verification, which is followed by another cycle of four assignments and a verification. Therefore in total we have 10 stages of assignment/verification. Let $c_i[x]$ ($1 \le i \le 10$) denote the average complexity associated with each stage, assuming that x elements of the N / 2 odd-indexed positions are already filled, then we have

$$ c_i[x] = \left\{ \begin{array}{ll} \frac{x}{N/2} \cdot c_{i+1}[x] + (1-\frac{x}{N/2} ) \cdot (\frac{N}{2} -x) \cdot c_{i+1}[x+1] , &{} \text{ for } i\in [1,10] \setminus \{5,10\}\\ \\ ( \frac{x}{N/2})^2 \cdot c_{i+1}[x] + (1-\frac{x}{N/2} ) ^2 \cdot c_{i+1}[x+1] , &{} \text{ for } i=5,10 \\ &{} \,{} \texttt {/\!\!*}c_{11}\, \texttt { denotes }\, c_1\texttt {*/} .\\ \end{array} \right. $$

In the above equation, when $i\in [1,10] \setminus \{5,10\}$, it denotes an assignment phase, when $i=5,10$, it denotes a verification phase. During an assignment, if x elements are already present in the permutation, then with probability $\frac{x}{N/2}$, the index to be assigned would be already filled, and in this case the algorithm would move on to stage $i+1$ without assignment. Alternatively with probability $1-\frac{x}{N/2}$, the index is empty and there are exactly $\frac{N}{2} -x$ ways to assign it, after which it moves to stage $i+1$. During verification stage the analysis is as follows:

• a. With probability $\frac{x}{N/2}$, the verification index d is already filled.

• b. Therefore with probability $\frac{x}{N/2} \cdot (1-\frac{x}{N/2} )$, the index is already filled by a value other than $Z_r$. In this case the path is terminated.

• c. With probability $(\frac{x}{N/2})^2$ the index is filled with $Z_r$ and the algorithm moves to the next phase.

• d. With probability $(1-\frac{x}{N/2})$ the verification index d is empty.

• e. Therefore with probability $(1-\frac{x}{N/2})\cdot (\frac{x}{N/2} )$ it happens that $Z_r$ exists in some other index of the permutation. In this case too the path is terminated.

• f. With probability $(1-\frac{x}{N/2})^2$, $Z_r$ is not present in the permutation, and so after assigning $S[d]\leftarrow Z_r$ it moves to the next stage.

The complexity $\mathcal {T}_1$ can be estimated as $c_1[0]$, with the boundary conditions $c_i[\frac{N}{2}-1]=1$. The above recurrence can be solved by a dynamic programming approach to find an estimate for $c_1[0]$. A similar recurrence relation can be deduced for estimating $\mathcal {T}_2$ by keeping track of the even valued assignment/verification indices. We write the recurrence relation below for the benefit of the reader.

$$ c_i[x] = \left\{ \begin{array}{ll} \frac{x}{N/2} \cdot c_{i+1}[x] + (1-\frac{x}{N/2} ) \cdot (\frac{N}{2} -x) \cdot c_{i+1}[x+1] , &{} \text{ for } i\in [1,14] \setminus \{6,10\}\\ \\ ( \frac{x}{N/2})^2 \cdot c_{i+1}[x] + (1-\frac{x}{N/2} ) ^2 \cdot c_{i+1}[x+1] , &{} \text{ for } i=6,10 \\ &{} \,{} \texttt {/\!\!*}c_{15}\,\, \texttt { denotes }\,\, c_1\texttt {*/} .\\ \end{array} \right. $$

Fig. 4.

Experimental and theoretical estimates of $\log _2\mathcal {T}$ (Color figure online)

Experimental Results: We performed the state recovery for $N=14,16,18,20$ for 100 random permutations. The algorithm was always able to recover the permutation. In Fig. 4, we plot the base 2 logarithm of the theoretical estimate $\mathcal {T}$ with the base 2 logarithm of the experimentally obtained average number of steps, for different even values of N. We can see that the theoretical value always overestimates the experimentally obtained complexity. For $N=256$, the theoretical estimate for $\mathcal {T}\approx 2^{1233}$. And so the estimated complexity of state recovery is given as $\mathcal {T}\cdot \left( \frac{N}{2}\right) ^2\approx 2^{1247}$ (taking into account the additional complexity of guessing the values of j, k at the beginning of the SQUEEZE phase). So the total complexity consists of $\rho ^{-1}$ encryptions plus $\mathcal {T}\cdot \left( \frac{N}{2}\right) ^2$ assignments which again comes to approximately $2^{1247}$.

4 Conclusion

In this paper, we analyzed the security of the stream cipher Spritz. We first proposed distinguishing attacks based on the short-term and the long-term biases in the keystream of Spritz. The distinguisher can be used both for distinguishing keystreams produced by multiple key-IVs and for distinguishing a keystream produced by a single key-IV pair. In the second half of the paper we looked at the state recovery attack on Spritz (in the multiple IV setting), in the situation when the cipher has entered a special class of SPECIAL states. We calculated the probability of such an event happening, and went on to outline an algorithm to recover the internal permutation. Our estimates suggest that in this case we need approximately $2^{1247}$ assignments to recover the internal state which is an improvement on the $2^{1400}$ step algorithm proposed in [2].