Editing RC4 (section)

==RC4 variants==
As mentioned above, the most important weakness of RC4 comes from the insufficient key schedule; the first bytes of output reveal information about the key.  This can be corrected by simply discarding some initial portion of the output stream.<ref>{{Citation |chapter-url=http://eprint.iacr.org/2002/067 |chapter=(Not So) Random Shuffles of RC4 |author=Ilya Mironov |date=1 June 2002 |title=Advances in Cryptology – CRYPTO 2002 |pages=304–319 |series=Lecture Notes in Computer Science |volume=2442 |publisher=Springer-Verlag |isbn=978-3-540-44050-5 |doi=10.1007/3-540-45708-9_20 |id=Cryptology ePrint Archive: Report 2002/067 |access-date=2011-11-04|url=http://www.iacr.org/archive/crypto2002/24420305/24420305.pdf |doi-access=free }}</ref> This is known as RC4-drop''N'', where ''N'' is typically a multiple of 256, such as 768 or 1024.

A number of attempts have been made to strengthen RC4, notably Spritz, RC4A, [[Variably Modified Permutation Composition|VMPC]], and RC4<sup>+</sup>.

===RC4A===
[[Souradyuti Paul]] and [[Bart Preneel]] have proposed an RC4 variant, which they call RC4A.<ref>{{Citation |chapter=A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher |author1=Souradyuti Paul |author-link1=Souradyuti Paul |author2=Bart Preneel |author-link2=Bart Preneel |chapter-url=http://homes.esat.kuleuven.be/~psourady/publication-info/PP04-bias_rc4.htm |year=2004 |title=Fast Software Encryption, FSE 2004 |series=Lecture Notes in Computer Science |volume=3017 |publisher=Springer-Verlag |isbn=978-3-540-22171-5 |pages=245–259 |doi=10.1007/978-3-540-25937-4_16 |access-date=2011-11-04|doi-access=free }}</ref>

RC4A uses two state arrays {{mono|S1}} and {{mono|S2}}, and two indexes {{mono|<var>j1</var>}} and {{mono|<var>j2</var>}}.  Each time {{mono|<var>i</var>}} is incremented, two bytes are generated:
# First, the basic RC4 algorithm is performed using {{mono|S1}} and {{mono|<var>j1</var>}}, but in the last step, {{mono|S1[<var>i</var>]+S1[<var>j1</var>]}} is looked up in {{mono|S2}}.
# Second, the operation is repeated (without incrementing {{mono|<var>i</var>}} again) on {{mono|S2}} and {{mono|<var>j2</var>}}, and {{mono|S1[S2[<var>i</var>]+S2[<var>j2</var>]<nowiki>]</nowiki>}} is output.

Thus, the algorithm is:

 <span style="color: green;">''All arithmetic is performed modulo 256''</span>
 i := 0
 j1 := 0
 j2 := 0
 '''while''' GeneratingOutput:
     i := i + 1
     j1 := j1 + S1[i]
     [[Swap (computer science)|swap values]] of S1[i] and S1[j1]
     '''output''' S2[S1[i] + S1[j1]<nowiki>]</nowiki>
     j2 := j2 + S2[i]
     swap values of S2[i] and S2[j2]
     '''output''' S1[S2[i] + S2[j2]<nowiki>]</nowiki>
 '''endwhile'''

Although the algorithm required the same number of operations per output byte, there is greater parallelism than RC4, providing a possible speed improvement.

Although stronger than RC4, this algorithm has also been attacked, with Alexander Maximov<ref>{{Citation |title=Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 Family of Stream Ciphers |author=Alexander Maximov |url=http://eprint.iacr.org/2007/070 |date=22 February 2007 |id=Cryptology ePrint Archive: Report 2007/070 |access-date=2011-11-04}}</ref> and a team from NEC<ref name="nec">{{Citation |title=The Most Efficient Distinguishing Attack on VMPC and RC4A |url=http://www.ecrypt.eu.org/stream/papersdir/037.pdf |year=2005 |author1=Yukiyasu Tsunoo |author2=Teruo Saito |author3=Hiroyasu Kubo |author4=Maki Shigeri |author5=Tomoyasu Suzaki |author6=Takeshi Kawabata}}</ref> developing ways to distinguish its output from a truly random sequence.

===VMPC===
{{Main article|Variably Modified Permutation Composition}}
Variably Modified Permutation Composition (VMPC) is another RC4 variant.<ref>{{Citation |chapter=VMPC One-Way Function and Stream Cipher |chapter-url=http://www.vmpcfunction.com/vmpc.pdf |author=Bartosz Zoltak |year=2004 |title=Fast Software Encryption, FSE 2004 |series=Lecture Notes in Computer Science |volume=3017 |publisher=Springer-Verlag |doi=10.1007/978-3-540-25937-4_14 |isbn=978-3-540-22171-5 |pages=210–225 |access-date=2011-11-04|url=https://www.iacr.org/archive/fse2004/30170209/30170209.pdf |citeseerx=10.1.1.469.8297 }}</ref> It uses similar key schedule as RC4, with
{{mono|1=j := S[(j + S[i] + key[i mod keylength]) mod 256]}} iterating 3 × 256 = 768 times rather than 256, and with an optional additional 768 iterations to incorporate an initial vector. The output generation function operates as follows:

 <span style="color: green;">''All arithmetic is performed modulo 256.''</span>
 i := 0
 '''while''' GeneratingOutput:
     j := S[j + S[i]]
     
     '''output''' S[S[S[j]] + 1]
     Swap S[i] and S[j]          <span style="color: green;">(''b := S[j]; S[j] := S[i]; S[i] := b)'')</span>
     
     i := i + 1
 '''endwhile'''

This was attacked in the same papers as RC4A, and can be distinguished within 2<sup>38</sup> output bytes.<ref name="maximov">{{Cite web |url=http://www.cryptolounge.org/wiki/RC4A |title=CryptoLounge: RC4A |access-date=4 November 2011 |archive-url=https://web.archive.org/web/20111001012601/http://www.cryptolounge.org/wiki/RC4A |archive-date=1 October 2011 |url-status=dead |df=dmy-all }}</ref><ref name="nec"/>

===RC4<sup>+</sup>===
RC4<sup>+</sup> is a modified version of RC4 with a more complex three-phase key schedule (taking about three times as long as RC4, or the same as RC4-drop512), and a more complex output function which performs four additional lookups in the S array for each byte output, taking approximately 1.7 times as long as basic RC4.<ref name ="rc4+">{{Citation |chapter=Analysis of RC4 and Proposal of Additional Layers for Better Security Margin |chapter-url=http://eprint.iacr.org/2008/396 |author1=Subhamoy Maitra |author2=Goutam Paul |title=Progress in Cryptology - INDOCRYPT 2008 |date=19 September 2008 |pages=27–39 |series=Lecture Notes in Computer Science |volume=5365 |publisher=Springer-Verlag |isbn=978-3-540-89753-8 |doi=10.1007/978-3-540-89754-5_3 |id=Cryptology ePrint Archive: Report 2008/396 |access-date=2011-11-04|url=http://eprint.iacr.org/2008/396.pdf |citeseerx=10.1.1.215.7178 }}</ref>

 <span style="color: green;">''All arithmetic modulo 256.  ''<<'' and ''>>'' are left and right shift, ''⊕'' is exclusive OR''</span>
 '''while''' GeneratingOutput:
     i := i + 1
     a := S[i]
     j := j + a
     
     Swap S[i] and S[j]               <span style="color: green;">(''b := S[j]; S[j] := S[i]; S[i] := b;'')</span>
     
     c := S[i<<5 ⊕ j>>3] + S[j<<5 ⊕ i>>3]
     '''output''' (S[a+b] + S[c⊕0xAA]) ⊕ S[j+b]
 '''endwhile'''

This algorithm has not been analyzed significantly.

===Spritz===

In 2014, Ronald Rivest gave a talk and co-wrote a paper<ref name="Rivest2014">{{cite news |last1=Rivest |first1=Ron |last2=Schuldt |first2=Jacob |date=27 October 2014 |title=Spritz – a spongy RC4-like stream cipher and hash function |url=http://people.csail.mit.edu/rivest/pubs/RS14.pdf |access-date=26 October 2014}}</ref> on an updated redesign called Spritz. A hardware accelerator of Spritz was published in Secrypt, 2016<ref>{{cite web | title=Hardware Accelerator for Stream Cipher Spritz | url=https://blogs.ntu.edu.sg/debjyoti001/files/2016/07/paper-1rf0pxd.pdf | publisher=Secrypt 2016 | access-date=29 July 2016 |author1=Debjyoti Bhattacharjee  |author2=Anupam Chattopadhyay}}</ref> and shows that due to multiple nested calls required to produce output bytes, Spritz performs rather slowly compared to other hash functions such as SHA-3 and the best known hardware implementation of RC4.

Like other [[sponge function]]s, Spritz can be used to build a cryptographic hash function, a deterministic random bit generator ([[DRBG]]), an encryption algorithm that supports [[authenticated encryption]] with associated data (AEAD), etc.<ref name="Rivest2014"/>

In 2016, Banik and Isobe proposed an attack that can distinguish Spritz from random noise.<ref>{{Cite book|last1=Banik|first1=Subhadeep|last2=Isobe|first2=Takanori|title=Fast Software Encryption |chapter=Cryptanalysis of the Full Spritz Stream Cipher |date=2016-03-20|publisher=Springer Berlin Heidelberg|isbn=9783662529928|editor-last=Peyrin|editor-first=Thomas|series=Lecture Notes in Computer Science|volume=9783 |pages=63–77|language=en|doi=10.1007/978-3-662-52993-5_4|s2cid=16296315}}</ref> In 2017, Banik, Isobe, and Morii proprosed a simple fix that removes the distinguisher in the first two keystream bytes, requiring only one additional memory access without diminishing software performance substantially.<ref>{{Cite journal|last1=Banik|first1=Subhadeep|last2=Isobe|first2=Takanori|last3=Morii|first3=Masakatu|date=2017-06-01|title=Analysis and Improvements of the Full Spritz Stream Cipher|url=https://www.jstage.jst.go.jp/article/transfun/E100.A/6/E100.A_1296/_article|journal=IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences|volume=E100.A|issue=6|pages=1296–1305|doi=10.1587/transfun.E100.A.1296|bibcode=2017IEITF.100.1296B |hdl=10356/81487|hdl-access=free}}</ref>