Editing RC4 (section)

===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.