Editing RC4 (section)

==Security==
Unlike a modern stream cipher (such as those in [[eSTREAM]]), RC4 does not take a separate [[cryptographic nonce|nonce]] alongside the key.  This means that if a single long-term key is to be used to securely encrypt multiple streams, the protocol must specify how to combine the nonce and the long-term key to generate the stream key for RC4.  One approach to addressing this is to generate a "fresh" RC4 key by [[cryptographic hash function|hashing]] a long-term key with a [[cryptographic nonce|nonce]]. However, many applications that use RC4 simply concatenate key and nonce; RC4's weak [[key schedule]] then gives rise to [[related-key attack]]s, like the [[Fluhrer, Mantin and Shamir attack]] (which is famous for breaking the [[Wired Equivalent Privacy|WEP]] standard).<ref>{{cite web |date=1 September 2001 |title=RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4 |publisher=RSA Laboratories |url=http://www.emc.com/emc-plus/rsa-labs/historical/rsa-security-response-weaknesses-algorithm-rc4.htm }}</ref>
<!-- Should this be merged into the "Fluhrer, Mantin and Shamir attack" section below? -->

Because RC4 is a [[stream cipher]], it is more [[malleability (cryptography)|malleable]] than common [[block cipher]]s. If not used together with a strong [[message authentication code]] (MAC), then encryption is vulnerable to a [[bit-flipping attack]]. The cipher is also vulnerable to a [[stream cipher attack]] if not implemented correctly.<ref>{{cite book |url=https://books.google.com/books?id=dQE6LGep6wEC |pages=92–93 |title=Hidden Keys to Software Break-Ins and Unauthorized Entry |first=Dmitry |last=Sklyarov |publisher=A-List Publishing |year=2004 |isbn=978-1931769303}}</ref>

It is noteworthy, however, that RC4, being a stream cipher, was for a period of time the only common cipher that was immune<ref>[http://serverfault.com/questions/315042/ "ssl - Safest ciphers to use with the BEAST? (TLS 1.0 exploit) I've read that RC4 is immune"]. ''serverfault.com''.</ref> to the 2011 [[BEAST attack]] on [[Transport Layer Security#TLS 1.0|TLS&nbsp;1.0]]. The attack exploits a known weakness in the way [[Block cipher modes of operation#Cipher-block chaining .28CBC.29|cipher-block chaining mode]] is used with all of the other ciphers supported by TLS&nbsp;1.0, which are all block ciphers.

In March 2013, there were new attack scenarios proposed by Isobe, Ohigashi, Watanabe and Morii,<ref>{{cite web |url=http://home.hiroshima-u.ac.jp/ohigashi/rc4/ |title=Security of RC4 Stream Cipher |last1=Isobe |first1=Takanori |last2=Ohigashi |first2=Toshihiro |date=10–13 Mar 2013 |publisher=Hiroshima University |access-date=2014-10-27 }}</ref> as well as AlFardan, Bernstein, Paterson, Poettering and Schuldt that use new statistical biases in RC4 key table<ref>{{cite book |author1=Pouyan Sepehrdad |author2=Serge Vaudenay |author3=Martin Vuagnoux |title=Selected Areas in Cryptography |chapter=Discovery and Exploitation of New Biases in RC4 |series=Lecture Notes in Computer Science | year=2011 | volume=6544 | pages=74–91 | doi=10.1007/978-3-642-19574-7_5|isbn = 978-3-642-19573-0}}</ref> to recover plaintext with large number of TLS encryptions.<ref>{{cite web | url=http://blog.cryptographyengineering.com/2013/03/attack-of-week-rc4-is-kind-of-broken-in.html | title=Attack of the week: RC4 is kind of broken in TLS | work=Cryptography Engineering | access-date=12 March 2013 | author=Green, Matthew | date=2013-03-12 }}</ref><ref>{{cite web | title=On the Security of RC4 in TLS | url=http://www.isg.rhul.ac.uk/tls/ | publisher=Royal Holloway University of London | access-date=13 March 2013 |author1=Nadhem AlFardan |author2=Dan Bernstein |author3=Kenny Paterson |author4=Bertram Poettering |author5=Jacob Schuldt }}</ref>

The use of RC4 in TLS is prohibited by RFC 7465 published in February 2015.

===Roos' biases and key reconstruction from permutation===
In 1995, Andrew Roos experimentally observed that the first byte of the keystream is correlated with the first three bytes of the key, and the first few bytes of the permutation after the KSA are correlated with some linear combination of the key bytes.<ref>Andrew Roos. A Class of Weak Keys in the RC4 Stream Cipher. Two posts in sci.crypt, message-id 43u1eh$1j3@hermes.is.co.za and 44ebge$llf@hermes.is.co.za, 1995.</ref> These biases remained unexplained until 2007, when Goutam Paul, Siddheshwar Rathi and Subhamoy Maitra<ref>Goutam Paul, Siddheshwar Rathi and Subhamoy Maitra. On Non-negligible Bias of the First Output Byte of RC4 towards the First Three Bytes of the Secret Key. Proceedings of the International Workshop on Coding and Cryptography (WCC) 2007, pages 285–294 and Designs, Codes and Cryptography Journal, pages 123–134, vol. 49, no. 1-3, December 2008.</ref> proved the keystream–key correlation and, in another work, Goutam Paul and Subhamoy Maitra<ref>Goutam Paul and Subhamoy Maitra. Permutation after RC4 Key Scheduling Reveals the Secret Key. SAC 2007, pages 360–377, vol. 4876, [[Lecture Notes in Computer Science]], Springer.</ref> proved the permutation–key correlations. The latter work also used the permutation–key correlations to design the first algorithm for complete key reconstruction from the final permutation after the KSA, without any assumption on the key or [[initialization vector]]. This algorithm has a constant probability of success in a time, which is the square root of the exhaustive key search complexity. Subsequently, many other works have been performed on key reconstruction from RC4 internal states.<ref>Eli Biham and Yaniv Carmeli. Efficient Reconstruction of RC4 Keys from Internal States. FSE 2008, pages 270–288, vol. 5086, Lecture Notes in Computer Science, Springer.</ref><ref>Mete Akgun, Pinar Kavak, Huseyin Demirci. New Results on the Key Scheduling Algorithm of RC4. INDOCRYPT 2008, pages 40–52, vol. 5365, Lecture Notes in Computer Science, Springer.</ref><ref>Riddhipratim Basu, Subhamoy Maitra, Goutam Paul and Tanmoy Talukdar. On Some Sequences of the Secret Pseudo-random Index j in RC4 Key Scheduling. Proceedings of the 18th International Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes (AAECC), 8–12 June 2009, Tarragona, Spain, pages 137–148, vol. 5527, Lecture Notes in Computer Science, Springer.</ref> Subhamoy Maitra and Goutam Paul<ref>Subhamoy Maitra and Goutam Paul. New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4. Proceedings of the 15th Fast Software Encryption (FSE) Workshop, 10–13 February 2008, Lausanne, Switzerland, pages 253–269, vol. 5086, Lecture Notes in Computer Science, Springer.</ref> also showed that the Roos-type biases still persist even when one considers nested permutation indices, like {{mono|S[S[i]]}} or {{mono|S[S[S[i]]]}}. These types of biases are used in some of the later key reconstruction methods for increasing the success probability.

===Biased outputs of the RC4===
The keystream generated by the RC4 is biased to varying degrees towards certain sequences, making it vulnerable to [[distinguishing attack]]s. The best such attack is due to Itsik Mantin and [[Adi Shamir]], who showed that the second output byte of the cipher was biased toward zero with probability 1/128 (instead of 1/256). This is due to the fact that if the third byte of the original state is zero, and the second byte is not equal to 2, then the second output byte is always zero. Such bias can be detected by observing only 256&nbsp;bytes.<ref name="mantin">{{cite conference |author1=Itsik Mantin |author2=[[Adi Shamir]] |date=2001 |title=A Practical Attack on Broadcast RC4 |conference=FSE 2001 |pages=152–164 |url=https://link.springer.com/content/pdf/10.1007%2F3-540-45473-X_13.pdf |doi=10.1007/3-540-45473-X_13}}</ref>

[[Souradyuti Paul]] and [[Bart Preneel]] of [[COSIC]] showed that the first and the second bytes of the RC4 were also biased. The number of required samples to detect this bias is 2<sup>25</sup>&nbsp;bytes.<ref>{{cite conference |author1=[[Souradyuti Paul]] |author2=[[Bart Preneel]] |title=Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator |conference=[[Indocrypt]] 2003 |pages=52–67 |url=http://www.cosic.esat.kuleuven.be/publications/article-86.pdf }}</ref>

[[Scott Fluhrer]] and David McGrew also showed attacks that distinguished the keystream of the RC4 from a random stream given a gigabyte of output.<ref>{{cite conference |author1=Scott R. Fluhrer |author2=David A. McGrew |title=Statistical Analysis of the Alleged RC4 Keystream Generator |conference=FSE 2000 |pages=19–30 |url=http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/FluhrerMcgrew.pdf |url-status=dead |archive-url=https://web.archive.org/web/20140502020708/http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/FluhrerMcgrew.pdf |archive-date=2 May 2014 |df=dmy-all }}</ref>

The complete characterization of a single step of RC4 PRGA was performed by Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra, and Goutam Paul.<ref>{{cite journal |first1=Riddhipratim |last1=Basu |first2=Shirshendu |last2=Ganguly |first3=Subhamoy |last3=Maitra |first4=Goutam |last4=Paul |title=A Complete Characterization of the Evolution of RC4 Pseudo Random Generation Algorithm |journal=Journal of Mathematical Cryptology |pages=257–289 |volume=2 |issue=3 |year=2008 |doi=10.1515/JMC.2008.012 |s2cid=9613837 |doi-access=free }}</ref> Considering all the permutations, they proved that the distribution of the output is not uniform given i and j, and as a consequence, information about j is always leaked into the output.

===Fluhrer, Mantin and Shamir attack===
{{Main article|Fluhrer, Mantin and Shamir attack}}

In 2001, a new and surprising discovery was made by [[Scott Fluhrer|Fluhrer]], [[Itsik Mantin|Mantin]] and [[Adi Shamir|Shamir]]: over all the possible RC4 keys, the statistics for the first few bytes of output keystream are strongly non-random, leaking information about the key. If the nonce and long-term key are simply concatenated to generate the RC4 key, this long-term key can be discovered by analysing a large number of messages encrypted with this key.<ref>{{cite journal |first1=Scott R. |last1=Fluhrer |first2=Itsik |last2=Mantin |first3=Adi |last3=Shamir |title=Weaknesses in the Key Scheduling Algorithm of RC4 |journal=[[Selected Areas in Cryptography]] |year=2001 |pages=1–24 |url=http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps |archive-url=https://web.archive.org/web/20040602051734/http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps |archive-date=2 June 2004}}</ref> This and related effects were then used to break the [[Wired Equivalent Privacy|WEP]] ("wired equivalent privacy") encryption used with [[802.11]] [[wireless network]]s. This caused a scramble for a standards-based replacement for WEP in the 802.11 market and led to the [[IEEE&nbsp;802.11i]] effort and [[Wi-Fi Protected Access|WPA]].<ref>{{cite web |url=http://findarticles.com/p/articles/mi_m0DIS/is_2003_Jan/ai_n27590035/ |archive-url=https://archive.today/20120709120158/http://findarticles.com/p/articles/mi_m0DIS/is_2003_Jan/ai_n27590035/ |url-status=dead |archive-date=2012-07-09 |title=Interim technology for wireless LAN security: WPA to replace WEP while industry develops new security standard}}</ref>

Protocols can defend against this attack by discarding the initial portion of the keystream. Such a modified algorithm is traditionally called "RC4-drop[{{mvar|n}}]", where {{mvar|n}} is the number of initial keystream bytes that are dropped. The SCAN default is {{mvar|n}} = 768&nbsp;bytes, but a conservative value would be {{mvar|n}} = 3072&nbsp;bytes.<ref>{{cite web |url=http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#RC4-drop |title=RC4-drop(nbytes) in the ''Standard Cryptographic Algorithm Naming'' database}}</ref>

The Fluhrer, Mantin and Shamir attack does not apply to RC4-based SSL, since SSL generates the encryption keys it uses for RC4 by hashing, meaning that different SSL sessions have unrelated keys.<ref>{{cite web |first=Ron |last=Rivest |url=https://www.rsa.com/rsalabs/node.asp?id=2009 |title=RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4}}</ref>

===Klein's attack===
In 2005, Andreas Klein presented an analysis of the RC4 stream cipher, showing more correlations between the RC4 keystream and the key.<ref>A. Klein, Attacks on the RC4 stream cipher, Designs, Codes and Cryptography (2008) 48:269–286.</ref> [[Erik Tews]], [[Ralf-Philipp Weinmann]], and [[Andrei Pychkine]] used this analysis to create aircrack-ptw, a tool that cracks 104-bit RC4 used in 128-bit WEP in under a minute.<ref>Erik Tews, Ralf-Philipp Weinmann, Andrei Pyshkin. [//eprint.iacr.org/2007/120 Breaking 104-bit WEP in under a minute].</ref> Whereas the Fluhrer, Mantin, and Shamir attack used around 10&nbsp;million messages, aircrack-ptw can break 104-bit keys in 40,000 frames with 50% probability, or in 85,000 frames with 95% probability.

===Combinatorial problem===
A combinatorial problem related to the number of inputs and outputs of the RC4 cipher was first posed by [[Itsik Mantin]] and [[Adi Shamir]] in 2001, whereby, of the total 256 elements in the typical state of RC4, if ''x'' number of elements (''x'' ≤ 256) are ''only'' known (all other elements can be assumed empty), then the maximum number of elements that can be produced deterministically is also {{mvar|x}} in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given by [[Souradyuti Paul]] and [[Bart Preneel]].<ref>[[Souradyuti Paul]] and [[Bart Preneel]], [http://www.cosic.esat.kuleuven.be/publications/article-40.pdf A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher]. [[Fast Software Encryption]] – FSE 2004, pp.&nbsp;245–259.</ref>

===Royal Holloway attack===
In 2013, a group of security researchers at the Information Security Group at Royal Holloway, University of London reported an attack that can become effective using only 2<sup>34</sup> encrypted messages.<ref>{{cite news |url=https://www.theregister.co.uk/2013/03/15/tls_broken/ |title=HTTPS cookie crypto CRUMBLES AGAIN in hands of stats boffins |author=John Leyden |website=The Register |date=15 March 2013}}</ref><ref>{{cite web |url=http://www.isg.rhul.ac.uk/tls/RC4biases.pdf |title=On the Security of RC4 in TLS and WPA |last=AlFardan |publisher=Information Security Group, Royal Holloway, University of London |date=8 July 2013 |display-authors=etal |access-date=6 September 2013 |archive-date=22 September 2013 |archive-url=https://web.archive.org/web/20130922170155/http://www.isg.rhul.ac.uk/tls/RC4biases.pdf |url-status=dead }}</ref><ref>{{cite web |title=On the Security of RC4 in TLS and WPA |url=http://www.isg.rhul.ac.uk/tls/ |publisher=Information Security Group, Royal Holloway, University of London |access-date=2013-09-06}}</ref> While yet not a practical attack for most purposes, this result is sufficiently close to one that it has led to speculation that it is plausible that some state cryptologic agencies may already have better attacks that render RC4 insecure.<ref name=Leyden20130906>{{cite web |url=https://www.theregister.co.uk/2013/09/06/nsa_cryptobreaking_bullrun_analysis/ |title=That earth-shattering NSA crypto-cracking: Have spooks smashed RC4? |author=John Leyden |date=6 September 2013 |website=The Register}}</ref> Given that, {{asof|2013|lc=yes}}, a large amount of [[Transport Layer Security|TLS]] traffic uses RC4 to avoid attacks on block ciphers that use [[cipher block chaining]], if these hypothetical better attacks exist, then this would make the TLS-with-RC4 combination insecure against such attackers in a large number of practical scenarios.<ref name=Leyden20130906/>

In March 2015, researcher to Royal Holloway announced improvements to their attack, providing a 2<sup>26</sup> attack against passwords encrypted with RC4, as used in TLS.<ref>{{Cite web |title=RC4 must die |url=http://www.isg.rhul.ac.uk/tls/RC4mustdie.html}}</ref>

===Bar mitzvah attack===
{{main article|Bar mitzvah attack}}
At the Black Hat Asia 2015 Conference, Itsik Mantin presented another attack against SSL using RC4 cipher.<ref>{{Cite web| url=https://www.blackhat.com/asia-15/briefings.html#bar-mitzva-attack-breaking-ssl-with-13-year-old-rc4-weakness| title=Briefings – March 26 & 27| access-date=November 19, 2016| date=2015}}</ref><ref>{{Cite web| title=Attacking SSL when using RC4| date=2015| url=https://www.imperva.com/docs/HII_Attacking_SSL_when_using_RC4.pdf| access-date=November 19, 2016}}</ref>

===NOMORE attack===
In 2015, security researchers from [[Katholieke Universiteit Leuven|KU Leuven]] presented new attacks against RC4 in both [[Transport Layer Security|TLS]] and [[Temporal Key Integrity Protocol|WPA-TKIP]].<ref name=rc4nomore>{{cite web |url=https://www.rc4nomore.com/ |title=RC4 NOMORE: Numerous Occurrence MOnitoring & Recovery Exploit |author1=Mathy Vanhoef |author2=Frank Piessens |date=9 August 2015}}</ref> Dubbed the Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE) attack, it is the first attack of its kind that was demonstrated in practice. Their attack against [[Transport Layer Security|TLS]] can decrypt a secure [[HTTP cookie]] within 75&nbsp;hours. The attack against WPA-TKIP can be completed within an hour and allows an attacker to decrypt and inject arbitrary packets.