Skip to main content
Update
Source Link
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

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 ArchiveIACR 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 ArchiveIACR 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 knowknow 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.

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 no reason why the techniques used towards that goal would fail.

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.

Give an element towards the third point
Source Link
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

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$;\nbsp;    (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^{16834}$$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)$$\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 no reason why the techniques used towards that goal would fail.

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$;\nbsp; (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^{16834}$ 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$ ).

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 no reason why the techniques used towards that goal would fail.

Source Link
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

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$;\nbsp; (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^{16834}$ 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$ ).